\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

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

  • * Corresponding author: Jingwen Zhang

    * Corresponding author: Jingwen Zhang 
Abstract Full Text(HTML) Figure(11) / Table(7) Related Papers Cited by
  • 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.

    Mathematics Subject Classification: Primary: 90B35, 90C11.

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  An example of a DRCMPSPTT

    Figure 2.  Renumbered network of the example

    Figure 3.  Individual representation for the DRCMPSPTT

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

    Figure 5.  The adaptive serial SGS with transfer times

    Figure 6.  The adaptive parallel SGS with transfer times

    Figure 7.  Two-point crossover operator

    Figure 8.  Average APDs obtained by different schemes

    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 10.  (a) The three types PREs, and (b) computation times of the solution methods

    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

    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
     | Show Table
    DownLoad: CSV

    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
     | Show Table
    DownLoad: CSV

    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
     | Show Table
    DownLoad: CSV

    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
     | Show Table
    DownLoad: CSV

    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
     | Show Table
    DownLoad: CSV

    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
     | Show Table
    DownLoad: CSV

    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
     | Show Table
    DownLoad: CSV
  • [1] S. AdhauM. 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.
    [2] S. AdhauM. 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.
    [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.
    [4] C. ArtiguesP. 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.
    [5] D. Bedworth and J. Bailey, Integrated Production Control Systems Management, Analysis, Design, 2$^nd$ edition, John Wiley & Sons, Inc., New York, 1999.
    [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.
    [7] P. BruckerS. KnustA. 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.
    [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.
    [9] G. ConfessoreS. 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.
    [10] E. W. Davis, Project network summary measures constrained resource scheduling, AIIE Transactions, 7 (1975), 132-142.  doi: 10.1080/05695557508974995.
    [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.
    [12] L. DjeridM. 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.
    [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.
    [14] J. B. Holland and  J. H. HollandAdaption in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, Mich., 1975. 
    [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.
    [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.
    [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.
    [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.
    [19] J. E. Kelley, The critical-path method: Resources planning and scheduling, Industrial Scheduling, 13 (1963), 347365.
    [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.
    [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.
    [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.
    [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.
    [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.
    [25] R. Kolisch and A. Sprecher, PSPLIB–A project scheduling library, European Journal of Operation Research, 96 (1996), 205-216. 
    [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.
    [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.
    [28] C. J. LiaoC. 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.
    [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.
    [30] A. LovaP. TormosM. 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.
    [31] D. MerkleM. 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.
    [32] M. MikaG. 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.
    [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.
    [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.
    [35] M. S. NaganoA. 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.
    [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.
    [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.
    [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.
    [39] V. RoshanaeiB. NaderiF. 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.
    [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.
    [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.
    [42] V. VallsF. 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.
    [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.
    [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.
    [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. 
  • 加载中

Figures(11)

Tables(7)

SHARE

Article Metrics

HTML views(1465) PDF downloads(763) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return