Skip to main content
Top

2016 | OriginalPaper | Chapter

An Iterated Local Search for a Re-entrant Flow Shop Scheduling Problem

Authors : Richard Hinze, Dirk Sackmann

Published in: Operations Research Proceedings 2014

Publisher: Springer International Publishing

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

search-config
loading …

Abstract

This paper discusses a re-entrant permutation flow shop scheduling problem with missing operations. The two considered objective functions are makespan and total flow time. Re-entrant flows are characterized by a multiple processing of jobs on more than one machine. We propose a heuristic for solving the problem. Since there have been promising approaches in literature on other scheduling problems, we chose the iterated local search (ILS). This meta-heuristic framework combines the advantages of local search algorithm and still tries to avoid being stuck in local optima by a so called shaking step. The initial solution for the ILS is obtained by a dispatching rule. Various rules have been tested, e.g., total job processing time and total processing time of job levels. A hill climbing algorithm has been implemented as the integrated local search method of the ILS. The ILS is compared to a MIP formulation from literature. The results show, that the ILS can deliver better results.

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!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literature
1.
go back to reference Chamnanlor, C., Sethanan, K., Chien, C., Gen, M.: Reentrant flow-shop scheduling with time windows for hard-disk manufacturing by hybrid genetic algorithms. In: Asia Pacific Industrial Engineering and Management Systems Conference, pp. 896–907 (2012) Chamnanlor, C., Sethanan, K., Chien, C., Gen, M.: Reentrant flow-shop scheduling with time windows for hard-disk manufacturing by hybrid genetic algorithms. In: Asia Pacific Industrial Engineering and Management Systems Conference, pp. 896–907 (2012)
2.
go back to reference Danping, L., Lee, C.K.: A review of the research methodology for the re-entrant scheduling problem. Int. J. Prod. Res. 49, 2221–2242 (2011)CrossRef Danping, L., Lee, C.K.: A review of the research methodology for the re-entrant scheduling problem. Int. J. Prod. Res. 49, 2221–2242 (2011)CrossRef
3.
go back to reference Graves, S.C.: A review of production scheduling. Oper. Res. Inf. 29, 646–675 (1981)CrossRef Graves, S.C.: A review of production scheduling. Oper. Res. Inf. 29, 646–675 (1981)CrossRef
4.
go back to reference Hekmatfar, M., Fatemi Ghomi, S.M.T., Karimi, B.: Two stage reentrant hybrid flow shop with setup times and the criterion of minimizing makespan. Appl. Soft. Comput. 11, 4530–4539 (2011) Hekmatfar, M., Fatemi Ghomi, S.M.T., Karimi, B.: Two stage reentrant hybrid flow shop with setup times and the criterion of minimizing makespan. Appl. Soft. Comput. 11, 4530–4539 (2011)
5.
go back to reference Hinze, R., Sackmann, D., Buscher, U., Aust, G.: A contribution to the reentrant flow-shop scheduling problem. In: Proceedings of IFAC Conference Manufacturing Modelling, Management, and Control, pp. 718–723. IFAC, St. Petersburg (2013) Hinze, R., Sackmann, D., Buscher, U., Aust, G.: A contribution to the reentrant flow-shop scheduling problem. In: Proceedings of IFAC Conference Manufacturing Modelling, Management, and Control, pp. 718–723. IFAC, St. Petersburg (2013)
6.
go back to reference Lin, D., Lee, C., Wu, Z.: Integrated GA and AHP for re-entrant flow shop scheduling problem. In: 2011 IEEE International Conference on Quality and Reliability (ICQR), pp. 496–500. IEEE (2011) Lin, D., Lee, C., Wu, Z.: Integrated GA and AHP for re-entrant flow shop scheduling problem. In: 2011 IEEE International Conference on Quality and Reliability (ICQR), pp. 496–500. IEEE (2011)
7.
go back to reference Lin, D., Lee, C., Wu, Z.: Integrating analytical hierarchy process to genetic algorithm for re-entrant flow shop scheduling problem. Int. J. Prod. Res. 50, 1813–1824 (2012)CrossRef Lin, D., Lee, C., Wu, Z.: Integrating analytical hierarchy process to genetic algorithm for re-entrant flow shop scheduling problem. Int. J. Prod. Res. 50, 1813–1824 (2012)CrossRef
8.
go back to reference Pan, J., Chen, J.: Minimizing makespan in re-entrant permutation flow-shops. J. Oper. Res. Soc. 54, 642–653 (2003)CrossRef Pan, J., Chen, J.: Minimizing makespan in re-entrant permutation flow-shops. J. Oper. Res. Soc. 54, 642–653 (2003)CrossRef
9.
go back to reference Uzsoy, R., Lee, C.Y., Martin-Vega, L.A.: A review of production planning and scheduling models in the semiconductor industry. Part I: System characteristics, performance evaluation and production planning. IIE Trans. 24, 47–60 (1992)CrossRef Uzsoy, R., Lee, C.Y., Martin-Vega, L.A.: A review of production planning and scheduling models in the semiconductor industry. Part I: System characteristics, performance evaluation and production planning. IIE Trans. 24, 47–60 (1992)CrossRef
10.
go back to reference Uzsoy, R., Lee, C.Y., Martin-Vega, L.A.: A review of production planning and scheduling models in the semiconductor industry. Part II: Shop-floor control. IIE Trans. 26, 44–55 (1994)CrossRef Uzsoy, R., Lee, C.Y., Martin-Vega, L.A.: A review of production planning and scheduling models in the semiconductor industry. Part II: Shop-floor control. IIE Trans. 26, 44–55 (1994)CrossRef
Metadata
Title
An Iterated Local Search for a Re-entrant Flow Shop Scheduling Problem
Authors
Richard Hinze
Dirk Sackmann
Copyright Year
2016
DOI
https://doi.org/10.1007/978-3-319-28697-6_31