Volume 2 Issue 1 pp. 45-60 Winter, 2011


Artificial Bee colony for resource constrained project scheduling problem


Reza Akbari, Vahid Zeighami and Koorush Ziarati


Solving resource constrained project scheduling problem (RCPSP) has important role in the context of project scheduling. Considering a single objective RCPSP, the goal is to find a schedule that minimizes the makespan. This is NP-hard problem (Blazewicz et al., 1983) and one may use meta-heuristics to obtain a global optimum solution or at least a near-optimal one. Recently, various meta-heuristics such as ACO, PSO, GA, SA etc have been applied on RCPSP. Bee algorithms are among most recently introduced meta-heuristics. This study aims at adapting artificial bee colony as an alternative and efficient optimization strategy for solving RCPSP and investigating its performance on the RCPSP. To evaluate the artificial bee colony, its performance is investigated against other meta-heuristics for solving case studies in the PSPLIB library. Simulation results show that the artificial bee colony presents an efficient way for solving resource constrained project scheduling problem.


DOI: 10.5267/j.ijiec.2010.04.004

Keywords: Meta-heuristic, Artificial bee colony, Resource constrained project scheduling, Makespan, Single mode
References

Abbasi, B., Shadrokh, S., & Arkat, J.(2006). Bi-objective resource-constrained project scheduling with robustness and makespan criteria. Journal of Applied Mathematics and Computation, 180, 146–152.

Agarwal, A., Colak, S., & Erenguc, S.(2010). A Neurogenetic approach for the resource-constrained project scheduling problem. Computers & Operations Research, doi:10.1016/j.cor.2010.01.007.

Akbari, R., Mohammadi, M., & Ziarati, K.(2010). A novel bee swarm optimization algorithm for numerical function optimization. Journal of Communications on Nonlinear Sciences and Numerical Simulation, 15, 3142-3155.

Ashtiani, B., Leus, R., & Aryanezhad, M. B.(2009). New competitive results for the stochastic resource-constrained project scheduling problem: exploring the benefits of pre-processing. Journal of Scheduling, doi: 10.1007/s10951-009-0143-7.

Alatas B.(2010). Chaotic bee colony algorithms for global numerical optimization. Expert Systems with Applications, 37, 5682-5687.

Blazewicz J., Lenstra J. K., & Rinnooy Kan A. H. G.(1983). Scheduling projects to resource constraints: classification and complexity. Discrete Applied Mathematics, 5, 11–24.

Boctor, F. F.(1990). Some efficient multi-heuristic procedures for resourceconstrained project scheduling. European Journal of Operational Research, 49, 3–13.

Boctor, F. F.(1996). An adaptation of the simulated annealing algorithm for solving resource-constrained project scheduling problems. International Journal of Production Research, 34, 2335–2351.

Bouleimen, K., & Lecocq, H.(1993). A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version. European Journal of Operational Research, 149, 268–281.

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, 1899–1910.

Chen, R. M., Lo, S. T., Wang, C. J., & Wu, C. L.(2006). Multiprocessor system scheduling with precedence and resources constraints by ant colony system. Proceeding of ICS Conference, 292-297.

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, 1899–1910.

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

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

Debels, D., & Vanhoucke, M.(2004). An Electromagnetism Meta-Heuristic For The Resource-Constrained Project Scheduling Problem. Lecture Notes on Computer Science, 3871, 259-270.

Debels, D., De Reyck, B., Leus, R., & Vanhoucke M.(2006). A hybrid scatter search /Electromagnetism meta–heuristic for project scheduling. European Journal of Operational Research, 169, 638-653.

Fekete, S. P., & Schepers, J.(1998). New classes of lower bounds for bin-packing problems. Lecture Notes in Computer Science, 1412, 257–270.

Karaboga, D., & Basturk, B.(2007). A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm. Journal of Global Optimization, 39, 459–471.

Karaboga, D., & Akay, B.(2009). A comparative study of Artificial Bee Colony algorithm. Applied Mathematics and Computation, 214, 108-132.

Kolisch, R., & Hartmann, S.(1999). Heuristic algorithms for solving the resource-constrained project scheduling problem: classification and computational analysis. J. Weglarz (Ed.), Project Scheduling: Recent Models, algorithms and Applications, Kluwer Academic Publishers, Berlin, 147–178.

Kolisch, R.(1996). Efficient priority rules for the resource-constrained project scheduling problem. Journal of Operations Management, 14, 179–192.

Krüger, D., & Scholl, A.(2009). A heuristic solution framework for the resource constrained multi-project scheduling problem with sequence-dependent transfer times. European Journal of Operational Research, 197, 492–508.

Hartmann, S., & Briskorn, D.(2010). A survey of variants and extensions of the resource-constrained project scheduling problem. European Journal of Operational Research, 207, 1-14.

Hartmann, S.(1998). A competitive genetic algorithm for resourceconstrained project scheduling. Naval Research Logistics, 45, 733– 750.

Mahdi Mobini, M. D., Rabbani, M., Amalnik, M. S., Razmi, J., & Rahimi-Vahed, A. R.(2009). Using an enhanced scatter search algorithm for a resource-constrained project scheduling problem. Soft Computing, 13, 597–610.

Mendes, J. J., Gonalves, J. F., & Resende M.G.C.(2009). A random key based genetic algorithm for the resource constrained project scheduling problem. Computers & Operations Research, 36, 92–109.

Mendes, J. J., Gonalves, J. F., Resende, M. G. C.(2009). A random key based genetic algorithm for the resource constrained project scheduling problem. Computers & Operations Research, 36, 92–109.

Mingozzi, A., Maniezzo, V., Ricciardelli, S., & Bianco, L.(1998). An exact algorithm for project scheduling with resource constraints based on a new mathematical formulation. Journal of Management Science, 44, 714–729.

Mobini, M., Mobini Z., & Rabbani M.(2010). An Artificial Immune Algorithm for the project scheduling problem under resource constraints. Applied Soft Computing, doi:10.1016/j.asoc.2010.06.013.

Montoya-Torres, J. R., Gutierrez-Franco, E., & Pirachica N-Mayorga, C.(2010). Project scheduling with limited resources using a genetic algorithm. International Journal of Project Management, 28, 619–628.

Neumann, K., Schwindt, C., & Zimmermann, J.(2003). Order-based neighborhoods for project scheduling with nonregular objective functions. European Journal of Operational Research, 149, 2, 325-343.

Pan, Q. K., M. Tasgetiren F., Suganthan, P. N., & Chua, T. J.(2010) A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem, Information Sciences. doi:10.1016/j.ins.2009.12.025.

Pham, D. T., Castellani, M., & Fahmy, A. A.(2008). Learning the inverse kinematics of a Robot manipulator using the bees algorithm. IEEE international conference on industrial informatics, 493–498.

Rabbani, M., Fatemi Ghomi, S.M.T., Jolai, F., & Lahiji, N.S.(2007). A new heuristic for resource-constrained project scheduling in stochastic networks using critical chain concept. European Journal of Operational Research, 176, 794–808.

Ranjbar, M.(2008). Solving the resource-constrained project scheduling problem using filter-and-fan approach. Journal of Applied Mathematics and Computation, 201, 313–318.

Sprecher, A.(2000). Scheduling resource-constrained projects competitively at modest memory requirements. Management Science, 46, 710–723.

Stork, F., & Uetz, M.(2005). On the generation of circuits and minimal forbidden sets. Mathematical Programming, 102, 185–203.

Teodorovic, D., & Dell Orco, M.(2007). Bee colony optimization–a cooperative learning approach to complex transportation problems. Advanced OR and AI Methods in Transportation, 51–60.

Teodorovic, D., Panta, L., Goran M., & Dell, O. M.(2006). Bee colony optimization: principles and applications. Proceeding of eighth seminar on neural network applications in electrical engineering, Neurel, 151–156.

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

Tormos, P., & Lova, A.(2001). A competitive heuristic solution technique for resource-constrained project scheduling. Annals of Operations Research, 102, 65–81.

Tseng, L.Y., & Chen, S. C.(2006). A hybrid metaheuristic for the resource-constrained project scheduling problem, European Journal of Operational Research, 175, 707–721.

Valls V., Ballestın F., & Quintanilla, S.(2008). A hybrid genetic algorithm for the resource-constrained project scheduling problem. European Journal of Operational Research, 185, 495–508.

Zhang, H., Li, X., Li, H., & Huang, F.(2005). Particle swarm optimization-based schemes for resource-constrained project scheduling. Journal of Automation in Construction, 14, 393– 404.

Zhang, H., Li, H., & Tam, C. M.(2006). Particle swarm optimization for resource-constrained project scheduling, International Journal of Project Management, 24, 83–92.