Cat Swarm Optimization-Based Schemes for Resource-Constrained Project Scheduling

Abstract:

This paper presents a cat swarm optimization (CSO)-based method for resource constrained project scheduling problem (RCPSP). The CSO simulates the behavior of cats in two sub-models and potential solution to the RCPSP is presented by the multidimensional positions of cats. CSO-based scheme for the RCPSP has three main stages: first randomly initialize the parameters of cats, then update the position in iteration and calculate the fitness through serial SGS method, finally terminate the process if the condition is satisfied. Compared to the other widely used heuristic methods, CSO is easy to understand and to implement. The adoption of CSO in solving RCPSP indicates the universality of CSO in solving operational problems. When solving RCPSP, some refinement of original CSO are made. The performance of the proposed algorithm is compared against a set of heuristic and meta-heuristic methods, and it is tested on standard problem sets called PSPLIB which is freely available on the Internet. The empirical results show that CSO has an average good performance among the other compared methods.

• Periodical: Applied Mechanics and Materials (Volumes 220-223)
• Pages: 251-258
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.220-223.251
• Online since: November 2012
• Authors: Long Xu, Wen Bin Hu
• Keywords: CSO, Meta-Heuristic, RCPSP

References

[1] Davis,L.,Handbook of Genetic Algorithms, Van Nostrand Reinhold, New York, 1991.

[2] K. Bouleimen, H. Lecocq, 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, 2003, p.268–281.

DOI: 10.1016/s0377-2217(02)00761-0

[3] T. Baar, P. Brucker, S. Knust, Tabu-search algorithms and lower bounds for the resource-constrained project scheduling problem, in: S Voss, S Martello, I Osman, C Roucairol (Eds.), Meta-heurisitics: Advances and Trends in Local Search Paradigms for Optimization, Kluwer, Dordrecht, 1998, p.1–8.

DOI: 10.1007/978-1-4615-5775-3_1

[4] Hartmann, S., A competitive genetic algorithm for resource-constrained project scheduling. Naval Research Logistics ,vol 45,1998, pp.279-302.

DOI: 10.1002/(sici)1520-6750(199810)45:7<733::aid-nav5>3.0.co;2-c

[5] Hartmann, S., A self-adapting genetic algorithm for project scheduling under resource constraints, Naval Research Logistics,vol 49, 2002, pp.433-448.

DOI: 10.1002/nav.10029

[6] W.T. Chan, D.K.H. Chua, G. Kannan, Construction resource scheduling with genetic algorithms, Journal of Construction Engineering and Management, ASCE,vol 122, 1996, pp.125-132.

DOI: 10.1061/(asce)0733-9364(1996)122:2(125)

[7] J. Alcaraz and C. Maroto, A Robust Genetic Algorithm for Resource Allocation in Project Scheduling, Annals of Operations Research, vol. 102, 2001, p.83–109.

[8] Dorigo, M., V. Maniezzo and A. Colorni, The ant system: Optimization by a colony of cooperating agents, IEEE Trans. on Systems, Man, and Cybernetics -Part B, vol.149, no.5, 1996, pp.379-386.

DOI: 10.1109/3477.484436

[9] Q. Duana, T. Warren Liao, Improved ant colony optimization algorithms for determining project critical paths, Automation in Construction ,Volume 19, Issue 6, 2010, pp.676-693.

DOI: 10.1016/j.autcon.2010.02.012

[10] Shih-Tang Lo., Multiprocessor system scheduling with precedence and resource constraints using an enhanced ant colony system, Expert Systems with Applications Volume 34, Issue 3, 2008, pp.2071-2081.

DOI: 10.1016/j.eswa.2007.02.022

[11] Hong Zhang., Particle swarm optimization-based schemes for resource-constrained project scheduling, Automation in Construction 14, 2005, p.393– 404.

DOI: 10.1016/j.autcon.2004.08.006

[12] J. Kennedy, R.C. Eberhart, Particle swarm optimization, Proc. IEEE Conf. Neural Netw., vol. IV, IEEE, Piscataway, NJ, 1995, p.1942– 1948.

[13] B. Jarboui., A combinatorial particle swarm optimization for solving multi-mode resource-constrained project scheduling problems. Applied Mathematics and Computation, vol. 195, 2008, pp.299-308.

DOI: 10.1016/j.amc.2007.04.096

[14] Ruey-Maw Chen, Using novel particle swarm optimization scheme to solve resource-constrained scheduling problem in PSPLIB. Expert Systems with Applications 37, 2010, p.1899–1910.

DOI: 10.1016/j.eswa.2009.07.024

[15] Koorush Ziarati., On the performance of bee algorithms for resource-constrained project scheduling problem, Applied Soft Computing, vol. 11, 2011, p.3720–3733.

DOI: 10.1016/j.asoc.2011.02.002

[16] Shu-Chuan Chu., Computational intelligence based on the behavior of cats, International Journal of Innovative Computing, Information and Control, vol. 3, 2007.

[17] Rainer Kolisch, PSPLIB – A project scheduling problem library, European Journal of Operational Research, 1996, pp.205-216.

DOI: 10.1016/s0377-2217(96)00170-1

[18] Project Scheduling Problem Library—PSPLIB, http://www.129.187.106.231/psplib/

[19] W. Chen, Y.J. Shi, H.F. Teng, X.P. Lan, L.C. Hu, An efficient hybrid algorithm for resource-constrained project scheduling, Information Sciences,vol. 180, 2010, p.1031–1039.

DOI: 10.1016/j.ins.2009.11.044

[20] R. Kolisch and S. Hartmann: Heuristic algorithms for solving the resource-constrained project scheduling problem - Classification and computational analysis; Kluwer; Weglarz, J. (Hrsg.): Handbook on recent advances in project scheduling , 1999, pp.147-178.

DOI: 10.1007/978-1-4615-5533-9_7

[21] J.J.M. Mendes, J.F. Goncalves, M.G.C. Resende, A random key based genetic algorithm for the resource constrained project scheduling problem, Computers & Operations Research, vol. 36, 2009, p.92–109.

DOI: 10.1016/j.cor.2007.07.001