Particle Swarm Optimization for Preemptive Scheduling under Break and Resource-Constraints
Publication: Journal of Construction Engineering and Management
Volume 132, Issue 3
Abstract
This paper introduces a particle swarm optimization (PSO)-based methodology to implement preemptive scheduling under break and resource-constraints (PSBRC) for construction projects. The PSBRC under study allows the preemptive activities to be interrupted in off-working time and not to resume immediately in the next working period because all the limited resources are to be reallocated during a break. The potential solution to the PSBRC, i.e., a set of priorities deciding the order to start the activities or restart the interrupted activities, is represented by the multidimensional particle position. Hence PSO is applied to search for the optimal schedule for the PSBRC, in which a parallel scheme is adopted to transform the particle-represented priorities to a schedule. Computational analyses are presented to verify the effectiveness of the proposed methodology. This paper provides an attempt to make use of preemption and break for the resource-constrained construction project with the objective of minimizing project duration.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgment
The work described in this article was fully supported by a grant from the Research Grants Office of City University of Hong Kong (Project No. City U 7200036.)
References
Baker, E. (1983). “An exact algorithm for the time-constrained traveling salesmen problem.” Oper. Res., 31, 938–945.
Bean, J. (1994). “Genetic algorithms and random keys for sequencing and optimization.” Oper. Res. Soc. Am., 6(2), 154–160.
Boctor, F. F. (1990). “Some efficient multi-heuristic procedures for resource-constrained project scheduling.” Eur. J. Oper. Res., 49, 3–13.
Brucker, P., Heitmann, S., and Hurink, J. (2003). “How useful are preemptive schedules?” Oper. Res. Lett., 31, 129–136.
Chan, W. T., Chua, D. K. H., and Kannan, G. (1996). “Construction resource scheduling with genetic algorithms.” J. Constr. Eng. Manage., 122(2), 125–132.
Chan, W. T., and Hao, H. (2002). “Production scheduling for precast plants using a flow shop sequencing model.” J. Comput. Civ. Eng., 16(3), 165–174.
Christofides, N., Mingozzi, A., and Toth, P. (1981). “State space relaxation procedures for the computation of bounds to routing problems.” Networks, 11, 145–164.
Clerc, M., and Kennedy, J. (2002). “The particle swarm-explosion, stability, and convergence in a multidimensional complex space.” IEEE Trans. Evol. Comput., 6(1), 58–73.
Demeulemeester, E. L., and Herroelen, W. S. (1996).“An efficient optimal solution procedure for the preemptive resource-constrained project scheduling problem.” Eur. J. Oper. Res., 90, 334–348.
Dumas, Y., Desrosiers, J., and Soumis, F. (1991). “The pickup and delivery problem with time windows.” Eur. J. Oper. Res., 54, 7–22.
Eberhart, R. C., and Shi, Y. (1998). “Comparison between genetic algorithms and particle swarm optimization.” Evolutionary Programming VII: Proc., Seventh Annual Conf. on Evolutionary Programming, San Diego, Calif., 611–616.
Eberhart, R. C., and Shi, Y. (2001). “Tracking and optimizing dynamic systems with particle swarms.” Proc., IEEE Congress on Evolutionary Computation (CEC 2001), Seoul, Korea, 94–97.
Fisher, M., and Jaikumar, R. (1981). “A generalized assignment heuristic for vehicle routing.” Networks, 11, 109–124.
Gavish, B., and Pirkul, H. (1991). “Algorithms for multi-resource generalized assignment problem.” Manage. Sci., 37(6), 695–713.
Gupta, C. G., Gupta, Y. P., and Kumar, A. (1993). “Minimizing flow time variance in a single system using genetic algorithm.” Eur. J. Oper. Res., 70, 289–303.
Hartmann, S. (1998). “A competitive genetic algorithm for resource-constrained project scheduling.” Naval Res. Logistics Quart., 45, 733–750.
Kennedy, J., and Eberhart, R. C. (1995). “Particle swarm optimization.” Proc., IEEE Conf. on Neural Networks, IV, Piscataway, N.J., 1942–1948.
Kennedy, J., Eberhart, R. C., and Shi, Y. (2001). Swarm intelligence, Morgan Kaufmann, San Francisco, Calif.
Kolisch, R. (1996). “Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation.” Eur. J. Oper. Res., 90, 320–333.
Lawler, E. L. (1982). “Preemptive scheduling of precedence-constrained jobs on parallel machines.” Deterministic and stochastic scheduling, M. A. H. Dempster, J. K. Lenstra and A. H. G. Rinnooy Kan, eds., Reidel, Dordrecht, 101–123.
Lee, J. K., and Kim, Y. D. (1996). “Search heuristics for resource constrained project scheduling.” J. Oper. Res. Soc., 47(5), 678–689.
Leu, S. S., and Yang, C. H. (1999). “GA-based multicriteria optimal model for construction scheduling.” J. Constr. Eng. Manage., 125(6), 420–427.
Padilla, E. M., and Carr, R. I. (1991). “Resource strategies for dynamic project management.” J. Constr. Eng. Manage., 117(2), 279–293.
Shi, Y., and Eberhart, R. C. (1998). “Parameter selection in particle swarm optimization.” Evolutionary Programming VII: Proc., Seventh Annual Conf. on Evolutionary Programming, Springer, New York, 591–600.
Solman, M. M. (1987). “Algorithms for the vehicle routing and scheduling problems with time window constraints.” Oper. Res., 35, 254–265.
Stinson, J. P. (1976). “A branch and bound algorithm for a general class resource-constrained scheduling problem.” PhD thesis, Univ. of North Carolina at Chapel Hill, Chapel Hill, N.C.
Talbot, F. B. (1982). “Resource-constrained project scheduling with time-resource tradeoffs: The nonpreemptive case.” Manage. Sci., 28(10), 1197–1210.
Trelea, I. C. (2003). “The particle swarm optimization algorithm: Convergence analysis and parameter selection.” Inf. Process. Lett., 85(6), 317–325.
Yang, H. H., and Chen, Y. L. (2000). “Finding the critical path in an activity network with time-switch constraints.” Eur. J. Oper. Res., 120, 603–613.
Young, S. Y. (2002). “Genetic algorithm with fuzzy logic controller for preemptive and non-preemptive job-shop scheduling problems.” Comput. Ind. Eng., 43, 623–644.
Information & Authors
Information
Published In
Journal of Construction Engineering and Management
Volume 132 • Issue 3 • March 2006
Pages: 259 - 267
Copyright
© 2006 ASCE.
History
Received: Oct 6, 2004
Accepted: Jul 1, 2005
Published online: Mar 1, 2006
Published in print: Mar 2006
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.