Skip to main content

Advertisement

Springer Nature Link
Log in

A hybrid genetic algorithm for job sequencing and worker allocation in parallel unrelated machines with sequence-dependent setup times

  • ORIGINAL ARTICLE
  • Published:
The International Journal of Advanced Manufacturing Technology Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Anghinolfi D, Paolucci M (2007) Parallel machine total tardiness scheduling with a new hybrid metaheuristic approach. Comput Oper Res 34:3471–3490

    Article  MathSciNet  MATH  Google Scholar 

  2. Askin RG, Huang RY (2001) Forming effective work teams for cellular manufacturing. Int J Prod Res 39(11):2431–2451

    Article  MATH  Google Scholar 

  3. Balin S (2011) Non-identical parallel machine scheduling using genetic algorithm. Expert Syst Appl 38:6814–6821

    Article  Google Scholar 

  4. 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

    Article  MATH  Google Scholar 

  5. 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

    Article  MATH  Google Scholar 

  6. 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

    Article  Google Scholar 

  7. 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

    Article  MathSciNet  Google Scholar 

  8. 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

    Article  Google Scholar 

  9. Cheng R, Gen M (1997) Parallel machine scheduling problems using memetic algorithms. Comput Ind Eng 33(3–4):761–764

    Article  Google Scholar 

  10. 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

    Article  MathSciNet  MATH  Google Scholar 

  11. 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

    Article  Google Scholar 

  12. Fanjul-Peyro L, Ruiz R (2011) Size-reduction heuristics for the unrelated parallel machines scheduling problem. Comput Oper Res 38:301–309

    Article  Google Scholar 

  13. Fanjul-Peyro L, Ruiz R (2012) Scheduling unrelated parallel machines with optional machines and jobs selection. Comput Oper Res 39:1745–1753

    Article  MathSciNet  MATH  Google Scholar 

  14. 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

    Article  Google Scholar 

  15. Holland JH (1975) Adaptation in natural and artificial systems. The University of Michigan Press, Ann Arbor

    Google Scholar 

  16. 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

    Article  Google Scholar 

  17. 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

    Article  Google Scholar 

  18. 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

    Article  Google Scholar 

  19. 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

    Article  Google Scholar 

  20. Kim SC, Bobrowsky PM (1997) Scheduling jobs with uncertain setup times and sequence dependency. OMEGA Int J Manag Sci 25(4):437–447

    Article  Google Scholar 

  21. 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

    Article  Google Scholar 

  22. 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

    Article  Google Scholar 

  23. Lenstra JK, Rinnooy Kan AHG, Brucker P (1977) Complexity of machine scheduling problems. Ann Discret Math 1:342–362

    MathSciNet  Google Scholar 

  24. Michalewicz Z (1994) Genetic algorithms + data structures = evolution programs, 2nd edn. Springer, Berlin

    MATH  Google Scholar 

  25. Montgomery D (2007) Design and analysis of experiments, 5th edn. Wiley, New York

    Google Scholar 

  26. Nelson RT (1967) Labor and machine limited production systems. Manag Sci 13(9):648–671

    Article  Google Scholar 

  27. 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

    Article  MATH  Google Scholar 

  28. 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

    Google Scholar 

  29. 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

    Article  Google Scholar 

  30. 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

    Article  MATH  Google Scholar 

  31. Pinedo M (2008) Scheduling: theory, algorithms and systems, 3rd edn. Prentice-Hall, New Jersey

    Google Scholar 

  32. Sule DR (2008) Production Planning and Industrial Scheduling: Examples, Case Studies and Applications, 2nd edn. CRC Press, Boca Raton

    Google Scholar 

  33. 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

    Google Scholar 

  34. Syswerda G (1991) Schedule optimization using genetic algorithms. In: Davis L (ed) Handbook of genetic algorithms. Van Nostrand Reinhold, New York

    Google Scholar 

  35. 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

    Article  MATH  Google Scholar 

  36. Treleven M (1989) A review of the dual resource constrained system research. IIE Trans 21(3):279–287

    Article  Google Scholar 

  37. 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

    Article  MathSciNet  Google Scholar 

  38. Xu J, Xu X, Xie SQ (2011) Recent developments in dual resource constrained (DRC) system research. Eur J Oper Res 215:309–318

    Article  Google Scholar 

  39. 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

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dipartimento di Ingegneria Industriale, University of Catania, Catania, Italy

    A. Costa & S. Fichera

  2. Dipartimento di Ingegneria Elettrica, Elettronica e Informatica, University of Catania, Catania, Italy

    F. A. Cappadonna

Authors
  1. A. Costa
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. F. A. Cappadonna
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. S. Fichera
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to A. Costa.

Rights and permissions

Reprints 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

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00170-013-5221-5

Keywords

Search

Navigation