Optimization and Simulation of Resource Constrained Scheduling Problem Using Genetic Algorithm
Department of Equipment Command, Equipment Academy, Beijing, China
To cite this article:
Jiancheng Wang. Optimization and Simulation of Resource Constrained Scheduling Problem Using Genetic Algorithm. Science Journal of Business and Management. Vol. 4, No. 6, 2016, pp. 229-237. doi: 10.11648/j.sjbm.20160406.18
Received: October 30, 2016; Accepted: November 22, 2016; Published: January 7, 2017
Abstract: Due to the development of management idea and the scarcity of some resources, the lean management has become the necessary request to implement effective control of resource constrained project. Resource constrained project scheduling is the significant guarantee to attain the lean management. The resource constrained project scheduling problem (RCPSP), with the objective of minimizing project duration and with the precedence relations described by an activity-on-arrow (AOA) network, is formulated as a combination optimization problem and solved using the priority-based genetic algorithm (GA). The activity priorities are represented by chromosome and serial scheduling scheme (SSS) and parallel scheduling scheme (PSS) are developed and utilized to transform chromosome-represented priorities to an active schedule subject to the logic and resource constraints so that project duration corresponding to each chromosome can be evaluated. The overall framework of the GA for the RCPSP is developed and the basic components of the algorithm are designed. Simulation is provided so as to investigate the performance of the priority-based GA with SSS and PSS as decoding method, respectively. The optimal solution to a small-sized resource constrained benchmark instance is scheduled to find the shortest project duration. Comparative simulation results demonstrate not only the effectiveness and efficiency of GA with SSS or PSS as decoding methods in solution to RCPSP with precedence relation of activities diagramed as an AOA network but also the effect of different evolution parameter settings on solution quality of the problem.
Keywords: Resource Constrained, Project Duration Optimization, Equipment Support, Genetic Algorithm, Network Planning, Activity-on-Arc Network, Serial Scheduling Scheme, Parallel Scheduling Scheme
Due to the development of management idea and the scarcity of resources, the importance of lean management has been gradually recognized. Lean management requests that limited resources should be considered when project scheduling is made. Resource-constrained scheduling is the effective approach to lean management, and it has been widely applied in various management fields such as construction engineering, equipment support, manufacturing industry, software development, and so on.
On account of the limited resource units that can be assigned to activities, the project completion time will most likely be greater than the duration that critical path method (CPM) has originally calculated, without taking into account the resource usage limit. It is obvious that a project scheduling with inadequate consideration of the resource usability will result in an unexpected ending. For project managers, activities of a project must be scheduled under resource constrained conditions such that the project will be completed within the scheduled task duration, which is advantageous in organizing and carrying out of the project in line with the predetermined arrangement. How to properly schedule the activities in a project under constraint of limited resources belongs to the resource constrained project schedule problem (RCPSP) [1-14]. The objective of RCPSP is to properly schedule dependent activities over time such that the task duration is minimized while the precedence and resource constraints have to be met.
Mingozzi et al.  and Brucker et al.  developed branch and bound algorithms, and Gavish and Pirkul  used dynamic programming. Blazewicz et al. proved that RCPSP is nondeterministic polynomial (NP)-hard in the strong sense such that the computation time for obtaining the optimal solution using exact algorithms can be extremely long for project even of medium scale. As a result, many procedures have been proposed in the past to overcome the combinatorial explosion problem. The approaches are grouped into priority rule-based methods, classical metaheuristics, non-standard metaheuristics, and other heuristics. Of the classical meta-heuristics, there are genetic algorithms (GAs), particle swarm optimization (PSO), tabu search (TS), simulated annealing (SA), and ant systems (AS), scatter search (SS), filter-and-fan approach [21-38]. For a detailed description of basic components of heuristics such as schedule generation schemes, priority rules, and representations, the reader is referred to [27-30].
This work is focused on a genetic algorithm based meta-heuristic approach with both serial scheduling scheme (SSS) and parallel scheduling scheme (PSS) as schedule generation scheme (SGS) to assist the resource constrained project scheduling. To the best of the author’s knowledge, the SGS is well studied for RCPSP with precedence relationship expressed in an activity-on-node (AON) format, but little efforts are given to extend the algorithms to RCPSP with precedence relationship expressed in an activity-on-arc (AOA) format. Simulation results show that none of the schemes is dominant. Generally speaking, for RCPSP with precedence relationship expressed in AOA format, serial scheduling scheme is suitable for relatively small instances while parallel scheduling scheme is suitable for relatively large ones, which is consistent with those for RCPSP with precedence relationship expressed in AON format. Simulation results demonstrate the solution quality and efficiency of RCPSP with moderate size is rather satisfactory. The deficiencies in GA performance such as premature convergence and slow convergence have been identified. The quality and efficiency of solution to RCPSP with moderate or large size may be further improved by bidirectional planning  and other strategies [40-52].
The rest of this paper is organized as follows: in Section 2 RCPSP is formulated as a combination optimization problem, in Section 3 the framework and basic components of genetic algorithm are developed and designed. Simulation results of a benchmark instance are given in Section 4. In the end, the work is concluded in Section 5.
The relationship among activities of a project can be described either as an AOA network or an AON network. The latter one is usually utilized in most research papers, but the former one is especially adopted here for purpose of comparison study. The AOA network is a directed acyclic diagram (DAG) G (V, A) where V is the set of nodes and A is the set of activities between which a finish-start precedence relationship with time lag 0 exists. Each activity can be distinguished either by number index or by node pair (p, q). In normal case, the number index expression of an activity in AOA network is adopted for simplicity and ease of description. The node pair expression of an activity is used where necessary. Sets of all immediate predecessor and successor activities of an activity j are denoted by Pj and Sj, respectively.
The Classical resource-constrained project scheduling problem (RCPSP) can be stated as follows: a project consists of N (|A|=N) activities in all including the dummy ones. The first activity 1 and the last activity N are, by convention, defined as dummy activities, i.e. activities that require zero execution time. The activities are interrelated by two types of constraints. The first one is a precedence relation between j and iPj which forces activity j not to be started before any one of its immediate predecessor activities, iPj, has been finished. This type of constraint can be determined by the corresponding AOA network of the project and the activity durations. The constraint of the second type is related to the resource requirements. The resources can be classified either as renewable or non-renewable. Non-renewable resources are consumed by the activities while renewable resources are not consumed and keep the same amount along the entire lifetime of the project. The renewable resources are considered here. The set of renewable resource types is K. While being processed, activity j requires units of resource of type kK, during each time period of its non-preemptable duration dj. Resource type k has a limited capacity of Rk, constant through the project execution, which cannot be violated at any time period, i.e., the sum of resource usage of all ongoing activities At in time instance t should not exceed Rk units of resource type kK. The parameters dj, , and Rk are assumed to be nonnegative, deterministic, and integer.
The objective for RCPSP is to find a schedule of the project such that the project duration is minimized subject to precedence and resource constraints. The problem is formulated as an optimization problem as in (1), (2), (3) and (4). The decision variable is the actual start time of activity j, .
In which, At is the set of ongoing activities in time instant t, as defined in (5).
An upper bound on the project’s makespan is denoted as , and is the as-yet-unused resource units of type k at time instant t.
The objective function (1) minimizes the makespan of the project. Constraints (2) take into consideration the precedence relations between activities i and j, where i immediately precedes j. Finally, constraint set (3) limits the total resource usage within each time period to the maximum available amount.
3. Solution Using Genetic Algorithm
GA is essentially an iteration procedure that operates on chromosomes, which resulting in solution to the decision variables.
3.1. Overall Framework
The overall framework of genetic algorithm is developed as in Algorithm 1. It is actually constructed as an iteration process. Initialization is done first, and then enters the outer-most loop. Within the loop, the population is evaluated, and the best individual of current generation and the best indivi-dual so far are updated. Generation gen is increased by 1. Terminating condition is now checked. If the terminating condition is not satisfied, selection, crossover and mutation operators as well as the elitist strategy are executed to generate the next population, which is the beginning of the next iteration; otherwise, exit outermost loop and necessary quantities as well as the elapsed time are output.
Algorithm 1. Framework of Genetic Algorithm
/* initialization */
set aPopulation.chrom=rand(popSize, N)
/* main loop */
if gen>1 then
/* generate next population */
roulette wheel selection
parametrized uniform crossover
/* perform evolution based on elitist strategy */
/* replace chromosome of a individual by that of current best one */
/* evaluation loop */
for i=1 to popSize do
decode aPopulation.Chrom(i, :) to get Sn and actual start time
compute project duration Tp from actual start times of all activities
/* find the best individual */
set bestIndividual.chrom=aPopulation.chrom(1, :)
set bestIndividual.serial=aPopulation.serial(1, :)
for i=1 to popSize do
if aPopulation.objValue(i)<bestIndividual.objValue then
set bestIndividual.chrom=aPopulation.chrom(i, :)
set bestIndividual.serial=aPopulation.serial(i, :)
/* find out the best individual so far */
if gen=1 then
if bestIndividual.objValue<currentBestIndividual. objValue then
until currentBestIndividual.objValue is good enough or gen>maxGen
/* output results */
output the scheduled actual start times of activities
Initialized quantities includes Pj, dj, and , jA, R1, crossover probability Pc, mutation probability Pm, crossover probability threshold TCP, percentage of mutants in a population Percm, maximum evolution generation maxGen, population size popSize, chromosome length N, the number of AOA network nodes numNode.
Define variable aPopulation to hold the whole population, which is a structure of chromosome chrom, precedence feasible serial serial, and objective value objValue. Define variable bestIndividual to track the best individual of the whole population in a generation, and variable bestIndex to track the index to the best individual in the generation. Define variable currentBestIndividual to track and record the best individual so far. The initial chromosomes are randomly generated such that aPopulation.chrom=rand(popSize, N).
3.3. Chromosome Expression
In general, there are two forms of chromosome representations: permutation-based representation and priority-based representation . The latter is adopted here for its remark-able merit that the activity sequence decoded from chromo-some after crossover and mutation is still precedence feasible, and no repairing operator is needed to resolve the precedence conflict, which would appear if the former expression of a chromosome is used. For priority-based representation, a chromosome is made of N genes:
The jth gene of a chromosome stands for the priority of activity j, which will be used by the chromosome decoding. For activity j, it would compete with its priority among its competitors in current decision set to be scheduled first.
3.4. Schedule Generation Scheme
Generally, a priority rule based scheduling heuristic is made up of two main components, a schedule generation scheme and a priority rule . Two different schemes can be distinguished: the so-called serial and the parallel method. Both generate a feasible schedule by extending a partial schedule (i.e. a schedule where only a subset of the activities has been assigned the start times) in a stage-wise fashion. In each stage the generation scheme forms the set of all schedulable activities, the so-called decision set. A specific priority rule is then employed in order to choose and schedule one or more activities from the decision set. The formal algorithm for serial scheduling scheme (SSS) and parallel scheduling scheme (PSS) are developed, as shown below, to transform the chromosome-represented priorities to an active schedule under the precedence constraints and limited resource constraints so that the chromosome can be evaluated during searching for an optimal solution.
Procedure 1. Serial Scheduling Scheme
while |Sn|<=N−1 do
for t=0 to T−1 do
if At= then
Procedure 2. Parallel Scheduling Scheme
while |AnCn|<=N−1 do
if n>1 then
if An= then
During each generation, the individuals in the current population are evaluated. To evaluate an individual, the chromosome is decoded first. By decoding, the actual start time of activity j, , is obtained, and the objective value can be further computed based on the actual start times of all activities. Closely after evaluation, the best individual of the generation, and the best individual so far are picked out.
3.6. Fitness Function
Since RCPSP is formulated as a minimization problem, and the roulette wheel selection is a fitness-proportional selection, a transformation is utilized to map the natural objective value into a fitness value to ensure the individual of lower objective value has bigger selection probability.
The transformation of objective value Tp corresponding to chromosome c into a fitness value is implemented by an absolute fitness function as shown in (6).
3.7. Next Population Generation
Based on the fitness value of chromosomes in the current generation, the roulette wheel selection mechanism is used to probabilistically copy N chromosomes into the next genera-tion. After pair making, parametrized uniform crossover  is utilized to inherit the genes of same loci into the chromosome of children either from father or from mother depending on the comparison between a real random number and the crossover probability threshold TCP. For each locus, a real random number in the interval [0,1] is generated. If the random number obtained is smaller than TCP, then the allele of father is inherited by the offspring. Otherwise, the inherited allele is that of the mother. Mutation operator should prevent premature convergence of the population to local minima. To this end, instead of performing gene-by-gene mutation at each generation with very small probability Pm, a few randomly selected individuals, say Percm percent of popSize, are replaced with randomly generated new ones. These new individuals (called mutants) are randomly generated with the same distribution as the original population. Therefore, no genetic material of the current population is brought into the mutants, and the mutation operator can therefore prevent premature convergence of the population and lead to a simple statement of convergence, i.e., if a sufficiently large number of generations are carried out, then the entire solution space will be sampled. After mutation, the elitist strategy  is performed to replace the chromosome of an arbitrary individual in current generation by that of the current best one so far. The main advantage of this strategy is that the best solution is monotonically improving from one generation to the next. At this point, the process of next generation is completed.
Outputted are the best chromosome chrombest, the best activity serial Sn corresponding to chrombest, the actual start time corresponding to Sn and the shortest project duration Tp. The consumed CPU time of a running of the algorithm is also stored.
4. Simulation Instance
In this section, numerical simulations is implemented in Matlab Language to evaluate the performance of the GA proposed in Section 3 and to compare the efficiency of serial scheduling scheme and parallel scheduling scheme. The results of revised version a small-sized benchmark instance  are reported, in which the precedence relation of activities in the project is diagramed as an activity on arrow network.
The AOA network for the instance with 12 nodes and 15 activities including 4 dummy ones is shown in Figure 1, and the parameters Pj, dj, and , are given in Table 1. R1=5. The evolutionary environment of the problem is that popSize=50, N=15, Pc=0.80, Percm=5, TCP=0.7, maxGen= 20. The GA program is randomly run 10 times with PSS as decoding method, and all solutions have attained the exact one of the problem, which shows the capability of the GA with PSS as decoding method and with the given parameter settings. The scheduled results of the precedence feasible activity sequence Sn and the actual start time for each run are listed in Table 2 (index to GA running is indicated by IX). The resource allocation profile with PSS as decoding method is shown is Figure 2. The evolution process of the problem is shown in Figure 3. The optimum project duration 20 is obtained at the early stage of the evolution process, which is the same as that of the AON network . It demonstrates that the proposed algorithm can approach the known exact solution rapidly.
For comparison, with the same parameter settings as used for the first 10 runs, the program is randomly run another 10 times for the solution of the instance problem with SSS as decoding method, and 9 out of 10 solutions (but not given here) have attained the exact one of the problem, which also shows the capability of the GA with SSS as decoding method and with the given parameter settings.
It can be drawn from the above two groups of solutions that the schedule generation scheme, PSS or SSS, has little effect on the running time rate of obtaining the same optimal solutions as the exact one to the problem. But if the size of the resource constrained project schedule problem is decreased or increased, the effect of schedule generation scheme on the rate may be different. In addition to the adoption of schedule generation scheme, the evolution parameter settings will also affect the solution quality of the genetic algorithm. For example, the GA program is randomly run the third 10 times with all the conditions being kept the same as the second 10 runs except for the percentage of mutants in a population, Percm, is increased from 5 to 15. Under this circumstance, all solutions have attained the exact one of the problem, as contrasted to the 9 out of 10 in the second 10 runs.
|11||(7, 9)||6, 7||3||2|
|13||(9, 10)||10, 11||2||5|
|15||(11, 12)||8, 12, 14||0||0|
|IX||Index to activity positions in precedence and resource feasible activity serial Sn|
Priority-based representation is used to express chromo-some in GA, which is decoded by serial scheduling scheme and parallel scheduling scheme. A resource constrained instance project is scheduled using genetic algorithm to find the shortest project duration. Simulation results show the capability of the GA with PSS or SSS as decoding method, as well as the effect of different evolution parameter settings on solution quality of the small-sized instance problem. Future efforts will be focused on the research regarding how the decoding method and evolution parameter settings affect the convergence and the efficiency of the proposed algorithm.