Differential evolution for solving multi-mode resource-constrained project scheduling problems. (English) Zbl 1179.90134

Damak, N.; Jarboui, B.; Siarry, P.; Loukil, T.

Comput. Oper. Res. 36, No. 9, 2653-2659 (2009).

Summary: We consider the resource-constrained project scheduling problem with multiple execution modes for each activity and minimization of the makespan. To solve this problem, we propose a differential evolution (DE) algorithm. We focus on the performance of this algorithm to solve the problem within small time per activity. Finally, we present the results of our thorough computational study. Results obtained on six classes of test problems and comparison with other algorithms from the literature show that our algorithm gives better solutions.

MSC:

90B35	Deterministic scheduling theory in operations research
90B50	Management decision making, including multiple objectives

Keywords:

differential evolution; scheduling; MRCPSP; makespan

References:

[1]	Sprecher, A.; Drexl, A., Solving multi-mode resource-constrained project scheduling by a simple, general and powerful sequencing algorithm, European Journal of Operational Research, 107, 431-450 (1998) · Zbl 0943.90042
[2]	Drexl, A.; Grünewald, J., Nonpreemptive multi-mode resource-constrained project scheduling, IIE Transactions, 25, 74-81 (1993)
[3]	Slowinski, R.; Soniewicki, B.; Weglarz, J., DSS for multiobjective project scheduling subject to multiple-category resource constraints, European Journal of Operational Research, 79, 220-229 (1994) · Zbl 0815.90099
[4]	Kolisch, R.; Drexl, A., Local search for non-preemptive multi-mode resource-constrained project scheduling, IIE Transactions, 29, 987-999 (1997)
[5]	Özdamar, L., A genetic algorithm approach to a general category project scheduling problem, IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, 29, 44-59 (1999)
[6]	Bouleimen, K.; Lecocq, H., A new efficient simulated annealing algorithm for the resource constrained project scheduling problem and its multiple mode version, European Journal of Operational Research, 149, 268-281 (2003) · Zbl 1040.90015
[7]	Hartmann, S.; Drexl, A., Project scheduling with multiple modes: a comparison of exact algorithms, Networks, 32, 283-297 (1998) · Zbl 1002.90025
[8]	Jarboui, B.; Damak, N.; Siarry, P.; Rebai, A., A combinatorial particle swarm optimization for solving multi-mode resource-constrained project scheduling problems, Applied Mathematics and Computation, 195, 299-308 (2008) · Zbl 1180.90125
[9]	Boctor, F. F., Heuristics for scheduling projects with resource restrictions and several resource duration modes, International Journal of Production Research, 31, 2547-2558 (1993)
[10]	Boctor, F. F., A new and efficient heuristic for scheduling projects with resource restrictions and multiple execution modes, European Journal of Operational Research, 90, 349-361 (1996) · Zbl 0916.90143
[11]	Storn, R.; Price, K., System design by constraint adaptation and differential evolution, IEEE Transactions on Evolutionary Computation, 3, 1, 22-34 (1999)
[13]	Babu, B. V.; Sastry, K. K.N., Estimation of heat transfer parameters in a trickle-bed reactor using differential evolution and orthogonal collocation, Computers and Chemical Engineering, 23, 3, 327-339 (1999)
[14]	Rajive, J.; Arthur, C., Minimal representation multisensor fusion using differential evolution, IEEE Transactions on Systems, Man and Cybernetics, Part A, 29, 1, 63-76 (1999), ISSN: 1083-4427
[15]	Jouni, L.; Ivan, Z., Mechanical engineering design optimization by differential evolution, (Corne, D.; Dorigo, M.; Glover, F., New ideas in optimization (1999), McGraw-Hill: McGraw-Hill London, UK), 127-146, ISBN 007-709506-5
[16]	Storn, R., System design by constraint adaptation and differential evolution, IEEE Transactions on Evolutionary Computation, 3, 1, 22-34 (1999)
[17]	Chang, T.; Chang, H., An efficient approach for reducing harmonic voltage distortion in distribution systems with active power line conditioners, IEEE Transactions on Power Delivery, 15, 3, 990-995 (2000)
[18]	Lameh, J.; Wang, P.; Elgart, D.; Meredith, D.; Shafer, S. L.; Loew, G. H., Unraveling the identity of benzodiazepine binding sites in rat hippocampus and olfactorybulb, European Journal of Pharmacology, 400, 2-3, 167-176 (2000)
[19]	Rogalsky, T.; Kocabiyik, S.; Derksen, R. W., Differential evolution in aerodynamic optimization, Canadian Aeronautics and Space Journal, 46, 4, 183-190 (2000)
[20]	Stumberger, G.; Pahner, U.; Hameyer, K., Optimization of radial active magnetic bearings using the finite element technique and the differential evolution algorithm, IEEE Transactions on Magnetics, 36, 4, 1009-1013 (2000)
[21]	Wang, F.; Sheu, J., Multiobjective parameter estimation problems of fermentation processes using a high ethanol tolerance yeast, Chemical Engineering Science, 55, 18, 3685-3695 (2000)
[22]	Booty, W. G.; Lam, C. L.D.; Wong, I. W.S.; Siconolfi, P., Design and implementation of an environmental decision support system, Environmental Modelling and Software, 16, 5, 453-458 (2000)
[23]	Cheng, S.; Hwang, C., Optimal approximation of linear systems by a differential evolution algorithm, IEEE Transactions on Systems, Man and Cybernetics, Part A, 31, 6, 698-707 (2001)
[25]	Ruzek, B.; Kvasnicka, M., Differential evolution algorithm in the earthquake hypocenter location, Pure and Applied Geophysics, 158, 4, 667-693 (2001)
[26]	Abbass, H. A., An evolutionary artificial neural networks approach for breast cancer diagnosis, Artificial Intelligence in Medicine, 25, 265-281 (2002)
[29]	Lorenzoni, L. L.; Ahonen, H.; Alvarenga, A. G., A multi-mode resource-constrained scheduling problem in the context of port operations, Computers and Industrial Engineering, 50, 55-56 (2006)
[31]	Kolisch, R.; Sprecher, A.; Drexl, A., Characterization and generation of a general class of resource constrained project scheduling problems, Management Science, 41, 1693-1703 (1995) · Zbl 0870.90070