Abstract
The resource-constrained project scheduling problem (RCPSP) has been of a continuing interest and challenge for researchers and practitioners since its advent. The formidable computational requirements of the RCPSP have resulted in numerous attempts to develop heuristic procedures, leading to the interest in improvement heuristics. Traditionally, such heuristics constructed a schedule by the scheme of forward, backward, or bidirectional planning directions. In this paper, we introduce a hybrid-directional planning that can make all improvement heuristics (e.g., meta-heuristics) more effective in solving the RCPSP. To validate its effectiveness, the proposed scheme is incorporated into three popular meta-heuristics, including genetic algorithm, simulated annealing, and Tabu search. A comprehensive numerical investigation shows that the performance of such meta-heuristics is significantly increased by using the hybrid-directional planning, which indicates that such a hybrid planning direction will hopefully encourage researchers and practitioners to apply it to different improvement heuristics for solving the RCPSP.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Kelley JE (1963) The critical path method: resources planning and scheduling. In: Muth JF, Thompson GL (eds) Industrial scheduling. Prentice-Hall, Upper Saddle River, NJ
Blażewicz J, Lenstra J, Rinnooy KA (1983) Scheduling subject to resource constraints: Classification and complexity. Discrete Appl Math 5:11–24
Alvarez-Valdés R, Tamarit JM (1993) The project scheduling polyhedron: dimension, facets and lifting theorems. Eur J Oper Res 67:204–220
Mingozzi A, Maniezzo V, Ricciardelli S, Bianco L (1998) An exact algorithm for the resource-constrained project scheduling problem based on a new mathematical formulation. Manage Sci 44:715–729
Stinson JP, Davis EW, Khumawala BM (1978) Multiple resource-constrained scheduling using branch and bound. AIIE Trans 10:252–259
Brucker P, Knust S, Schoo A, Thiele O (1998) A branch-and-bound algorithm for the resource-constrained project scheduling problem. Eur J Oper Res 107:272–288
Hartmann S, Kolisch R (2000) Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem. Eur J Oper Res 127:394–407
Klein R (2000) Scheduling of resource-constrained projects. Kluwer, Dordrecht
Ying KC (2008) Solving non-permutation flowshop scheduling problems by an effective iterated greedy heuristic. Int J Adv Manuf Tech, DOI 10.1007/s00170-007-1104-y
Lin SW, Ying KC (2007) Solving single-machine total weighted tardiness problems with sequence-dependent setup times by meta-heuristics. Int J Adv Manuf Tech 34:1183–1190
Ying KC, Lin SW (2007) Multi-heuristic desirability ant colony system heuristic for non-permutation flowshop scheduling problems. Int J Adv Manuf Tech 33:793–802
Reddy JP, Kumanan S, Chetty OVK (2001) Application of Petri nets and a genetic algorithm to multi-mode multi-resource constrained project scheduling. Int J Adv Manuf Tech 17:305–314
Hartmann S (2002) A self-adapting genetic algorithm for project scheduling under resource constraints. Nav Res Log 49:433–448
Kumanan S, Jose GJ, Raja K (2006) Multi-project scheduling using a heuristic and a genetic algorithm. Int J Adv Manuf Tech 31:360–366
Cho J, Kim YD (1997) A simulated annealing algorithm for resource-constrained project scheduling problems. J Oper Res Soc 48:736–744
Bouleimen K, Lecocq H (2003) A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple modes version. Eur J Oper Res 149:268–281
Shukla SK, Son YJ, Tiwari MK (2008) Fuzzy-based adaptive sample-sort simulated annealing for resource-constrained project scheduling. Int J Adv Manuf Tech, DOI 10.1007/s00170-006- 0907-6
Thomas PR, Salhi S (1998) A tabu search approach for the resource constrained project scheduling problem. J Heuristics 4:123–139
Agarwal R, Tiwari MK, Mukherjee SK (2007) Artificial immune system based approach for solving resource constraint project scheduling problem. Int J Adv Manuf Tech, DOI 10.1007/s00170- 006-0631-2
Li KY, Willis RJ (1992) An iterative scheduling technique for resource-constrained project scheduling. Eur J Oper Res 56:370–379
Klein R (2000) Bidirectional planning: improving priority rule-based heuristics for scheduling resource-constrained projects. Eur J Oper Res 127:619–638
Holland JH (1975) Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor
David L (1985) Applying adaptive algorithms to epistatic domains. Proceedings of the 9th International Joint Conference on Artificial Intelligence. IEEE Computer Society Press, Los Angeles, California
Metropolis N, Rosenbluth AW, Rosenbluth MN, Teller AH, Teller E (1953) Equations of state calculations by fast computing machines. J Chem Phys 21:1087–1092
Kirkpatrick S, Gelatt CD Jr, Vecchi MP (1983) Optimization by simulated annealing. Science 220:671–680
Glover F (1989) Tabu search-Part I. ORSA J Comput 1:190–206
Glover F (1990) Tabu search-Part II. ORSA J Comput 2:4–32
Glover F, Laguna M (1997) Tabu search. Kluwer, Dordrecht
Kolisch R, Sprecher A (1996) PSLIB - A project scheduling problem library. Eur J Oper Res 96:205–216
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Ying, KC., Lin, SW. & Lee, ZJ. Hybrid-directional planning: improving improvement heuristics for scheduling resource-constrained projects. Int J Adv Manuf Technol 41, 358–366 (2009). https://doi.org/10.1007/s00170-008-1486-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-008-1486-5