Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Safeguarding Personal Health Information: Case Study Read chapter Read first chapter

2018 | OriginalPaper | Chapter

88. Heuristic Approaches for the Open-Shop Scheduling Problem

Authors : Wissam Marrouche, Haidar M. Harmanani

Published in: Information Technology - New Generations

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

The open-shop scheduling problem is concerned with the allocation of tasks to resources, especially when resources are scarce. The problem has many practical applications in the production, manufacturing, testing, and telecommunication domains. In this paper, we study the non-preemptive open-shop scheduling problem with more than two machines using two metaheuristic algorithms: cuckoo search and ant colony optimization. The proposed algorithms are implemented using Python, and tested on the Taillard benchmarks. Favorable results comparisons are reported.

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

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!

inform now
previous chapter Degree Aware Triangulation of Annular Regions
next chapter Continuous State Power-Down Systems for Renewable Energy Management
Literature
1.
K. Baker, D. Trietsch, Principles to Sequencing and Scheduling (Wiley, London, 2009)
2.
C. Blum, Beam-ACO—hybridizing ant colony optimization with beam search: an application to open shop scheduling. Comput. Oper. Res. 32(6), 1565–1591 (2005)
3.
P. Brucker, J. Huring, B. Wostmann, A branch and bound algorithm for the open shop problem. Discret. Appl. Math. 76, 43–59 (1997)
4.
J. Carlier, E. Pinson, An algorithm for solving the job shop problem. Manag. Sci. 35(2), 164–176 (1989)
5.
R. Chen, S. Lo, C. Wu, T. Lin, An effective ant colony optimization-based algorithm for flow shop scheduling, in IEEE Conference on Soft Computing in Industrial Applications (2008), pp. 101–106
6.
Y. Chen, A. Zhang, G. Chen, J. Dong, Approximation algorithms for parallel open shop scheduling. Inf. Process. Lett. 113(7), 220–224 (2013)
7.
M. Dorigo, Optimization, learning and natural algorithms, Ph.D. thesis, Politecnico di Milano, 1992
8.
M. Dorigo, T. Stützle, Ant Colony Optimization (MIT Press, Cambridge, MA, 2004)
9.
M.R. Garey, D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (W. H. Freeman, San Francisco, CA, 1979)
10.
S.B. Ghosn, F. Drouby, H. Harmanani, A parallel genetic algorithm for the open-shop scheduling problem using deterministic and random moves. Int. J. Artif. Intell. 14(1), 130–144 (2016)
11.
T. Gonzalez, S. Sahni, Open shop scheduling to minimize finish time. J. Assoc. Comput. Mach. 23(4), 665–679 (1976)
12.
C. Gueret, C. Prins, Classical and new heuristics for the open-shop problem: a computational evaluation. Eur. J. Oper. Res. 107, 306–314 (1998)
13.
C. Guéret, C. Prins, A new lower bound for the open-shop problem. Ann. Oper. Res. 92, 165–183 (1999)
14.
H. Harmanani, S. Bou Ghosn, An efficient method for the open-shop scheduling problem using simulated annealing, in Information Technology: New Generations: 13th International Conference on Information Technology (Springer, Cham, 2016), pp. 1183–1193
15.
M. Hassan, I. Kacem, S. Martin, I.M. Osman, Mathematical formulation for open shop scheduling problem, in International Conference on Control, Decision and Information Technologies (CoDIT) (2017), pp. 803–808
16.
S. Khuri, S. Miryala, Genetic algorithms for solving open shop scheduling problems, in Proceedings of the Portuguese Conference on Artificial Intelligence (1999), pp. 357–368
17.
C.-F. Liaw, An iterative improvement approach for the nonpreemptive open shop scheduling problem. Eur. J. Oper. Res. 111, 509–517 (1998)
18.
C.-F. Liaw, A tabu search algorithm or the open shop scheduling problem. Comput. Oper. Res. 26(2), 109–126 (1999)
19.
C.-F. Liaw, Applying simulated annealing to the open shop scheduling problem. IIE Trans. Schedul. Logist. 31(5), 457–465 (1999)
20.
C.-F. Liaw, A hybrid genetic algorithm for the open shop scheduling problem. Eur. J. Oper. Res. 124, 28–42 (2000)
21.
S. Luke, Essentials of Metaheuristics (Lulu, Morrisville, NC, 2013)
22.
I. Pavlyukevich, Lévy flights, non-local search and simulated annealing. J. Comput. Phys. 226, 1830–1844 (2007)
23.
M. Pineda, Scheduling: Theory, Algorithms, and Systems (Prentice Hall, Englewood Cliffs, NJ, 1995)
24.
C. Prins, Competitive genetic algorithms for the open-shop scheduling problem. Math. Meth. Oper. Res. 52(3), 389–411 (2000)MathSciNetCrossRef
25.
D.Y. Shaa, C.-Y. Hsu, A new particle swarm optimization for the open shop scheduling problem. Comput. Oper. Res. 35, 3243–3261 (2008)CrossRef
26.
D.P. Van, M. Fiorani, L. Wosinska, J. Chen, Adaptive open-shop scheduling for optical interconnection networks. J. Lightwave Technol. 35(13), 2503–2513 (2017)CrossRef
27.
S. Walton, O. Hassan, K. Morgan, M.R. Brown, Modified cuckoo search: a new gradient free optimisation algorithm. Chaos, Solitons Fractals 44, 710–718 (2011)CrossRef
28.
T. Yamada, R. Nakano, A genetic algorithm applicable to large-scale job-shop problems, in Parallel Problem Solving from Nature (1992), pp. 281–290
29.
X.-S. Yang, S. Deb, Cuckoo search via Lévy flights, in World Congress on Nature and Biologically Inspired Computing NaBIC (2009), pp. 210–214
30.
X.-S. Yang, S. Deb, Engineering optimisation by cuckoo search. Int. J. Math. Model. Numer. Optim. 1(4), 330–343 (2010)MATH
31.
W. Yu, Z. Liu, L. Wanga, T. Fan, Routing open shop and flow shop scheduling problems. Discret. Optim. 213, 24–36 (2011)MathSciNetMATH
Metadata
Title
Heuristic Approaches for the Open-Shop Scheduling Problem
Authors
Wissam Marrouche
Haidar M. Harmanani
Copyright Year
2018
Book
Information Technology - New Generations

Print ISBN: 978-3-319-77027-7

Electronic ISBN: 978-3-319-77028-4

Copyright Year: 2018

DOI
https://doi.org/10.1007/978-3-319-77028-4_88

Premium Partner

    Image Credits