Minimizing makespan of a resource-constrained scheduling problem: A hybrid greedy and genetic algorithms

Abstract: Resource-Constrained Project Scheduling Problem (RCPSP) is considered as an important project scheduling problem. However, increasing dimensions of a project, whether in number of activities or resource availability, cause unused resources through the planning horizon. Such phenomena may increase makespan of a project and also decline resource-usage efficiency. To solve this problem, many methods have been proposed before. In this article, an effective backward-forward search method (BFSM) is proposed using Greedy algorithm that is employed as a part of a hybrid with a two-stage genetic algorithm (BFSM-GA). The proposed method is explained using some related examples from literature and the results are then compared with a forward serial programming method. In addition, the performance of the proposed method is measured using a mathematical metric. Our findings show that the proposed approach can provide schedules with good quality for both small and large scale problems.

How to cite this paper

 Delgoshaei, A., Ariffin, M., Baharudin, B & Leman, Z. (2015). Minimizing makespan of a resource-constrained scheduling problem: A hybrid greedy and genetic algorithms.International Journal of Industrial Engineering Computations , 6(4), 503-520.

Refrences

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

Achuthan, N., & Hardjawidjaja, A. (2001). Project scheduling under time dependent costs–A branch and bound algorithm. Annals of Operations Research, 108(1-4), 55-74.

Alcaraz, J., & Maroto, C. (2001). A robust genetic algorithm for resource allocation in project scheduling. Annals of Operations Research, 102(1-4), 83-109.

Buddhakulsomsiri, J., & Kim, D. S. (2006). Properties of multi-mode resource-constrained project scheduling problems with resource vacations and activity splitting. European Journal of Operational Research, 175(1), 279-295.

Castej?n-Limas, M., Ordieres-Meré, J., Gonz?lez-Marcos, A., & Gonz?lez-Castro, V. (2011). Effort estimates through project complexity. Annals of Operations Research, 186(1), 395-406.

Chtourou, H., & Haouari, M. (2008). A two-stage-priority-rule-based algorithm for robust resource-constrained project scheduling. Computers & industrial engineering, 55(1), 183-194.

Delgoshaei, A., Ariffin, M. K., Baharudin, B. H. T. B., & Leman, Z. (2014). A Backward Approach for Maximizing Net Present Value of Multi-mode Pre-emptive Resource-Constrained Project Scheduling Problem with Discounted Cash Flows Using Simulated Annealing Algorithm. International Journal of Industrial Engineering and Management, 5(3), 151-158.

Demeulemeester, E. L. (2002). Project scheduling: a research handbook (Vol. 102): Springer.

Hartmann, S. (2001). Project scheduling with multiple modes: a genetic algorithm. Annals of Operations Research, 102(1-4), 111-135.

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), 1-14.

Icmeli, O., Erenguc, S. S., & Zappe, C. J. (1993). Project scheduling problems: a survey. International Journal of Operations & Production Management, 13(11), 80-91.

Ke, H., & Liu, B. (2010). Fuzzy project scheduling problem and its hybrid intelligent algorithm. Applied Mathematical Modelling, 34(2), 301-308.

Kelley, J. E. (1963). The critical-path method: Resources planning and scheduling. Industrial scheduling, 13, 347-365.

Kim, K., Yun, Y., Yoon, J., Gen, M., & Yamazaki, G. (2005). Hybrid genetic algorithm with adaptive abilities for resource-constrained multiple project scheduling. Computers in industry, 56(2), 143-160.

Kolisch, R. (1996). Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation. European Journal of Operational Research, 90(2), 320-333.

Kolisch, R., & Hartmann, S. (1999). Heuristic algorithms for the resource-constrained project scheduling problem: Classification and computational analysis: Springer.

Laslo, Z. (2010). Project portfolio management: An integrated method for resource planning and scheduling to minimize planning/scheduling-dependent expenses. International Journal of Project Management, 28(6), 609-618.

Lee, C.-Y., & Lei, L. (2001). Multiple-project scheduling with controllable project duration and hard resource constraint: some solvable cases. Annals of Operations Research, 102(1-4), 287-307.

Lombardi, M., & Milano, M. (2012). A min-flow algorithm for minimal critical set detection in resource constrained project scheduling. Artificial Intelligence, 182, 58-67.

Lova, A., & Tormos, P. (2001). Analysis of scheduling schemes and heuristic rules performance in resource-constrained multiproject scheduling. Annals of Operations Research, 102(1-4), 263-286.

Patterson, J., Slowinski, R., Talbot, F., & Weglarz, J. (1989). An algorithm for a general class of precedence and resource constrained scheduling problems. Advances in project scheduling, 187, 3-28.

Peteghem, V. 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.

Policella, N., Cesta, A., Oddi, A., & Smith, S. F. (2007). From precedence constraint posting to partial order schedules A CSP approach to Robust Scheduling. Ai Communications, 20(3), 163-180.

Seifi, M., & Tavakkoli-Moghaddam, R. (2008). A new bi-objective model for a multi-mode resource-constrained project scheduling problem with discounted cash flows and four payment models. Int. J. of Engineering, Transaction A: Basic, 21(4), 347-360.

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

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

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

Sung, C., & Lim, S. (1994). A project activity scheduling problem with net present value measure. International Journal of Production Economics, 37(2), 177-187.

Talbot, F. B. (1982). Resource-constrained project scheduling with time-resource tradeoffs: The nonpreemptive case. Management Science, 28(10), 1197-1210.

Ulusoy, G., Sivrikaya-?erifo?lu, F., & ?ahin, ?. (2001). Four payment models for the multi-mode resource constrained project scheduling problem with discounted cash flows. Annals of Operations Research, 102(1-4), 237-261.

Van de Vonder, S., Demeulemeester, E., Herroelen, W., & Leus, R. (2005). The use of buffers in project management: The trade-off between stability and makespan. International Journal of Production Economics, 97(2), 227-240.

Van de Vonder, S., Demeulemeester, E., Herroelen, W., & Leus, R. (2006). The trade-off between stability and makespan in resource-constrained project scheduling. International Journal of Production Research, 44(2), 215-236.

Yang, K. K., Talbot, F. B., & Patterson, J. H. (1993). Scheduling a project to maximize its net present value: an integer programming approach. European Journal of Operational Research, 64(2), 188-198.

Yu, L., Wang, S., Wen, F., & Lai, K. K. (2012). Genetic algorithm-based multi-criteria project portfolio selection. Annals of Operations Research, 197(1), 71-86.