Journal of Computers, Vol 6, No 11 (2011), 2365-2375, Nov 2011
doi:10.4304/jcp.6.11.2365-2375

A Serial Insertion Schedule Generation Scheme for Resource-constrained Project Scheduling

Chunfeng Liu, Shanlin Yang

Abstract


When dealing with resource-constrained project scheduling problem (RCPSP), the classical serial and parallel schedule generation schemes (SGSs) are often used as core components by heuristics. In this paper, a new serial insertion SGS for the RCPSP is proposed. The new SGS differs from the classical ones in the fact that it allows to insert an unscheduled activity inside the optimal insertion position at each iteration of serial scheduling, which can eventually leads to a compact project schedule. Computational experiments are conducted to show that the new polynomial-time scheme is effective in reducing project makespan and efficient in shortening runtime compared to another insertion SGS.


Keywords


resource-constrained project scheduling; schedule generation scheme; activity insertion; computational evaluation

References


[1] J. Blazewicz, J. K. Lenstra, and A. H. G. R. Kan, “Scheduling subject to resource-constraints: Classification and complexity,” Discrete Applied Mathematics, vol. 5, pp. 11–24, 1983.
http://dx.doi.org/10.1016/0166-218X(83)90012-4

[2] N. Xu, S. A. McKee, L. K. Nozick, and R. Ufomata, “Augmenting priority rule heuristics with justification and rollout to solve the resource-constrained project scheduling problem,” Computers & Operations Research, vol. 35, pp. 3284–3297, 2008.
http://dx.doi.org/10.1016/j.cor.2007.02.016

[3] K. C. Ying, S. W. Lin, and Z. J. Lee, “Hybrid-directional planning: Improving improvement heuristics for scheduling resource-constrained projects,” International Journal of Advanced Manufacturing Technology, vol. 41, pp. 358–366, 2009.
http://dx.doi.org/10.1007/s00170-008-1486-5

[4] K. Moumene and J. A. Ferland, “Activity list representation for a generalization of the resource-constrained project scheduling problem,” European Journal of Operational Research, vol. 199, pp. 46–54, 2009.
http://dx.doi.org/10.1016/j.ejor.2008.10.030

[5] L. Deng, Y. Lin, and M. Chen, “Hybrid ant colony optimization for the resource-constrained project scheduling problem,” Journal of Systems Engineering and Electronics, vol. 21, pp. 67–71, 2010.

[6] R. Kolisch and S. Hartmann, “Experimental investigation of heuristics for resource-constrained project scheduling: An update,” European Journal of Operational Research, vol. 174, pp. 23–37, 2006.
http://dx.doi.org/10.1016/j.ejor.2005.01.065

[7] A. Sprecher, R. Kolisch, and A. Drexl, “Semi-active, active and non-delay schedules for the resource-constrained project scheduling problem,” European Journal of Operational Research, vol. 80, pp. 94–102, 1995.
http://dx.doi.org/10.1016/0377-2217(93)E0294-8

[8] S. Hartmann and R. Kolisch, “Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem,” European Journal of Operational Research, vol. 127, pp. 394–407, 2000.
http://dx.doi.org/10.1016/S0377-2217(99)00485-3

[9] R. Kolisch, “Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation,” European Journal of Operational Research, vol. 90, pp. 320–333, 1996.
http://dx.doi.org/10.1016/0377-2217(95)00357-6

[10] S. Hartmann, “A self-adapting genetic algorithm for project scheduling under resource constraints,” Naval Research Logistics, vol. 49, pp. 433–448, 2002.
http://dx.doi.org/10.1002/nav.10029

[11] T. Baar, P. Brucker, and S. Knust, “Tabu-search algorithms and lower bounds for the resource-constrained project scheduling problem,” in Meta-heuristics: Advances and Trends in Local Search Paradigms for Optimization, S. Voss, S. Martello, I. Osman, and C. Roucairol, Eds. Kluwer Academic Publishers, 1999, pp. 1–8.
http://dx.doi.org/10.1007/978-1-4615-5775-3_1

[12] F. F. Boctor, “An adaptation of the simulated annealing algorithm for solving resource-constrained project scheduling problems,” International Journal of Production Research, vol. 34, pp. 2335–2351, 1996.
http://dx.doi.org/10.1080/00207549608905028

[13] K. Bouleimen and H. Lecocq, “A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version,” European Journal of Operational Research, vol. 149, pp. 268–281, 2003.
http://dx.doi.org/10.1016/S0377-2217(02)00761-0

[14] S. Hartmann, “A competitive genetic algorithm for resource-constrained project scheduling,” Naval Research Logistics, vol. 45, pp. 733–750, 1998.
http://dx.doi.org/10.1002/(SICI)1520-6750(199810)45:7<733::AID-NAV5>3.0.CO;2-C

[15] E. Pinson, C. Prins, and F. Rullier, “Using tabu search for solving the resource-constrained project scheduling problem,” in Proc. of the fourth international workshop on project management and scheduling, Leuven, Belgium, 1994, pp. 102–106.

[16] J. L. Kim and R. D. Ellis, “Comparing schedule generation schemes in resource-constrained project scheduling using elitist genetic algorithm,” Journal of Construction Engineering and Management, vol. 136, pp. 160–169, 2010.
http://dx.doi.org/10.1061/(ASCE)0733-9364(2010)136:2(160)

[17] P. Brucker, A. Drexl, R. Möhring, K. Neumann, and E. Pesch, “Resource-constrained project scheduling: Notation, classification, models and methods,” European Journal of Operational Research, vol. 112, pp. 3–41, 1999.
http://dx.doi.org/10.1016/S0377-2217(98)00204-5

[18] A. A. B. Pritsker, L. J. Watters, and P. M. Wolfe, “Multiproject scheduling with limited resources: A zero-one programming approach,” Management Science, vol. 16, pp. 93–108, 1969.
http://dx.doi.org/10.1287/mnsc.16.1.93

[19] C. Artigues, P. Michelon, and S. Reusser, “Insertion techniques for static and dynamic resource-constrained project scheduling,” European Journal of Operational Research, vol. 149, pp. 249–267, 2003.
http://dx.doi.org/10.1016/S0377-2217(02)00758-0

[20] C. Artigues and F. Roubellat, “A polynomial activity insertion algorithm in a multi-resource schedule with cumulative constraints and multiple mode,” European Journal of Operational Research, vol. 127, pp. 297–316, 2000.
http://dx.doi.org/10.1016/S0377-2217(99)00496-8

[21] R. Kolisch, A. Sprecher, and A. Drexl, “Characterization and generation of a general class of resource constrained project scheduling problems,” Management Science, vol. 41, pp. 1693–1703, 1995.
http://dx.doi.org/10.1287/mnsc.41.10.1693

[22] R. Kolisch and A. Sprecher, “PSPLIB — a project scheduling problem library,” European Journal of Operational Research, vol. 96, pp. 205–216, 1996.
http://dx.doi.org/10.1016/S0377-2217(96)00170-1

[23] C. Briand, “A new any-order schedule generation scheme for resource-constrained project scheduling,” RAIRO Operations Research, vol. 43, pp. 297–308, 2009.
http://dx.doi.org/10.1051/ro/2009017

[24] R. Kolisch, “Efficient priority rules for the resourceconstrained project scheduling problem,” Journal of Operations Management, vol. 14, pp. 179–192, 1996.
http://dx.doi.org/10.1016/0272-6963(95)00032-1

[25] R. Klein and A. Scholl, “Computing lower bounds by destructive improvement: An application to resource constrained project scheduling,” European Journal of Operational Research, vol. 112, pp. 322–346, 1999.
http://dx.doi.org/10.1016/S0377-2217(97)00442-6


Full Text: PDF


Journal of Computers (JCP, ISSN 1796-203X)

Copyright @ 2006-2012 by ACADEMY PUBLISHER – All rights reserved.