Top

Production Engineering

Published in:

12-06-2018 | Production Management

Review and classification of hybrid shop scheduling

Authors: Kun Fan, Yafei Zhai, Xinning Li, Meng Wang

Published in: Production Engineering | Issue 5/2018

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Hybrid shop scheduling has gained popularity due to the rapid rise of market demand and development of production technology. It is a combination of more than one classical shop scheduling, such as flow shop scheduling, job shop scheduling, open shop scheduling, parallel machine scheduling, and multiprocessor task scheduling. In this paper, a classification of hybrid shop scheduling problem based on the criterion of machine environment is proposed. The problem is classified into hybrid shop scheduling with parallel machines, hybrid shop scheduling with multiprocessor task, and other hybrid shop scheduling such as the mixed shop scheduling. The citation analysis method is used to give a brief review of hybrid flow shop and job shop with parallel machines. At the same time, for hybrid shop scheduling with multiprocessor task and other hybrid shop scheduling, a detailed overview is given because of its relatively few researches. Finally, some research directions for the hybrid shop scheduling are also discussed.

previous article Control-based compensation of friction and backlash within rack-and-pinion drives

next article Scheduling two interfering job sets on parallel machines under peak power constraint

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Pinedo M, Hadavi K (1992) Scheduling: theory. Algorithms and systems development. Springer, Berlin

Baker KR (1974) Introduction to sequencing and scheduling. Handb Oper Res Manag Sci 28:203

Chen B, Potts CN, Woeginger GJ (1998) A review of machine scheduling: complexity. Algorithms and approximability. Springer, New YorkMATH

Paul PMS, Vincent CSW (1996) The complexity of scheduling in practice. Int J Oper Prod Manag 16:37–53

Graham RL et al (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann Discret Math 5:287–326MathSciNetMATH

Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W.H. Freeman, New YorkMATH

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

Kolonko M (1999) Some new results on simulated annealing applied to the job shop scheduling problem. Eur J Oper Res 113:123–136MATH

Linn R, Zhang W (1999) Hybrid flow shop scheduling: a survey. Comput Ind Eng 37:57–61

10.

Wang H (2005) Flexible flow shop scheduling: optimum, heuristics and artificial intelligence solutions. Expert Syst 22:78–85

11.

Ruiz R, Vázquez-Rodríguez JA (2010) The hybrid flow shop scheduling problem. Eur J Oper Res 205:1–18MathSciNetMATH

12.

Arthanari TS, Ramamurthy KG (1971) An extension of two machines sequencing problem. Opsearch 8:10–22MathSciNet

13.

Salvador MS (1973) A solution to a special class of flow shop scheduling problems. Symposium on the theory of scheduling and its applications. Springer, Berlin

14.

Kis T, Pesch E (2005) A review of exact solution methods for the non-preemptive multiprocessor flowshop problem. Eur J Oper Res 164:592–608MathSciNetMATH

15.

Gupta JND (1988) Two-stage, hybrid flowshop scheduling problem. J Oper Res Soc 39:359–364MATH

16.

Hoogeveen JA, Lenstra JK, Veltman B (1996) Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard. Eur J Oper Res 89:172–175MATH

17.

Wittrock RJ (1985) Scheduling algorithms for flexible flow lines. IBM J Res Dev 29:401–412

18.

Wittrock RJ (1988) An adaptable scheduling algorithm for flexible flow lines. Oper Res 36:445–453MATH

19.

Ribas I, Leisten R, Framiñan JM (2010) Review and classification of hybrid flow shop scheduling problems from a production system and a solutions procedure perspective. Comput Oper Res 37:1439–1454MathSciNetMATH

20.

Morais MDF, Filho MG, Boiko TJP (2013) Hybrid flow shop scheduling problems involving setup considerations: a literature review and analysis. Int J Ind Eng Theory 20:614–630

21.

Zandieh M, Ghomi SMTF, Husseini SMM (2006) An immune algorithm approach to hybrid flow shops scheduling with sequence-dependent setup times. Appl Math Comput 180:111–127MathSciNetMATH

22.

Engin O, Döyen A (2004) A new approach to solve hybrid flow shop scheduling problems by artificial immune system. Futur Gener Comput Syst 20:1083–1095

23.

Allaoui H, Artiba A (2004) Integrating simulation and optimization to schedule a hybrid flow shop with maintenance constraints. Comput Ind Eng 47:431–450

24.

Allaoui H, Artiba A (2006) Scheduling two-stage hybrid flow shop with availability constraints. Comput Oper Res 33:1399–1419MathSciNetMATH

25.

Adam Janiak et al (2007) Metaheuristic approaches to the hybrid flow shop scheduling problem with a cost-related criterion. Int J Prod Econ 105:407–424

26.

Alaykýran K, Engin O, Döyen A (2007) Using ant colony optimization to solve hybrid flow shop scheduling problems. Int J Adv Manuf Technol 35:541–550

27.

Haouari M, Hidri L, Gharbi A (2006) Optimal scheduling of a two-stage hybrid flow shop. Math Method Oper Res 64:107–124MathSciNetMATH

28.

Jungwattanakit J et al (2008) Algorithms for flexible flow shop problems with unrelated parallel machines, setup times, and dual criteria. Int J Adv Manuf Technol 37(3–4):354–370

29.

Allahverdi A (2015) The third comprehensive survey on scheduling problems with setup times\(\backslash\)costs. Eur J Oper Res 246:345–378MathSciNetMATH

30.

Wang SY et al (2013) An enhanced estimation of distribution algorithm for solving hybrid flow-shop scheduling problem with identical parallel machines. Int J Adv Manuf Technol 68:2043–2056

31.

Eskandari H, Hosseinzadeh A (2014) A variable neighbourhood search for hybrid flow-shop scheduling problem with rework and set-up times. J Oper Res Soc 65:1221–1231

32.

Li JQ, Pan QK, Wang FT (2014) A hybrid variable neighborhood search for solving the hybrid flow shop scheduling problem. Appl Soft Comput 24:63–77

33.

Jun S, Park J (2015) A hybrid genetic algorithm for the hybrid flow shop scheduling problem with nighttime work and simultaneous work constraints: A case study from the transformer industry. Expert Syst Appl 42:6196–6204

34.

Li JQ, Pan QK (2015) Solving the large-scale hybrid flow shop scheduling problem with limited buffers by a hybrid artificial bee colony algorithm. Inform Sci 316:487–502

35.

Azzi A et al (2011) Lot splitting scheduling procedure for makespan reduction and machine capacity increase in a hybrid flow shop with batch production. Int J Adv Manuf Technol 59:775–786

36.

Wang S, Liu M (2012) A genetic algorithm for two-stage no-wait hybrid flow shop scheduling problem. Comput Oper Res 40:1064–1075MathSciNetMATH

37.

Qin H (2014) An estimation of distribution algorithm for hybrid flow shop scheduling under stochastic processing times. Int J Prod Res 52:7360–7376

38.

Wang SY, Wang L, Liu M, Xu Y (2014) An order-based estimation of distribution algorithm for stochastic hybrid flow-shop scheduling problem. Int J Comput Integr Manuf 28:307–320

39.

Xia W, Wu Z (2005) An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems. Comput Ind Eng 48:409–425

40.

Brucker P, Schlie R (1991) Job-shop scheduling with multi-purpose machines. Computing 45:369–375MathSciNetMATH

41.

Dauzere-Peres S, Paulli J (1997) An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search. Ann Oper Res 70:281–306MathSciNetMATH

42.

Chen KP et al (2006) The shifting bottleneck procedure for job-shops with parallel machines. Int J Ind Syst Eng 1:244–262

43.

Brandimarte P (1993) Routing and scheduling in a flexible job shop by tabu search. Ann Oper Res 41:157–183MATH

44.

Zhang G et al (2009) An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem. Comput Ind Eng 56:1309–1318

45.

Du X, Li Z, Xiong W (2008) Flexible job shop scheduling problem solving based on genetic algorithm with model constraints. In: IEEE international conference on industrial engineering and engineering management. IEEE, pp 1239–1243

46.

Genova K, Kirilov L, Guliashki V (2015) A survey of solving approaches for multiple objective flexible job shop scheduling problems. Cybern Inf Technol 15:3–22MathSciNet

47.

Chaudhry IA, Khan AA (2016) A research survey: review of flexible job shop scheduling techniques. Int Trans Oper Res 23:551–591MathSciNetMATH

48.

Pezzella F, Morganti G, Ciaschetti G (2008) A genetic algorithm for the flexible job-shop scheduling problem. Comput Oper Res 35:3202–3212MATH

49.

Gao J, Sun L, Gen M (2008) A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems. Comput Oper Res 35:2892–2907MathSciNetMATH

50.

Ho NB, Tay JC, Lai MK (2007) An effective architecture for learning and evolving flexible job-shop schedules. Eur J Oper Res 179:316–333MATH

51.

Fattahi P, Mehrabad MS, Jolai F (2007) Mathematical modeling and heuristic approaches to flexible job shop scheduling problems. J Intell Manuf 18:331–342

52.

Yazdani M, Amiri M, Zandieh M (2010) Flexible job-shop scheduling with parallel variable neighborhood search algorithm. Expert Syst Appl 37:678–687MATH

53.

Tay JC, Ho NB (2008) Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems. Comput Ind Eng 54:453–473

54.

Bagheri A et al (2010) An artificial immune algorithm for the flexible job-shop scheduling problem. Futur Gener Comput Syst 26:533–541

55.

Xing LN et al (2010) A knowledge-based ant colony optimization for flexible job shop scheduling problems. Appl Soft Comput 10:888–896

56.

Li JQ, Pan QK, Liang YC (2010) An effective hybrid tabu search algorithm for multi-objective flexible job-shop scheduling problems. Comput Ind Eng 59:647–662

57.

Zhang G, Gao L, Shi Y (2011) An effective genetic algorithm for the flexible job-shop scheduling problem. Expert Syst Appl 38:3563–3573

58.

Li X, Gao L (2016) An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem. Int J Prod Econ 174:93–110

59.

Li JQ, Pan QK, Tasgetiren MF (2014) A discrete artificial bee colony algorithm for the multi-objective flexible job-shop scheduling problem with maintenance activities. Appl Math Model 38:1111–1132MathSciNet

60.

Yuan Y, Xu H (2015) Multiobjective flexible job shop scheduling using memetic algorithms. IEEE T Autom Sci Eng 12:336–353

61.

Rey GZ et al (2015) Solving the flexible job-shop just-in-time scheduling problem with quadratic earliness and tardiness costs. Int J Adv Manuf Technol 81:1871–1891

62.

Chiang TC, Lin HJ (2013) A simple and effective evolutionary algorithm for multiobjective flexible job shop scheduling. Int J Prod Econ 141:87–98

63.

Gao KZ et al (2016) Artificial bee colony algorithm for scheduling and rescheduling fuzzy flexible job shop problem with new job insertion. Knowl Based Syst 109:1–16

64.

Gao KZ et al (2014) Pareto-based grouping discrete harmony search algorithm for multi-objective flexible job shop scheduling. Inf Sci 289:76–90MathSciNetMATH

65.

Xiong J et al (2012) A hybrid multiobjective evolutionary approach for flexible job-shop scheduling problems. Math Probl Eng 2012:857–868

66.

Jia S, Hu ZH (2014) Path-relinking Tabu search for the multi-objective flexible job shop scheduling problem. Comput Oper Res 47:11–26MathSciNetMATH

67.

Karthikeyan S et al (2015) A hybrid discrete firefly algorithm for solving multi-objective flexible job shop scheduling problems. Int J Bio-Inspired Comput 7:386–401

68.

Gao KZ et al (2015) An effective discrete harmony search algorithm for flexible job shop scheduling problem with fuzzy processing time. Int J Prod Res 19:5896–5911

69.

Bai D, Zhang ZH, Zhang Q (2015) Flexible open shop scheduling problem to minimize makespan. Comput Oper Res 67:207–215MathSciNetMATH

70.

Lawler EL, Luby MG, Vazirani VV (1982) Scheduling open shops with parallel machines. Oper Res Lett 1:161–164MATH

71.

Werra DD, Kis T, Kubiak W (2008) Preemptive open shop scheduling with multiprocessors: polynomial cases and applications. J Sched 11:75–83MathSciNetMATH

72.

Kis T, Werra DD, Kubiak W (2010) A projective algorithm for preemptive open shop scheduling with two multiprocessor groups. Oper Res Lett 38:129–132MathSciNetMATH

73.

Matta ME, Elmaghraby SE (2010) Polynomial time algorithms for two special classes of the proportionate multiprocessor open shop. Eur J Oper Res 201:720–728MathSciNetMATH

74.

Chen B, Strusevich VA (1993) Worst-case analysis of heuristics for open shops with parallel machines. Eur J Oper Res 70:379–390MATH

75.

Schuurman P, Woeginger GJ (1999) Approximation algorithms for the multiprocessor open shop scheduling problem. Oper Res Lett 24:157–163MathSciNetMATH

76.

Bárány I, Fiala T (1982) Nearly optimum solution of multi-machine scheduling problems. Szigma Mat-Közgazdasági Folyóirat 15:177–191MathSciNetMATH

77.

Sevastianov SV, Woeginger GJ (2001) Linear time approximation scheme for the multiprocessor open shop problem. Discret Appl Math 114:273–288MATH

78.

Naderi B et al (2011) Scheduling open shops with parallel machines to minimize total completion time. J Comput Appl Math 235:1275–1287MathSciNetMATH

79.

Chou FD, Wang HM (2013) A simulated annealing to solve four-stage open shops with parallel machines. Appl Mech Mater 330:843–847

80.

Drozdowski M (1996) Scheduling multiprocessor tasks. An overview. Eur J Oper Res 94:215–230MATH

81.

Oǧuz C et al (2004) Hybrid flow-shop scheduling problems with multiprocessor task systems. Eur J Oper Res 152:115–131MathSciNet

82.

Brucker P, Krämer A (1995) Shop scheduling problems with multiprocessor tasks on dedicated processors. Ann Oper Res 57:13–27MathSciNetMATH

83.

Brucker P, Krämer A (1996) Polynomial algorithms for resource-constrained and multiprocessor task scheduling problems. Eur J Oper Res 90:214–226MATH

84.

Sun JH, Meng YK (2015) An approximation scheme for heterogeneous parallel task scheduling in a two-stage hybrid flow shop. J Inf Sci Eng 31:1291–1308MathSciNet

85.

Oǧuz C et al (2003) Parallel genetic algorithm for a flow-shop problem with multiprocessor tasks. Int Conf Comput Sci Part III 2667:987–997

86.

Oǧuz C et al (2003) Heuristic algorithms for multiprocessor task scheduling in a two-stage hybrid flow-shop. Eur J Oper Res 149:390–403MathSciNet

87.

Şerifoǧlu FS, Ulusoy G (2004) Multiprocessor task scheduling in multistage hybrid flow-shops: a genetic algorithm approach. J Oper Res Soc 55:504–512MATH

88.

Oǧuz C, Ercan MF (2005) A genetic algorithm for hybrid flow-shop scheduling with multiprocessor tasks. J Sched 8:323–351MathSciNetMATH

89.

Engin O, Ceran G, Yilmaz MK (2011) An efficient genetic algorithm for hybrid flow shop scheduling with multiprocessor task problems. Appl Soft Comput 11:3056–3065

90.

Ying KC, Lin SW (2006) Multiprocessor task scheduling in multistage hybrid flow-shops: an ant colony system approach. Int J Prod Res 44:3161–3177MATH

91.

Ying KC (2009) An iterated greedy heuristic for multistage hybrid flowshop scheduling problems with multiprocessor tasks. J Oper Res Soc 60:810–817MATH

92.

Liao CJ (2008) A particle swarm optimization algorithm for hybrid flow-shop scheduling with multiprocessor tasks. Int J Prod Res 46:4655–4670MATH

93.

Chou FD (2013) Particle swarm optimization with cocktail decoding method for hybrid flow shop scheduling problems with multiprocessor tasks. Int J Prod Econ 141:137–145

94.

Kahraman C et al (2010) Multiprocessor task scheduling in multistage hybrid flow-shops: a parallel greedy algorithm approach. Appl Soft Comput 10:1293–1300

95.

Akhshabi M, Akhshabi M, Khalatbari J (2011) A memetic algorithm for hybrid flow shop scheduling with multiprocessor task problems. Appl Soft Comput 11:3056–3065

96.

Wang HM, Chou FD, Wu FC (2011) A simulated annealing for hybrid flow shop scheduling with multiprocessor tasks to minimize makespan. Int J Adv Manuf Technol 53:761–776

97.

Xu Y et al (2013) An effective shuffled frog-leaping algorithm for hybrid flow-shop scheduling with multiprocessor tasks. Int J Adv Manuf Technol 68:1529–1537

98.

Lin SW, Ying KC, Huang CY (2013) Multiprocessor task scheduling in multistage hybrid flowshops: a hybrid artificial bee colony algorithm with bi-directional planning. Comput Oper Res 40:1186–1195MathSciNetMATH

99.

Xu Y et al (2013) An effective immune algorithm based on novel dispatching rules for the flexible flow-shop scheduling problem with multiprocessor tasks. Int J Adv Manuf Technol 67:121–135

100.

Akkoyunlu MC, Engin O, Buyukozkan K (2015) A harmony search algorithm for hybrid flow shop scheduling with multiprocessor task problems. In: International conference on modeling, simulation, and applied optimization. IEEE, pp 1–3

101.

Wang HM et al (2011) Hybrid flow shop scheduling problems with multiprocessor tasks. Appl Mech Mater 110–116:3914–3921

102.

Lahimer A, Lopez P, Haouari M (2013) Improved bounds for hybrid flow shop scheduling with multiprocessor tasks. Comput Ind Eng 66:1106–1114MATH

103.

Brucker P, Neyer J (1998) Tabu-search for the multi-mode job-shop problem. Oper Res Spektrum 20:21–28MathSciNetMATH

104.

Heinz G et al (2008) Feasible job insertions in the multi-processor-task job shop. Eur J Oper Res 185:1308–1318MathSciNetMATH

105.

Masuda T, Ishii H, Nishida T (1985) The mixed shop scheduling problem. Discret Appl Math 11:175–186MathSciNetMATH

106.

Strusevich VA (1991) Two-machine super-shop scheduling problem. J Oper Res Soc 42:479–492MATH

107.

Shakhlevich NV, Sotskov YN, Werner F (2000) Complexity of mixed shop scheduling problems: a survey. Eur J Oper Res 120:343–351MathSciNetMATH

108.

Liu SQ, Ong HL (2012) Metaheuristics for the mixed shop scheduling problem. Asia Pac J Oper Res 21:97–115MathSciNetMATH

109.

Anand E, Panneerselvam R (2013) A novel metaheuristics to solve mixed shop scheduling problems. Int J Found Comput Sci Technol 3:33–52

110.

Sevast’yanov SV (1981) Some generalizations of the Johnson problem. Upravlyaemye Sistemy 21(45–61):71MathSciNetMATH

111.

Kostoff RN (1998) The use and misuse of citation analysis in research evaluation. Scientometrics 43:27–43

Title: Review and classification of hybrid shop scheduling
Authors: Kun Fan
Yafei Zhai
Xinning Li
Meng Wang
Publication date: 12-06-2018
Publisher: Springer Berlin Heidelberg
Published in: Production Engineering / Issue 5/2018
Print ISSN: 0944-6524
Electronic ISSN: 1863-7353
DOI: https://doi.org/10.1007/s11740-018-0832-1

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Other articles of this Issue 5/2018

Experimental investigation of the friction stir welding dynamics of 6000 series aluminum alloys

Coordination policy for production and delivery scheduling in the closed loop supply chain

Control-based compensation of friction and backlash within rack-and-pinion drives

Efficiency improvement in electrical discharge machining (EDM) of constant section cavity based on experimental study and numerical calculations

A novel competitive hybrid approach based on grouping evolution strategy algorithm for solving U-shaped assembly line balancing problems

Modeling of an aluminum melting process using constructive polynomial functions

Premium Partners