An effective shuffled frog-leaping algorithm for resource-constrained project scheduling problem. (English) Zbl 1251.90140
Summary: We propose an effective heuristic based on the framework of the shuffled frog-leaping algorithm (SFLA) for solving the resource-constrained project scheduling problem (RCPSP). We encode the virtual frog as the extended activity list (EAL) and decode it by the SFLA-specific serial schedule generation scheme (SSSGS). The initial population is generated by the regret-based sampling method and the priority rule. Then, virtual frogs are partitioned into several memeplexes, and each memeplex evolves by adopting the effective resource-based crossover (RBCO). To enhance the exploitation ability, a combined local search including permutation-based local search (PBLS) and forward – backward improvement (FBI) is performed in each memeplex. To maintain the diversity of each memeplex, virtual frogs are periodically shuffled and reorganized into new memeplexes. Basing on some theoretical analysis, speed-up evaluation methods are proposed to improve the efficiency of the SFLA, which are also suitable for other heuristics designed for RCPSP. In addition, we make use of a design-of-experiment method to determine the set of suitable parameters for the SFLA. Computational results and comparisons with some typical existing algorithms demonstrate the effectiveness of the proposed SFLA.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90B50 | Management decision making, including multiple objectives |
Keywords:
resource-constrained project scheduling; shuffled frog-leaping algorithm; resource-based crossover; combined local search; speed-up evaluation; design-of-experimentSoftware:
PSPLIBReferences:
| [1] | Brucker, P.; Drexl, A.; Möhring, R.; Neumann, K.; Pesch, E., Resource-constrained project scheduling: notation, classification, models, and methods, European Journal of Operational Research, 112, 1, 3-41 (1999) · Zbl 0937.90030 |
| [2] | Hartmann S. Scheduling medical research experiments: an application of project scheduling methods. Technical Report, University Kiel, Germany; 1997.; Hartmann S. Scheduling medical research experiments: an application of project scheduling methods. Technical Report, University Kiel, Germany; 1997. |
| [3] | Alba, E.; Chicano, J. F., Software project management with GAs, Information Science, 177, 10, 2380-2401 (2007) |
| [4] | Dodin, B.; Elimam, A. A.; Rolland, E., Tabu search in audit scheduling, European Journal of Operational Research, 106, 2, 373-392 (1998) · Zbl 0991.90058 |
| [5] | Hartmann, S., Project scheduling under limited resources: models, methods, and applications (1999), Springer Press: Springer Press Berlin · Zbl 0957.90059 |
| [6] | Blazewicz, J.; Lenstra, J. K.; Rinnoy, K., Scheduling projects subject to resource constraints: classification and complexity, Discrete Applied Mathematics, 5, 1, 11-24 (1983) · Zbl 0516.68037 |
| [7] | Kolisch, R., Serial and parallel resource-constrained project scheduling methods revisited: theory and computation, European Journal of Operational Research, 90, 2, 320-333 (1996) · Zbl 0916.90151 |
| [8] | Alvarez-Valdés, R.; Tamarit, J. M., Heuristic algorithms for resource-constrained project scheduling: a review and an empirical analysis. Advances in project scheduling (1989), Elsevier Press: Elsevier Press Amsterdam, p. 134-43 |
| [9] | Davis, E. W.; Patterson, J. H., A comparison of heuristic and optimum solutions in resource-constrained project scheduling, Management Science, 21, 7, 944-955 (1975) |
| [10] | Kolisch, R., Project scheduling under resource constraints: efficient heuristics for several problem classes (1995), Springer Press: Springer Press Heidelberg |
| [11] | Kolisch, R., Efficient priority rules for the resource-constrained project scheduling problem, Journal of Operations Management, 14, 3, 179-192 (1996) |
| [12] | Shaffer, L. R.; Ritter, J. B.; Meyer, W. L., The critical-path method (1965), McGraw-Hill Press: McGraw-Hill Press New York |
| [13] | Cooper, D. F., A note on serial and parallel heuristics for resource-constrained project scheduling, Foundations of Control Engineering, 2, 4, 131-133 (1977) · Zbl 0372.90061 |
| [14] | Thomas, P. R.; Salhi, S., An investigation into the relationship of heuristic performance with network-resource characteristics, Journal of the Operational Research Society, 48, 1, 34-43 (1997) · Zbl 0881.90076 |
| [15] | Drexl, A., Scheduling of project networks by job assignment, Management Science, 37, 1590-1602 (1991) · Zbl 0729.91011 |
| [16] | Hartmann, S., A competitive genetic algorithm for resource-constrained project scheduling, Naval Research Logistics, 45, 6, 733-750 (1998) · Zbl 0936.90024 |
| [17] | Alcaraz, J.; Maroto, C., A robust genetic algorithm for resource allocation in project scheduling, Annals of Operations Research, 102, 1, 83-109 (2001) · Zbl 1024.90036 |
| [18] | Hartmann, S., A self-adapting genetic algorithm for project scheduling under resource constraints, Naval Research Logistics, 49, 5, 433-448 (2002) · Zbl 1013.90062 |
| [19] | Boctor, F. F., A new and efficient heuristic for scheduling projects with resource restrictions and multiple execution modes, European Journal of Operational Research, 90, 2, 349-361 (1996) · Zbl 0916.90143 |
| [20] | Cho, J. H.; Kim, Y. D., A simulated annealing algorithm for resource constrained project scheduling problems, Journal of the Operational Research Society, 48, 6, 736-744 (1997) · Zbl 0881.90069 |
| [21] | 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, 2, 268-281 (2003) · Zbl 1040.90015 |
| [22] | Klein, R., Project scheduling with time-varying resource constraints, International Journal of Production Research, 38, 15, 3937-3952 (2000) · Zbl 1094.90558 |
| [23] | Artigues, C.; Michelon, P.; Reusser, S., Insertion techniques for static and dynamic resource-constrained project scheduling, European Journal of Operational Research, 149, 2, 249-267 (2003) · Zbl 1040.90013 |
| [24] | Mika, M.; Waligóra, G.; Weglarz, J., Tabu search for multi- mode resource-constrained project scheduling with schedule-dependent setup time, European Journal of Operational Research, 187, 3, 1238-1250 (2008) · Zbl 1137.90508 |
| [25] | Zhang, H.; Li, X.; Li, H., Particle swarm optimization-based schemes for resource-constrained project scheduling, Automation in Construction, 14, 3, 393-404 (2005) |
| [26] | Jarboui, B.; Damak, N.; Siarry, P., A combinatorial particle swarm optimization for solving multi-mode resource-constrained project scheduling problems, Applied Mathematics Computation, 195, 1, 299-308 (2008) · Zbl 1180.90125 |
| [27] | Eusuff, M.; Lansey, K.; Pasha, F., Shuffled frog-leaping algorithm: a memetic meta-heuristic for discrete optimization, Engineering Optimization, 38, 2, 129-154 (2006) |
| [28] | Eusuff, M.; Lansey, K., Optimization of water distribution network design using the shuffled frog leaping algorithm, Journal of Water Resources Planning and Management, 129, 3, 210-225 (2003) |
| [29] | Rahimi-Vahed, A.; Mirzaei, A. H., A hybrid multi-objective shuffled frog-leaping algorithm for a mixed-model assembly line sequencing problem, Computers and Industrial Engineering, 53, 4, 642-666 (2007) |
| [30] | Rahimi-Vahed, A.; Mirzaei, A. H., Solving a bi-criteria permutation flow-shop problem using shuffled frog-leaping algorithm, Soft Computing, 12, 5, 435-452 (2008) · Zbl 1170.90397 |
| [31] | Rahimi-Vahed, A.; Dangchi, M.; Rafiei, H.; Salimi, E., A novel hybrid multi-objective shuffled frog-leaping algorithm for a bi-criteria permutation flow shop scheduling problem, International Journal of Advanced Manufacturing Technology, 41, 10, 1227-1239 (2009) |
| [32] | Chung, G.; Lansey, K. E., Application of the shuffled frog leaping algorithm for the optimization of a general large-scale water supply system, Water Resource Management, 23, 4, 797-823 (2009) |
| [33] | Kolisch, R.; Hartmann, S., Heuristic algorithms for solving the resource-constrained project scheduling problem: classification, computational, analysis, (Weglarz, J., Project scheduling: recent models, algorithms and applications (1999), Kluwer Press: Kluwer Press Berlin), 147-178 |
| [34] | Leon, V. J.; Ramamoorthy, B., Strength and adaptability of problem space based neighborhoods for resource-constrained scheduling, OR Spectrum, 17, 2-3, 173-182 (1995) · Zbl 0842.90062 |
| [35] | Debels, D.; Vanhoucke, M., A decomposition-based genetic algorithm for the resource-constrained project scheduling problem, Operations Research, 55, 3, 457-469 (2007) · Zbl 1167.90664 |
| [36] | Li, K. Y.; Willis, R. J., An iterative scheduling technique for resource constrained project scheduling, European Journal of Operational Research, 56, 3, 370-379 (1992) · Zbl 0825.90536 |
| [37] | Kolisch, R.; Sprecher, A., PSPLIB—a project scheduling problem library, European Journal of Operational Research, 96, 1, 205-216 (1997) · Zbl 0947.90587 |
| [38] | Stinson, J. P.; Davis, E. W.; Khumawala, B. M., Multiple resource-constrained scheduling using branch and bound, IIE Transactions, 10, 3, 23-40 (1978) |
| [39] | Kochetov Y, Stolyar A. Evolutionary local search with variable neighborhood for the resource constrained project scheduling problem. In: Proceedings of the 3rd International Workshop of Computer Science and Information Technologies, Russia; 2003.; Kochetov Y, Stolyar A. Evolutionary local search with variable neighborhood for the resource constrained project scheduling problem. In: Proceedings of the 3rd International Workshop of Computer Science and Information Technologies, Russia; 2003. · Zbl 1042.90022 |
| [40] | Mendes, J. J.; Goncalves, J. F.; Resende, M. G.C., A random key based genetic algorithm for the resource constrained project scheduling problem, Computers and Operations Research, 36, 1, 92-109 (2009) · Zbl 1163.90500 |
| [41] | Debels, D.; Reyck, B.; De, Leus, R.; Vanhoucke, M., A hybrid scatter-search/electromagnetism meta-heuristic for the resource-constrained project scheduling problem, European Journal of Operational Research, 169, 3, 638-653 (2006) · Zbl 1079.90051 |
| [42] | Valls, V.; Ballestin, F.; Quintanilla, S., A hybrid genetic algorithm for the resource-constrained project scheduling problem, European Journal of Operational Research, 185, 2, 495-508 (2008) · Zbl 1137.90526 |
| [43] | Alcaraz J, Maroto C, Ruiz R. Improving the performance of genetic algorithms for the RCPS problem. In: Proceedings of the 9th International Workshop on Project Management and Scheduling; 2004. p. 40-3.; Alcaraz J, Maroto C, Ruiz R. Improving the performance of genetic algorithms for the RCPS problem. In: Proceedings of the 9th International Workshop on Project Management and Scheduling; 2004. p. 40-3. |
| [44] | Nonobe, K.; Ibaraki, T., Formulation and tabu search algorithm for the resource constrained project scheduling problem (RCPSP), (Ribeiro, C. C.; Hansen, P., Essays and surveys in meta-heuristics (2002), Kluwer Press: Kluwer Press Boston), 557-588 · Zbl 1048.90116 |
| [45] | Coelho J, Tavares L. Comparative analysis of meta-heuristics for the resource constrained project scheduling problem. Technical Report, Department of Civil Engineering, Instituto Superior Tecnico; 2003.; Coelho J, Tavares L. Comparative analysis of meta-heuristics for the resource constrained project scheduling problem. Technical Report, Department of Civil Engineering, Instituto Superior Tecnico; 2003. |
| [46] | Schirmer, A., Case-based reasoning and improved adaptive search for project scheduling, Naval Research Logistics, 47, 3, 201-222 (2000) · Zbl 0956.90011 |
| [47] | Kolisch, R.; Drexl, A., Adaptive search for solving hard project scheduling problems, Naval Research Logistics, 43, 1, 23-40 (1996) · Zbl 0870.90069 |
| [48] | Agarwal, A.; Colak, S.; Erenguc, S., A neurogenetic approach for the resource-constrained project scheduling problem, Computer and Operations Research, 38, 1, 44-50 (2011) · Zbl 1231.90170 |
| [49] | Chen, W.; Shi, Y. J.; Teng, H. F.; Lan, X. P.; Hu, L. C., An efficient hybrid algorithm for resource-constrained project scheduling, Information Sciences, 180, 5, 1031-1039 (2010) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
