Top

Journal of Scheduling

Published in:

01-06-2015

Schedule generation scheme for solving multi-mode resource availability cost problem by modified particle swarm optimization

Authors: Jian-Jun Qi, Ya-Jie Liu, Ping Jiang, Bo Guo

Published in: Journal of Scheduling | Issue 3/2015

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The resource availability cost problem (RACP) (Möhring, Operations Research, 32:89–120, 1984) is commonly encountered in project scheduling. RACP aims to minimize the resource availability cost of a project by a given project deadline. In this study, RACP is extended from a single mode to a multi-mode called multi-mode RACP (MMRACP), which is more complicated than RACP but more convenient in practice. To solve MMRACP efficiently, forward activity list (FAL), a schedule generation scheme, is proposed. Heuristic algorithms are designed according to the characteristics of FAL to repair infeasible solutions and to improve the fitness of the solution. Modified particle swarm optimization (MPSO), which combines the advantages of particle swarm optimization and scatter search, is proposed to make the search for the best solution efficient. Computational experiments involving 180 instances are performed to validate the performance of the proposed algorithm. The results reveal that MPSO using FAL is a very effective method to solve MMRACP.

previous article The impact of core precedences in a cyclic RCPSP with precedence delays

next article A note on -hardness of preemptive mean flow-time scheduling for parallel machines

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Alfandari, L., Plateau, A., & Tolla, P. (2001). A two-phase path-relinking algorithm for the generalized assignment problem. Proceedings of the Fourth Metaheuristics International Conference, Porto.

Alvarez, A. M., González-Velarde, J. L., & De-Alba, K. (2005). GRASP embedded scatter search for the multicommodity capacitated network design problem. Journal of Heuristics, 11(3), 233–257.CrossRef

Barrios, A., Ballestín, F., & Valls, V. (2011). A double genetic algorithm for the MRCPSP/max. Computers & Operations Research, 38(1), 33–43.CrossRef

Chen, T., Zhang, B., Hao, X., & Dai, Y. (2006, July). Task scheduling in grid based on particle swarm optimization. Fifth IEEE International Symposium on Parallel and Distributed Computing, ISPDC’06 (pp. 238–245).

Chen, R. M., Wu, C. L., Wang, C. M., & Lo, S. T. (2010). Using novel particle swarm optimization scheme to solve resource-constrained scheduling problem in PSPLIB. Expert Systems with Applications, 37(3), 1899–1910.CrossRef

Clerc, M., & Kennedy, J. (2002). The particle swarm-explosion, stability, and convergence in a multidimensional complex space. IEEE Transactions on Evolutionary Computation, 6(1), 58–73.CrossRef

Damak, N., Jarboui, B., Siarry, P., & Loukil, T. (2009). Differential evolution for solving multi-mode resource-constrained project scheduling problems. Computers & Operations Research, 36(9), 2653–2659.CrossRef

Deblaere, F., Demeulemeester, E., & Herroelen, W. (2011). Reactive scheduling in the multi-mode RCPSP. Computers & Operations Research, 38(1), 63–74.CrossRef

Glover, F. (1977). Heuristics for integer programming using surrogate constraints. Decision Sciences, 8(1), 156–166.CrossRef

Glover, F. (1998). A template for scatter search and path relinking. In J.-K. Hao (Ed.), Artificial evolution (pp. 1–51). Berlin: Springer.CrossRef

Goldberg, D. E., & Holland, J. H. (1988). Genetic algorithms and machine learning. Machine Learning, 3(2), 95–99.CrossRef

Kennedy, J., & Eberhart, R. C. (1995). Particle swarm optimization. Proceedings of IEEE international conference on neural networks, 4, 1942–1948.CrossRef

Khorasani, J. (2012). A new heuristic approach for unit commitment problem using particle swarm optimization. Arabian Journal for Science and Engineering, 37(4), 1033–1042.CrossRef

Kolisch, R., & Sprecher, A. (1997). PSPLIB-a project scheduling problem library: OR software-ORSEP operations research software exchange program. European Journal of Operational Research, 96(1), 205–216.CrossRef

Laguna, M., & Martín, R. (2003). Scatter search: methodology and implementations in C. Kluwer: Springer.CrossRef

Lambrechts, O., Demeulemeester, E., & Herroelen, W. (2008). A tabu search procedure for developing robust predictive project schedules. International Journal of Production Economics, 111(2), 493–508.CrossRef

Liu, Y. H. (2006). A scatter search based approach with approximate evaluation for the heterogeneous probabilistic traveling salesman problem. IEEE Congress on InEvolutionary Computation, CEC 2006 (pp. 1603–1609).

López, F. C. G., Torres, M. G., Pérez, J. A. M., & Vega, J. M. M. (2004). Scatter search for the feature selection problem. In R. Conejo (Ed.), Current topics in artificial intelligence (pp. 517–525). Berlin: Springer.CrossRef

Lova, A., Tormos, P., Cervantes, M., & Barber, F. (2009). An efficient hybrid genetic algorithm for scheduling projects with resource constraints and multiple execution modes. International Journal of Production Economics, 117(2), 302–316.CrossRef

Luo, X., Wang, D., Tang, J., & Tu, Y. (2006). An improved PSO algorithm for resource-constrained project scheduling problem, intelligent control and automation, 2006. The Sixth World Congress on WCICA, 2006(1), 3514–3518.

Maghsoudi, M. J., Ibrahim, Z., Buyamin, S., & Rahmat, M. F. A. (2012). Data clustering for the DNA computing readout method implemented on LightCycler and based on particle swarm optimization. Arabian Journal for Science and Engineering, 37(3), 697–707.CrossRef

Möhring, R. H. (1984). Minimizing costs of resource requirements in project networks subject to a fixed completion time. Operations Research, 32(1), 89–120.CrossRef

Neumann, K., Nübel, H., & Schwindt, C. (2000). Active and stable project scheduling. Mathematical Methods of Operations Research, 52(3), 441–465.

Orosz, J. E., & Jacobson, S. H. (2002). Analysis of static simulated annealing algorithms. Journal of Optimization theory and Applications, 115(1), 165–182.CrossRef

Ozdamar, L. (1999). A genetic algorithm approach to a general category project scheduling problem. IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, 29(1), 44–59.CrossRef

Pardalos, P. M., & Resende, M. G. (Eds.). (2002). Handbook of applied optimization. Oxford: Oxford University Press.

Parsopoulos, K. E., & Vrahatis, M. N. (2004). On the computation of all global minimizers through particle swarm optimization. IEEE Transactions on Evolutionary Computation, 8(3), 211–224.CrossRef

Van Peteghem, V., & Vanhoucke, M. (2010). A genetic algorithm for the preemptive and non-preemptive multi-mode resource-constrained project scheduling problem. European Journal of Operational Research, 201(2), 409–418.CrossRef

Ranjbar, M., Kianfar, F., & Shadrokh, S. (2008). Solving the resource availability cost problem in project scheduling by path relinking and genetic algorithm. Applied Mathematics and Computation, 196(2), 879–888.CrossRef

Rodrigues, S. B., & Yamashita, D. S. (2010). An exact algorithm for minimizing resource availability costs in project scheduling. European Journal of Operational Research, 206(3), 562–568.CrossRef

Russell, R. A., & Chiang, W. C. (2006). Scatter search for the vehicle routing problem with time windows. European Journal of Operational Research, 169(2), 606–622.CrossRef

Santana-Quintero, L. V., Ramírez, N., & Coello, C. C. (2006). A multi-objective particle swarm optimizer hybridized with scatter search. In A. Gelbukh & C. A. Reyes-Garcia (Eds.), MICAI 2006: advances in artificial intelligence (pp. 294–304). Berlin: Springer.CrossRef

Shadrokh, S., & Kianfar, F. (2007). A genetic algorithm for resource investment project scheduling problem, tardiness permitted with penalty. European Journal of Operational Research, 181(1), 86–101.CrossRef

Shou, Y.-Y. (2010). Resource-constrained multi-project scheduling models and methods. Hangzhou: Zhejiang University Press.

Speranza, M. G., & Vercellis, C. (1993). Hierarchical models for multi-project planning and scheduling. European Journal of Operational Research, 64(2), 312–325.CrossRef

Sprecher, A., Hartmann, S., & Drexl, A. (1997). An exact algorithm for project scheduling with multiple modes. Operations-Research-Spektrum, 19(3), 195–203.

Thomas, P. R., & Salhi, S. (1998). A tabu search approach for the resource constrained project scheduling problem. Journal of Heuristics, 4(2), 123–139.CrossRef

Toklu, Y. C. (2002). Application of genetic algorithms to construction scheduling with or without resource constraints. Canadian Journal of Civil Engineering, 29(3), 421–429.CrossRef

Triki, E., Collette, Y., & Siarry, P. (2005). A theoretical study on the behavior of simulated annealing leading to a new cooling schedule. European Journal of Operational Research, 166(1), 77–92.CrossRef

Valls, V., Laguna, M., Lino, P., Pérez, A., & Quintanilla, S. (1999). Project scheduling with stochastic activity interruptions. In J. Wȩglarz (Ed.), Project scheduling (pp. 333–353). Kluwer: Springer.CrossRef

Yamashita, D. S., Armentano, V. A., & Laguna, M. (2006). Scatter search for project scheduling with resource availability cost. European Journal of Operational Research, 169(2), 623–637.CrossRef

Zhang, C., Sun, J., Zhu, X., & Yang, Q. (2008). An improved particle swarm optimization algorithm for flowshop scheduling problem. Information Processing Letters, 108(4), 204–209.CrossRef

Title: Schedule generation scheme for solving multi-mode resource availability cost problem by modified particle swarm optimization
Authors: Jian-Jun Qi
Ya-Jie Liu
Ping Jiang
Bo Guo
Publication date: 01-06-2015
Publisher: Springer US
Published in: Journal of Scheduling / Issue 3/2015
Print ISSN: 1094-6136
Electronic ISSN: 1099-1425
DOI: https://doi.org/10.1007/s10951-014-0374-0

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 3/2015

Energetic reasoning for energy-constrained scheduling with a continuous resource

The impact of core precedences in a cyclic RCPSP with precedence delays

A note on the preemptive scheduling to minimize total completion time with release time and deadline constraints

A note on the Coffman–Sethi bound for LPT scheduling

Erratum to: Flow shops with WIP and value added costs

Erratum to: A survey on offline scheduling with rejection