×

A modified PSO algorithm for minimizing the total costs of resources in MRCPSP. (English) Zbl 1264.90092

Summary: We introduce a multimode resource-constrained project scheduling problem with finish-to-start precedence relations among project activities, considering renewable and nonrenewable resource costs. We assume that renewable resources are rented and are not available in all periods of time of the project. In other words, there is a mandated ready date as well as a due date for each renewable resource type so that no resource is used before its ready date. However, the resources are permitted to be used after their due dates by paying penalty costs. The objective is to minimize the total costs of both renewable and nonrenewable resource usage. This problem is called multimode resource-constrained project scheduling problem with minimization of total weighted resource tardiness penalty cost (MRCPSP-TWRTPC), where, for each activity, both renewable and nonrenewable resource requirements depend on activity mode. For this problem, we present a metaheuristic algorithm based on a modified Particle Swarm Optimization (PSO) approach introduced by Tchomté and Gourgand which uses a modified rule for the displacement of particles. We present a prioritization rule for activities and several improvement and local search methods. Experimental results reveal the effectiveness and efficiency of the proposed algorithm for the problem in question.

MSC:

90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
90C11 Mixed integer programming

Software:

Tabu search; PSPLIB
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] E. Demeulemeester and W. S. Herroelen, Project Scheduling, A Research Handbook, Kluwer Academic, Dordrecht, The Netherlands, 2001. · Zbl 1059.90068
[2] M. Ranjbar, M. Khalilzadeh, F. Kianfar, and K. Etminani, “An optimal procedure for minimizing total weighted resource tardiness penalty costs in the resource-constrained project scheduling problem,” Computers and Industrial Engineering, vol. 62, no. 1, pp. 264-270, 2012. · doi:10.1016/j.cie.2011.09.013
[3] R. Heilmann, “A branch-and-bound procedure for the multi-mode resource-constrained project scheduling problem with minimum and maximum time lags,” European Journal of Operational Research, vol. 144, no. 2, pp. 348-365, 2003. · Zbl 1012.90513 · doi:10.1016/S0377-2217(02)00136-4
[4] G. Zhu, J. F. Bard, and G. Yu, “A branch-and-cut procedure for the multimode resource-constrained project-scheduling problem,” INFORMS Journal on Computing, vol. 18, no. 3, pp. 377-390, 2006. · Zbl 1241.90168 · doi:10.1287/ijoc.1040.0121
[5] H. Zhang, C. M. Tam, and H. Li, “Multimode project scheduling based on particle swarm optimization,” Computer-Aided Civil and Infrastructure Engineering, vol. 21, no. 2, pp. 93-103, 2006. · doi:10.1111/j.1467-8667.2005.00420.x
[6] A. Lova, P. Tormos, and F. Barber, “Multi-mode resource constrained project scheduling: scheduling schemes, priority rules and mode selection rules,” Inteligencia Artificial, vol. 10, no. 30, pp. 69-86, 2006.
[7] A. Lova, P. Tormos, M. Cervantes, and F. Barber, “An efficient hybrid genetic algorithm for scheduling projects with resource constraints and multiple execution modes,” International Journal of Production Economics, vol. 117, no. 2, pp. 302-316, 2009. · doi:10.1016/j.ijpe.2008.11.002
[8] B. Jarboui, N. Damak, P. Siarry, and A. Rebai, “A combinatorial particle swarm optimization for solving multi-mode resource-constrained project scheduling problems,” Applied Mathematics and Computation, vol. 195, no. 1, pp. 299-308, 2008. · Zbl 1180.90125 · doi:10.1016/j.amc.2007.04.096
[9] M. Ranjbar, B. De Reyck, and F. Kianfar, “A hybrid scatter search for the discrete time/resource trade-off problem in project scheduling,” European Journal of Operational Research, vol. 193, no. 1, pp. 35-48, 2009. · Zbl 1152.90464 · doi:10.1016/j.ejor.2007.10.042
[10] V. Van Peteghem and M. Vanhoucke, “A genetic algorithm for the preemptive and non-preemptive multi-mode resource-constrained project scheduling problem,” European Journal of Operational Research, vol. 201, no. 2, pp. 409-418, 2010. · Zbl 1175.90205 · doi:10.1016/j.ejor.2009.03.034
[11] F. S. Kazemi and R. Tavakkoli-Moghaddam, “Solving a multi-objective multi-mode resource-constrained project scheduling problem with particle swarm optimization,” International Journal of Academic Research, vol. 3, no. 1, pp. 103-110, 2011.
[12] J. Bła\Dzewicz, J. K. Lenstra, and A. H. G. Rinnooy Kan, “Scheduling subject to resource constraints: classification and complexity,” Discrete Applied Mathematics, vol. 5, no. 1, pp. 11-24, 1983. · Zbl 0516.68037 · doi:10.1016/0166-218X(83)90012-4
[13] P. Brucker, A. Drexel, R. Mohring, K. Neumann, and E. Pesch, “Resource-constrained project scheduling: notation, classification, models and methods,” European Journal of Operational Research, vol. 113, pp. 3-41, 1999. · Zbl 0937.90030 · doi:10.1016/S0377-2217(98)00204-5
[14] S. K. Tchomté and M. Gourgand, “Particle swarm optimization: a study of particle displacement for solving continuous and combinatorial optimization problems,” International Journal of Production Economics, vol. 121, no. 1, pp. 57-67, 2009. · doi:10.1016/j.ijpe.2008.03.015
[15] J. Kennedy and R. Eberhart, “Particle swarm optimization,” in Proceedings of the IEEE International Conference on Neural Networks, pp. 1942-1948, Piscataway, NJ, USA, December 1995.
[16] Y. Shi and R. Eberhart, “Modified particle swarm optimizer,” in Proceedings of the IEEE International Conference on Evolutionary Computation (ICEC ’98), pp. 69-73, Piscataway, NJ, USA, May 1998.
[17] Y. Shi and R. Eberhart, “Parameter selection in particle swarm optimization,” in Annual Conference Evolutionary Programming, San Diego, Calif, USA, 1998.
[18] C. Y. Tsai and S. W. Yeh, “A multiple objective particle swarm optimization approach for inventory classification,” International Journal of Production Economics, vol. 114, no. 2, pp. 656-666, 2008. · doi:10.1016/j.ijpe.2008.02.017
[19] S. Liu, J. Tang, and J. Song, “Order-planning model and algorithm for manufacturing steel sheets,” International Journal of Production Economics, vol. 100, no. 1, pp. 30-43, 2006. · doi:10.1016/j.ijpe.2004.10.002
[20] Y. Shi and R. Eberhart, “Empirical study of particle swarm optimization,” in Proceedings of the IEEE Congress on Evolutionary Computation, pp. 945-1950, Piscataway, NJ, USA, 1999.
[21] M. Clerc, “Discrete particle swarm optimization,” in New Optimization Techniques in Engineering, G. C. Onwubolu and B. V. Babu, Eds., pp. 204-219, Springer, Berlin, Germany, 2004. · Zbl 1139.90415
[22] Kennedy and R. C. Eberhart, “Discrete binary version of the particle swarm algorithm,” in Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, vol. 5, pp. 4104-4108, IEEE Computer Society, Washington, DC, USA, 1997.
[23] F. Glover and M. Laguna, “Tabu search,” in Handbook of Combinatorial Optimization, D.-Z. Du and P. M. Pardalos, Eds., vol. 3, pp. 621-757, Kluwer Academic, Boston, Mass, USA, 1998. · Zbl 0991.90091 · doi:10.1016/S0377-2217(97)00295-6
[24] A. Sprecher, S. Hartmann, and A. Drexl, “An exact algorithm for project scheduling with multiple modes,” OR Spektrum, vol. 19, no. 3, pp. 195-203, 1997. · Zbl 0885.90059 · doi:10.1007/BF01545587
[25] S. Hartmann and D. Briskorn, “A survey of variants and extensions of the resource-constrained project scheduling problem,” European Journal of Operational Research, vol. 207, no. 1, pp. 1-14, 2010. · Zbl 1205.90123 · doi:10.1016/j.ejor.2009.11.005
[26] R. M. Chen, C. L. Wu, C. M. Wang, and S. T. Lo, “Using novel particle swarm optimization scheme to solve resource-constrained scheduling problem in PSPLIB,” Expert Systems with Applications, vol. 37, no. 3, pp. 1899-1910, 2010. · doi:10.1016/j.eswa.2009.07.024
[27] R. Kolisch and A. Sprecher, “PSPLIB-a project scheduling problem library,” European Journal of Operational Research, vol. 96, no. 1, pp. 205-216, 1997. · Zbl 0947.90587 · doi:10.1016/S0377-2217(96)00170-1
[28] 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. 693-1703, 1995. · Zbl 0870.90070 · doi:10.1287/mnsc.41.10.1693
[29] M. Khalilzadeh, F. Kianfar, and M. Ranjbar, “A Scatter Search Algorithm for RCPSP with discounted weighted earliness-tardiness costs,” Life Science Journal, vol. 8, no. 2, pp. 634-640, 2011.
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.