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

doi:10.1007/s42524-020-0100-x

Front. Eng

2020, Vol. 7

Issue (3) : 426-446 https://doi.org/10.1007/s42524-020-0100-x

RESEARCH ARTICLE

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

Fikri KUCUKSAYACIGIL¹, Gündüz ULUSOY²(

)

¹. Industrial Engineering Department, University of Arkansas, Fayetteville, AR 72701, USA
². Industrial Engineering Department, Sabanci University, Istanbul, Turkey

Download: PDF(1587 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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

Corresponding Author(s): Gündüz ULUSOY

Just Accepted Date: 11 March 2020 Online First Date: 17 April 2020 Issue Date: 06 August 2020

Cite this article:

Fikri KUCUKSAYACIGIL,Gündüz ULUSOY. Hybrid genetic algorithm for bi-objective resource-constrained project scheduling[J]. Front. Eng, 2020, 7(3): 426-446.

URL:

https://academic.hep.com.cn/fem/EN/10.1007/s42524-020-0100-x
https://academic.hep.com.cn/fem/EN/Y2020/V7/I3/426

Notations	Definitions
H, t	Time horizon and time period index, t = 1,…, H
P, p	Set of projects and project index, p = 1,…, \|P\|
J_p, j	Set of activities in project p and activity index, j = 1,…, \|J_p\| for project p
M_pj, m	Set of modes of activity j in project p and mode index, m = 1,…, \|M_pj\| for project p and activity j
d_pjm	Duration of activity j of project p in mode m
R, r	Set of renewable resources and renewable resource index, r = 1,…, \|R\|
N, n	Set of non-renewable resources and non-renewable resource index, n = 1,…, \|N\|
$r^p j m r$	Amount of renewable resource r required by activity j of project p in mode m
$n^p j m n$	Amount of non-renewable resource n required by activity j of project p in mode m
$r ‾ r t$	Capacity of renewable resource r in period t
$n ‾ n$	Capacity of non-renewable resource n
E_pj, L_pj	Earliest and latest completion times of activity j in project p
C	Set of all pairs of activities with immediate predecessor relationship; for example, (i, j) ÎC means that activity i precedes activity j
x	Set of decision variables
V	Number of objective functions
f_k(x)	kth objective function, k = 1,…, V
f(x)	Vector of objective functions

Tab.1 Notations for the mathematical formulation

Fig.1 Example of the individual representation.

Tab.2 Example of the individual representation

Fig.2 Example of an SSGS application.

Tab.3 Example of an SSGS application

Fig.3 Example of the hypervolume, maximum spread, and size of the set of non-dominated solutions.

Tab.4 Parameter ranges

Fig.4 Pseudocode for the BFP procedure.

Fig.5 Flowchart of hybrid-NSGA-II.

Test sets	Number of instances	$A C max ‾$			$A N P V ‾$
Test sets	Number of instances	NSGA-II	BFP on the archive	p-value	NSGA-II	BFP on the archive	p-value
A	81	110.97	106.96	5E - 15*	281806	282119	0.03*
B	84	114.75	110.69	2E - 15*	332864	333123	0.17
C	27	108.31	104.44	9E - 11	385864	385461	0.36*

Tab.5 Comparison of the performances of NSGA-II and NSGA-II with BFP on the archive

Test sets	Number of instances	$A C max ‾$			$A N P V ‾$
Test sets	Number of instances	BFP on the archive w/o injection	Hybrid-NSGA-II	p-value	BFP on the archive w/o injection	Hybrid-NSGA-II	p-value
A	81	106.96	112.99	3E - 29	282119	296752	5E - 15*
B	84	110.69	118.42	8E - 26	333123	354743	2E - 15*
C	27	104.44	110.99	7E - 06*	385461	400699	1E - 11

Tab.6 Effects of the injection procedure on

A C max ‾

and

A N P V ‾

Fig.6 Comparison of NSGA-II and hybrid-NSGA-II in four different instances.

Test sets		Number of instances	$A M F T ‾$			$A M C T ‾$
Test sets		Number of instances	BFP on the archive w/o injection	Hybrid-NSGA-II	p-value	BFP on the archive w/o injection	Hybrid-NSGA-II	p-value
A	81		84.73	60.80	5E - 15*	88.59	76.54	5E - 15*
B	84		91.40	66.75	2E - 15*	94.65	80.48	2E - 15*
C	27		79.32	61.40	7E - 11	82.21	73.91	8E - 09

Tab.7 Effects of the injection procedure on

A M F T ‾

and

A M C T ‾

Tab.8 Comparison of the average number of non-dominated solutions with and without injection

Tab.9 Hypervolume, maximum spread, and size of the non-dominated solution set metrics for NSGA-II and hybrid-NSGA-II

Objective combinations	$A N P V ‾$	$A M F T ‾$	$A M C T ‾$	$A C max ‾$
minC_max/maxNPV	296752	60.8	76.5	113.0
minMFT/maxNPV	278305	37.7	103.7	194.1
minMCT/maxNPV	302253	49.3	69.0	125.1

Tab.10 Comparison of the results of different objective combinations from set A

Objective combinations	$A N P V ‾$	$A M F T ‾$	$A M C T ‾$	$A C max ‾$
minC_max/maxNPV	354743	66.7	80.5	118.4
minMFT/maxNPV	311640	42.7	140.0	266.0
minMCT/maxNPV	363284	56.1	73.7	132.4

Tab.11 Comparison of the results of different objective combinations from set B

Objective combinations	$A N P V ‾$	$A M F T ‾$	$A M C T ‾$	$A C max ‾$
minC_max/maxNPV	400699	61.4	73.9	111.0
minMFT/maxNPV	356321	38.5	131.7	259.8
minMCT/maxNPV	407492	50.5	64.3	128.0

Tab.12 Comparison of the results of different objective combinations from set C

Fig.7 CB diagram of instances A21_11 and A21_21.

Table A1 Sample of CPU times for NSGA-II, injection, and BFP on the archive

Fig. B1 Comparison of NSGA-II and hybrid-NSGA-II for problem set A.

Fig. B2 Comparison of NSGA-II and hybrid-NSGA-II for problem set B.

Fig. B3 Comparison of NSGA-II and hybrid-NSGA-II for problem set C.

1	S B Ahmad, F Svalestuen, B Andersen, O Torp (2016). A review of performance measurement for successful concurrent construction. Procedia: Social and Behavioral Sciences, 226: 447–454 https://doi.org/10.1016/j.sbspro.2016.06.210
2	F Ballestín, R Blanco (2015). Theoretical and practical fundamentals. In: Schwindt C, Zimmermann J, eds. Handbook on Project Management and Scheduling, vol. 1. Cham: Springer, 411–427
3	N Balouka, I Cohen, A Shtub (2016). Extending the multimode resource-constrained project scheduling problem by including value considerations. IEEE Transactions on Engineering Management, 63(1): 4–15 https://doi.org/10.1109/TEM.2015.2497209
4	U Beşikci, Ü Bilge, G Ulusoy (2015). Multi-mode resource constrained multi-project scheduling and resource portfolio problem. European Journal of Operational Research, 240(1): 22–31 https://doi.org/10.1016/j.ejor.2014.06.025
5	J Blazewicz, J K Lenstra, A R Kan (1983). Scheduling subject to resource constraints: Classification and complexity. Discrete Applied Mathematics, 5(1): 11–24 https://doi.org/10.1016/0166-218X(83)90012-4
6	P Brucker, A Drexl, R Möhring, K Neumann, E Pesch (1999). Resource-constrained project scheduling: Notation, classification, models, and methods. European Journal of Operational Research, 112(1): 3–41 https://doi.org/10.1016/S0377-2217(98)00204-5
7	A Can, G Ulusoy (2014). Multi-project scheduling with two-stage decomposition. Annals of Operations Research, 217(1): 95–116 https://doi.org/10.1007/s10479-014-1555-0
8	P C Chang, S H Chen, K L Lin (2005). Two-phase sub population genetic algorithm for parallel machine-scheduling problem. Expert Systems with Applications, 29(3): 705–712 https://doi.org/10.1016/j.eswa.2005.04.033
9	J K Cochran, S M Horng, J W Fowler (2003). A multi-population genetic algorithm to solve multi-objective scheduling problems for parallel machines. Computers & Operations Research, 30(7): 1087–1102 https://doi.org/10.1016/S0305-0548(02)00059-X
10	K Deb, H Jain (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 https://doi.org/10.1109/TEVC.2013.2281535
11	K Deb, A Pratap, S Agarwal, T A M T Meyarivan (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2): 182–197 https://doi.org/10.1109/4235.996017
12	E L Demeulemeester, W S Herroelen (2002). Project Scheduling: A Research Handbook. Boston: Kluwer Academic Publishers
13	N Gademann, M Schutten (2005). Linear-programming-based heuristics for project capacity planning. IIE Transactions, 37(2): 153–165 https://doi.org/10.1080/07408170590885611
14	M Gagnon, F F Boctor, G d’Avignon (2005). Multicriteria project scheduling with resource availability cost. Quebec: Laval University
15	J Gang, J Xu, Y Xu (2013). Multi-project resources allocation model under fuzzy random environment and its application to industrial equipment installation engineering. Journal of Applied Mathematics, 1–19 https://doi.org/10.1155/2013/818731
16	D E Goldberg (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Massachusetts: Addison-Wesley Professional
17	E M Goldratt (1997). Critical Chain. Great Barrington: North River Press
18	H Gu, A Schutt, P J Stuckey, M G Wallace, G Chu (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	S Hartmann (2001). Project scheduling with multiple modes: A genetic algorithm. Annals of Operations Research, 102(1–4): 111–135 https://doi.org/10.1023/A:1010902015091
20	S Hartmann, D Briskorn (2010). A survey of variants and extensions of the resource-constrained project scheduling problem. European Journal of Operational Research, 207(1): 1–14 https://doi.org/10.1016/j.ejor.2009.11.005
21	W Herroelen, B de Reyck, E Demeulemeester (1998). Resource-constrained project scheduling: A survey of recent developments. Computers & Operations Research, 25(4): 279–302 https://doi.org/10.1016/S0305-0548(97)00055-5
22	W Herroelen, R Leus (2001). On the merits and pitfalls of critical chain scheduling. Journal of Operations Management, 19(5): 559–577 https://doi.org/10.1016/S0272-6963(01)00054-7
23	W Herroelen, R Leus (2005). Project scheduling under uncertainty: Survey and research potentials. European Journal of Operational Research, 165(2): 289–306 https://doi.org/10.1016/j.ejor.2004.04.002
24	S Khalili, A A Najafi, S T A Niaki (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 https://doi.org/10.1007/s00170-013-5057-z
25	R Kolisch (1996). Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation. European Journal of Operational Research, 90(2): 320–333 https://doi.org/10.1016/0377-2217(95)00357-6
26	R Kolisch, A Drexl (1997). Local search for non-preemptive multi-mode resource-constrained project scheduling. IIE Transactions, 29(11): 987–999 https://doi.org/10.1080/07408179708966417
27	R Kolisch, R Padman (2001). An integrated survey of deterministic project scheduling. Omega, 29(3): 249–272 https://doi.org/10.1016/S0305-0483(00)00046-3
28	R Kolisch, A Sprecher (1997). PSPLIB—A project scheduling problem library. European Journal of Operational Research, 96(1): 205–216 https://doi.org/10.1016/S0377-2217(96)00170-1
29	F Kucuksayacigil, G Ulusoy (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	P Leyman, M Vanhoucke (2016). Payment models and net present value optimization for resource-constrained project scheduling. Computers & Industrial Engineering, 91(1): 139–153 https://doi.org/10.1016/j.cie.2015.11.008
31	K Y Li, R J Willis (1992). An iterative scheduling technique for resource-constrained project scheduling. European Journal of Operational Research, 56(3): 370–379 https://doi.org/10.1016/0377-2217(92)90320-9
32	H Liu, Y Wang (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	M Mika, G Waligora, J Węglarz (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 https://doi.org/10.1016/j.ejor.2003.10.053
34	R H Myers, D C Montgomery, C M Anderson-Cook (2016). Response Surface Methodology: Process and Product Optimization Using Designed Experiments. New Jersey: John Wiley & Sons
35	A A Najafi, S T A Niaki, M Shahsavar (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 https://doi.org/10.1016/j.cor.2009.01.016
36	M Ning, Z He, T Jia, N Wang (2017). Metaheuristics for multi-mode cash flow balanced project scheduling with stochastic duration of activities. Automation in Construction, 81: 224–233 https://doi.org/10.1016/j.autcon.2017.06.011
37	L Özdamar, G Ulusoy (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 https://doi.org/10.1016/0377-2217(94)00272-X
38	M T Pich, C H Loch, A D Meyer (2002). On uncertainty, ambiguity, and complexity in project management. Management Science, 48(8): 1008–1023 https://doi.org/10.1287/mnsc.48.8.1008.163
39	A Riise, C Mannino, E K Burke (2016). Modelling and solving generalised operational surgery scheduling problems. Computers & Operations Research, 66: 1–11 https://doi.org/10.1016/j.cor.2015.07.003
40	R Sacks, O Seppänen, V Priven, J Savosnick (2017). Construction flow index: A metric of production flow quality in construction. Construction Management and Economics, 35(1–2): 45–63 https://doi.org/10.1080/01446193.2016.1274417
41	A Shahsavar, A A Najafi, S T A Niaki (2015). Three self-adaptive multi-objective evolutionary algorithms for a triple-objective project scheduling problem. Computers & Industrial Engineering, 87(1): 4–15 https://doi.org/10.1016/j.cie.2015.04.027
42	A Singh (2014). Resource constrained multi-project scheduling with priority rules & analytic hierarchy process. Procedia Engineering, 69: 725–734 https://doi.org/10.1016/j.proeng.2014.03.048
43	F Sivrikaya-Şerifoğlu (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	D E Smith-Daniels, N J Aquilano (1987). Using a late-start resource-constrained project schedule to improve project net present value. Decision Sciences, 18(4): 617–630
45	M G Speranza, C Vercellis (1993). Hierarchical models for multi-project planning and scheduling. European Journal of Operational Research, 64(2): 312–325 https://doi.org/10.1016/0377-2217(93)90185-P
46	A Sprecher, S Hartmann, A Drexl (1997). An exact algorithm for project scheduling with multiple modes. Operations-Research-Spektrum, 19(3): 195–203 https://doi.org/10.1007/BF01545587
47	F B Talbot (1982). Resource-constrained project scheduling with time-resource tradeoffs: The non-preemptive case. Management Science, 28(10): 1197–1210 https://doi.org/10.1287/mnsc.28.10.1197
48	G Ulusoy, L Özdamar (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 https://doi.org/10.1108/01443579510077241
49	G Ulusoy, F Sivrikaya-Şerifoğlu, Ş Ş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 https://doi.org/10.1023/A:1010914417817
50	M Vanhoucke (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	L Wang, X L Zheng (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 https://doi.org/10.1016/j.swevo.2017.06.001
52	W X Wang, X Wang, X L Ge, L Deng (2014). Multi-objective optimization model for multi-project scheduling on critical chain. Advances in Engineering Software, 68(1): 33–39 https://doi.org/10.1016/j.advengsoft.2013.11.004
53	T Wauters, J Kinable, P Smet, W Vancroonenburg, G Vanden Berghe, J Verstichel (2016). The multi-mode resource-constrained multi-project scheduling problem. Journal of Scheduling, 19(3): 271–283 https://doi.org/10.1007/s10951-014-0402-0
54	J Węglarz, J Józefowska, M Mika, G Waligóra (2011). Project scheduling with finite or infinite number of activity processing modes—A survey. European Journal of Operational Research, 208(3): 177–205 https://doi.org/10.1016/j.ejor.2010.03.037
55	J Xiao, Z Wu, X X Hong, J C Tang, Y Tang (2016). Integration of electromagnetism with multi-objective evolutionary algorithms for RCPSP. European Journal of Operational Research, 251(1): 22–35 https://doi.org/10.1016/j.ejor.2015.10.059
56	J Xu, C Feng (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	E Zitzler (1999). Evolutionary Algorithms for Multi-objective Optimization: Methods and Applications. Dissertation for the Doctoral Degree. Zürich: Swiss Federal Institute of Technology
58	E Zitzler, L Thiele (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

Viewed

Full text

Abstract

Cited

Shared

Discussed