Resource constrained portfolio scheduling problem (RCPoSP): A hybrid approach

Abstract

The resource constrained portfolio scheduling problem (RCPoSP), in which orders are grouped in portfolios, is proposed in this study. In the RCPoSP the objective is to deliver all orders in the portfolio at the same time after processing. This problem finds many applications in industrial services, manufacturing companies and, where all items (products, services, items etc.) ordered by the customer have to be delivered at the same time in one lot. The goal is to reduce the delivery costs and/or that all elements of the delivery have the same priority, etc. The presented problem also concerns the scheduling of new orders in project portfolios and/or a new project portfolio etc. The minimizations of makespan and/or resource needs for the portfolio are also discussed. The authors present a reference model for the RCPoSP and an intelligent framework for modeling and solving the modeled problem based on the original hybrid approach. The opportunity to ask questions, receive answers as well as data representation in the form of facts constitute an invaluable intelligent support to users utilizing this framework. The goal is to provide an intelligent hybrid framework for stating and solving constraint satisfaction or optimization of RCPoSPs. The calculation examples illustrate the capabilities and computational efficiency of the proposed framework.

Keywords

Resource constrained scheduling constraint satisfaction problem constraint logic programming mathematical programming decision support group scheduling fact-based representation hybrid methods

1 Introduction

Considering fierce competition and fast-changing customer needs, making swift and, if possible, optimal business decisions is a requirement. This requirement is particularly important for SMEs (small and medium enterprises), in which even a single incorrect decision may result in unacceptable delays, lack of necessary resources or financial loss.

The optimal allocation of constrained resources to orders, timely execution of orders, profit maximization, etc. are challenges that every manager has to face. This is especially challenging when simultaneously dealing with dynamic business-related events (e.g. new orders, new products, price changes etc.) and technical and technological difficulties (breakdowns, bottlenecks etc.). The resolution of this problem has broad applications within scheduling and resource allocation and is widely covered and classified in the literature [1]. Many methods have been proposed for solving resource assignment and scheduling problems exactly as mathematical programming, dynamic programming, etc., and approximately as evolutionary algorithms, tabu search, ant colony and dedicated heuristics. Likewise commercial advanced planning and scheduling software applications have been developed, such as SAP APS, Asprova by PMC, D-Opt by Greycon, etc.

Several factors make the above solutions unfit for the needs of SMEs. Firstly, SMEs cannot afford those mostly large and expensive modules of systems like SAP APS. Secondly, these systems are not intuitive and require trained operators and well-prepared users. But most importantly, these systems are intended for solving classic scheduling problems in job-shop, flow-shop or project environments. Whereas the models of organization, production and services used in SMEs are frequently modified, short term opportunities dictate decisions, technologies are matched to the currently available resources and so on.

In the authors’ opinion, the best form of decision support in SME is building an interactive intelligent decision support system that allows managers to formulate simple questions and obtain a response in acceptable time [2]. Examples of questions that could be asked by managers using such a system include (but are not limited to): Can the order be completed before a given deadline? Is it possible to undertake new order the under given (time-constrained) resources availability while guaranteeing disturbance-free execution of the already executed orders? What is the minimum makespan? etc.

This paper addresses a practical problem of scheduling and resource allocation related to the work group. The problem is termed a resource-constrained portfolio scheduling problem (RCPoSP). In RCPoSP orders enter at specific moments of time in groups (portfolio) and require simultaneous completion for the entire group of orders. For RCPoSP, no process flow structure (such as: job-shop, flow-shop, project, etc.) is predetermined.

The primary contribution of the presented study is the original reference model for the RCPoSP, its transformation and the intelligent framework for the implementation of models of this class, which allows users to ask questions. The proposed RCPoSP reference model varies substantially from other resource-constrained project scheduling problem (RCPSP) models known from the literature (Section 2) in that it enables order grouping, handling orders not only one at a time, combining resources into resource sets, simultaneous completion of all orders in the group, and elimination of intervals between operations within one order. The proposed framework relies on the proprietary hybridization of two environments, mathematical programming (MP) and constraint logic programming (CLP), and uses the fact-based representation of the problem.

Presented solution allows various methods of execution (scenarios), which may vary in both the resources and technology used (routing problem). Additionally, it allows one to take into account the dynamics of appearing orders, resources, portfolios etc. There are constraints on different types of resources.

2 Literature review

A vast part of the literature devoted to scheduling and resource allocation problems addresses the (single-project) RCPSP [3]. Quite a few extensions on the classical RCPSP have been examined to make the problem formulation more practical and useful. A number of studies on resource-constrained multi-project scheduling problems (RCMPSP) [4] have been reported. In general two approaches are used when dealing with multi-project environments: (a) a single-project approach using dummy activities and precedence graphs to combine the projects into a single large project, thereby reducing the RCMPSP to a RCPSP with a single critical path, or (b) a multi-project approach, maintaining the RCMPSP and a separate critical path per project. Activities can be executed in one of many possible modes in both RCPSP and in RCMPSP, with each mode having different resource requirements resources. No alternative scenarios exist for the execution of individual projects [3, 4].

Frequently, both RCPSPs and RCMPSPs are static issues with different objective functions (minimize makespan, minimize total project delay, lateness, or tardiness, minimize average project delay, minimize total lateness or lateness penalty etc.). Due dates for the completion of individual projects in the RCMPSP are specified for each individual project [4]. An exhaustive literature search for RCMPSPs did not reveal any requirement for simultaneous completion date (deadline) for the entire group of projects.

This condition was however, included in [5], but concerned the flexible flow scheduling problem (FFSP) instead. Unfortunately, FFSP affects only one process flow structure: the flow-shop [6]. This limits its use in many practical situations. In FFSPs and their models alternative execution of a routing problem is impossible and the only possibility is to use parallel machines.

The proposed FFSP models have different objective functions: minimization of makespan [7], minimization of the average flow time, minimization of a dual-criteria objective function [5] etc. These models are also static models related to specific predefined groups of orders/jobs.

3 Problem description

Nevertheless, the idea of RCPoSP was inspired by FFSP and in particular by using the process of preparing and serving a meal in a restaurant [5] as an analogy for the problem nature. Guests enter the restaurant in different groups at different moments. Each group chooses a table and all orders of the group members are taken simultaneously. The process of preparing meals contains a specific number of steps: preparing ingredients, cooking (roasting, baking, boiling, frying etc.), preparation of dishes and serving. Every meal passes through part of or all the steps. However, some meal items should be processed by a specific resource in one or more steps. The process time in each stage as well as the eligible resource to process the meal are fixed for a specific kind of meal. After the accomplishment of processes, all meal items ordered by a group are served simultaneously.

The proposed research problem (RCPoSP) finds many applications in industrial services and manufacturing companies, including but not limited to food, ceramic tile, textile production industries, distributions, supply chain, manufacturing of complex devices, assembling but also in the rescue from disasters, restaurants services, software engineering etc. and everywhere, where all items (products, services, items etc.) ordered by the customer should be delivered at the same time in one package that reduce the delivery costs and/or have the same priority.

Given system (within production, service, etc.) which can be separated into two areas; the so-called Back-Office (production plant, manufacturing department, set of CNC machine tools, service infrastructure/facilities, etc.) involved with manufacturing and developing processes, and the Front-Office (order placement points, assembly stations, packing stations, forwarding points, shipping points etc.) to support customer order fulfillment and delivery (Fig. 1). This system is defined by a set K = {k₁, . . . k_i, . . . k_LK} of resource types, where k_i is the i–th type and LK is the number of resource types in the system. These resources are limited and d_ki is the available quantity of resource k_i. The system produces products P = {p₁, . . . p_i, . . . p_LP} (a product means a real product or service), where p_i is the i–th product type and LP is the number of the product types. The performance of the system is considered in the given time horizon G = {g₁, . . . , g_i, . . . g_LG} where g_i is the i-th period of time and LG is the number of the periods. The system contains order placement points A = {a₁, . . . , a_i, . . . a_LA}, where a_i is the i-th point and LA is the number of order placement points. At the defined time instants v_i (where v_i is the i-th time period from set V = {v₁, . . . , v_i, . . . v_LV} and LV is the number of planning periods, (e.g. v₃ = 23 means that the third order set arrived at thetwenty-third execution period g = 23) order portfolios $E^{v_{i}} = {E_{a_{1}}^{v_{i}}, E_{a_{2}}^{v_{i}}, . . ., E_{a_{j}}^{v_{i}}, . . ., E_{a_{LA}}^{v_{i}}},$ are introduced into the system through the individual points a_i, where $E_{a_{j}}^{v_{i}} = {{zgp}_{p_{1}}^{v_{i}, a_{j}}, {zgp}_{p_{2}}^{v_{i}, a_{j}}, . . ., {zgp}_{p_{l}}^{v_{i}, a_{j}}, . .,$ ${zgp}_{p_{LP}}^{v_{i}, a_{j}}}$ and ${zgp}_{p_{l}}^{v_{i}, a_{j}}$ is how many products p_l have been ordered in the period v_i by point a_i (Fig. 1). A set of execution scenarios $Z^{p_{j}} = {Z_{1,}^{p_{j}}, . . ., Z_{i,}^{p_{j}}, . ., Z_{{PAN}_{j},}^{p_{j}}},$ is defined for each product type p_i, where PAN_j–is the number of scenarios for product p_j. A defined set of operations $O^{z_{i, j}} = {o_{1,}^{z_{i, j}}, o_{2,}^{z_{i, j}}, . . ., o_{l,}^{z_{i, j}}, . . ., o_{{LO}_{z_{i, j}}}^{z_{i, j}}}$ is assigned to each scenario $Z_{i,}^{p_{j}}$ , where $o_{l}^{z_{i, j}}$ is the l-th operation in the scenario $Z_{i,}^{p_{j}}$ and LO_{z
_i,j} is the number of operations in this scenario. The lead time $t_{l}^{z_{i, j}}$ for each operation $o_{l}^{z i, j}$ in this version is known and fixed. For each scenario $Z_{i,}^{p_{j}}$ operation execution is specified by the digraph $T^{z_{i, j}} = {O^{z_{i, j}}, F^{z_{i, j}}}$ , vertices of which refer to operations from set O^{z
_i,j} and arcs represents relation $o_{l}^{z_{i, j}} ≺ o_{k}^{z_{i, j}}$ (≺ ⊆ O^{z
_i,j} × O^{z
_i,j}) which means: $o_{l}^{z i, j}$ is executed before $o_{k}^{z i, j}$ , which implies that $(o_{l}^{z_{i, j}}, o_{k}^{z_{i, j}}) \in F^{z_{i, j}}$ . Each operation $o_{l}^{z_{i, j}}$ is executed using the specified resource set $S_{o_{l}}^{z_{i, j}} = {k_{1}^{o_{l}^{z_{i, j}}}, . . ., k_{m}^{{ol}_{z_{i, j}}}, . . .,$ $k_{LK}^{o_{l}^{z_{i, j}}}}$ , where $k_{m}^{{ol}^{z_{i, j}}}$ is how much $k_{m}$ resource is necessary to execute operation $o_{l}^{z_{i, j}}$ .

Fig.1

Scheme for scheduling a portfolio of orders (E_i) for ordering periods (v_i).

The following main assumptions are presupposed:

the order can be completed before a given deadline;

all portfolios E^v
_i will be executed;

the order ${zgp}_{p_{l}}^{v_{i}, a_{j}}$ on product p_i could be executed according to any scenario Z^p
_j;

all order from the set $E_{a_{j}}^{v_{i}}$ have been completed in the same period g;

the resources that belong to $S_{o_{l}}^{z_{i, j}}$ and operations that belong to O^z
_i,j are non-preemptable, that is, all resources of $S_{o_{l}}^{z_{i, j}} =$ ${k_{1}^{o_{l}^{z_{i, j}}}, . . ., k_{m}^{{ol}^{z_{i, j}}}, . . ., k_{LK}^{o_{l}^{z_{i, j}}},}$ are reserved by operation o until its completion, and cannot be used by other operations;

there are no gaps (no idle-time) between the operations of the order;

resources from $S_{o_{l}}^{z_{i, j}}$ are released immediately after completion of actually executed operations.

Furthermore, one additional type of resource – universal resource is introduced (packers, quality control staff, paramedics) and rzg is the limit to this resource.

These assumptions take into account the cases when some orders ${zgp}_{p_{l}}^{v_{i}, a_{j}}$ for product p_i can be made according to several scenarios Z^p. Each of the scenarios can vary in both the number of resources k and the number of operations O^Z. For illustration, let us consider processing the portfolio $E_{1}^{1}$ consisting of two orders: ${zgp}_{1}^{1, 1}$ and ${zgp}_{6}^{1, 1}$ (Fig. 2).

Fig.2

Example of possible scenarios for portfolio $E_{1}^{1}$ (selected scenarios were marked in gray).

The presented system provides an option of simultaneous execution of one order according to several scenarios, provided that it is not a unitary/unary order.

Which scenario should one choose? Will the portfolio be executed before the deadline? What resources will be needed and when? Is it possible to execute a new portfolio in a given deadline etc.? - all managers want to know the answers to these questions. Which product can I choose with guaranteed delivery time? Which product has the shortest delivery time? etc. – these are the questions could be asked by users.

The questions relate to both back office and front office areas and may concern situations, which require forward scheduling (F) - customer order processing, failure, accident, etc. or backward scheduling (B) - reservations, planned repairs, processing planned orders, etc. Table 1 summarizes examples of possible questions that can be asked in the presented version of the framework (Section 5).

Table 1

Examples of possible questions for RCPoSP

Q	Description	Type
Q1	What is the minimum lead time (makespan) for the portfolios of orders arriving in period v at point a?	F
Q2	Can new order portfolios arriving in subsequent periods v be executed at the defined time T? (with no changes to orders being executed)	B
Q3	What is the minimum number of universal resources (quality controllers, packers) needed to execute portfolio orders within T?	B
Q4	How to execute portfolio of orders within the T time with the minimum usage of resource k?	B
Q5	Can new order portfolios from period v be executed with the existing resources within the set time T?	B
Q6	What/Which order portfolios from period v can be executed within the T time while processing other orders?	B
Q7	How many order portfolios can be executed concurrently with the assumed number of available resources?	F

4 A reference model for RCPoSP

The formal model for the RCPoSP is constructed by introducing appropriate decision variables and constraints. The decision variables define the number of orders executed according to a given scenario ZK_a,z, starting times of the operation of the given order B_a,z,o allocation of resources for the operation (Z_a,z,o,k,g, Zo_a,z,o,k,g), etc. Table A1 in Appendix A shows a full set of the decision variables together with the description and symbols used. Each constraint specifies the admissible values for a group of decision variables. Constraints (A1) and (A2) define scenarios $Z_{j,}^{p_{i}}$ of order execution within the portfolio E^{v
_i} and establish the value of respective decision variables. The precedence constraint (A3) controls the sequence of operations in respect of the ${zgp}_{p_{l}}^{v_{i}, a_{j}}$ order. Constraint (A4) indicates the starting times for the use of the resource k necessary to execute order ${zgp}_{p_{l}}^{v_{i}, a_{j}}$ . Constraint (A5) prevents the start of operation $o_{l}^{z_{i, j}}$ prior to the arrival of order ${zgp}_{p_{l}}^{v_{i}, a_{j}}$ . The completion of execution of the order portfolio E^{v
_i}is defined by constraint (A6). Constraint (A7) ensures that the quantity of the available resources k is not exceeded. The resource k is reserved for the time of the order execution by constraint (A8). The continuity of operation $o_{l}^{z_{i, j}}$ execution is ensured by constraint (A9). Constraint (A10) ensures that the orders from the same portfolio are completed in the same period. Constraint (A11) determines the time/instant of portfolio execution completion. Constraint (A12) guarantees that the limit for the available universal resources is not exceeded. The description and symbols of all the parameters and constrains are summarized in Table A1 and Table A2 in Appendix A.

5 A hybrid approach to modelingand solving RCPoSP

Constraints are a natural and declarative way of expressing our needs. Very often, they are also our intermediary in interaction with a computer. In practice, they can define a set of admissible decisions or lack thereof. They are our intelligent assistant to express our needs or preferences. Their solving environments can than decide how best satisfy them [8]. The most interesting solving environments include declarative programming, which additionally support solving CSPs (Constraint Satisfaction Problems). An instance of a CSP (X,C,D) involves a set of variables X = {X₁, X₂, . . . , X_n} a domain D_i for each variable and a set of constraints C = {C₁, C_&2, . . . , C_q} s.t. C_i ⊆ D₁xD₂x . . . xD_n which define feasible combinations of domain values. The solution is the assignment of domain values to all variables, which is consistent with all imposed constraints. CSPs on finite domains are usually solved using a form of search. The most used methods and algorithms are local search, different variants of backtracking and the most important one constraint propagation which narrows the domains of decision variables. A general search algorithm for solving a CSP is presented in [9]. In the CSP a set of constraints defines the potential space of feasible solutions. Its shape and size depend on the values of individual parameters and input quantities. Based on the CSP constraint logic programming (CLP) paradigm was developed [9, 10]. According to many researchers, the CLP has the power to tackle difficult practical combinatorial problems which stretch conventional methods beyond their breaking points.

In CLP we state the problem requirements; we do not need to specify how to meet these requirements. Constraints do not require us to envision how the information is to be used. CLP programs are built from valid Prolog-based logic data-structures. A program is a collection of predicates, and a predicate is a collection of clauses. The idea of a clause is to define that something is true. The simplest form of a clause is the fact. For example, the following two are facts: technology (product_id, machine_id, execution_time). vehicle (vehicle_id, capacity, type, cost).

The reference model data layer consists of a set of facts, the structure and interrelations of which are shown in Fig. 3 and Appendix B. The reference model parameters (Table A1) constitute the attributes of individual facts. Selected attributes, marked with #, enable establishing relations between the facts.

Fig.3

A set of facts and relations between them for the reference model.

The reference model is presented as a set of CSP_s that contain adequate sets of constraints, questions, etc. This manner of modeling is flexible and can be easily expanded and implemented in CLP. Together with the set of facts, it forms the basis for building intelligent tools to support decision makers.

Figure 4a shows a graphical visualization of the reference model concept as a CSP_R, composed of two subproblems CSP₁ and CSP₂. CSP₁ refers to the back-office (e.g. production, service, etc.) and to the processes of preparing the product. CSP₂ includes the front-office area (restaurant dining room, order placement and check-out points, etc) and refers to the processes of ordering and delivery. Adding new constraints and variables can further develop either of these subproblems. Both subproblems are connected through a suitable set of variables and constraints (Figs. 4a and 4b), contained in both CSP₁ and CSP₂ (CSP_1∩2).

Fig.4

a) Reference model for RCPoSP as a CSP_R. b) Sub-problems CSP for RCPoSP (Decision variables, Constraints-Appendix A).

The main weakness of the search algorithms for solving CSPs is process of distribute the variables (process in which decision variables are to be considered to be specified as well as the order in which the values are assigned to the variable on backtracking) [9, 10]. If there exist constraints that bind a larger number of decision variables (more than 2), then the distribution of variables makes the entire algorithm non-effective. Elimination of the variable distribution mechanism while leaving the mechanism of constraint propagation has become a key direction of the authors’ research. As a result, a hybrid approach is proposed to combine MP and CLP environments and enable transformation of the problem [11, 12]. The introduction of transformation as a key component of the hybrid approach and withdrawal from distribution of variables in the CLP, clearly distinguishes this approach from those known from literature [13, 14]. Hybrid approach can be used wherever: (a) a problem can be represented by constraints; (b) data can be written as set of facts, (c) there are exclusions and unacceptable allocations, for example resources, etc.

Problem transformation is central to the proposed hybrid approach. Its use significantly enhances the effectiveness of the integrated CLP and MP environments. The methodology of the transformation has been developed based on earlier studies of CLP and MP hybridization, within which transformations were performed for specific logistic cases [11 , 15]. Generally, the transformation in this approach is the element that allows eliminating infeasible points in the decision variables space prior to defining the values of the decision variables which results from fact-based representation.

Moreover, in the case of RCPoSP, the transformation is associated with the change in problem representation from the classical, operation-based representation to the resource-based one, where the operation index is needless and infeasible.

This type of transformation is possible for all scheduling and resource allocation problems that take resources into account and do not accept time gaps between operations. In the new representation of the problem, operation indices are removed from the decision variables, parameters etc. as unacceptable. Examples of transformations indices are shown in Fig. 5. After transformation, a new set of decision variables is obtained. The schema of index and decision variables transformation is shown in Fig. 5. Table A3 in Appendix A summarizes all decision variables before and after transformation.

Fig.5

Examples of decision variables and index transformation.

In general, the transformation of RCPoSP results in: (a) a reduction in the total number of decision variables attained through aggregation and elimination; (b)a change in the nature of the variables; (c) a reduction in the number and complexity of constraints;(d) a reduction of the solution search time; and (e) an extension of the scope of constraint propagation.

The generalized transformation algorithm was developed based on the elimination of infeasible combinations of decision variable indices. The algorithm generalizes the methods for the change of problem representation in respect of the specific cases studied in [11 , 15] and in this paper. The algorithm together with an analysis of its properties and computational complexity will be published in future work.

The novel idea for the application of the hybrid approach to RCPoSP in the form of hybrid intelligent framework, based on the reference model and the set of questions, is shown in Fig. 6.

Fig.6

Hybrid framework for decision support for RCPoSP.

In the first stage, dedicated decision model in the form of a CSP_R is built using the reference model, set of facts and the questions (Table 1). The resultant dedicated model is then initially solved using constraint propagation to obtain the narrowing of domains of the decision variables. In the next step, the model is transformed. After transformation, the model is solved using again the propagation of constraints. The obtained domain solution is the basis for the generation of the MILP^T (Transformed Mixed Integer Linear Programing) model in the MP environment. In the last stage, the linear model is solved using mathematical programming methods[16].

The high effectiveness of the hybrid approach results from the difference in treatment of constraints in the two environments, by applying twice the constraint propagation and from the possibility of problem transformation, which reduces the number of variables and constraints.

Framework implementation was performed according to the chart in Fig. 6. From a variety of tools for the implementation of the CLP the ECLⁱPS^e software [10] is selected. ECLⁱPS^e is an open-source software system for cost-effective development and deployment of constraint programming applications. Gurobi [17] is used for the implementation of MILP as it is a powerful tool for building and solving mathematical optimization models.

An original iterative algorithm [18] was used, which ensures that the decision and/or optimization models can be activated in subsequent periods g and in any period of resource reservation, indicating current availability of the resources.

The framework presented in this paper can be a basis for building interactive intelligent decision support systems for RCPoSP or other scheduling and resource allocation problems.

6 Computational experiments

In order to verify and evaluate the proposed approach and hybrid framework, many numerical experiments were performed for the illustrative example. The experiments were on one hand designed to assess the proposed solutions in terms of functionality and decision support range and the effectiveness of the proposed implementation with a focus on optimization issues on the other.

In the first phase, all the experiments relate to the system with ten points (tables, ordering points etc.) (i = 1 . .10), ten order types (j = 1 . .10), eight resource types (k = 1 . .8), thirty time periods (g = 1 . .30) and fifteen orders. Orders are placed in 6 portfolios $E_{1}^{v 1} E_{3}^{v 1} E_{5}^{v 2} E_{6}^{v 2} E_{7}^{v 3} E_{3}^{v 4}$ for v₁ = 1, v₂ = 3, v₃ = 6, v₄ = 8 periods. All numerical data used in the experiments are summarized in Appendix B. The computational experiments consisted of addressing questions: Q1 . . Q7, to the reference model (Section 3.). The reference model was implemented in the hybrid framework (Section 4) run iteratively with the interactive algorithm. The results are presented in a tabular form or, where especially interesting, represented on Gantt charts. Gantt charts illustrate the schedule of order portfolio execution and the resulting utilization of resources in time.

The answer to question Q1 (What is the minimum execution time (makespan) for portfolios of orders entering in periods v₁ = 1, v₂ = 3, v₃ = 6, v₄ = 8?) is Tpk = 11 (makespan = 10) for period v₁, Tpk = 6 (makespan = 3) for period v₂, Tpk = 10 (makespan = 4) for period v₃, and Tpk = 12 (makespan = 4) for period v₄. Figure 8a shows the implementation schedule of all portfolios (Appendix B) for this example while minimizing the makespan (Q1). The resource usage from the answer to Q1 is shown in Figs. 7a and 7b.

Fig.7

a) Gantt chart for the answer to question Q1 (portfolios E enter in v₁ = 1, v₂ = 3, v₃ = 6, v₄ = 8, zk-method of order execution in the portfolio)-optimal makespan. b) Gantt chart for the answer to question Q1 (resource usage).

The answer to question Q2 (Is it possible to execute new portfolios of orders that enter in the coming periods v within a specified period T?) for portfolios from ordering period v₁ = 1 is shown in Table 2 and Figs. 8 and 9a shows the Gantt chart for the answer to question Q4 (How to realize portfolios of orders $E_{1}^{v 1} E_{3}^{v 1} E_{5}^{v 2} E_{6}^{v 2} E_{7}^{v 3} E_{3}^{v 4}$ in time T < =20 with minimal use of the resource k_l?).

Table 2

Answer to question Q2

T(g)	Portfolios from v₁ = 1
14	Yes
12	Yes
10	No
8	No

Fig.8

Gantt chart for the answer to question Q2.

Fig.9

a) The top chart shows the answer to question Q1 while the chart below shows the answer to question Q4. b) The top chart shows that the use of the resource k_l when answering to question Q1 while the chart below shows the use of the resource k₁ when answering the question Q4.

The use of the resource k_l for Q4 is presented in Fig. 9b. Both charts were compared with analogous charts obtained from the answer to Q1. The answers to question Q5 (Is it possible to realize the new portfolio of orders from the period v with existing resources at specified period T?) are shown in Tables 4, 5 and Figs. 10a.–10c. The answers to questions Q6 and Q7 are variants of and / or subsets answers to questions Q2 and Q5. The results confirm the flexibility and functionality of the proposed approach, in which all types of questions can be formulated (general, wh-questions, optimization questions, etc.).

Table 3

Answer to question Q3

T (g)	rzgo
15	1
12	3

Table 4

The possibility of execution at time T portfolios of orders from the period of v₂ = 3, (unchanged execution of the portfolios from period v₁ = 1)

T(g)	Portfolios from v₂ = 3
12	Yes
10	Yes
8	Yes

Table 5

The possibility of execution at time T portfolios of orders from the period of v₃ = 6, (unchanged execution of the portfolios from period v₁ = 1 and v₂ = 3)

T(g)	Portfolios from v₃ = 6
12	Yes
10	Yes
8	No

Fig.10

a) Gantt chart for the answer to question Q5 (entering portfolios from v₂ = 3 without change portfolios from v₁. b) Gantt chart for the answer to question Q5 (entering portfolio from v₃ = 6). c) Gantt chart for the answer to queston Q5 (entering portfolio from v₄ = 8 without change portfolios from v₁ = 1, v₂ = 3 and v₃ = 6).

Due to the lack of benchmark data for the RCPoSP, the effectiveness of the hybrid approach was investigated using the question Q1 (What is the minimum lead time (makespan) for the portfolios of orders arriving in period v at point a?) and question Q3 (What is the minimum number of universal resources (waiters, packers) needed to execute portfolio orders within T? see results in Table 3) the most complex questions in numerical sense from Table 1. Q1 is a classical computation-intense question in resource allocation and scheduling problems and is classified as NP-hard [6].

The hybrid approach was subject to comparative analysis relative to its individual components (CLP and MP) in terms of decision variables, constraints and response time to Q1 and Q3.

The optimization models answering to Q1 and Q3 were generated for the same data instances and solved according to three scenarios:

S1 – reference model-based generation and solution in the MP environment.

S2 – reference model-based generation and solution in the CLP environment.

S3 – transformed reference model-based generation and solution through the hybrid framework.

The detailed results for multiple instances of data that differ in number of orders in the portfolios are presented in Table 6. The application of scenarios S3 allowed us to find the most effective solution in the shortest time: 30 to 100 times faster than in scenario S1. Scenario S2 did not find the optimal or admissible solution within an acceptable time. The decision variables and constraints were reduced in number by a factor of 12 and 10, respectively.

Table 6

The results of answers to the questions Q1and Q3 implemented by variants S1, S2, S3

Number of orders	S1
	V	C	Q₁		Q₃
			T	Fc	T	Fc
1	6926951	1235561	182	5	262	1
5	6926951	1235561	302	11	222	1
10	6926951	1235561	458	11	418	1
20	6926951	1235561	1200^*	16^*	1200^*	2^*
40	6926951	1235561	1200^*	Unknown	1200^*	Unknown
50	6926951	1235561	1200^*	Unknown	1200^*	Unknown
Number of orders	S2
	V	C	Q₁		Q₃
			T	Fc	T	Fc
1	692754	^***	226	5	191	1
5	692754	^***	382	11	254	1
10	692754	^***	459	11	338	1
20	692754	^***	1200^*	Unknown	1200^*	Unknown
40	692754	^***	1200^*	Unknown	1200^*	Unknown
50	692754	^***	1200^*	Unknown	1200^*	Unknown
Number of orders	S3
	V	C	Q₁		Q₃
			T	Fc	T	Fc
1	2288	161938	2	5	2	1
5	6297	160291	9	11	5	1
10	9357	158622	8	11	13	1
20	17017	154950	18	11	13	1
40	32474	148237	53	13	86	3
50	40653	144130	96	15	96	4

V-the number of decision variables, C- the number of constraints, T-time of finding solution (in seconds), *the calculation was stopped after 1200s, **feasible solution, ***CLP does not provide this information.

Thus the application of the proposed hybrid approach and implementation framework will result in: (a) a significant reduction in search time and (b) the possibility of solving larger problems within the acceptable period of time (more than three times larger in terms of number of orders).

In future experiments, the effectiveness of the hybrid approach and implementation platform will be tested in the context of JSSPs (Job-Shop Scheduling Problems), FFSSPs (Flexible Flow-Shop Scheduling Problems), RCPSP (Resource Constrained Project Scheduling Problems) and these will act as instances of the reference model for RCPoSP and other scheduling problems [19].

7 Remarks and conclusion

The reference model for the RCPoSP considered here could be the basis for the generation of multiple decision and optimization models for group work of any organizational scheme (job-shop, flow-shop, flexible flow-shop, project, multi-project etc.). The hybrid approach applied to the generation and solution of these models show considerably higher effectiveness than each of its components alone (Table 6).

It is particularly important that the proposed solutions are highly flexible in terms of modeling and finding the solution and allow formulating and asking questions to the system in a natural way, which is a big convenience for both managers and customers. In addition, the reference model and the hybrid approach can be applied to similar problems in resource allocation and task scheduling, such as JSSP, FFSSP, RCPSP, etc. The only changes that will be necessary are to include data instances and some of the reference model constraints. A quite innovative approach is to propose a generation of dedicated optimization / decision-making models based on the reference model, questions and specific data instances (facts). Such models are most suited to the specific real problems in terms of both structure and parameters.

Further work will focus on indicating the possibility of generating decision and optimization models for other task scheduling and resource assignment models using the reference model and solving them using the hybrid framework. Other objectives will include the expansion of the number of questions to be asked by managers and customers, the introduction of elements of fuzzy logic [20, 21], to the reference model and soft constraints [22] to the hybrid platform, and finally a benchmark study [23] for the JSSP, FFSSP and RCPSP. It is planned to expand the RCPoSP model by order quantity distribution[24].

Footnotes

Appendix A Reference model for RCPoSP

Table A3

The schema of transformation (comparison of decision variables before and after transformation)- gray marked items that have been transformed

Decision variables
Reference	Reference^T	Reference	Reference^T
Tkp _a	Tkp _a	Xo _a,z,o,k,g	Xo _a,z,k,g
Zk _a,z	Zk _a,z	Y _a,z,o,k,g	Y _a,z,k,g
Xzk _a,z	Xz _a,z	W _a,g	W _a,g
B _a,z,o	- - - -	S _a,z,o,k	S _a,z,k
X _a,z,o,k,g	X _a,z,k,g

Appendix B. Data for numerical examples

number_of_periods(30). number_of_periods_ orders(4). number_of_secent_type(4).

p(#a) – points: p(1). p(2). p(3). p(4). p(5). p(6). p(7). p(8). p(9). p(10).

pr(#p) – products: pr(1). pr(2). pr(3). pr(4). pr(5). pr(6). pr(7). pr(8). pr(9). pr(wy10).

r(#k, d _ k) – resources: r(’k01’,4). r(2,4). r(3,4). r(4,4). r(5,4). r(6,4). r(7,4). r(8,4).

O(#o) – operations; o(1). o(2). o(3). o(4). o(5). o(6). o(7). o(8). o(9). o(10). o(11). o(12).

t(#z) - types_of_orders: t(1). t(2). t(3). t(4). t(5). t(6). t(7). t(8). t(9). t(10). t(11). t(12). t(13). t(14). t(15). t(16). t(17). t(18). t(19). t(20). t(21). t(22). t(23). t(24). t(25).

ex(#p,#z) – execution: ex(1,1). ex(1,2). ex(1,3). ex(2,4). ex(2,5). ex(2,6). ex(3,7). ex(3,8). ex(3,9). ex(4,10). ex(4,11). ex(4,12). ex(5,13). ex(5,14). ex(5,15). ex(6,16). ex(6,17). ex(7,18). ex(7,19). ex(8,20). ex(8,21). ex(9,22). ex(9,23). ex(10,24). ex(10,25).

ro(#o,#k, r _ o, k) - resource_to_operation: ro(1,1,1). ro(2,2,1). ro(3,3,1). ro(4,4,1). ro(5,5,1). ro(6,6,1). ro(7,7,1). ro(8,8,1). ro(9,1,1). ro(9,2,1). ro(10,3,1). ro(10,4,1). ro(11,5,1). ro(11,6,1). ro(12,7,1). ro(12,8,1).

or(#z,#o, t _ z, o) - operations_on_route: or(1,1,1). or(1,2,1). or(1,3,1). or(1,4,1). or(1,5,1). or(2,9,2). or(2,11,1). or(2,12,1). or(3,1,2). or(3,10,1). or(3,12,1). or(4,1,1). or(4,6,1). or(4,7,1). or(4,8,1). or(5,2,1). or(5,6,1). or(5,7,1). or(5,8,1). or(6,3,1). or(6,6,1). or(6,7,1). or(6,8,1). or(13,1,2). or(13,2,2). or(13,3,2). or(13,4,2). or(13,5,2). or(14,1,2). or(14,2,2). or(14,3,2). or(14,4,2). or(14,5,2). or(15,1,2). or(15,2,2). or(15,3,2). or(15,4,2). or(15,5,2). or(16,1,1). or(16,2,1). or(16,3,1). or(16,4,1). or(16,5,1). or(17,7,1). or(17,8,1). or(17,9,1). or(7,4,2). or(7,7,2). or(7,8,1). or(8,4,2). or(8,7,2). or(8,9,1). or(9,4,2). or(9,8,1). or(9,9,2). or(10,1,1). or(10,2,1). or(10,3,1). or(10,4,1). or(10,5,1). or(10,6,1). or(11,9,2). or(11,10,2). or(11,11,1). or(12,1,1). or(12,2,1). or(12,3,1). or(12,4,1). or(12,11,1). or(17,10,1). or(17,11,1). or(18,3,2). or(18,4,1). or(18,5,1). or(19,7,1). or(19,8,1). or(19,9,1). or(20,1,2). or(20,2,1). or(20,6,1). or(21,7,1). or(21,8,1). or(21,9,1). or(22,3,1). or(22,4,1). or(22,6,1). or(23,7,1). or(23,8,1). or(23,11,1). or(24,1,1). or(24,2,1). or(25,9,1).

so(#z,#o,#0#) - sequence_operations: so(1,1,3). so(1,2,3). so(1,3,4). so(1,4,5). so(2,9,11). so(2,11,12). so(3,1,10). so(3,10,12). so(4,1,6). so(4,6,7). so(4,7,8). so(5,2,6). so(5,6,7). so(5,7,8). so(6,3,6). so(6,6,7). so(6,7,8). so(13,1,2). so(13,2,3). so(13,3,4). so(13,4,5). so(14,3,4). so(14,4,1). so(14,1,2). so(14,2,5). so(15,4,3). so(15,3,2). so(15,2,1). so(15,1,5). so(16,1,2). so(16,2,3). so(16,3,4). so(16,4,5). so(17,7,8). so(7,4,7). so(7,7,8). so(8,4,7). so(8,7,9). so(9,4,9). so(9,9,8). so(10,2,3). so(10,3,4). so(10,4,5). so(10,5,6). so(11,9,10). so(11,10,11). so(12,1,2). so(12,2,3). so(12,3,4). so(12,4,11). so(17,8,9). so(17,9,10). so(17,10,11). so(18,3,4). so(18,4,5). so(19,7,8). so(19,8,9). so(20,1,2). so(20,2,6). so(21,7,8). so(21,8,9). so(22,3,4). so(22,4,6). so(23,7,8). so(23,8,11). so(24,1,2).

or(a,p,v,zgp _ a, p, y) - orders

Orders for questions Q1..Q7: or(1,1,1,2). or(1,2,1,1). or(1,3,1,2). or(3,4,1,1). or(3,5,1,1). or(5,7,3,1). or(5,8,3,1). or(5,9,3,2). or(6,10,3,1). or(6,8,3,1). or(7,1,6,2). or(7,2,6,2). or(7,9,6,2). or(3,10,8,2). or(3,2,8,2).

Orders for question Q1,Q3 (efficiency research – Table 7): or(1,1,1,2). or(1,2,1,1). or(1,3,1,1). or(1,4,1,1). or(1,5,1,1). or(2,6,1,1). or(2,7,1,1). or(2,8,1,1). or(2,9,1,1). or(2,10,1,2). or(3,3,1,1). or(3,4,1,2). or(3,5,1,1). or(4,6,1,1). or(4,7,1,1). or(4,8,1,1). or(5,9,1,1). or(5,10,1,1). or(5,7,1,1). or(5,2,1,1). or(6,10,1,1). or(6,9,1,1). or(6,8,1,1). or(6,7,1,1). or(6,6,1,1). or(7,5,1,1). or(7,4,1,1). or(7,3,1,1). or(7,2,1,1). or(7,1,1,1). or(1,6,1,1). or(2,1,1,1). or(3,6,1,1). or(4,1,1,1). or(5,3,1,1). or(6,1,1,1). or(7,10,1,1). or(1,7,1,1). or(2,2,1,1). or(3,7,1,1). or(1,10,1,1). or(2,3,1,1). or(3,8,1,1). or(4,2,1,1). or(5,4,1,1). or(6,2,1,1). or(7,9,1,1). or(5,1,1,1). or(6,3,1,1). or(7,8,1,1).

References

Schwindt

and Zimmermann

, Handbook on Project Management and Scheduling, 2015. doi: 10.1007/978-3-319-05443-8

Burstein

and Clyde

, Handbook on Decision Support Systems 2: Variations (1st ed.), Springer Publishing Company, Incorporated, Holsapple, 2008.

Brucker

, Drexl

, Mohring

, Neumann

and Pesch

, Resource-constrained project scheduling: Notation, classification, models, and methods, European Journal of Operational Research 112(1) (1999), 3–41.

Tyson, R. Browning and A. Yassine, Resource-constrained multi-project scheduling: Priority rule performance revisited, International Journal Production Economics, 2010.

Tadayon

and Salmasi

, A two-criteria objective function flexible flowshop scheduling problem with machine eligibility constraint, The International Journal of Advanced Manufacturing Technology 64(5–8) (2013), 1001–1015.

Błażewicz

, Ecker

K.H.

, Pesch

, Schmidt

and Węglarz

, Handbook on Scheduling, From Theory to Applications, Springer, ISBN: 978-3-540-28046-0, 2007.

Sawik

, An exact approach for batch scheduling in flexible flow lines with limited intermediate buffers, Mathematic Computer Model 36(4–5) (2002), 461–471.

Freuder

E.C.

, Progress towards the Holy Grail, Constraints 23(2) (2018), 158–171. doi: 10.1007/s10601-017-9275-0

Rossi

, Van Beek

and Walsh

, Handbook of Constraint Programming (Foundations of Artificial Intelligence), New York: Elsevier Science Inc, 2006.

10.

Apt

, Wallace

and Logic

Constraint.

, Programming using Eclipse, Cambridge: Cambridge University Press, 2006.

11.

Sitek

, Nielsen

I.E.

and Wikarek

, A Hybrid Multi-agent Approach to the Solving Supply Chain Problems, Elsevier, Knowledge-Based and Intelligent Information & Engineering Systems 18th Annual Conference, KES-2014 (2014), 1557–1566. doi: 10.1016/j.procs.2014.08.239.

12.

Sitek

and Wikarek

, A hybrid framework for the modelling and optimisation of decision problems in sustainable supply chain management, International Journal of Production Research (2015), 1–18. DOI: 10.1080/00207543.2015.1005762

13.

Hooker

J.N.

, Logic, Optimization, and Constraint Programming, Journal of Computing 14(4) (2002), 295–321.

14.

Milano

, Wallace

and Operations

Integrating.

, Research in Constraint Programming, Annals of Operations Research 175(1) (2010), 37–76.

15.

Sitek

and Wikarek

, A Hybrid Programming Framework for Modeling and Solving Constraint Satisfactionand Optimization Problems, Scientific Programming 2016 (2016), Article ID 5102616, pp. 13. doi: 10.1155/2016/5102616

16.

Schrijver

, Theory of Linear and Integer Programming, John Wiley & Sons, New York, NY, USA, 1998.

17.

Gurobi Optimization. – The State-of-the-Art Mathematical Programming, Accessed August 12, http://www.gurobi.com/.

18.

Sitek

and Wikarek

, A novel approach to decision support and optimization of group job handling for multimodal processes in manufacturing and services, IFAC-PapersOnLine 48(3) (2015), pp. 2115–2120. doi: 10.1016/j.ifacol.2015.06.40

19.

Nielsen

, Dang

Q.-V.

, Nielsen

and Pawlewski

, Scheduling of mobile robots with preemptive tasks Advances in Intelligent Systems and Computing, 290 (2014), pp. 19–27.

20.

Bzdyra

, Bocewicz

and Banaszak

, Mass customized projects portfolio scheduling-imprecise operationstime approach, Applied Mechanics and Materials 791(2015), 70–80. 2015. Doi: 10.4028/www.scientific.net/AMM.791.70

21.

C.S.

and Chiang

, Complex Fuzzy Computing to Time Series Prediction - A Multi-Swarm PSO Learning Approach, Intelligent Information And Database Systems, ACIIDS 2011, Edited by: Nguyen

, Kim

, Janiak

. Book Series: Lecture Notes in Artificial Intelligence 6592 (2011), pp. 242–251.

22.

Bistarelli

, Furhwirth

, Marte

and Rossi

, Soft Constraint Propagation and Solving in Constraint Handling Rules, Computational Intelligence 20(2) (2004), 287–307.

23.

Koch

et al. MIPLIB 2010 Mixed Integer Programming Library version 5, Math Prog Comp 3 103–1632011, DOI 10.1007/s12532-011-0025-9

24.

Eriksen

P.S.

and Nielsen

, Order quantity distributions: Estimating an adequate aggregation horizon, Management and Production Engineering Review 7(3) (2016), pp. 39–48.