A combinatorial particle swarm optimization for solving multi-mode resource-constrained project scheduling problems. (English) Zbl 1180.90125

Summary: The particle swarm optimization (PSO) has been widely used to solve continuous problems. The discrete problems have just begun to be also solved by the discrete PSO. However, the combinatorial problems remain a prohibitive area to the PSO mainly in case of integer values.
In this paper, we propose a combinatorial PSO (CPSO) algorithm that we take up challenge to use in order to solve a multi-mode resource-constrained project scheduling problem (MRCPSP). The results that have been obtained using a standard set of instances, after extensive experiments, prove to be very competitive in terms of number of problems solved to optimality. By comparing average deviations and percentages of optima found, our CPSO algorithm outperforms the simulated annealing algorithm and it is close to the PSO algorithm.


90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
90C27 Combinatorial optimization


local search
Full Text: DOI


[1] Elmaghraby, S.E., Activity networks: project planning and control by network models, (1977), Wiley New York · Zbl 0385.90076
[2] Sprecher, A., ()
[3] Sprecher, A.; Drexl, A., Multi-mode resource-constrained project scheduling by a simple, general and powerful sequencing algorithm, European journal of operational research, 107, 431-450, (1998) · Zbl 0943.90042
[4] Drexl, A.; Grünewald, J., Nonpreemptive multi-mode resource-constrained project scheduling, IIE transactions, 25, 74-81, (1993)
[5] Slowinski, R.; Soniewicki, B.; Weglarz, J., DSS for multiobjective project scheduling subject to multiple-category resource constraints, European journal of operational research, 79, 220-229, (1994) · Zbl 0815.90099
[6] Kolisch, R.; Drexl, A., Local search for non-preemptive multi-mode resource-constrained project scheduling, IIE transactions, 29, 987-999, (1997)
[7] Özdamar, L., A genetic algorithm approach to a general category project scheduling problem, IEEE transactions on systems, man, and cybernetics, part C: applications and reviews, 29, 44-59, (1999)
[8] Bouleimen, K.; Lecocq, H., A new efficient simulated annealing algorithm for the resource constrained project scheduling problem, (), 19-22 · Zbl 1040.90015
[9] Hartmann, S.; Drexl, A., Project scheduling with multiple modes: a comparison of exact algorithms, Networks, 32, 283-297, (1998) · Zbl 1002.90025
[10] Boctor, F.F., Heuristics for scheduling projects with resource restrictions and several resource duration modes, International journal of production research, 31, 2547-2558, (1993)
[11] Boctor, F.F., A new and efficient heuristic for scheduling projects with resource restrictions and multiple execution modes, European journal of operational research, 90, 349-361, (1996) · Zbl 0916.90143
[12] M.F. Tasgetiren, Y.C. Liang, M. Sevkli, G. Gencyilmaz, Particle swarm optimization algorithm for makespan and maximum lateness minimization in permutation flowshop sequencing problem. In: Proceedings of the Fourth International Symposium on Intelligent Manufacturing Systems, Turkey, Sakarya, 2004, pp. 431-441. · Zbl 1110.90044
[13] Tasgetiren, MF.; Liang, YC.; Sevkli, M.; Gencyilmaz, G., Particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem, European journal of operational research, 177, 3, 1930-1947, (2007) · Zbl 1110.90044
[14] Liao, C.; Tseng, C.; Luarn, P., A discrete version of particle swarm optimization for flowshop scheduling problems, Computers & operations research, 3099-3111, (2007) · Zbl 1185.90083
[15] Salman, A.; Ahmad, I.; Al-Madani, S., Particle swarm optimization for task assignment problem, Microprocessors and microsystems, 26, 363-371, (2002)
[16] Zhang, H.; Tam, C.M.; Li, H., Mulitmode project scheduling based on particle swarm optimization, Computer-aided civil and infrastructure engineering, 21, 93-103, (2006)
[17] Kennedy, J.; Eberhart, RC., Particle swarm optimization, (), 1942-1948
[18] Kolisch, R.; Sprecher, A.; Drexl, A., Characterization and generation of a general class of resource constrained project scheduling problems, Management science, 41, 1693-1703, (1995) · Zbl 0870.90070
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.