American Institute of Mathematical Sciences

Advanced
doi: 10.3934/jimo.2020140

An efficient genetic algorithm for decentralized multi-project scheduling with resource transfers

Jingwen Zhang , , Wanjun Liu and  Wanlin Liu

School of Management, Northwestern Polytechnical University, Xi’an 710072, Shaanxi, China

* Corresponding author: Jingwen Zhang

Received  January 2020 Revised  July 2020 Published  September 2020

This paper investigates the decentralized resource-constrained multi-project scheduling problem with transfer times (DRCMPSPTT) in which the transfer times of the global resources among different projects are assumed to be sequence-independent, while transfers of local resources take no time within a project. First, two decision variables ($ {y_{ijg}} $ and $ {w_{ijg}} $) are adopted to express the transition state of global resources between projects. $ {y_{ijg}} $ (takes a value of 0 or 1) represents whether activity i transfers global resource g to activity j; accordingly, the transferred quantity is denoted as $ {w_{ijg}} $. Then, we construct an integer linear model with the goal of minimizing the average project delay for the DRCMPSPTT. Second, an adaptive genetic algorithm (GA) is developed to solve the DRCMPSPTT. To gain the schedules for the DRCMPSPTT, the traditional serial and parallel scheduling generation schemes (SGSs) are modified to combine with different resource transfer rules and to design multiple decoding schemes. Third, the numerical experiments are implemented to analyse the effects of eight decoding schemes, and we found that the scheme comprising the parallel SGS and maxRS rule can make the GA work the best; furthermore, the effectiveness of the GA_maxRS (GA embedded with the best scheme) is demonstrated by solving some instances with different sizes.

Keywords: Decentralized multi-project scheduling, resource transfer times, genetic algorithm, scheduling generation schemes, resource transfer rules.
Mathematics Subject Classification: Primary: 90B35, 90C11.
Citation: Jingwen Zhang, Wanjun Liu, Wanlin Liu. An efficient genetic algorithm for decentralized multi-project scheduling with resource transfers. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2020140
References:
[1]

S. Adhau, M. L. Mittal and A. Mittal, A multi-agent system for decentralized multi project scheduling with resource transfers, International Journal of Production Economics, 146 (2013), 646-661.  doi: 10.1016/j.ijpe.2013.08.013.  Google Scholar

[2]

S. Adhau, M. L. Mittal and A. Mittal, A multi-agent system for distributed multi-project scheduling: An auction-based negotiation approach, Engineering Applications of Artificial Intelligence, 25 (2012), 1738-1751.  doi: 10.1016/j.engappai.2011.12.003.  Google Scholar

[3]

B. Afshar-Nadjafi and M. Majlesi, Resource constrained project scheduling problem with setup times after preemptive processes, Computers and Chemical Engineering, 69 (2014), 16-25.  doi: 10.1016/j.compchemeng.2014.06.012.  Google Scholar

[4]

C. Artigues, P. Michelon and S. Reusser, Insertion techniques for static and dynamic resource-constrained project scheduling, European Journal of Operational Research, 149 (2003), 249-267.  doi: 10.1016/S0377-2217(02)00758-0.  Google Scholar

[5]

D. Bedworth and J. Bailey, Integrated Production Control Systems Management, Analysis, Design, 2$^nd$ edition, John Wiley & Sons, Inc., New York, 1999. Google Scholar

[6]

C. Bierwirth, D. Mattfeld and H. Kopfer, On permutation representations for scheduling problems, in Parallel Problem Solving from Nature, Lecture Notes in Computer Science, 1996,310–318. doi: 10.1007/3-540-61723-X_995.  Google Scholar

[7]

P. Brucker, S. Knust, A. Schoo and O. Thiele, A branch and bound algorithm for the resource-constrained project scheduling problem, European Journal of Operational Research, 107 (1998), 272-288.  doi: 10.1016/S0377-2217(97)00335-4.  Google Scholar

[8]

Z. Cai and X. Li, A hybrid genetic algorithm for resource-constrained multi-project scheduling problem with resource transfer time, IEEE International Conference on Automation Science and Engineering, Seoul, 2012,569–574. doi: 10.1109/CoASE.2012.6386457.  Google Scholar

[9]

G. Confessore, S. Giordani and S. Rismondo, A market-based multi-agent system model for decentralized multi–project scheduling, Annals of Operations Research, 150 (2007), 115-135.  doi: 10.1007/s10479-006-0158-9.  Google Scholar

[10]

E. W. Davis, Project network summary measures constrained resource scheduling, AIIE Transactions, 7 (1975), 132-142.  doi: 10.1080/05695557508974995.  Google Scholar

[11]

E. L. Demeulemeester and W. S. Herroelen, An efficient optimal solution procedure for the preemptive resource-constrained project scheduling problem, European Journal of Operational Research, 90 (1996), 334-348.  doi: 10.1016/0377-2217(95)00358-4.  Google Scholar

[12]

L. Djerid, M. C. Portman and P. Villon, Performance analysis of permutation cross-over genetic operators, Journal of Decision Systems, 5 (1996), 131-140.  doi: 10.1080/12460125.1996.10511679.  Google Scholar

[13]

S. Hartmann and R. Kolisch, Experimental evaluation of state-of-the-art heuristics for resource-constrained project scheduling problem, European Journal of Operational Research, 127 (2000), 394-407.  doi: 10.1016/S0377-2217(99)00485-3.  Google Scholar

[14] J. B. Holland and J. H. Holland, Adaption in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, Mich., 1975.   Google Scholar
[15]

J. Homberger, A multi-agent system for the decentralized resource constrained multi-project scheduling problem, International Transactions in Operational Research, 14 (2007), 565-589.  doi: 10.1111/j.1475-3995.2007.00614.x.  Google Scholar

[16]

J. Homberger, A (${\mu}$, ${\lambda}$)-coordination mechanism for agent-based multi-project scheduling, OR Spectrum, 34 (2012), 107-132.  doi: 10.1007/s00291-009-0178-3.  Google Scholar

[17]

R. Jans and Z. Degraeve, Modeling industrial lot sizing problems: A review, International Journal of Production Research, 46 (2008), 1619-1643.  doi: 10.1080/00207540600902262.  Google Scholar

[18]

R. L. Kadri and F. F. Boctor, An efficient genetic algorithm to solve the resource-constrained project scheduling problem with transfer times: The single mode case, European Journal of Operational Research, 265 (2018), 454-–462. doi: 10.1016/j.ejor.2017.07.027.  Google Scholar

[19]

J. E. Kelley, The critical-path method: Resources planning and scheduling, Industrial Scheduling, 13 (1963), 347365. Google Scholar

[20]

S. Khalilpourazari, B. Naderi and S. Khalilpourazary, Multi-objective stochastic fractal search: A powerful algorithm for solving complex multi-objective optimization problems, Soft Computing, 24 (2020), 3037–-3066. doi: 10.1007/s00500-019-04080-6.  Google Scholar

[21]

S. Khalilpourazari and S. H. R. Pasandideh, Modeling and optimization of multi-item multi-constrained EOQ model for growing items, Knowledge-Based Systems, 164 (2019), 150-162.  doi: 10.1016/j.knosys.2018.10.032.  Google Scholar

[22]

S. Khalilpourazari and S. H. R. Pasandideh, Sine-cosine crow search algorithm: Theory and applications, Neural Computing and Applications, 32 (2019), 7725–-7742. doi: 10.1007/s00521-019-04530-0.  Google Scholar

[23]

R. Kolisch, Project scheduling with setup times, in Project Scheduling Under Resource Constraints, Production and Logistics, Physica, Heidelberg, 1995,177–185. doi: 10.1007/978-3-642-50296-5_8.  Google Scholar

[24]

R. Kolisch and S. Hartmann, Heuristic algorithms for solving the resource-constrained project scheduling problem: Classification and computational analysis, in Project Scheduling, International Series in Operations Research & Management Science, Springer, Boston, 1999,147–178. doi: 10.1007/978-1-4615-5533-9_7.  Google Scholar

[25]

R. Kolisch and A. Sprecher, PSPLIB–A project scheduling library, European Journal of Operation Research, 96 (1996), 205-216.   Google Scholar

[26]

D. Kruger and A. Scholl, A heuristic solution framework for the resource constrained (multi-)project scheduling problem with sequence-dependent transfer times, European Journal of Operation Research, 197 (2009), 492-508.  doi: 10.1016/j.ejor.2008.07.036.  Google Scholar

[27]

D. Kruger and A. Scholl, Managing and modelling general resource transfers in (multi-)project scheduling, OR Spectrum, 32 (2010), 369-394.  doi: 10.1007/s00291-008-0144-5.  Google Scholar

[28]

C. J. Liao, C. W. Chao and L. C. Chen, An improved heuristic for parallel machine weighted flowtime scheduling with family set-up times, Computers and Mathematics with Applications, 63 (2012), 110-117.  doi: 10.1016/j.camwa.2011.10.077.  Google Scholar

[29]

A. Lova and P. Tormos, Analysis of scheduling schemes and heuristic rules performance in resource-constrained multiproject scheduling, Annals of Operations Research, 102 (2001), 263-286.  doi: 10.1023/A:1010966401888.  Google Scholar

[30]

A. Lova, P. Tormos, M. Cervantes and F. Barber, An efficient hybrid genetic algorithm for scheduling projects with resource constraints and multiple execution modes, International Journal of Production Economics, 117 (2009), 302-316.  doi: 10.1016/j.ijpe.2008.11.002.  Google Scholar

[31]

D. Merkle, M. Middendorf and H. Schmeck, Ant colony optimization for resource-constrained project scheduling, IEEE Transactions on Evolutionary Computation, 6 (2002), 333-346.  doi: 10.1109/TEVC.2002.802450.  Google Scholar

[32]

M. Mika, G. Waligra and J. Weglarz, Tabu search for multi-mode resource-constrained project scheduling with schedule-dependent setup times, European Journal of Operational Research, 187 (2008), 1238-1250.  doi: 10.1016/j.ejor.2006.06.069.  Google Scholar

[33]

M. L. Mittal and A. Kanda, Scheduling of multiple projects with resource transfers, International Journal of Mathematics in Operational Research, 1 (2009), 303-325.  doi: 10.1504/IJMOR.2009.024288.  Google Scholar

[34]

K. Moumene and J. A. Ferland, Activity list representation for a generalization of the resource-constrained project scheduling problem, European Journal of Operational Research, 199 (2009), 46-54.  doi: 10.1016/j.ejor.2008.10.030.  Google Scholar

[35]

M. S. Nagano, A. A. Silva and L. A. N. Lorena, A new evolutionary clustering search for a no-wait flow shop problem with set-up times, Engineering Applications of Artificial Intelligence, 25 (2012), 1114-1120.  doi: 10.1016/j.engappai.2012.05.017.  Google Scholar

[36]

K. Neumann, C. Schwindt and J. Zimmermann, Project Scheduling with Time Windows and Scarce Resources, Springer-Verlag, Berlin, 2002. doi: 10.1007/978-3-540-24800-2.  Google Scholar

[37]

S. H. R. Pasandideh and S. Khalilpourazari, Sine cosine crow search algorithm: A powerful hybrid meta heuristic for global optimization, preprint, arXiv: 1801.08485. Google Scholar

[38]

J. Poppenborg and S. Knust, A flow-based tabu search algorithm for the RCPSP with transfer times, OR Spectrum, 38 (2016), 305-334.  doi: 10.1007/s00291-015-0402-2.  Google Scholar

[39]

V. Roshanaei, B. Naderi, F. Jolai and M. Khalili, A variable neighborhood search for job shop scheduling with set-up times to minimize makespan, Future Generation Computer Systems, 25 (2009), 654-661.  doi: 10.1016/j.future.2009.01.004.  Google Scholar

[40]

M. Rostami, M. Bagherpour, M. M. Mazdeh and A. Makui, Resource Pool Location for Periodic Services in Decentralized Multi-Project Scheduling Problems, Journal of Computing in Civil Engineering, 31 (2017), 04017022. doi: 10.1061/(ASCE)CP.1943-5487.0000671.  Google Scholar

[41]

V. Valls, F. Ballestin and M. S. Quintanilla, A hybrid genetic algorithm for the RCPSP, Technical report, Department of Statistics and Operations Research, University of Valencia, 2003. Google Scholar

[42]

V. Valls, F. Ballestin and M. S. Quintanilla, Justification and RCPSP: A technique that pays, European Journal of Operational Research, 165 (2005), 375-386.  doi: 10.1016/j.ejor.2004.04.008.  Google Scholar

[43]

M. Vanhoucke, Setup times and fast tracking in resource-constrained project scheduling, Computers & Industrial Engineering, 54 (2008), 1062-1070.  doi: 10.1016/j.cie.2007.11.008.  Google Scholar

[44]

K. K. Yang and C. C. Sum, A comparison of resource allocation and activity scheduling rules in a dynamic multi-project environment, Journal of Operation Management, 11 (1993), 207-218.  doi: 10.1016/0272-6963(93)90023-I.  Google Scholar

[45]

K. K. Yang and C. C. Sum, An evaluation of due date, resource allocation, project release, and activity scheduling rules in a multi project environment, European Journal of Operational Research, 103 (1997), 139-154.   Google Scholar

show all references

References:
[1]

S. Adhau, M. L. Mittal and A. Mittal, A multi-agent system for decentralized multi project scheduling with resource transfers, International Journal of Production Economics, 146 (2013), 646-661.  doi: 10.1016/j.ijpe.2013.08.013.  Google Scholar

[2]

S. Adhau, M. L. Mittal and A. Mittal, A multi-agent system for distributed multi-project scheduling: An auction-based negotiation approach, Engineering Applications of Artificial Intelligence, 25 (2012), 1738-1751.  doi: 10.1016/j.engappai.2011.12.003.  Google Scholar

[3]

B. Afshar-Nadjafi and M. Majlesi, Resource constrained project scheduling problem with setup times after preemptive processes, Computers and Chemical Engineering, 69 (2014), 16-25.  doi: 10.1016/j.compchemeng.2014.06.012.  Google Scholar

[4]

C. Artigues, P. Michelon and S. Reusser, Insertion techniques for static and dynamic resource-constrained project scheduling, European Journal of Operational Research, 149 (2003), 249-267.  doi: 10.1016/S0377-2217(02)00758-0.  Google Scholar

[5]

D. Bedworth and J. Bailey, Integrated Production Control Systems Management, Analysis, Design, 2$^nd$ edition, John Wiley & Sons, Inc., New York, 1999. Google Scholar

[6]

C. Bierwirth, D. Mattfeld and H. Kopfer, On permutation representations for scheduling problems, in Parallel Problem Solving from Nature, Lecture Notes in Computer Science, 1996,310–318. doi: 10.1007/3-540-61723-X_995.  Google Scholar

[7]

P. Brucker, S. Knust, A. Schoo and O. Thiele, A branch and bound algorithm for the resource-constrained project scheduling problem, European Journal of Operational Research, 107 (1998), 272-288.  doi: 10.1016/S0377-2217(97)00335-4.  Google Scholar

[8]

Z. Cai and X. Li, A hybrid genetic algorithm for resource-constrained multi-project scheduling problem with resource transfer time, IEEE International Conference on Automation Science and Engineering, Seoul, 2012,569–574. doi: 10.1109/CoASE.2012.6386457.  Google Scholar

[9]

G. Confessore, S. Giordani and S. Rismondo, A market-based multi-agent system model for decentralized multi–project scheduling, Annals of Operations Research, 150 (2007), 115-135.  doi: 10.1007/s10479-006-0158-9.  Google Scholar

[10]

E. W. Davis, Project network summary measures constrained resource scheduling, AIIE Transactions, 7 (1975), 132-142.  doi: 10.1080/05695557508974995.  Google Scholar

[11]

E. L. Demeulemeester and W. S. Herroelen, An efficient optimal solution procedure for the preemptive resource-constrained project scheduling problem, European Journal of Operational Research, 90 (1996), 334-348.  doi: 10.1016/0377-2217(95)00358-4.  Google Scholar

[12]

L. Djerid, M. C. Portman and P. Villon, Performance analysis of permutation cross-over genetic operators, Journal of Decision Systems, 5 (1996), 131-140.  doi: 10.1080/12460125.1996.10511679.  Google Scholar

[13]

S. Hartmann and R. Kolisch, Experimental evaluation of state-of-the-art heuristics for resource-constrained project scheduling problem, European Journal of Operational Research, 127 (2000), 394-407.  doi: 10.1016/S0377-2217(99)00485-3.  Google Scholar

[14] J. B. Holland and J. H. Holland, Adaption in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, Mich., 1975.   Google Scholar
[15]

J. Homberger, A multi-agent system for the decentralized resource constrained multi-project scheduling problem, International Transactions in Operational Research, 14 (2007), 565-589.  doi: 10.1111/j.1475-3995.2007.00614.x.  Google Scholar

[16]

J. Homberger, A (${\mu}$, ${\lambda}$)-coordination mechanism for agent-based multi-project scheduling, OR Spectrum, 34 (2012), 107-132.  doi: 10.1007/s00291-009-0178-3.  Google Scholar

[17]

R. Jans and Z. Degraeve, Modeling industrial lot sizing problems: A review, International Journal of Production Research, 46 (2008), 1619-1643.  doi: 10.1080/00207540600902262.  Google Scholar

[18]

R. L. Kadri and F. F. Boctor, An efficient genetic algorithm to solve the resource-constrained project scheduling problem with transfer times: The single mode case, European Journal of Operational Research, 265 (2018), 454-–462. doi: 10.1016/j.ejor.2017.07.027.  Google Scholar

[19]

J. E. Kelley, The critical-path method: Resources planning and scheduling, Industrial Scheduling, 13 (1963), 347365. Google Scholar

[20]

S. Khalilpourazari, B. Naderi and S. Khalilpourazary, Multi-objective stochastic fractal search: A powerful algorithm for solving complex multi-objective optimization problems, Soft Computing, 24 (2020), 3037–-3066. doi: 10.1007/s00500-019-04080-6.  Google Scholar

[21]

S. Khalilpourazari and S. H. R. Pasandideh, Modeling and optimization of multi-item multi-constrained EOQ model for growing items, Knowledge-Based Systems, 164 (2019), 150-162.  doi: 10.1016/j.knosys.2018.10.032.  Google Scholar

[22]

S. Khalilpourazari and S. H. R. Pasandideh, Sine-cosine crow search algorithm: Theory and applications, Neural Computing and Applications, 32 (2019), 7725–-7742. doi: 10.1007/s00521-019-04530-0.  Google Scholar

[23]

R. Kolisch, Project scheduling with setup times, in Project Scheduling Under Resource Constraints, Production and Logistics, Physica, Heidelberg, 1995,177–185. doi: 10.1007/978-3-642-50296-5_8.  Google Scholar

[24]

R. Kolisch and S. Hartmann, Heuristic algorithms for solving the resource-constrained project scheduling problem: Classification and computational analysis, in Project Scheduling, International Series in Operations Research & Management Science, Springer, Boston, 1999,147–178. doi: 10.1007/978-1-4615-5533-9_7.  Google Scholar

[25]

R. Kolisch and A. Sprecher, PSPLIB–A project scheduling library, European Journal of Operation Research, 96 (1996), 205-216.   Google Scholar

[26]

D. Kruger and A. Scholl, A heuristic solution framework for the resource constrained (multi-)project scheduling problem with sequence-dependent transfer times, European Journal of Operation Research, 197 (2009), 492-508.  doi: 10.1016/j.ejor.2008.07.036.  Google Scholar

[27]

D. Kruger and A. Scholl, Managing and modelling general resource transfers in (multi-)project scheduling, OR Spectrum, 32 (2010), 369-394.  doi: 10.1007/s00291-008-0144-5.  Google Scholar

[28]

C. J. Liao, C. W. Chao and L. C. Chen, An improved heuristic for parallel machine weighted flowtime scheduling with family set-up times, Computers and Mathematics with Applications, 63 (2012), 110-117.  doi: 10.1016/j.camwa.2011.10.077.  Google Scholar

[29]

A. Lova and P. Tormos, Analysis of scheduling schemes and heuristic rules performance in resource-constrained multiproject scheduling, Annals of Operations Research, 102 (2001), 263-286.  doi: 10.1023/A:1010966401888.  Google Scholar

[30]

A. Lova, P. Tormos, M. Cervantes and F. Barber, An efficient hybrid genetic algorithm for scheduling projects with resource constraints and multiple execution modes, International Journal of Production Economics, 117 (2009), 302-316.  doi: 10.1016/j.ijpe.2008.11.002.  Google Scholar

[31]

D. Merkle, M. Middendorf and H. Schmeck, Ant colony optimization for resource-constrained project scheduling, IEEE Transactions on Evolutionary Computation, 6 (2002), 333-346.  doi: 10.1109/TEVC.2002.802450.  Google Scholar

[32]

M. Mika, G. Waligra and J. Weglarz, Tabu search for multi-mode resource-constrained project scheduling with schedule-dependent setup times, European Journal of Operational Research, 187 (2008), 1238-1250.  doi: 10.1016/j.ejor.2006.06.069.  Google Scholar

[33]

M. L. Mittal and A. Kanda, Scheduling of multiple projects with resource transfers, International Journal of Mathematics in Operational Research, 1 (2009), 303-325.  doi: 10.1504/IJMOR.2009.024288.  Google Scholar

[34]

K. Moumene and J. A. Ferland, Activity list representation for a generalization of the resource-constrained project scheduling problem, European Journal of Operational Research, 199 (2009), 46-54.  doi: 10.1016/j.ejor.2008.10.030.  Google Scholar

[35]

M. S. Nagano, A. A. Silva and L. A. N. Lorena, A new evolutionary clustering search for a no-wait flow shop problem with set-up times, Engineering Applications of Artificial Intelligence, 25 (2012), 1114-1120.  doi: 10.1016/j.engappai.2012.05.017.  Google Scholar

[36]

K. Neumann, C. Schwindt and J. Zimmermann, Project Scheduling with Time Windows and Scarce Resources, Springer-Verlag, Berlin, 2002. doi: 10.1007/978-3-540-24800-2.  Google Scholar

[37]

S. H. R. Pasandideh and S. Khalilpourazari, Sine cosine crow search algorithm: A powerful hybrid meta heuristic for global optimization, preprint, arXiv: 1801.08485. Google Scholar

[38]

J. Poppenborg and S. Knust, A flow-based tabu search algorithm for the RCPSP with transfer times, OR Spectrum, 38 (2016), 305-334.  doi: 10.1007/s00291-015-0402-2.  Google Scholar

[39]

V. Roshanaei, B. Naderi, F. Jolai and M. Khalili, A variable neighborhood search for job shop scheduling with set-up times to minimize makespan, Future Generation Computer Systems, 25 (2009), 654-661.  doi: 10.1016/j.future.2009.01.004.  Google Scholar

[40]

M. Rostami, M. Bagherpour, M. M. Mazdeh and A. Makui, Resource Pool Location for Periodic Services in Decentralized Multi-Project Scheduling Problems, Journal of Computing in Civil Engineering, 31 (2017), 04017022. doi: 10.1061/(ASCE)CP.1943-5487.0000671.  Google Scholar

[41]

V. Valls, F. Ballestin and M. S. Quintanilla, A hybrid genetic algorithm for the RCPSP, Technical report, Department of Statistics and Operations Research, University of Valencia, 2003. Google Scholar

[42]

V. Valls, F. Ballestin and M. S. Quintanilla, Justification and RCPSP: A technique that pays, European Journal of Operational Research, 165 (2005), 375-386.  doi: 10.1016/j.ejor.2004.04.008.  Google Scholar

[43]

M. Vanhoucke, Setup times and fast tracking in resource-constrained project scheduling, Computers & Industrial Engineering, 54 (2008), 1062-1070.  doi: 10.1016/j.cie.2007.11.008.  Google Scholar

[44]

K. K. Yang and C. C. Sum, A comparison of resource allocation and activity scheduling rules in a dynamic multi-project environment, Journal of Operation Management, 11 (1993), 207-218.  doi: 10.1016/0272-6963(93)90023-I.  Google Scholar

[45]

K. K. Yang and C. C. Sum, An evaluation of due date, resource allocation, project release, and activity scheduling rules in a multi project environment, European Journal of Operational Research, 103 (1997), 139-154.   Google Scholar

Figure 1.  An example of a DRCMPSPTT
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  Renumbered network of the example
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  Individual representation for the DRCMPSPTT
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 4.  A precedence feasible AL of the multi-project example
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 5.  The adaptive serial SGS with transfer times
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 6.  The adaptive parallel SGS with transfer times
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 7.  Two-point crossover operator
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 8.  Average APDs obtained by different schemes
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 9.  (a) APDs obtained by the two schemes, and (b) the deviation of the APDs obtained by the two schemes varies as $ UF_{AV} $ increases
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 10.  (a) The three types PREs, and (b) computation times of the solution methods
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 11.  (a) mean value of the APD obtained by different methods, and (b) The three types PREs, (c) The $ PRE_{_GA} $ of the 12 problem sets, and (d) The change trend of $ PRE_{_GA} $ as $ UF_{AV} $ increases
Figure Options

Download full-size image

Download as PowerPoint slide

Table 1.  Literature review of the project scheduling with transfer 09:49:34
Authors Project Objective Transfer times Algorithm
Single Multi- Decentralized multi- Makespan Others sequence-dependent sequence-independent
Kolisch (1995) $ \surd $ $ \surd $ $ \surd $ Parallel scheme based heuristic
Neumann et al (2003) $ \surd $ $ \surd $ $ \surd $ Branch-and-bound
Vanhoucke(2008) $ \surd $ $ \surd $ $ \surd $ Branch-and-bound
Mika (2008) $ \surd $ $ \surd $ $ \surd $ Tabu search
Afshar-Nadjafi et al (2014) $ \surd $ $ \surd $ $ \surd $ GA
Poppenborg(2016) $ \surd $ $ \surd $ $ \surd $ Tabu search
Kadri and Boctor (2017) $ \surd $ $ \surd $ $ \surd $ GA
Yang and Sum(1993, 1997) $ \surd $ $ \surd $ $ \surd $ Computational experiment
Mittal and Kanda (2009) $ \surd $ $ \surd $ Cost $ \surd $ Heuristics
Kruger and Scholl(2009, 2010) $ \surd $ $ \surd $ $ \surd $ Cost $ \surd $ Priority-rule based heuristic
Cai and Li(2012) $ \surd $ APD $ \surd $ Hybrid GA
Adhau and Mittal(2013) $ \surd $ APD $ \surd $ DMAS/RIA
This research $ \surd $ APD $ \surd $ GA
Table Options

Download as excel

Authors Project Objective Transfer times Algorithm
Single Multi- Decentralized multi- Makespan Others sequence-dependent sequence-independent
Kolisch (1995) $ \surd $ $ \surd $ $ \surd $ Parallel scheme based heuristic
Neumann et al (2003) $ \surd $ $ \surd $ $ \surd $ Branch-and-bound
Vanhoucke(2008) $ \surd $ $ \surd $ $ \surd $ Branch-and-bound
Mika (2008) $ \surd $ $ \surd $ $ \surd $ Tabu search
Afshar-Nadjafi et al (2014) $ \surd $ $ \surd $ $ \surd $ GA
Poppenborg(2016) $ \surd $ $ \surd $ $ \surd $ Tabu search
Kadri and Boctor (2017) $ \surd $ $ \surd $ $ \surd $ GA
Yang and Sum(1993, 1997) $ \surd $ $ \surd $ $ \surd $ Computational experiment
Mittal and Kanda (2009) $ \surd $ $ \surd $ Cost $ \surd $ Heuristics
Kruger and Scholl(2009, 2010) $ \surd $ $ \surd $ $ \surd $ Cost $ \surd $ Priority-rule based heuristic
Cai and Li(2012) $ \surd $ APD $ \surd $ Hybrid GA
Adhau and Mittal(2013) $ \surd $ APD $ \surd $ DMAS/RIA
This research $ \surd $ APD $ \surd $ GA
Table 2.  Resource transfer rules
Transfer rules Priority value $ \pi_i $ Extremum
minTT $ \pi_i = \Delta_{ijg} $ min
minGAP $ \pi_i = gap_{ijg} = t - (F_i + \Delta_{ijg}) $ min
maxRS $ \pi_i = v_{ig} = u_{ig} - \sum\limits_{l \in PS} {w_{ilg}} $ max
minRS $ \pi_i = v_{ig} = u_{ig} - \sum\limits_{l \in PS} {w_{ilg}} $ min
Table Options

Download as excel

Transfer rules Priority value $ \pi_i $ Extremum
minTT $ \pi_i = \Delta_{ijg} $ min
minGAP $ \pi_i = gap_{ijg} = t - (F_i + \Delta_{ijg}) $ min
maxRS $ \pi_i = v_{ig} = u_{ig} - \sum\limits_{l \in PS} {w_{ilg}} $ max
minRS $ \pi_i = v_{ig} = u_{ig} - \sum\limits_{l \in PS} {w_{ilg}} $ min
Table 3.  The instances for the DRCMPSP
Problem subset NOI Characterization per instance UF$ _{AV} $
$ \left| {P} \right| $ $ \left| J_{p} \right| $ $ (\left| G \right| $; $ \left| L_{p} \right|) $
MP30_2 5 2 30 (1;3)/(2;2)/(3;1) 0.84
MP90_2 5 2 90 (1;3)/(2;2)/(3;1) 0.57
MP120_2 5 2 120 (1;3)/(2;2)/(3;1) 1.31
MP30_5 5 5 30 (1;3)/(2;2)/(3;1) 0.82
MP90_5 5 5 90 (1;3)/(2;2)/(3;1) 0.61
MP120_5 5 5 120 (1;3)/(2;2)/(3;1) 1.32
MP30_10 5 10 30 (1;3)/(2;2)/(3;1) 2.38
MP90_10 5 10 90 (1;3)/(2;2)/(3;1) 1.14
MP120_10 5 10 120 (1;3)/(2;2)/(3;1) 1.91
MP30_20 5 20 30 (1;3)/(2;2)/(3;1) 3.37
MP90_20 5 20 90 (1;3)/(2;2)/(3;1) 0.9
MP120_20 5 20 120 (1;3)/(2;2)/(3;1) 0.87
Table Options

Download as excel

Problem subset NOI Characterization per instance UF$ _{AV} $
$ \left| {P} \right| $ $ \left| J_{p} \right| $ $ (\left| G \right| $; $ \left| L_{p} \right|) $
MP30_2 5 2 30 (1;3)/(2;2)/(3;1) 0.84
MP90_2 5 2 90 (1;3)/(2;2)/(3;1) 0.57
MP120_2 5 2 120 (1;3)/(2;2)/(3;1) 1.31
MP30_5 5 5 30 (1;3)/(2;2)/(3;1) 0.82
MP90_5 5 5 90 (1;3)/(2;2)/(3;1) 0.61
MP120_5 5 5 120 (1;3)/(2;2)/(3;1) 1.32
MP30_10 5 10 30 (1;3)/(2;2)/(3;1) 2.38
MP90_10 5 10 90 (1;3)/(2;2)/(3;1) 1.14
MP120_10 5 10 120 (1;3)/(2;2)/(3;1) 1.91
MP30_20 5 20 30 (1;3)/(2;2)/(3;1) 3.37
MP90_20 5 20 90 (1;3)/(2;2)/(3;1) 0.9
MP120_20 5 20 120 (1;3)/(2;2)/(3;1) 0.87
Table 4.  APDs obtained by the adaptive GA with different schemes
Problem subsets Serial parallel
minTT minGAP maxRS minRS minTT minGAP maxRS minRS
MP30_2 14.8 13.7 14.8 16.1 13.9 13.3 13.7 14
MP90_2 10 8.8 10.1 11.3 6.9 6.8 7.1 7.3
MP120_2 86.3 83.6 85.1 92.3 57.2 56.7 56.6 57.2
MP30_5 34.24 34.2 36.44 39.04 23.16 23.28 22.48 23.36
MP90_5 23.96 21.76 22.92 25.44 12.4 12.4 11.76 13
MP120_5 104.04 104.44 106.56 112.64 67.72 68.32 67.56 67.8
MP30_10 131.78 126.4 134.3 145.34 85.1 85.22 83.48 87.62
MP90_10 104.14 106.72 108.96 114.3 61.34 60.4 61.12 62.1
MP120_10 252.43 254.44 256.73 262.54 164.38 166.78 166.84 171.96
MP30_20 333.61 340.69 338.15 352.6 205.06 208.3 203.74 213.16
MP90_20 65.24 65.04 66.76 72.84 44.16 43.95 44.06 44.49
MP120_20 71.28 70.49 71.48 77.56 47.48 48.28 47.24 47.52
Average 102.65 102.52 104.36 110.17 65.73 66.14 65.47 67.46
Table Options

Download as excel

Problem subsets Serial parallel
minTT minGAP maxRS minRS minTT minGAP maxRS minRS
MP30_2 14.8 13.7 14.8 16.1 13.9 13.3 13.7 14
MP90_2 10 8.8 10.1 11.3 6.9 6.8 7.1 7.3
MP120_2 86.3 83.6 85.1 92.3 57.2 56.7 56.6 57.2
MP30_5 34.24 34.2 36.44 39.04 23.16 23.28 22.48 23.36
MP90_5 23.96 21.76 22.92 25.44 12.4 12.4 11.76 13
MP120_5 104.04 104.44 106.56 112.64 67.72 68.32 67.56 67.8
MP30_10 131.78 126.4 134.3 145.34 85.1 85.22 83.48 87.62
MP90_10 104.14 106.72 108.96 114.3 61.34 60.4 61.12 62.1
MP120_10 252.43 254.44 256.73 262.54 164.38 166.78 166.84 171.96
MP30_20 333.61 340.69 338.15 352.6 205.06 208.3 203.74 213.16
MP90_20 65.24 65.04 66.76 72.84 44.16 43.95 44.06 44.49
MP120_20 71.28 70.49 71.48 77.56 47.48 48.28 47.24 47.52
Average 102.65 102.52 104.36 110.17 65.73 66.14 65.47 67.46
Table 5.  Parameter configurations to generate test problems
Parameter J P K $ r_j $ $ d_j $ NC RF RS
value 5, 8, 10 or 14 2 or 3 4 $ [1,8] $ $ [1,5] $ 1.5 0.25 0.2
Table Options

Download as excel

Parameter J P K $ r_j $ $ d_j $ NC RF RS
value 5, 8, 10 or 14 2 or 3 4 $ [1,8] $ $ [1,5] $ 1.5 0.25 0.2
Table 6.  Results of the two methods
instances CPLEX GA_maxRS (100 solutions) $ PRE_w $
(%)		 $ PRE_b $
(%)		 $ PRE_m $
(%)
opt $ ct_{ave} (s) $ worst best mean $ ct_{ave} (s) $
J5_2 1 3 0.08 3 3 3 0.11 0 0 0
2 1.5 0.03 1.5 1.5 1.5 0.14 0 0 0
3 2 0.05 2 2 2 0.1 0 0 0
4 5 0.08 5 5 5 0.15 0 0 0
5 2 0.05 2 2 2 0.13 0 0 0
J8_2 1 0.5 0.06 0.5 0.5 0.5 0.11 0 0 0
2 1 0.09 1 1 1 0.17 0 0 0
3 2.5 0.08 2.5 2.5 2.5 0.2 0 0 0
4 5 0.3 5 5 5 0.24 0 0 0
5 3 0.2 3 3 3 0.31 0 0 0
J10_2 1 2.5 2.11 2.5 2.5 2.5 0.94 0 0 0
2 9 3.72 9.5 9 9.1 0.87 6 0 1
3 10.5 2.23 12 10.5 11 1.06 14 0 5
4 7.5 3.2 7.5 7.5 7.5 0.56 0 0 0
5 7 4.83 7 7 7 1.42 0 0 0
J14_2 1 2 0.94 2.5 2 2.2 0.89 25 0 10
2 6 25.23 6 6 6 0.99 0 0 0
3 4.5 1.91 5.5 4.5 4.7 1.18 22 0 4
4 7.5 30.42 7.5 7.5 7.5 1.5 0 0 0
5 4 15.2 6 4 5.5 1.45 50 0 38
J5_3 1 4.33 0.23 4.33 4.33 4.33 0.44 0 0 0
2 2.67 0.63 3.67 3.33 3.53 0.82 37 25 32
3 4 0.86 5.33 4 4.67 0.61 33 0 17
4 3.33 0.19 4.33 3.33 3.94 0.45 30 0 18
5 3.33 0.7 3.33 3.33 3.33 0.63 0 0 0
J8_3 1 2 0.5 2 2 2 0.75 0 0 0
2 7.67 15.69 8.67 7.67 7.94 1.18 13 0 4
3 2 0.22 2 2 2 0.58 0 0 0
4 6 152.2 8.33 6 6.47 1.85 39 0 8
5 1.33 0.41 1.33 1.33 1.33 0.66 0 0 0
J10_3 1 8.67 157.94 9.33 8.76 9.01 1.86 8 1 4
2 10.67 249.08 11 10.67 10.79 1.67 3 0 1
3 4.33 320.17 5.67 4.33 4.79 1.27 31 0 11
4 8 824.63 8 8 8 1.28 0 0 0
5 6 1832.06 6 6 6 1.06 0 0 0
J14_3 1 6.33 131.98 6.33 6.33 6.33 2.14 0 0 0
2 3.33 411.58 5 3.33 3.79 2.93 50 0 14
3 5.67 3600.44 6.67 5.67 5.79 3.03 18 0 2
4 11 3600.13 13.67 11 12.1 7.33 24 0 10
5 5 450.97 7 5 5.4 3.01 40 0 8
Table Options

Download as excel

instances CPLEX GA_maxRS (100 solutions) $ PRE_w $
(%)		 $ PRE_b $
(%)		 $ PRE_m $
(%)
opt $ ct_{ave} (s) $ worst best mean $ ct_{ave} (s) $
J5_2 1 3 0.08 3 3 3 0.11 0 0 0
2 1.5 0.03 1.5 1.5 1.5 0.14 0 0 0
3 2 0.05 2 2 2 0.1 0 0 0
4 5 0.08 5 5 5 0.15 0 0 0
5 2 0.05 2 2 2 0.13 0 0 0
J8_2 1 0.5 0.06 0.5 0.5 0.5 0.11 0 0 0
2 1 0.09 1 1 1 0.17 0 0 0
3 2.5 0.08 2.5 2.5 2.5 0.2 0 0 0
4 5 0.3 5 5 5 0.24 0 0 0
5 3 0.2 3 3 3 0.31 0 0 0
J10_2 1 2.5 2.11 2.5 2.5 2.5 0.94 0 0 0
2 9 3.72 9.5 9 9.1 0.87 6 0 1
3 10.5 2.23 12 10.5 11 1.06 14 0 5
4 7.5 3.2 7.5 7.5 7.5 0.56 0 0 0
5 7 4.83 7 7 7 1.42 0 0 0
J14_2 1 2 0.94 2.5 2 2.2 0.89 25 0 10
2 6 25.23 6 6 6 0.99 0 0 0
3 4.5 1.91 5.5 4.5 4.7 1.18 22 0 4
4 7.5 30.42 7.5 7.5 7.5 1.5 0 0 0
5 4 15.2 6 4 5.5 1.45 50 0 38
J5_3 1 4.33 0.23 4.33 4.33 4.33 0.44 0 0 0
2 2.67 0.63 3.67 3.33 3.53 0.82 37 25 32
3 4 0.86 5.33 4 4.67 0.61 33 0 17
4 3.33 0.19 4.33 3.33 3.94 0.45 30 0 18
5 3.33 0.7 3.33 3.33 3.33 0.63 0 0 0
J8_3 1 2 0.5 2 2 2 0.75 0 0 0
2 7.67 15.69 8.67 7.67 7.94 1.18 13 0 4
3 2 0.22 2 2 2 0.58 0 0 0
4 6 152.2 8.33 6 6.47 1.85 39 0 8
5 1.33 0.41 1.33 1.33 1.33 0.66 0 0 0
J10_3 1 8.67 157.94 9.33 8.76 9.01 1.86 8 1 4
2 10.67 249.08 11 10.67 10.79 1.67 3 0 1
3 4.33 320.17 5.67 4.33 4.79 1.27 31 0 11
4 8 824.63 8 8 8 1.28 0 0 0
5 6 1832.06 6 6 6 1.06 0 0 0
J14_3 1 6.33 131.98 6.33 6.33 6.33 2.14 0 0 0
2 3.33 411.58 5 3.33 3.79 2.93 50 0 14
3 5.67 3600.44 6.67 5.67 5.79 3.03 18 0 2
4 11 3600.13 13.67 11 12.1 7.33 24 0 10
5 5 450.97 7 5 5.4 3.01 40 0 8
Table 7.  Results of GA_maxRS and DMAS/RIA
Problem subsets GA_maxRS DMAS/RIA $ PRE_{_A} $
(%)
with TT without TT $ PRE_{_GA} $
(%)		 with TT without TT $ PRE_{_D} $
(%)
MP30_2 13 10.9 19 23.3 18 29 -39
MP90_2 6.9 6.7 3 17.1 11.8 45 -43
MP120_2 56.1 55.6 1 89.6 80.3 12 -31
MP30_5 22.2 18.08 23 35.28 21.64 63 -16
MP90_5 11.68 9.36 25 22 13.32 65 -30
MP120_5 66.84 65.48 2 86.12 77.68 11 -16
MP30_10 81.58 78.16 4 92.68 83 12 -6
MP90_10 59.34 50.36 18 62.66 61.52 2 -18
MP120_10 164.28 140.3 17 162.6 144.1 13 -3
MP30_20 199.63 189.6 5 206.9 193 7 -2
MP90_20 43.38 34.92 24 42.88 43.13 -1 -19
MP120_20 46.42 39.71 17 48.09 42.11 14 -6
Average 64.28 58.26 10 74.1 65.8 13 -11
Table Options

Download as excel

Problem subsets GA_maxRS DMAS/RIA $ PRE_{_A} $
(%)
with TT without TT $ PRE_{_GA} $
(%)		 with TT without TT $ PRE_{_D} $
(%)
MP30_2 13 10.9 19 23.3 18 29 -39
MP90_2 6.9 6.7 3 17.1 11.8 45 -43
MP120_2 56.1 55.6 1 89.6 80.3 12 -31
MP30_5 22.2 18.08 23 35.28 21.64 63 -16
MP90_5 11.68 9.36 25 22 13.32 65 -30
MP120_5 66.84 65.48 2 86.12 77.68 11 -16
MP30_10 81.58 78.16 4 92.68 83 12 -6
MP90_10 59.34 50.36 18 62.66 61.52 2 -18
MP120_10 164.28 140.3 17 162.6 144.1 13 -3
MP30_20 199.63 189.6 5 206.9 193 7 -2
MP90_20 43.38 34.92 24 42.88 43.13 -1 -19
MP120_20 46.42 39.71 17 48.09 42.11 14 -6
Average 64.28 58.26 10 74.1 65.8 13 -11
[1]

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, 2021, 17 (5) : 2451-2474. doi: 10.3934/jimo.2020077
[2]

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

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

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

Shuang Zhao. Resource allocation flowshop scheduling with learning effect and slack due window assignment. Journal of Industrial & Management Optimization, 2021, 17 (5) : 2817-2835. doi: 10.3934/jimo.2020096
[6]

Didem Cinar, José António Oliveira, Y. Ilker Topcu, Panos M. Pardalos. A priority-based genetic algorithm for a flexible job shop scheduling problem. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1391-1415. doi: 10.3934/jimo.2016.12.1391
[7]

Xuewen Huang, Xiaotong Zhang, Sardar M. N. Islam, Carlos A. Vega-Mejía. An enhanced Genetic Algorithm with an innovative encoding strategy for flexible job-shop scheduling with operation and processing flexibility. Journal of Industrial & Management Optimization, 2020, 16 (6) : 2943-2969. doi: 10.3934/jimo.2019088
[8]

Jiping Tao, Zhijun Chao, Yugeng Xi. A semi-online algorithm and its competitive analysis for a single machine scheduling problem with bounded processing times. Journal of Industrial & Management Optimization, 2010, 6 (2) : 269-282. doi: 10.3934/jimo.2010.6.269
[9]

Xianyu Yu, Dar-Li Yang, Dequn Zhou, Peng Zhou. Multi-machine scheduling with interval constrained position-dependent processing times. Journal of Industrial & Management Optimization, 2018, 14 (2) : 803-815. doi: 10.3934/jimo.2017076
[10]

Ji-Bo Wang, Bo Zhang, Hongyu He. A unified analysis for scheduling problems with variable processing times. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021008
[11]

Wenchang Luo, Lin Chen. Approximation schemes for scheduling a maintenance and linear deteriorating jobs. Journal of Industrial & Management Optimization, 2012, 8 (2) : 271-283. doi: 10.3934/jimo.2012.8.271
[12]

Reza Lotfi, Zahra Yadegari, Seyed Hossein Hosseini, Amir Hossein Khameneh, Erfan Babaee Tirkolaee, Gerhard-Wilhelm Weber. A robust time-cost-quality-energy-environment trade-off with resource-constrained in project management: A case study for a bridge construction project. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020158
[13]

Jiping Tao, Ronghuan Huang, Tundong Liu. A $2.28$-competitive algorithm for online scheduling on identical machines. Journal of Industrial & Management Optimization, 2015, 11 (1) : 185-198. doi: 10.3934/jimo.2015.11.185
[14]

Nan Li, Song Wang, Shuhua Zhang. Pricing options on investment project contraction and ownership transfer using a finite volume scheme and an interior penalty method. Journal of Industrial & Management Optimization, 2020, 16 (3) : 1349-1368. doi: 10.3934/jimo.2019006
[15]

Güvenç Şahin, Ravindra K. Ahuja. Single-machine scheduling with stepwise tardiness costs and release times. Journal of Industrial & Management Optimization, 2011, 7 (4) : 825-848. doi: 10.3934/jimo.2011.7.825
[16]

P. Liu, Xiwen Lu. Online scheduling of two uniform machines to minimize total completion times. Journal of Industrial & Management Optimization, 2009, 5 (1) : 95-102. doi: 10.3934/jimo.2009.5.95
[17]

Mehmet Duran Toksari, Emel Kizilkaya Aydogan, Berrin Atalay, Saziye Sari. Some scheduling problems with sum of logarithm processing times based learning effect and exponential past sequence dependent delivery times. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021044
[18]

Fan Zhang, Guifa Teng, Mengmeng Gao, Shuai Zhang, Jingjing Zhang. Multi-machine and multi-task emergency allocation algorithm based on precedence rules. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1501-1513. doi: 10.3934/dcdss.2019103
[19]

Ping Yan, Ji-Bo Wang, Li-Qiang Zhao. Single-machine bi-criterion scheduling with release times and exponentially time-dependent learning effects. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1117-1131. doi: 10.3934/jimo.2018088
[20]

Bin Zheng, Min Fan, Mengqi Liu, Shang-Chia Liu, Yunqiang Yin. Parallel-machine scheduling with potential disruption and positional-dependent processing times. Journal of Industrial & Management Optimization, 2017, 13 (2) : 697-711. doi: 10.3934/jimo.2016041

2019 Impact Factor: 1.366

Tools

Article outline

Figures and Tables

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences