Hybrid genetic algorithm for bi-objective resource-constrained project scheduling

Abstract

In this study, we considered a bi-objective, multi-project, multi-mode resource-constrained project scheduling problem. We adopted three objective pairs as combinations of the net present value (NPV) as a financial performance measure with one of the time-based performance measures, namely, makespan (C_max), mean completion time (MCT), and mean flow time (MFT) (i.e., minC_max/maxNPV, minMCT/maxNPV, and minMFT/maxNPV). We developed a hybrid non-dominated sorting genetic algorithm II (hybrid-NSGA-II) as a solution method by introducing a backward–forward pass (BFP) procedure and an injection procedure into NSGA-II. The BFP was proposed for new population generation and post-processing. Then, an injection procedure was introduced to increase diversity. The BFP and injection procedures led to improved objective functional values. The injection procedure generated a significantly high number of non-dominated solutions, thereby resulting in great diversity. An extensive computational study was performed. Results showed that hybrid-NSGA-II surpassed NSGA-II in terms of the performance metrics hypervolume, maximum spread, and the number of non-dominated solutions. Solutions were obtained for the objective pairs using hybrid-NSGA-II and three different test problem sets with specific properties. Further analysis was performed by employing cash balance, which was another financial performance measure of practical importance. Several managerial insights and extensions for further research were presented.

Keywords

backward–forward scheduling / hybrid bi-objective genetic algorithm / injection procedure / maximum cash balance / multi-objective multi-project multi-mode resource-constrained project scheduling problem

References

[1] Ahmad S B, Svalestuen F, Andersen B, Torp O (2016). A review of performance measurement for successful concurrent construction. Procedia: Social and Behavioral Sciences, 226: 447–454

[2] Ballestín F, Blanco R (2015). Theoretical and practical fundamentals. In: Schwindt C, Zimmermann J, eds. Handbook on Project Management and Scheduling, vol. 1. Cham: Springer, 411–427

[3] Balouka N, Cohen I, Shtub A (2016). Extending the multimode resource-constrained project scheduling problem by including value considerations. IEEE Transactions on Engineering Management, 63(1): 4–15

[4] Beşikci U, Bilge Ü, Ulusoy G (2015). Multi-mode resource constrained multi-project scheduling and resource portfolio problem. European Journal of Operational Research, 240(1): 22–31

[5] Blazewicz J, Lenstra J K, Kan A R (1983). Scheduling subject to resource constraints: Classification and complexity. Discrete Applied Mathematics, 5(1): 11–24

[6] Brucker P, Drexl A, Möhring R, Neumann K, Pesch E (1999). Resource-constrained project scheduling: Notation, classification, models, and methods. European Journal of Operational Research, 112(1): 3–41

[7] Can A, Ulusoy G (2014). Multi-project scheduling with two-stage decomposition. Annals of Operations Research, 217(1): 95–116

[8] Chang P C, Chen S H, Lin K L (2005). Two-phase sub population genetic algorithm for parallel machine-scheduling problem. Expert Systems with Applications, 29(3): 705–712

[9] Cochran J K, Horng S M, Fowler J W (2003). A multi-population genetic algorithm to solve multi-objective scheduling problems for parallel machines. Computers & Operations Research, 30(7): 1087–1102

[10] Deb K, Jain H (2014). An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: Solving problems with box constraints. IEEE Transactions on Evolutionary Computation, 18(4): 577–601

[11] Deb K, Pratap A, Agarwal S, Meyarivan T A M T (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2): 182–197

[12] Demeulemeester E L, Herroelen W S (2002). Project Scheduling: A Research Handbook. Boston: Kluwer Academic Publishers

[13] Gademann N, Schutten M (2005). Linear-programming-based heuristics for project capacity planning. IIE Transactions, 37(2): 153–165

[14] Gagnon M, Boctor F F, d’Avignon G (2005). Multicriteria project scheduling with resource availability cost. Quebec: Laval University

[15] Gang J, Xu J, Xu Y (2013). Multi-project resources allocation model under fuzzy random environment and its application to industrial equipment installation engineering. Journal of Applied Mathematics, 1–19

[16] Goldberg D E (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Massachusetts: Addison-Wesley Professional

[17] Goldratt E M (1997). Critical Chain. Great Barrington: North River Press

[18] Gu H, Schutt A, Stuckey P J, Wallace M G, Chu G (2015). Exact and heuristic methods for the resource-constrained net present value problem. In: Schwindt C, Zimmermann J, eds. Handbook on Project Management and Scheduling, vol. 1. Cham: Springer, 299–318

[19] Hartmann S (2001). Project scheduling with multiple modes: A genetic algorithm. Annals of Operations Research, 102(1–4): 111–135

[20] 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

[21] Herroelen W, de Reyck B, Demeulemeester E (1998). Resource-constrained project scheduling: A survey of recent developments. Computers & Operations Research, 25(4): 279–302

[22] Herroelen W, Leus R (2001). On the merits and pitfalls of critical chain scheduling. Journal of Operations Management, 19(5): 559–577

[23] Herroelen W, Leus R (2005). Project scheduling under uncertainty: Survey and research potentials. European Journal of Operational Research, 165(2): 289–306

[24] Khalili S, Najafi A A, Niaki S T A (2013). Bi-objective resource constrained project scheduling problem with makespan and net present value criteria: Two meta-heuristic algorithms. The International Journal of Advanced Manufacturing Technology, 69(1–4): 617–626

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

[26] Kolisch R, Drexl A (1997). Local search for non-preemptive multi-mode resource-constrained project scheduling. IIE Transactions, 29(11): 987–999

[27] Kolisch R, Padman R (2001). An integrated survey of deterministic project scheduling. Omega, 29(3): 249–272

[28] Kolisch R, Sprecher A (1997). PSPLIB—A project scheduling problem library. European Journal of Operational Research, 96(1): 205–216

[29] Kucuksayacigil F, Ulusoy G (2018). A hybrid genetic algorithm application for a bi-objective, multi-project, multi-mode, resource-constrained project scheduling problem. Working Paper #36791. Istanbul: Sabancı University

[30] Leyman P, Vanhoucke M (2016). Payment models and net present value optimization for resource-constrained project scheduling. Computers & Industrial Engineering, 91(1): 139–153

[31] Li K Y, Willis R J (1992). An iterative scheduling technique for resource-constrained project scheduling. European Journal of Operational Research, 56(3): 370–379

[32] Liu H, Wang Y (2009). A method for multi-project with resource constraints based on greedy strategy. In: Proceedings of the Fifth International Conference on Autonomic and Autonomous Systems. Valencia: IEEE, 22–27

[33] Mika M, Waligora G, Węglarz J (2005). Simulated annealing and tabu search for multi-mode resource-constrained project scheduling with positive discounted cash flows and different payment models. European Journal of Operational Research, 164(3): 639–668

[34] Myers R H, Montgomery D C, Anderson-Cook C M (2016). Response Surface Methodology: Process and Product Optimization Using Designed Experiments. New Jersey: John Wiley & Sons

[35] Najafi A A, Niaki S T A, Shahsavar M (2009). A parameter-tuned genetic algorithm for the resource investment problem with discounted cash flows and generalized precedence relations. Computers & Operations Research, 36(11): 2994–3001

[36] Ning M, He Z, Jia T, Wang N (2017). Metaheuristics for multi-mode cash flow balanced project scheduling with stochastic duration of activities. Automation in Construction, 81: 224–233

[37] Özdamar L, Ulusoy G (1996). A note on an iterative forward/backward scheduling technique with reference to a procedure by Li and Willis. European Journal of Operational Research, 89(2): 400–407

[38] Pich M T, Loch C H, Meyer A D (2002). On uncertainty, ambiguity, and complexity in project management. Management Science, 48(8): 1008–1023

[39] Riise A, Mannino C, Burke E K (2016). Modelling and solving generalised operational surgery scheduling problems. Computers & Operations Research, 66: 1–11

[40] Sacks R, Seppänen O, Priven V, Savosnick J (2017). Construction flow index: A metric of production flow quality in construction. Construction Management and Economics, 35(1–2): 45–63

[41] Shahsavar A, Najafi A A, Niaki S T A (2015). Three self-adaptive multi-objective evolutionary algorithms for a triple-objective project scheduling problem. Computers & Industrial Engineering, 87(1): 4–15

[42] Singh A (2014). Resource constrained multi-project scheduling with priority rules & analytic hierarchy process. Procedia Engineering, 69: 725–734

[43] Sivrikaya-Şerifoğlu F (1997). A New Uniform Order-Based Crossover Operator for Genetic Algorithm Applications to Multi-component Combinatorial Optimization Problems. Dissertation for the Doctoral Degree. Istanbul: Boğaziçi University

[44] Smith-Daniels D E, Aquilano N J (1987). Using a late-start resource-constrained project schedule to improve project net present value. Decision Sciences, 18(4): 617–630

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

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

[47] Talbot F B (1982). Resource-constrained project scheduling with time-resource tradeoffs: The non-preemptive case. Management Science, 28(10): 1197–1210

[48] Ulusoy G, Özdamar L (1995). A heuristic scheduling algorithm for improving the duration and net present value of a project. International Journal of Operations & Production Management, 15(1): 89–98

[49] 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

[50] Vanhoucke M (2009). A genetic algorithm for net present value maximization for resource constrained projects. In: Cotta C, Cowling P, eds. Evolutionary Computation in Combinatorial Optimization. Berlin, Heidelberg: Springer, 13–24

[51] Wang L, Zheng X L (2018). A knowledge-guided multi-objective fruit fly optimization algorithm for the multi-skill resource constrained project scheduling problem. Swarm and Evolutionary Computation, 38: 54–63

[52] Wang W X, Wang X, Ge X L, Deng L (2014). Multi-objective optimization model for multi-project scheduling on critical chain. Advances in Engineering Software, 68(1): 33–39

[53] Wauters T, Kinable J, Smet P, Vancroonenburg W, Vanden Berghe G, Verstichel J (2016). The multi-mode resource-constrained multi-project scheduling problem. Journal of Scheduling, 19(3): 271–283

[54] Węglarz J, Józefowska J, Mika M, Waligóra G (2011). Project scheduling with finite or infinite number of activity processing modes—A survey. European Journal of Operational Research, 208(3): 177–205

[55] Xiao J, Wu Z, Hong X X, Tang J C, Tang Y (2016). Integration of electromagnetism with multi-objective evolutionary algorithms for RCPSP. European Journal of Operational Research, 251(1): 22–35

[56] Xu J, Feng C (2014). Multi-mode resource-constrained multiple project scheduling problem under fuzzy random environment and its application to a large-scale hydropower construction project. The Scientific World Journal, 463692

[57] Zitzler E (1999). Evolutionary Algorithms for Multi-objective Optimization: Methods and Applications. Dissertation for the Doctoral Degree. Zürich: Swiss Federal Institute of Technology

[58] Zitzler E, Thiele L (1998). Multi-objective optimization using evolutionary algorithms—A comparative case study. In: Proceedings of the Fifth International Conference on Parallel Problem Solving from Nature. Amsterdam: Springer, 292–301

RIGHTS & PERMISSIONS

Higher Education Press