An Efficient Imperialist Competitive Algorithm for Resource Constrained Project Scheduling Problem

Document Type : Research Paper

Authors

Faculty of Industrial and Systems Engineering, Tarbiat Modares University, Tehran, Iran

Abstract

In this paper, a new algorithm based on the framework of the imperialist competitive algorithm for solving resource constrained project scheduling problem (RCPSP) will be proposed. In this problem, the activities are scheduled based on the resource and precedence relationships constraints in a way that the makes pan will be minimized. In order to model the assimilation process, a uniform crossover has been used, and to avoid premature convergence of the proposed algorithm, two revolution operators including one point revolution and multi-point revolution will be introduced. Also, in order to enhance the exploitation ability, a combined local search including permutation based local search (PBLS) and forward-backward improvement (FBI) is performed. The algorithm parameters are determined by designing Taguchi experiment, and the efficiency of proposed ICA is demonstrated by solving PSPLIB problems. Computational results and comparisons with some existing algorithms show that the proposed algorithm can produce near-optimal solution for small problems and competitive solution for large ones.

Keywords

Main Subjects

References

1. Blazewicz, J., Lenstra, J. and Rinnoy Kan, A. H. (1983). “Scheduling subject to resource classification and complexity constraint.”, Discret. Appl. Math., Vol. 5, No. 1, PP. 11–24.
2. Hartmann, S. (1997). Scheduling medical research experiments: an application of project scheduling methods, Technical Report, University Kiel, Germany.
3. Alba, E. and Francisco Chicano, J. (2007). “Software project management with Gas”, Information Sciences, Vol. 177, No. 11, PP. 2380–2401.
4. Dodin, B., Elimam, A. A. and Rolland, E. (1998). “Tabu search in audit scheduling.”, European Journal of Operational Research, Vol. 106, No. 2–3, PP. 373–392.
5. Sprecher, A. (1994). “Special cases”, In Resource-constrained project scheduling: Exact methods for the multi-mode case,1th Ed,PP. 10–18, Springer, Berlin, Germany.
6. Demeulemeester, E. L. and Herroelen, W. S. (2002). The Resource-Constrained Project Scheduling Problem, In Project Scheduling: A Research Handbook, 1th Ed, PP. 203–342, Springer, Berlin, Germany.
7. Hartmann, S. (1998). “A competitive genetic algorithm for resource-constrained project scheduling”, Naval Research Logistics, Vol. 45, No. 6, PP. 733–750.
8. Hartmann, S. (2002). “A self-adapting genetic algorithm for project scheduling under resource constraints”, Naval Research Logistics, Vol. 49, No. 5, PP. 433–448
9. Bouleimen, K. and Lecocq, H. (2003). “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, No. 2, PP. 268–281.
10. Valls, V., Ballestín, F. and Quintanilla, S. (2008). “A hybrid genetic algorithm for the resource-constrained project scheduling problem”, European Journal of Operational Research, Vol. 185, No. 2, PP. 495–508.
11. Ziarati, K., Akbari, R. and Zeighami, V. (2011). “On the performance of bee algorithms for resource-constrained project scheduling problem”, Applied Soft Computing, Vol. 11, No. 4, PP. 3720–3733.
12. Fang, C. and Wang, L. (2012). “An effective shuffled frog-leaping algorithm for resource-constrained project scheduling problem”, Computers & Operations Research, Vol. 39, No. 5, PP. 890–901.
13. Fahmy, A., Hassan, T. M. and Bassioni, H. (2014). “Improving RCPSP solutions quality with Stacking Justification—Application with particle swarm optimization”, Expert Systems with Applications, Vol. 41, No. 13, PP. 5870–5881.
14. Zheng, X. and Wang, L. (2015). “A multi-agent optimization algorithm for resource constrained project scheduling problem”, Expert Systems with Applications, Vol. 42, No. 15–16, PP. 6039–6049.
15. Atashpaz-Gargari, E. and Lucas, C. (2007). “Imperialist competitive algorithm: An algorithm for optimization inspired by imperialistic competition”, IEEE Congress on Evolutionary Computation, PP. 4661–4667.
16. Hosseini, S. and Al Khaled, A. (2014). “A survey on the Imperialist Competitive Algorithm metaheuristic: Implementation in engineering domain and directions for future research”, Applied Soft Computing, Vol. 24, PP. 1078–1094.
17. Kolisch, R. (1996). “Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation”, European Journal of Operational Research, Vol. 90, No. 95, PP. 320–333.
18. Li, K. Y. and Willis, R. J. (1992). “An iterative scheduling technique for resource-constrained project scheduling”, European Journal of Operational Research, Vol. 56, No. 3, PP. 370–379.
19. Kolisch, R. and Sprecher, A. (1997). “PSPLIB - A project scheduling problem library”, European Journal of Operational Research, Vol. 96, No. 1, PP. 205–216.
20. Kolisch, R. and Drexl, A. (1996). “Adaptive search for solving hard project scheduling problems”, Naval Research Logistics, Vol. 43, No. 1, PP. 23–40.
21. Schirmer, A. (2000). “Case-based reasoning and improved adaptive search for project scheduling. Naval Research Logistics”, Naval Research Logistics, Vol. 47, No. 3, PP. 201–222.
22. Coelho, J. and Tavares, L. (2005). “Comparative analysis of metaheuristics for the resource constrained project scheduling problem”, European Journal of Operational Research, Vol. 165, PP. 375–386.
23. Agarwal, A., Colak, S. and Erenguc, S. (2011). “A Neurogenetic approach for the resource-constrained project scheduling problem”, Computers & Operations Research, Vol. 38, No. 1, PP. 44–50.
24. Kolisch, R. and Hartmann, S. (2006). “Experimental investigation of heuristics for resource-constrained project scheduling: An update”, European Journal of Operational Research, Vol. 174, No. 1, PP. 23–37.
Advances in Industrial Engineering
Volume 51, Issue 2
July 2017
Pages 161-174

Files

Share

How to cite

Statistics