A new solution encoding for solving the resource-constrained project scheduling problem with genetic algorithms

JAVIER ALCARAZ AND CONCEPCIÓN MAROTO
Department of Applied Statistics, Operations Research and Quality
Universidad Politécnica de Valencia
C. de Vera S/N. 46071 Valencia
SPAIN
     http://www.upv.es/gio

Abstract: - The problem considered in this work is the well known and widely studied Resource-Constrained Project Scheduling Problem (RCPSP), denoted as m,1/cpm/Cmax (Herroelen et al. [8]) or PS/prec/Cmax (Brucker et al. [4]). Several different heuristic, metaheuristic and hybrid techniques have been developed to solve this combinatorial optimization problem. We have developed an efficient, competitive and robust genetic algorithm, based on a new solutions encoding, knowledge specific genetic operators and an improvement mechanism. We have compared this algorithm with the best algorithms published so far, using the standard benchmark of PSPLIB. The preliminary results show the excellent performance of our algorithm. The algorithm has not been completely calibrated yet, but once this task has been completed, these results will be surely improved.

Key-Words: - Project scheduling, Limited resources, Genetic algorithms, Metaheuristics, Hybrid algorithms, Genetic encoding

1   The Genetic Algorithm
The algorithm we propose is based on the efficient genetic algorithms previously designed by us to solve this NP-hard problem. We use a new solutions encoding, which is the combination of two previously designed encodings which have reported excellent results in different genetic algorithms. These two encodings are extensions of the standard activity list representation. 
     The first was developed by Hartmann [5] and includes an additional gene indicating if the serial or the parallel scheduling generation scheme (SGS) is used to build up the schedule. 
     The second one was designed by Alcaraz and Maroto [1] and also includes one more gene, called  forward/backward gene, that indicates if forward or backward SGS is used to build up the schedule. 
     The representation proposed by Hartmann allows that the own genetic process decides the SGS which is used to build up the schedules: serial or parallel, but always employing forward scheduling. By the other hand, the representation designed by Alcaraz and Maroto can use forward or backward scheduling, but always using the serial SGS.

1.1	Genetic encoding
The new representation proposed is given in Figure 1. A solution is encoded as a chromosome with N+2 genes. One of the additional genes is the forward/backward gene (f/b gene) used in the representation previously designed by Alcaraz & Maroto. 
     The interest of that representation is to exploit the possibility of scheduling a solution in a forward/backward way, which produces left/right shifted schedules with possibly different makespan. By applying backward scheduling we can build schedules which can not be obtained by forward scheduling and vice-versa. The other additional bit is the serial-parallel gene (s/p gene) which indicates if serial or parallel scheduling is used in the schedule construction. 
     Computational studies carried out by Hartmann and Kolisch [6] show that for large project sizes the parallel SGS obtains better results than the serial one, because the search space of the parallel scheme is typically smaller. As the parallel SGS is not immediately applicable to deal with activity lists, when the forward (backward) parallel scheme is used, the position number of an activity indicates its priority to be scheduled, being the activity with the lowest (highest) position number, the activity with the highest priority. 
     With this representation, not only the solution of the problem, but also the scheduling mechanism used to construct the schedule is subject to genetic optimization. 

Activity list	f/b gene	s/p gene	
Fig. 1. Genetic encoding.

1.2	Genetic operators
We have also extended the crossover and mutation mechanisms previously designed by Alcaraz and Maroto [1] to operate over the activity list with scheduling mode representation and extended later to work on the multi-mode version of the problem in Alcaraz et al. [2], to deal with the serial-parallel gene. 
     The crossover operation depends on the parents f/b genes. The parents s/p genes do not influence the crossover procedure. The daughter inherits the s/p and the f/b genes from the mother and the son from the father. 
     The mutation operator designed by Alcaraz and Maroto [1] has also been extended to operate over the new representation. Each activity in the project is inserted in a randomly chosen position, preserving the precedence feasibility, with a given probability of Pmut. Then, the f/b and the s/p genes also change with the same probability. We have incorporated a local search procedure in order to improve the performance of the algorithm. 

1.3	Local search procedure
After the crossover and mutation operations are applied over the solutions, the local search procedure is performed. Activities are sorted depending on its start/finish time in the schedule. Then, this sorted sequence replaces the original activity list. This sorting procedure can be applied in one or two phases. 
     This procedure depends on the f/b gene of the solution. If forward (backward) scheduling has been initially applied to build up the schedule, i.e. the f/b gene is “f” (“b”), in the first phase activities are sorted with respect to non-decreasing finish (start) times and the schedule is constructed again applying now backward (forward) scheduling. 
     In the second phase, if applied, activities are now sorted with respect to non-decreasing start (finish) times, and the schedule is The effect of this reordering is to right/left shift the schedule if the serial SGS is applied. Thus, this local search procedure can not lead to an increasing of the schedule makespan. 
     This procedure has previously successfully applied by different authors such us Tormos and Lova [9] or Valls et al. [10]. However, if the parallel scheme is being applied, the local search procedure could worsen the solution quality. In this case, the new solution does not replace the initial one.

2   Computational Results
In order to determine the behaviour of the algorithm we have solved the standard instances of PSPLIB (www.bwl.uni-kiel.de/Prod/psplib) J30, J60 and J120, computing 1000, 5000, and 50000 schedules and we have compared the results with some of the best and more recent metaheuristics. 
     Table 1, Table 2 and Table 3 show some of these results for different genetic algorithms (GA), a simulated annealing algorithm (SA) and a multi-pass procedure (MP). For the set J30 the deviation from the optimal solution is given and for the sets J60 and J120 we have measured the deviation from the critical path based lower bound. As we can see, our genetic algorithm obtains good quality results for all the project sizes. 
For the small and medium projects (J30 and J60), our new algorithm is the best when the number of computer schedules is 1000 or 5000. When the number of schedules is increased to 50000 the new genetic algorithm is only outperformed by the genetic algorithm developed by Valls et al. [10], which is the fourth when computing a lower number of schedules.
For the largest projects this situation changes. Our algorithm is the best if the number of schedules is medium or high, but the Valls algorithm is better when 1000 schedules are computed.

Authors - Algorithm	J30	
	1,000	5,000	50,000	
New Algorithm	0.25	0.04	0.03	
Tormos & Lova- MP [9])	0.30	0.17	0.09	
Alcaraz & Maroto - GA [1]	0.33	0.12	-	
Valls, et al. - GA [10]
	0.34	0.20	0.02	
Hartmann - GA [7]	0.37	0.21	0.08	
Bouleimen & Lecocq - SA [3]	0.38	0.23	-	
Table. 1. Comparison of heuristics. J30.
Authors - Algorithm (year)	J60	
	1,000	5,000	50,000	
New Algorithm	11.88	11.19	10.83	
Tormos & Lova- MP [9]	12.14	11.82	11.47	
Alcaraz & Maroto - GA [1]	12.26	11.70	-	
Valls et al. - GA [10]	12.21	11.27	10.74	
Hartmann - GA [7]	12.35	11.70	11.21	
Bouleimen & Lecocq - SA [3]	12.75	11.90	-	

Table. 2. Comparison of heuristics. J60.
Authors - Algorithm (year)	J120	
	1,000	5,000	50,000	
New Algorithm	36.52	33.77	31.49	
Tormos & Lova- MP [9]	36.24	35.56	34.77	
Alcaraz & Maroto - GA [1]	37.17	35.35	-	
Valls, et al. - GA [10]	35.18	34.02	32.81	
Hartmann - GA [7]	37.33	35.60	33.21	
Bouleimen & Lecocq - SA [3]	42.81	37.68	-	
Table. 3. Comparison of heuristics. J90.

References:
[1]	Alcaraz, J. and C. Maroto (2001). A robust genetic algorithm for resource allocation in project scheduling. Ann Oper Res, 102, 83-109. 
[2]	Alcaraz, J., C. Maroto and R. Ruiz (2003). Solving the MRCPSP with genetic algorithms. J Opl Res Soc, 54, 6, 614-626. 
[3]	Bouleimen, K and H. Lecocq (2003). A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version. Eur J Opl Res, 149, 268-281.
[4]	Brucker, P. A. Drexl, R. Mohring, K. Neumann and E. Pesch (1999). Resource-constrained project scheduling: Notation, classification, models, and methods. Eur J Opl Res, 112, 1, 3-41.
[5]	Hartmann, S. (1999). Project Scheduling under limited resources. Models, methods and applications, Springer, Berlin.
[6]	Hartmann, S. and R. Kolisch (2000). Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem. Eur J Opl Res, 127, 394-407.
[7]	Hartmann, S. (2002). A self-adapting genetic algorithm for project scheduling under resource constraints. Nav Res Log, 49, 433-448.
[8]	Herroelen, W., E. Demeulemeester and B. De Reyck (1999). A classification scheme for project scheduling. In: Project Scheduling: Recent Models, Algorithms and applications. (J. Weglarz, ed.), pp 1-26, Kluwer, Amsterdam.
[9]	P. Tormos and A. Lova (2003). An efficient multi-pass heuristic for project scheduling with constrained resources. Intl. J Prod Res, 41, 5, 1071-1086. 
[10] Valls, V., Ballestín, F. and S. Quintanilla (2004). Justification and RCPSP: A technique that pays. Eur J Opl Res, In press.