# American Institute of Mathematical Sciences

doi: 10.3934/jimo.2020077

## Tabu search and simulated annealing for resource-constrained multi-project scheduling to minimize maximal cash flow gap

 1 School of Engineering and Applied Science, Aston University, Birmingham, B4 7ET, United Kingdom 2 School of management, Xi'an Jiaotong University, Xi'an 710049, China

* Corresponding author: Nengmin Wang

Received  May 2019 Revised  November 2019 Published  April 2020

Fund Project: The second author is supported by the National Natural Science Foundation of China grant 71871176. The third author is supported by the National Natural Science Foundation of China grants 71732006 and 71572138

In reality, a contractor may implement multiple projects simultaneously and in such an environment, how to achieve a positive balance between cash outflow and inflow by scheduling is an important problem for the contractor has to tackle. For this fact, this paper investigates a resource-constrained multi-project scheduling problem with the objective of minimizing the contractor's maximal cash flow gap under the constraint of a project deadline and renewable resource. In the paper, we construct a non-linear integer programming optimization model for the studied problem at first. Then, for the NP-hardness of the problem, we design three metaheuristic algorithms to solve the model: tabu search (TS), simulated annealing (SA), and an algorithm comprising both TS and SA (SA-TS). Finally, we conduct a computational experiment on a data set coming from existing literature to evaluate the performance of the developed algorithms and analyze the effects of key parameters on the objective function. Based on the computational results, the following conclusions are drawn: Among the designed algorithms, the SA-TS with an improvement measure is the most promising for solving the problem under study. Some parameters may exert an important effect on the contractor's maximal cash flow gap.

Citation: Yukang He, Zhengwen He, Nengmin Wang. Tabu search and simulated annealing for resource-constrained multi-project scheduling to minimize maximal cash flow gap. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2020077
##### References:

show all references

##### References:
A Numerical Example
The Generated Starting Solution
Process for Updating Current Solution by TS
Operation on a Forbidden Move to Generate a Solution Better than $S^{\rm best}$
Experimental Design
Performance of Algorithms
Effects of Improvement Measure
Effects of Parameters on Objective Function Value
Interactive Effects of Parameters on Objective Function Value
Summary of Reviewed Literature
 The positive cash flow balance is taken as a constraint The positive cash flow balance is taken as an objective The objective is to maximize project profit The objective is to minimize project duration The objective is the optimal trade-off among multiple objectives The activity durations are constants The activity durations are stochastic variables A contractor needs to implement a single project Doersch and Patterson ([8]); Smith-Daniels and Smith-Daniels ([31]); Smith-Daniels et al. ([32]); Özdamar and Dündar ([28]); Özdamar ([29]); He et al. ([18]); Leyman and Vanhoucke ([21]); Leyman and Vanhoucke ([22]); Leyman and Vanhoucke ([23]) Elazouni and Gab-Allah ([10]); Alghazi et al. ([1]); Ali and Elazouni ([2]); Elazouni et al. ([11]); Al-Shihabi and AlDurgam ([4]) Fathi and Afshar ([15]) He et al. ([19]) Ning et al. ([26]); Ning et al. ([27]) A contractor needs to implement multiple projects concurrently Liu and Wang ([24]) Elazouni ([12]) Elazouni and Abido ([13]); Abido and Elazouni ([3]); El-Abbasy et al. ([14]) This paper
 The positive cash flow balance is taken as a constraint The positive cash flow balance is taken as an objective The objective is to maximize project profit The objective is to minimize project duration The objective is the optimal trade-off among multiple objectives The activity durations are constants The activity durations are stochastic variables A contractor needs to implement a single project Doersch and Patterson ([8]); Smith-Daniels and Smith-Daniels ([31]); Smith-Daniels et al. ([32]); Özdamar and Dündar ([28]); Özdamar ([29]); He et al. ([18]); Leyman and Vanhoucke ([21]); Leyman and Vanhoucke ([22]); Leyman and Vanhoucke ([23]) Elazouni and Gab-Allah ([10]); Alghazi et al. ([1]); Ali and Elazouni ([2]); Elazouni et al. ([11]); Al-Shihabi and AlDurgam ([4]) Fathi and Afshar ([15]) He et al. ([19]) Ning et al. ([26]); Ning et al. ([27]) A contractor needs to implement multiple projects concurrently Liu and Wang ([24]) Elazouni ([12]) Elazouni and Abido ([13]); Abido and Elazouni ([3]); El-Abbasy et al. ([14]) This paper
Cash Flows under the $S^{\rm star}$ and $S^{\rm earl}$
 Project 1 Project 2 $t$ Cash outflow Cash inflow Cash outflow Cash inflow $ACO_t$ $ACI_t$ $G_t$ Cash flows under the $S^{\rm star}$ ($G_{\rm max}$ = 8) 0 4 / / / 4 0 4 2 $/$ $/$ 4 $/$ 8 0 8 3 2 5.4 $/$ $/$ 10 5.4 4.6 4 2 $/$ 5 5.1 17 10.5 6.5 5 3 5.4 $/$ $/$ 20 15.9 4.1 7 $/$ $/$ $/$ 2.55 20 18.45 1.55 9 $/$ 6.2 $/$ $/$ 20 24.65 –4.65 10 $/$ $/$ $/$ 6.35 20 31 –11 Cash flows under the $S^{\rm earl}$ ($G_{\rm max}$ = 13) 0 6 $/$ $/$ $/$ 6 0 6 2 $/$ $/$ 7 $/$ 13 0 13 3 2 8.1 $/$ $/$ 15 8.1 6.9 4 $/$ $/$ 2 5.1 17 13.2 3.8 5 3 2.7 $/$ $/$ 20 15.9 4.1 7 $/$ $/$ $/$ 2.55 20 18.45 1.55 8 $/$ $/$ $/$ 6.35 20 24.8 –4.8 9 $/$ 6.2 $/$ $/$ 20 31 –11
 Project 1 Project 2 $t$ Cash outflow Cash inflow Cash outflow Cash inflow $ACO_t$ $ACI_t$ $G_t$ Cash flows under the $S^{\rm star}$ ($G_{\rm max}$ = 8) 0 4 / / / 4 0 4 2 $/$ $/$ 4 $/$ 8 0 8 3 2 5.4 $/$ $/$ 10 5.4 4.6 4 2 $/$ 5 5.1 17 10.5 6.5 5 3 5.4 $/$ $/$ 20 15.9 4.1 7 $/$ $/$ $/$ 2.55 20 18.45 1.55 9 $/$ 6.2 $/$ $/$ 20 24.65 –4.65 10 $/$ $/$ $/$ 6.35 20 31 –11 Cash flows under the $S^{\rm earl}$ ($G_{\rm max}$ = 13) 0 6 $/$ $/$ $/$ 6 0 6 2 $/$ $/$ 7 $/$ 13 0 13 3 2 8.1 $/$ $/$ 15 8.1 6.9 4 $/$ $/$ 2 5.1 17 13.2 3.8 5 3 2.7 $/$ $/$ 20 15.9 4.1 7 $/$ $/$ $/$ 2.55 20 18.45 1.55 8 $/$ $/$ $/$ 6.35 20 24.8 –4.8 9 $/$ 6.2 $/$ $/$ 20 31 –11
Parameter Settings
 Parameter Setting Number of projects, $H$ 3 Number of non-dummy activities in projects, $n^h$–2 20 Network complexity of multiple projects, $C$ LLL, HLL, HHL, HHH, where "L" and "H" represent the network complexity of an individual project. "L" means that the network complexity of the project equals 0.14 while "H" implies it is 0.69 Number of resource types, $K$ 4 Normalized average resource loading factor, $NARLF$ –2, 0, 2 Modified average utilization factor, $MAUF$ 0.8, 1.0, 1.2 Variance in $MAUF$s of different resource, $\sigma^2_{MAUF}$ 0, 0.25 Cost of activities, $c_i$ Randomly selected from U[1, 9] Earned value of activities, $v_i$ $\rho_v\cdot c_i$, where $\rho_v$, which is a special parameter defined for generating $v_i$, is randomly selected from U[1.3, 1.5] Number of milestone activities, $M^h$ 4, 5, 6, where the dummy end activity must be a milestone activity while other milestone activities are randomly selected from all the non-dummy activities Compensation proportion of projects, $\theta^h$ 0.7, 0.8, 0.9 Earliest start time of projects, $EST^h$ Randomly selected from U[1, 5] Deadline of projects, $D^h$ 1.1$\cdot CPL$, 1.3$\cdot CPL$, 1.5$\cdot CPL$, where $CPL$ is the critical path length of the project network without the consideration of renewable resource constraints
 Parameter Setting Number of projects, $H$ 3 Number of non-dummy activities in projects, $n^h$–2 20 Network complexity of multiple projects, $C$ LLL, HLL, HHL, HHH, where "L" and "H" represent the network complexity of an individual project. "L" means that the network complexity of the project equals 0.14 while "H" implies it is 0.69 Number of resource types, $K$ 4 Normalized average resource loading factor, $NARLF$ –2, 0, 2 Modified average utilization factor, $MAUF$ 0.8, 1.0, 1.2 Variance in $MAUF$s of different resource, $\sigma^2_{MAUF}$ 0, 0.25 Cost of activities, $c_i$ Randomly selected from U[1, 9] Earned value of activities, $v_i$ $\rho_v\cdot c_i$, where $\rho_v$, which is a special parameter defined for generating $v_i$, is randomly selected from U[1.3, 1.5] Number of milestone activities, $M^h$ 4, 5, 6, where the dummy end activity must be a milestone activity while other milestone activities are randomly selected from all the non-dummy activities Compensation proportion of projects, $\theta^h$ 0.7, 0.8, 0.9 Earliest start time of projects, $EST^h$ Randomly selected from U[1, 5] Deadline of projects, $D^h$ 1.1$\cdot CPL$, 1.3$\cdot CPL$, 1.5$\cdot CPL$, where $CPL$ is the critical path length of the project network without the consideration of renewable resource constraints
$ARP$(%) of Algorithms under Different Values of Parameters
 Parameter Value $\rm TS^{NIM}$ $\rm TS^{IM}$ $\rm SA^{NIM}$ $\rm SA^{IM}$ SA-$\rm TS^{NIM}$ SA-$\rm TS^{IM}$ $C$ LLL 8.26 3.30 7.36 2.18 6.23 1.46 HLL 7.57 2.63 7.15 2.04 6.10 1.35 HHL 7.13 2.47 6.84 1.91 5.41 1.40 HHH 6.28 1.77 5.97 1.67 5.13 1.23 $NARLF$ –2 7.06 2.36 6.62 1.80 5.55 1.24 0 7.38 2.61 6.70 1.90 5.75 1.39 2 7.49 2.65 7.18 2.16 5.86 1.45 $MAUF$ 0.8 8.20 3.00 7.57 2.46 6.23 1.52 1.0 7.33 2.70 6.74 1.88 5.67 1.35 1.2 6.41 1.93 6.18 1.51 5.26 1.20 $\sigma^2_{MAUF}$ 0 7.13 2.42 6.71 1.89 5.54 1.19 0.25 7.49 2.67 6.94 2.01 5.90 1.53 $D^h$ 1.1$\cdot CPL$ 6.05 1.84 5.85 1.54 5.07 1.13 1.3$\cdot CPL$ 7.25 2.45 6.76 1.96 5.61 1.35 1.5$\cdot CPL$ 8.63 3.33 7.89 2.35 6.47 1.60
 Parameter Value $\rm TS^{NIM}$ $\rm TS^{IM}$ $\rm SA^{NIM}$ $\rm SA^{IM}$ SA-$\rm TS^{NIM}$ SA-$\rm TS^{IM}$ $C$ LLL 8.26 3.30 7.36 2.18 6.23 1.46 HLL 7.57 2.63 7.15 2.04 6.10 1.35 HHL 7.13 2.47 6.84 1.91 5.41 1.40 HHH 6.28 1.77 5.97 1.67 5.13 1.23 $NARLF$ –2 7.06 2.36 6.62 1.80 5.55 1.24 0 7.38 2.61 6.70 1.90 5.75 1.39 2 7.49 2.65 7.18 2.16 5.86 1.45 $MAUF$ 0.8 8.20 3.00 7.57 2.46 6.23 1.52 1.0 7.33 2.70 6.74 1.88 5.67 1.35 1.2 6.41 1.93 6.18 1.51 5.26 1.20 $\sigma^2_{MAUF}$ 0 7.13 2.42 6.71 1.89 5.54 1.19 0.25 7.49 2.67 6.94 2.01 5.90 1.53 $D^h$ 1.1$\cdot CPL$ 6.05 1.84 5.85 1.54 5.07 1.13 1.3$\cdot CPL$ 7.25 2.45 6.76 1.96 5.61 1.35 1.5$\cdot CPL$ 8.63 3.33 7.89 2.35 6.47 1.60
$G_{\rm max}$ under Different Values of Parameters
 Parameter Value $G_{\rm max}$ Parameter Value $G_{\rm max}$ $C$ LLL 66.06 $\sigma^2_{MAUF}$ 0 70.37 HLL 67.34 0.25 66.86 HHL 69.66 $M^h$ 4 81.48 HHH 71.43 5 67.12 $NARLF$ –2 70.63 6 57.26 0 68.51 $\theta^h$ 0.7 83.76 2 66.73 0.8 68.73 $MAUF$ 0.8 65.57 0.9 53.36 1.0 68.44 $D^h$ 1.1$\cdot CPL$ 72.88 1.2 71.86 1.3$\cdot CPL$ 67.66 1.5$\cdot CPL$ 65.33
 Parameter Value $G_{\rm max}$ Parameter Value $G_{\rm max}$ $C$ LLL 66.06 $\sigma^2_{MAUF}$ 0 70.37 HLL 67.34 0.25 66.86 HHL 69.66 $M^h$ 4 81.48 HHH 71.43 5 67.12 $NARLF$ –2 70.63 6 57.26 0 68.51 $\theta^h$ 0.7 83.76 2 66.73 0.8 68.73 $MAUF$ 0.8 65.57 0.9 53.36 1.0 68.44 $D^h$ 1.1$\cdot CPL$ 72.88 1.2 71.86 1.3$\cdot CPL$ 67.66 1.5$\cdot CPL$ 65.33
$G_{\rm max}$ under Combinations of Different Values of Parameters
 $MAUF$ $C$ $G_{\rm max}$ $MAUF$ $NARLF$ $G_{\rm max}$ $MAUF$ $\sigma^2_{MAUF}$ $G_{\rm max}$ $MAUF$ $D^h$ $G_{\rm max}$ 0.8 LLL 61.8 0.8 –2 66.96 0.8 0 66.67 0.8 1.1$\cdot CPL$ 71.33 HLL 64.29 0 65.46 0.25 64.46 1.3$\cdot CPL$ 64.61 HHL 66.6 2 64.28 1.0 0 69.99 1.5$\cdot CPL$ 60.78 HHH 69.58 1.0 –2 70.3 0.25 66.88 1.0 1.1$\cdot CPL$ 72.2 1.0 LLL 66.08 0 68.33 1.2 0 74.46 1.3$\cdot CPL$ 67.46 HLL 67.16 2 66.7 0.25 69.25 1.5$\cdot CPL$ 65.65 HHL 69.48 1.2 –2 74.62 1.2 1.1$\cdot CPL$ 75.12 HHH 71.05 0 71.75 1.3$\cdot CPL$ 70.9 1.2 LLL 70.3 2 69.21 1.5$\cdot CPL$ 69.57 HLL 70.58 HHL 72.9 HHH 73.67
 $MAUF$ $C$ $G_{\rm max}$ $MAUF$ $NARLF$ $G_{\rm max}$ $MAUF$ $\sigma^2_{MAUF}$ $G_{\rm max}$ $MAUF$ $D^h$ $G_{\rm max}$ 0.8 LLL 61.8 0.8 –2 66.96 0.8 0 66.67 0.8 1.1$\cdot CPL$ 71.33 HLL 64.29 0 65.46 0.25 64.46 1.3$\cdot CPL$ 64.61 HHL 66.6 2 64.28 1.0 0 69.99 1.5$\cdot CPL$ 60.78 HHH 69.58 1.0 –2 70.3 0.25 66.88 1.0 1.1$\cdot CPL$ 72.2 1.0 LLL 66.08 0 68.33 1.2 0 74.46 1.3$\cdot CPL$ 67.46 HLL 67.16 2 66.7 0.25 69.25 1.5$\cdot CPL$ 65.65 HHL 69.48 1.2 –2 74.62 1.2 1.1$\cdot CPL$ 75.12 HHH 71.05 0 71.75 1.3$\cdot CPL$ 70.9 1.2 LLL 70.3 2 69.21 1.5$\cdot CPL$ 69.57 HLL 70.58 HHL 72.9 HHH 73.67
 [1] Jingwen Zhang, Wanjun Liu, Wanlin Liu. An efficient genetic algorithm for decentralized multi-project scheduling with resource transfers. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020140 [2] T. W. Leung, Chi Kin Chan, Marvin D. Troutt. A mixed simulated annealing-genetic algorithm approach to the multi-buyer multi-item joint replenishment problem: advantages of meta-heuristics. Journal of Industrial & Management Optimization, 2008, 4 (1) : 53-66. doi: 10.3934/jimo.2008.4.53 [3] Y. K. Lin, C. S. Chong. A tabu search algorithm to minimize total weighted tardiness for the job shop scheduling problem. Journal of Industrial & Management Optimization, 2016, 12 (2) : 703-717. doi: 10.3934/jimo.2016.12.703 [4] Adel Dabah, Ahcene Bendjoudi, Abdelhakim AitZai. An efficient Tabu Search neighborhood based on reconstruction strategy to solve the blocking job shop scheduling problem. Journal of Industrial & Management Optimization, 2017, 13 (4) : 2015-2031. doi: 10.3934/jimo.2017029 [5] Mingyong Lai, Xiaojiao Tong. A metaheuristic method for vehicle routing problem based on improved ant colony optimization and Tabu search. Journal of Industrial & Management Optimization, 2012, 8 (2) : 469-484. doi: 10.3934/jimo.2012.8.469 [6] Tao Zhang, Yue-Jie Zhang, Qipeng P. Zheng, P. M. Pardalos. A hybrid particle swarm optimization and tabu search algorithm for order planning problems of steel factories based on the Make-To-Stock and Make-To-Order management architecture. Journal of Industrial & Management Optimization, 2011, 7 (1) : 31-51. doi: 10.3934/jimo.2011.7.31 [7] Dieudonné Nijimbere, Songzheng Zhao, Xunhao Gu, Moses Olabhele Esangbedo, Nyiribakwe Dominique. Tabu search guided by reinforcement learning for the max-mean dispersion problem. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020115 [8] Lan Luo, Zhe Zhang, Yong Yin. Simulated annealing and genetic algorithm based method for a bi-level seru loading problem with worker assignment in seru production systems. Journal of Industrial & Management Optimization, 2019  doi: 10.3934/jimo.2019134 [9] Jian Xiong, Yingwu Chen, Zhongbao Zhou. Resilience analysis for project scheduling with renewable resource constraint and uncertain activity durations. Journal of Industrial & Management Optimization, 2016, 12 (2) : 719-737. doi: 10.3934/jimo.2016.12.719 [10] Abdel-Rahman Hedar, Ahmed Fouad Ali, Taysir Hassan Abdel-Hamid. Genetic algorithm and Tabu search based methods for molecular 3D-structure prediction. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 191-209. doi: 10.3934/naco.2011.1.191 [11] Cheng-Ta Yeh, Yi-Kuei Lin. Component allocation cost minimization for a multistate computer network subject to a reliability threshold using tabu search. Journal of Industrial & Management Optimization, 2016, 12 (1) : 141-167. doi: 10.3934/jimo.2016.12.141 [12] Jianjun Liu, Min Zeng, Yifan Ge, Changzhi Wu, Xiangyu Wang. Improved Cuckoo Search algorithm for numerical function optimization. Journal of Industrial & Management Optimization, 2020, 16 (1) : 103-115. doi: 10.3934/jimo.2018142 [13] Emiliano Cristiani, Elisa Iacomini. An interface-free multi-scale multi-order model for traffic flow. Discrete & Continuous Dynamical Systems - B, 2019, 24 (11) : 6189-6207. doi: 10.3934/dcdsb.2019135 [14] Zhe Zhang, Jiuping Xu. Bi-level multiple mode resource-constrained project scheduling problems under hybrid uncertainty. Journal of Industrial & Management Optimization, 2016, 12 (2) : 565-593. doi: 10.3934/jimo.2016.12.565 [15] Xiaoxiao Yuan, Jing Liu, Xingxing Hao. A moving block sequence-based evolutionary algorithm for resource investment project scheduling problems. Big Data & Information Analytics, 2017, 2 (1) : 39-58. doi: 10.3934/bdia.2017007 [16] Ondrej Budáč, Michael Herrmann, Barbara Niethammer, Andrej Spielmann. On a model for mass aggregation with maximal size. Kinetic & Related Models, 2011, 4 (2) : 427-439. doi: 10.3934/krm.2011.4.427 [17] Radu C. Cascaval, Ciro D'Apice, Maria Pia D'Arienzo, Rosanna Manzo. Flow optimization in vascular networks. Mathematical Biosciences & Engineering, 2017, 14 (3) : 607-624. doi: 10.3934/mbe.2017035 [18] Behrouz Kheirfam, Morteza Moslemi. On the extension of an arc-search interior-point algorithm for semidefinite optimization. Numerical Algebra, Control & Optimization, 2018, 8 (2) : 261-275. doi: 10.3934/naco.2018015 [19] Mohamed A. Tawhid, Ahmed F. Ali. An effective hybrid firefly algorithm with the cuckoo search for engineering optimization problems. Mathematical Foundations of Computing, 2018, 1 (4) : 349-368. doi: 10.3934/mfc.2018017 [20] Kien Ming Ng, Trung Hieu Tran. A parallel water flow algorithm with local search for solving the quadratic assignment problem. Journal of Industrial & Management Optimization, 2019, 15 (1) : 235-259. doi: 10.3934/jimo.2018041

2019 Impact Factor: 1.366

## Tools

Article outline

Figures and Tables