Solving a well-known resource constrained project scheduling problem (RCPSP) is crucial for project management. It consists of assigning a start time to each activity such that the precedence relations and the resource constraints are satisfied [1, 2]. The resulting schedule usually quantitatively distributes resources along the project timeline. However, for practical purposes, individual schedules have to be obtained for employees and other named resources to organize the workflow. Such resource allocation was previously presented assuming the difference in skills and other individual features [3]. This approach dramatically extends the search space. In practice, accounting resource heterogeneity is usually redundant or difficult to implement. This paper proposes the two-stage approach to individual schedule construction assuming that all units of the same resource are interchangeable. The first stage is a general scheduling based on genetic algorithm. The modified multi-project and multi-mode variation of the problem (also known as MRCMPSP) is considered as it is much closer to the real-world problems [4]. The second stage includes individual scheduling by allocating resource units to activities subject to the required condition (in this case, the uniformity of resource allocation). A simulated annealing algorithm is proposed for this purpose.
time unit. Workers and machines are examples of this type of resource. Each resource l Lp of the project p has a capacity of cpl . There are also global renewable resources G limited by capacities cg , g G . They can be used in any project.
Each activity j J p , p P is performed in exactly one mode mpj from the set of possible execution modes M pj . The mode determines activity duration and specific resource requirements. Let d pjmpj be the processing time of activity j J p in mode mpj M pj , and rpjmpjl define its consumption of l .
The objective is to find such activity start times spj and mode assignments mpj that satisfy precedence and resource constraints while minimizing the total project delay TPD . The total project delay is calculated as follows: where Finishp is the last activity completion time for the project p ; CPDp is a critical path duration assuming resource constraint relaxation and the assignment of execution modes with the shortest durations.
Thus, the objective can be formulated as the combinatorial optimization problem: TPD (MK p CPDp )
pP MSp Finishp Startp
TPD min subject to: rpjmpjl cpl jAp (t) rpjmpjl cpl jJp rpjmpj g cg pP jAp (t) p P,l Lp ,t 0,T
p P,l Lp g G ,t 0,T spj d pjmpj spj
p P, j J p , j Pre( j)
spj Startp
mpj M pj
p P, j J p
p P, j J p
Ap (t) j J p | spj t spj d pjmpj
(
The second stage is aimed to find correspondences between activities and resource units that are in some sense optimal. The schedule obtained in the first stage determines durations and resource requirements for each activity. Let Hl be the set of all available units of resource l and Jl
J p be the set of all activities that require resource l .
pP Each activity j Jl has duration d j and requires rjl of resource l . For each resource unit h we define Sh as the desired set of activities from its individual schedule. In this case, the uniformity of the resource allocation is considered as the optimality criterion. We assume that no resource unit can be utilized in multiple parallel activities. Thus, we can formulate the following combinatorial optimization problems for each renewable resource type l G Lp : subject to: pP (U (h) AvgU (l))2 min hHl
U (h) d j
jSh AvgU (l) hHl U (h)
Hl Sh | j Sh rjl
j Jl j Over( j)
h Hl ; j, j Sh ; j j Sh Jl h Hl (11) (12) (13) (14) (15) (16)
Here Over( j) is the set of activities which overlap with j . U (h) (12) is the total utilization of h , AvgU (l) (13) is the average resource utilization for l . Constraint (14) verifies that resource needs are met. Constraint (15) prevents allocation to overlapping activities. 3
RCPSP (and hence MRCMPSP) is computationally intensive combinatorial optimization task. It was proven to be NP-hard [5]. Optimal solution may be obtained only for rather small instances while practical problems can reach hundreds of activities. Therefore, the majority of studies consider applying different heuristics to find suboptimal solutions without traversing the entire search space [2].
In this study a genetic algorithm approach was used for general schedule construction. Some features of the previous implementations were incorporated [6, 7, 8]. Implementation details are provided below. 3.1
Each solution is encoded by a chromosome which corresponds to strictly one feasible schedule. Each chromosome consists of two parts: the first one contains an activity list in order of priority and the second one includes chosen activity modes. The corresponding schedule can be obtained by the following sequential procedure. Starting with an empty schedule we construct a new partial schedule by placing the next activity from an activity list to the earliest possible time so that precedence and resource constraints are satisfied. This is usually called a serial schedule generation scheme (SGS). Note that any such solution corresponds to only one schedule but the same schedules can be obtained from different solutions. 3.2
The modification of fitness function proposed in [8] was used for solution evaluation. It penalizes solutions by adding the number of requested non-renewable resource units that exceed the capacity. Such approach is considered more efficient in terms of faster convergence to suboptimal solutions.
1 MaxTPD TPD(I ) 1 f (I ) MaxTPD 1 TPD(I ) MaxTPD
ERR,
ERR 0 otherwise TMS MS p
pP MaxTMS d pjmpj
pP jJp MaxTPD d pjmpj CPDp pP jJ p ERR max 0, pP lLp jJ p rpjmpjl cpl
cpl (17) (18) (19) (20) (21) Here ERR (21) is the non-renewable resource error, TMS (18) is the total makespan of the projects, equations (19) and (20) define estimations of maximum total makespan and maximum total project delay respectively. 3.3
The initial population is randomly generated to ensure diversity of solutions. The procedure of random generation starts with an empty activity list. At each step of the procedure a random activity whose predecessors are already in the list is appended. Its mode is also taken randomly and added to the second part of the chromosome.
The resulting instances obviously satisfy the precedence constraints. And for the algorithm to work correctly crossover and mutation operations must be implemented in such a way that the resulting solutions are also feasible. 3.4
Crossover operation combines a pair of parent solutions to produce two children that inherit their parents’ features. The operation is applied independently to activity lists and mode lists of parent chromosomes.
A point q on both active lists is picked randomly splitting them into two parts. All activities from the first part of the first (second) activity list are transferred to the first (second) offspring list and the remaining activities are appended in the order in which they are located in the second (first) parent. Such method is called a single-point crossover.
Activity mode lists of the parents are crossed over according to uniform method. For each i-th activity a random value pi 0,1 is picked independently. If pi 0.5 then the first (second) child inherits the mode of this activity from the first (second) parent. Otherwise, the first (second) child inherits the mode from the second (first) parent. 3.5
Mutation is defined as a random change in the solution obtained by crossing over. Mutation operation is also applied independently to each part of a chromosome.
For each i-th activity of activity list a random value pi 0,1 is picked independently. If pi PPM , where PPM is initially defined mutation probability, then i-th and i+1 activities are swapped unless this violates the precedence constraints.
Each activity mode is replaced by a randomly picked one with initially defined probability PMM .
Since we assume interchangeability of individual units of the same resource, it's reasonable to represent solution as a multiset to reduce the search space. Thus, any solution is defined as:
Zl Sl(
The neighbor of any solution relative to the particular activity j can be obtained by removing this activity from some schedule and adding to another one. Note that target schedule should not contain any activities overlapping with j .
The initial solution can be randomly generated. The procedure starts with a set of empty schedules. Then each activity j from Jl is added rjl times to random schedules. Again, the target schedules should contain only activities which don't overlap with j .
Now it becomes possible to apply any local search algorithm to solve the problem. In this study the simulated annealing method was used. The main steps of the algorithm are:
Obtain random initial solution and set x (the current solution) and xbest (the best solution) to it. Store corresponding objective function value in fbest ; 1. Initialize the temperature T with T0 ; 2. Get random neighbor x of the current solution; 3. Calculate the objective function f (x) and the difference : f (x) f (x) ; 4. if 0 then x : x and 5.
if f (x) fbest then fbest : f (x) and xbest : x ;
6. Otherwise, if e/T p ( p [0,1] is a random value) then x : x ;
7. Lower the temperature: T : T ( (
The algorithm was tested on a subset of MISTA 2013 Challenge problem instances [4]. The algorithm was implemented in Python and all tests were performed on a computer with Intel Core i5 8250U.
Table 1 shows results for 9 problems of MISTA 2013 Challenge instance set. The problems with different number of projects, activities and renewable resources were considered. Parameters of genetic algorithm were: population size – 150, crossover probability – 0.8, mutation probability – 0.04. Simulated annealing parameters were: iteration count – 1000, initial temperature – 1000, temperature reduction factor – 0.9.
A series of tests was performed on the problem A-1 with different number of generations to estimate the rate of convergence of the proposed genetic algorithm. The values of other parameters were the same. 20 runs were made for each population size. The results are shown in table 2.
A series of tests was performed on the problem A-9 with different number of iterations to estimate the rate of convergence of the proposed simulated annealing method. The values of other parameters were the same. 20 runs were made for each number of iterations. The results are shown in table 3. In this study, an extension to the traditional MRCMPSP was introduced to make individual schedules for renewable resources. The resulting two-stage optimization model was implemented using genetic algorithm and simulated annealing method. The algorithm was tested on the set of problems from MISTA 2013 Challenge.