Advanced Search
Article Contents
Article Contents

A performance comparison and evaluation of metaheuristics for a batch scheduling problem in a multi-hybrid cell manufacturing system with skilled workforce assignment

  • * Corresponding author: Omer Faruk Yilmaz

    * Corresponding author: Omer Faruk Yilmaz 
Abstract Full Text(HTML) Figure(8) / Table(13) Related Papers Cited by
  • This paper focuses on the batch scheduling problem in multi-hybrid cell manufacturing systems (MHCMS) in a dual-resource constrained (DRC) setting, considering skilled workforce assignment (SWA). This problem consists of finding the sequence of batches on each cell, the starting time of each batch, and assigning employees to the operations of batches in accordance with the desired objective. Because handling both the scheduling and assignment decisions simultaneously presents a challenging optimization problem, it is difficult to solve the formulated model, even for small-sized problem instances. Three metaheuristics are proposed to solve the batch scheduling problem, namely the genetic algorithm (GA), simulated annealing (SA) algorithm, and artificial bee colony (ABC) algorithm. A serial scheduling scheme (SSS) is introduced and employed in all metaheuristics to obtain a feasible schedule for each individual. The main aim of this study is to identify an effective metaheuristic for determining the scheduling and assignment decisions that minimize the average cell response time. Detailed computational experiments were conducted, based on real production data, to evaluate the performance of the metaheuristics. The experimental results show that the performance of the proposed ABC algorithm is superior to other metaheuristics for different levels of experimental factors determined for the number of batches and the employee flexibility.

    Mathematics Subject Classification: Primary: 90B35, 90C10; Secondary: 90C27.


    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  Batch-flow and one-piece flow

    Figure 2.  Average cell response time (Solution decoding)

    Figure 3.  Multi-Hybrid Cell Manufacturing System for the illustrative example

    Figure 4.  Crossover operator

    Figure 5.  Box-plot of RPD values with respect to the algorithms (for nine employees)

    Figure 6.  Box-plots of RPD values obtained by the algorithms for each level of NBEC (for nine employees)

    Figure 7.  Box-plots of RPD values obtained by the algorithms for each level of NESL (for nine employees)

    Figure 8.  Box-plots of RPD values obtained by the ABC algorithm for each level of NESL (for nine employees)

    Table 1.  Illustrative example data for the problem

    $i$ $cx_i$ $cn_i$ $q_i$ $r_{im}$ $e_{zim}$ $r_{im}$ $e_{zim}$ $r_{im}$ $e_{zim}$ $r_{im}$ $e_{zim}$ $o_i$ $a_i$
     | Show Table
    DownLoad: CSV

    Table 2.  Maximum and minimum number of employees

    $i$ $W_i$ (Maximum) $W1_i$ (Minimum)
    1 (Cell1)21
    2 (Cell1)31
    3 (Cell2)31
    4 (Cell2)31
     | Show Table
    DownLoad: CSV

    Table 3.  The batch list representation scheme (Encoding scheme)

    position numbers1234
    batch list2413
    batch-employee assignment1-31-221-3
    employee-machine assignment(1-2) (3-4)(2-3) (1-4)(1-2-3-4)(3-4) (1-2)
     | Show Table
    DownLoad: CSV

    Table 4.  The cell cycle times and the first lead times

    $i$ $cn_i$employee1employee2employee3 $cy_i$ $FT_i$
    1 (Cell1)35-66-6686
    2 (Cell1)304343-4391
    3 (Cell2)3050-2550120
    4 (Cell2)203520-3585
     | Show Table
    DownLoad: CSV

    Table 5.  Cell cycle times, batch sizes, operation times and total walking times

    $i$ $cx_i$ $cn_i$ $q_i$ $e_{zim}$ $e_{zim}$ $e_{zim}$ $r_{im}$ $e_{zim}$ $e_{zim}$ $e_{zim}$$e_{zim}$ $o_i$
     | Show Table
    DownLoad: CSV

    Table 6.  Experimental factors and their levels

    Number of Batches on Each Cell (NBEC)1NB    
    (Problem size factor)2[5$\times$ NB]    
      3[10$\times$ NB]    
    Number of Employees for each Skill Level  JuniorNormalSenior
     | Show Table
    DownLoad: CSV

    Table 7.  The coefficient of skill levels

    Skill level coefficients0.6311.29
     | Show Table
    DownLoad: CSV

    Table 8.  The promising values of the parameters for the metaheuristics

    GA $PS$20, 40, 60, 80,100406080
    $pcross$0.2, 0.4, 0.6,
    $pmutation$0.1, 0.2, 0.3,
    ABC $NFS$20, 40, 60, 80,100404060
    $\lambda$2, 4, 6, 8, 10244
    $limit$2, 4, 6, 8, 10664
    SA $initialtemp$ $10^3\times$(1, 3, 5, 7)135
    $coolingrate$0.9, 0.95, 0.990.990.990.99
    $epoch$5, 10, 15, 20101515
     | Show Table
    DownLoad: CSV

    Table 9.  The tuned values of the parameters for the metaheuristics

    GA $PS$30, 40, 50 50, 60, 7070, 80, 90
    $pcross$ 0.7, 0.8, 0.90.5, 0.6, 0.70.5, 0.6, 0.7
    $pmutation$ 0.25, 0.3, 0.35 0.15, 0.2, 0.250.15, 0.2, 0.25
    ABC $NFS$ 30, 40, 5030, 40, 5050, 60, 70
    $\lambda$1, 2, 33, 4, 53, 4, 5
    $limit$5, 6, 75, 6, 73, 4, 5
    SA $initialtemp$ 750, 1000,12502500,3000, 35004000,5000, 6000
    $coolingrate$ 0.98, 0.990.98, 0.990.98, 0.99
    $epoch$ 8, 10, 12 13, 15, 1713, 15, 17
     | Show Table
    DownLoad: CSV

    Table 10.  The maximum computational times

     | Show Table
    DownLoad: CSV

    Table 11.  Median of RPD values and computational time of algorithms for 9 employees

    1$\times$12358017.6616.9618.821817, 1415
    Medians18.768 19.108 17.276 18.642 19.923 15
    Medians30.816 29.952 28.472 30.225 31.818 51.2
    Medians38.359 37.51 35.342 37.528 40.472 96.9
     | Show Table
    DownLoad: CSV

    Table 12.  Median of RPD values and computational time of algorithms for 15 employees

    NESL$\times$ NBECRPD
     | Show Table
    DownLoad: CSV

    Table 13.  Three-way ANOVA: RPD versus NBEC, NESL, and Algorithms

    SourceFSig. ($p$)Partial eta squared
     | Show Table
    DownLoad: CSV
  • [1] M. O. Adamu and A. Adewumi, Comparing the performance of different meta-heuristics for unweighted parallel machine scheduling, South African Journal of Industrial Engineering, 26 (2015), 143-157.  doi: 10.7166/26-2-628.
    [2] A. O. Adewumi and M. M. Ali, A multi-level genetic algorithm for a multi-stage space allocation problem, Mathematical and Computer Modeling, 51 (2010), 109-126.  doi: 10.1016/j.mcm.2009.09.004.
    [3] A. O. SawyerrB. A. Adewumi and M. M. Ali, A heuristic solution to the university timetabling problem, Engineering Computations, 26 (1984), 972-984.  doi: 10.1108/02644400910996853.
    [4] R. G. Askin and Y. Huang, Forming effective worker teams for cellular manufacturing, International Journal of Production Research, 39 (2001), 2431-2451.  doi: 10.1080/00207540110040466.
    [5] A. AzadehM. Sheikhalishahi and M. Koushan, An integrated fuzzy DEA-Fuzzy simulation approach for optimization of operator allocation with learning effects in multi products CMS, Applied Mathematical Modelling, 37 (2013), 9922-9933.  doi: 10.1016/j.apm.2013.05.039.
    [6] A. N. Balaji and S. Porselvi, Artificial immune system algorithm and simulated annealing algorithm for scheduling batches of parts based on job availability model in a multi-cell flexible manufacturing system, Procedia Engineering, 97 (2014), 1524-1533.  doi: 10.1016/j.proeng.2014.12.436.
    [7] J. T. Black and S. L. Hunter, Lean Manufacturing Systems and Cell Design, Society of Manufacturing Engineers, 2003.
    [8] G. CelanoA. Costa and S. Fichera, Scheduling of unrelated parallel manufacturing cells with limited human resources, International Journal of Production Research, 46 (2008), 405-427.  doi: 10.1080/00207540601138452.
    [9] V. I. Cesani and H. J. Steudel, A study of labor assignment flexibility in cellular manufacturing systems, Computers & Industrial Engineering, 48 (2005), 571-591.  doi: 10.1016/j.cie.2003.04.001.
    [10] W. D. Chang, Nonlinear CSTR control system design using an artificial bee colony algorithm, Simulation Modelling Practice and Theory, 31 (2013), 1-9.  doi: 10.1016/j.simpat.2012.11.002.
    [11] W. D. Chang, Equation of state calculations by fast computing machines, The Journal of Chemical Physics, 21 (1953), 1087-1092. 
    [12] S. Chetty and A. O. Adewumi, Three new stochastic local search metaheuristics for the annual crop planning problem based on a new irrigation scheme, Journal of Applied Mathematics, 2013 (2013), Article ID 158538, 14 pages. doi: 10.1155/2013/158538.
    [13] D. A. Coley, An Introduction to Genetic Algorithms for Scientists and Engineers, World Scientific Pub. Co. Inc., 1999. doi: 10.1142/3904.
    [14] P. CortesJ. LarranetaL. OnievaJ. M. García and M. S. Caraballo, Genetic algorithm for planning cable telecommunication networks, Applied Soft Computing, 1 (2001), 21-33.  doi: 10.1016/S1568-4946(01)00004-7.
    [15] A. CostaF. A. Cappadonna and S. Fichera, Joint optimization of a flow-shop group scheduling with sequence dependent set-up times and skilled workforce assignment, International Journal of Production Research, 52 (2014), 2696-2728.  doi: 10.1080/00207543.2014.883469.
    [16] A. CostaF. A. Cappadonna and S. Fichera, A hybrid genetic algorithm for job sequencing and worker allocation in parallel unrelated machines with sequence-dependent setup times, The International Journal of Advanced Manufacturing Technology, 69 (2013), 2799-2817.  doi: 10.1007/s00170-013-5221-5.
    [17] A. CostaS. Fichera and F. A. Cappadonna, A genetic algorithm for scheduling both jobs families and skilled workforce, International Journal of Operations and Quantitative Management, 19 (2013), 221-247. 
    [18] R. L. DanielsB. J. Hoopes and J. B. Mazzola, Scheduling parallel manufacturing cells with resource flexibility, Management Science, 42 (1996), 1260-1276.  doi: 10.1287/mnsc.42.9.1260.
    [19] S. R. Das and C. Canel, An algorithm for scheduling batches of parts in a multi-cell flexible manufacturing system, International Journal of Production Economics, 97 (2005), 247-262.  doi: 10.1016/j.ijpe.2004.07.006.
    [20] D. J. DavisH. V. Kher and B. J. Wagner, Influence of workload imbalances on the need for worker flexibility, Computers & Industrial Engineering, 57 (2009), 319-329.  doi: 10.1016/j.cie.2008.11.029.
    [21] E. B. EdisC. Oguz and I. Ozkarahan, Parallel machine scheduling with additional resources: Notation, classification, models and solution methods, European Journal of Operational Research, 230 (2013), 449-463.  doi: 10.1016/j.ejor.2013.02.042.
    [22] G. EgilmezB. Erenay and G. A. Suer, Stochastic skill-based manpower allocation in a cellular manufacturing system, Journal of Manufacturing Systems, 33 (2014), 578-588.  doi: 10.1016/j.jmsy.2014.05.005.
    [23] B. FahimniaH. Davarzani and A. Eshragh, Planning of complex supply chains: A performance comparison of three meta-heuristic algorithms, Computers & Operations Research, 89 (2018), 241-252.  doi: 10.1016/j.cor.2015.10.008.
    [24] J. FanM. Cao and D. Feng, Multi-objective dual resource-constrained model for cell formation problem, In Management of Innovation and Technology IEEE International Conference, (2010), 1031-1036.  doi: 10.1109/ICMIT.2010.5492881.
    [25] J. W. FowlerP. Wirojanagud and E. S. Gel, Heuristics for workforce planning with worker differences, European Journal of Operational Research, 190 (2008), 724-740.  doi: 10.1016/j.ejor.2007.06.038.
    [26] J. H. Holland, Genetic algorithms, Scientific American, 267 (1992), 66-72. 
    [27] M. P. Hottenstein and S. A. Bowman, Cross-training and worker flexibility: A review of DRC system research, The Journal of High Technology Management Research, 9 (1998), 157-174.  doi: 10.1016/S1047-8310(98)90002-5.
    [28] H. Hyer and U. Wemmerlov, Reorganizing the Factory Competing Through Cellular Manufacturing, Productivity Press, 2002.
    [29] J. B. Jensen, The impact of resource flexibility and staffing decisions on cellular and departmental shop performance, European Journal of Operational Research, 127 (2000), 279-296.  doi: 10.1016/S0377-2217(99)00491-9.
    [30] N. Karaboga, A new design method based on artificial bee colony algorithm for digital IIR filters, Journal of the Franklin Institute, 346 (2009), 328-348.  doi: 10.1016/j.jfranklin.2008.11.003.
    [31] D. Karaboga and B. Basturk, On the performance of artificial bee colony (ABC) algorithm, Applied Soft Computing, 8 (2008), 687-697.  doi: 10.1016/j.asoc.2007.05.007.
    [32] D. Karaboga and E. Kaya, An adaptive and hybrid artificial bee colony algorithm (aABC) for ANFIS training, Applied Soft Computing, 49 (2016), 423-436.  doi: 10.1016/j.asoc.2016.07.039.
    [33] S. Kirkpatrick, Optimization by simulated annealing: Quantitative studies, Journal of Statistical Physics, 34 (1984), 975-986.  doi: 10.1007/BF01009452.
    [34] R. Kolisch, Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation, European Journal of Operational Research, 90 (1996), 320-333.  doi: 10.1016/0377-2217(95)00357-6.
    [35] X. Li and L. Gao, An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem, International Journal of Production Economics, 174 (2016), 93-110.  doi: 10.1016/j.ijpe.2016.01.016.
    [36] Y. LiX. Li and J. N. D. Gupta, Solving the multi-objective flowline manufacturing cell scheduling problem by hybrid harmony search, Expert Systems with Applications, 42 (2015), 1409-1417.  doi: 10.1016/j.eswa.2014.09.007.
    [37] C. LiuJ. Wang and J. Y. T. Leung, Worker assignment and production planning with learning and forgetting in manufacturing cells by hybrid bacteria foraging algorithm, Computers & Industrial Engineering, 96 (2016), 162-179.  doi: 10.1016/j.cie.2016.03.020.
    [38] K. F. Man, K. S. Tang and S. Kwong, Genetic Algorithms: Concepts and Designs, Springer-Verlag London, Ltd., London, 1999.
    [39] B. L. Miller and D. E. Goldberg, Genetic algorithms, tournament selection, and the effects of noise, Complex Systems, 9 (1995), 193-212. 
    [40] J. Miltenburg, One-piece flow manufacturing on U-shaped production lines: A tutorial, IIE Transactions, 33 (2001), 303-321.  doi: 10.1080/07408170108936831.
    [41] D. NasoM. SuricoB. Turchiano and U. Kaymak, Genetic algorithms for supply-chain scheduling: A case study in the distribution of ready-mixed concrete, European Journal of Operational Research, 177 (2007), 2069-2099.  doi: 10.1016/j.ejor.2005.12.019.
    [42] F. NiakanA. BaboliT. Moyaux and V. Botta-Genoulaz, A new multi-objective mathematical model for dynamic cell formation under demand and cost uncertainty considering social criteria, Applied Mathematical Modelling, 40 (2016), 2674-2691.  doi: 10.1016/j.apm.2015.09.047.
    [43] B. A. NormanW. TharmmaphornphilasK. L. NeedyB. Bidanda and R. C. Warner, Worker assignment in cellular manufacturing considering technical and human skills, International Journal of Production Research, 40 (2002), 1479-1492.  doi: 10.1080/00207540110118082.
    [44] M. W. Park and Y. D. Kim, A systematic procedure for setting parameters in simulated annealing algorithms, Computers & Operations Research, 25 (1998), 207-217.  doi: 10.1016/S0305-0548(97)00054-3.
    [45] D. Quagliarella, Genetic Algorithms and Evolution Strategy in Engineering and Computer Science: Recent Advances and Industrial Applications, World John Wiley & Son Ltd., 1998.
    [46] S. RameshS. Kannan and S. Baskar, Application of modified NSGA-II algorithm to multi-objective reactive power planning, Applied Soft Computing, 12 (2012), 741-753.  doi: 10.1016/j.asoc.2011.09.015.
    [47] I. Ribas and R. Companys, Efficient heuristic algorithms for the blocking flow shop scheduling problem with total flow time minimization, Computers & Industrial Engineering, 87 (2015), 30-39.  doi: 10.1016/j.cie.2015.04.013.
    [48] S. I. SatogluM. B. Durmusoglu and T. Ertay, A mathematical model and a heuristic approach for design of the hybrid manufacturing systems to facilitate one-piece flow, International Journal of Production Research, 48 (2010), 5195-5220.  doi: 10.1080/00207540903089544.
    [49] S. I. Satoglu and N. C. Suresh, A goal-programming approach for design of hybrid cellular manufacturing systems in dual resource constrained environments, Computers & Industrial Engineering, 56 (2009), 560-575.  doi: 10.1016/j.cie.2008.06.009.
    [50] J. E. SchallerJ. N. D Gupta and A. J. Vakharia, Scheduling a flowline manufacturing cell with sequence dependent family setup times, European Journal of Operational Research, 125 (2000), 324-339. 
    [51] T. SousaT. SoaresH. MoraisR. Castro and Z. Vale, Simulated annealing to handle energy and ancillary services joint management considering electric vehicles, Electric Power Systems Research, 136 (2016), 383-397.  doi: 10.1016/j.epsr.2016.03.031.
    [52] G. A. Suer and O. Alhawari, Operator assignment decisions in a highly dynamic cellular environment, Operations Management Research and Cellular Manufacturing Systems: Innovative Methods and Approaches, (2011), 258-294. 
    [53] G. A. Suer and C. Dagli, Intra-cell manpower transfers and cell loading in labor-intensive manufacturing cells, Computers & Industrial Engineering, 48 (2005), 643-655.  doi: 10.1016/j.cie.2003.03.006.
    [54] G. A. Suer and R. R. Tummaluri, Multi-period operator assignment considering skills, learning and forgetting in labour-intensive cells, International Journal of Production Research, 46 (2008), 469-493.  doi: 10.1080/00207540601138551.
    [55] R. Suri, Quick response manufacturing: A competitive strategy for the 21st century, In Proceedings of the 2002 POLCA Implementation Workshop, 141 (2002).
    [56] E. G Talbi, Metaheuristics: From Design to Implementation, John Wiley & Son Ltd., 2009. doi: 10.1002/9780470496916.
    [57] M. Unal, A. Ak, V. Topuz and H. Erdal, Optimization of PID Controllers Using ant Colony and Genetic Algorithms, Springer, Heidelberg, 2013.
    [58] S. Venkataramanaiah, Scheduling in cellular manufacturing systems: An heuristic approach, International Journal of Production Research, 46 (2008), 429-449.  doi: 10.1080/00207540601138577.
    [59] J. X. Wang, Cellular Manufacturing: Mitigating Risk and Uncertainty, CRC Press, Boca Raton, USA, 2015. doi: 10.1201/b18009-1.
    [60] U. Wemmerlöv and N. L. Hyer, Cellular manufacturing in the US industry: A survey of users, International Journal of Production Research, 27 (1989), 1511-1530.  doi: 10.1080/00207548908942637.
    [61] J. XuX. Xu and S. Q. Xie, Recent developments in Dual Resource Constrained (DRC) system research, European Journal of Operational Research, 215 (2011), 309-318.  doi: 10.1016/j.ejor.2011.03.004.
    [62] O. F. YilmazE. Cevikcan and M. B. Durmusoglu, Scheduling batches in multi hybrid cell manufacturing system considering worker resources: A case study from pipeline industry, Advances in Production Engineering & Management, 11 (2016), 192-206.  doi: 10.14743/apem2016.3.220.
    [63] O. F. YilmazB. OztaysiM. B. Durmusoglu and S. C. Oner, Determination of material handling equipment for lean in-plant logistics using fuzzy analytical network process considering risk attitudes of the experts, International Journal of Industrial Engineering: Theory, Applications and Practice, 24 (2017), 81-122. 
  • 加载中




Article Metrics

HTML views(3175) PDF downloads(634) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint