Abstract
In this paper, the unrelated parallel machine scheduling problem with sequence-dependent setup times and limited human resources is addressed with reference to the makespan minimisation objective. Workers needed for setup operations are supposed to be a critical resource as their number is assumed to be lower than the number of workstations. In addition, each worker is characterised by a specific skill level, which affects setup times. Firstly, a mathematical model able to optimally solve small instances of the problem in hand is illustrated. Then, to deal with large-sized test cases, three different optimisation procedures equipped by different encoding methods are proposed: a permutation encoding-based genetic algorithm (GA), a multi-encoding GA and a hybrid GA that properly moves from a permutation encoding to a multi-encoding once a given threshold on the number of generations is achieved. In particular, three different hybrid GAs featured by different encoding switch thresholds were implemented. An extensive benchmark including both small- and large-sized instances was generated with the aim of both calibrating the genetic parameters and comparing the alternative GAs through distinct ANOVA analyses. Numerical results confirm the effectiveness of the hybrid genetic approach whose encoding switch threshold is fixed to 25 % of the overall generations. Finally, a further analysis concerning the impact of multi-skilled workforce on the performance of both production system and optimisation strategy is presented.
Similar content being viewed by others
References
Anghinolfi D, Paolucci M (2007) Parallel machine total tardiness scheduling with a new hybrid metaheuristic approach. Comput Oper Res 34:3471–3490
Askin RG, Huang RY (2001) Forming effective work teams for cellular manufacturing. Int J Prod Res 39(11):2431–2451
Balin S (2011) Non-identical parallel machine scheduling using genetic algorithm. Expert Syst Appl 38:6814–6821
Celano G, Costa A, Fichera S (2008) Scheduling of unrelated parallel manufacturing cells with limited human resources. Int J Prod Res 46(2):405–427
Celano G, Costa A, Fichera S, Perrone G (2004) Human factor policy testing in the sequencing of manual mixed model assembly lines. Comput Oper Res 31(1):39–59
Costa A, Celano G, Fichera S, Trovato E (2010) A new efficient encoding/decoding procedure for the design of a supply chain network with genetic algorithms. Comput Ind Eng 59(4):986–999
Chaudhry IA (2010) Minimizing flow time for the worker assignment problem in identical parallel machine models using GA. Int J Adv Manuf Technol 48:747–760
Chaudhry IA, Drake PR (2009) Minimizing total tardiness for the machine scheduling and worker assignment problems in identical parallel machines using genetic algorithms. Int J Adv Manuf Technol 42:581–594
Cheng R, Gen M (1997) Parallel machine scheduling problems using memetic algorithms. Comput Ind Eng 33(3–4):761–764
Cochran JK, Horng SM, Fowler JW (2003) A multi-population genetic algorithm to solve multi-objective scheduling problems for parallel machines. Comput Oper Res 30:1087–1102
ElMaraghy H, Patel V, Ben AI (2000) Scheduling of manufacturing systems under dual-resource constraints using genetic algorithms. J Manuf Syst 19(3):186–198
Fanjul-Peyro L, Ruiz R (2011) Size-reduction heuristics for the unrelated parallel machines scheduling problem. Comput Oper Res 38:301–309
Fanjul-Peyro L, Ruiz R (2012) Scheduling unrelated parallel machines with optional machines and jobs selection. Comput Oper Res 39:1745–1753
Gokhale R, Mathirajan M (2012) Scheduling identical parallel machines with machine eligibility restrictions to minimize total weighted flowtime in automobile gear manufacturing. Int J Adv Manuf Technol 60:1099–1110
Holland JH (1975) Adaptation in natural and artificial systems. The University of Michigan Press, Ann Arbor
Hottenstein MP, Bowman SA (1998) Cross-training and worker flexibility: a review of DRC system research. J High Technol Manag Res 9(2):157–174
Hu PC (2004) Minimising total tardiness for the worker assignment scheduling problem in identical parallel-machine models. Int J Adv Manuf Technol 23:383–388
Hu PC (2005) Minimizing total flow time for the worker assignment scheduling problem in the identical parallel-machines models. Int J Adv Manuf Technol 25:1046–1052
Hu PC (2006) Further study of minimizing total tardiness for the worker assignment scheduling problem in the identical parallel-machines models. Int J Adv Manuf Technol 29:165–169
Kim SC, Bobrowsky PM (1997) Scheduling jobs with uncertain setup times and sequence dependency. OMEGA Int J Manag Sci 25(4):437–447
Kim DW, Na DG, Chen FF (2003) Unrelated parallel machine scheduling with setup times and a total weighted tardiness objective. Robot Comput Integr Manuf 19:173–181
Kher HV, Fry TD (2001) Labour flexibility and assignment policies in a job shop having incommensurable objectives. Int J Prod Res 39(11):2295–2311
Lenstra JK, Rinnooy Kan AHG, Brucker P (1977) Complexity of machine scheduling problems. Ann Discret Math 1:342–362
Michalewicz Z (1994) Genetic algorithms + data structures = evolution programs, 2nd edn. Springer, Berlin
Montgomery D (2007) Design and analysis of experiments, 5th edn. Wiley, New York
Nelson RT (1967) Labor and machine limited production systems. Manag Sci 13(9):648–671
Norman BA, Tharmmaphornphilas W, Lascola Needy K, Bidanda B, Colosimo WN (2002) Worker assignment in cellular manufacturing considering technical and human skills. Int J Prod Res 40(6):1479–1492
Oliver IM, Smith DJ, Holland JRC (1987) A study of permutation crossover operators on the TSP. In: Grefenstette JJ (ed) Genetic algorithms and their applications: proceedings of the second international conference. Lawrence Erlbaum, Hillsdale
Pan QK, Suganthan PN, Chua TJ, Cai TX (2010) Solving manpower scheduling problem in manufacturing using mixed-integer programming with a two-stage heuristic algorithm. Int J Adv Manuf Technol 46:1229–1237
Pereira Lopes MJ, Valério de Carvalho JM (2007) A branch-and-price algorithm for scheduling parallel machines with sequence dependent setup times. Eur J Oper Res 176:1508–1527
Pinedo M (2008) Scheduling: theory, algorithms and systems, 3rd edn. Prentice-Hall, New Jersey
Sule DR (2008) Production Planning and Industrial Scheduling: Examples, Case Studies and Applications, 2nd edn. CRC Press, Boca Raton
Syswerda G (1989) Uniform crossover in genetic algorithms. In: Schaffer JD (ed) Proceedings of the Third International Conference on Genetic Algorithms. Morgan Kaufmann Publishers, San Mateo
Syswerda G (1991) Schedule optimization using genetic algorithms. In: Davis L (ed) Handbook of genetic algorithms. Van Nostrand Reinhold, New York
Tavakkoli-Moghaddam R, Taheri F, Bazzazi M, Izadi M, Sassani F (2009) Design of a genetic algorithm for bi-objective unrelated parallel machines scheduling with sequence-dependent setup times and precedence constraints. Comput Oper Res 36:3224–3230
Treleven M (1989) A review of the dual resource constrained system research. IIE Trans 21(3):279–287
Vallada E, Ruiz R (2011) A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times. Eur J Oper Res 211:612–622
Xu J, Xu X, Xie SQ (2011) Recent developments in dual resource constrained (DRC) system research. Eur J Oper Res 215:309–318
Zoubaa M, Baptistea P, Rebaineb D (2009) Scheduling identical parallel machines and operators within a period based changing mode. Comput Oper Res 36:3231–3239
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Costa, A., Cappadonna, F.A. & Fichera, S. A hybrid genetic algorithm for job sequencing and worker allocation in parallel unrelated machines with sequence-dependent setup times. Int J Adv Manuf Technol 69, 2799–2817 (2013). https://doi.org/10.1007/s00170-013-5221-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-013-5221-5