Top

Published in:

2018 | OriginalPaper | Chapter

Open-Shop Scheduling for Unit Jobs Under Precedence Constraints

Authors : An Zhang, Yong Chen, Randy Goebel, Guohui Lin

Published in: Combinatorial Optimization and Applications

Publisher: Springer International Publishing

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

search-config

AI-assisted search

Off

Abstract

We study open-shop scheduling for unit jobs under precedence constraints, where if one job precedes another job then it has to be finished before the other job can start to be processed. For the three-machine open-shop to minimize the makespan, we first present a simple 5/3-approximation based on a partition of the job set into agreeable layers using the natural layered representation of the precedence graph. We then show a greedy algorithm to reduce the number of singleton-job layers, resulting in an improved partition, which leads to a 4/3-approximation. Both approximation algorithms apply to the general m-machine open-shops too.

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 Related Machine Scheduling with Machine Speeds Satisfying Linear Constraints

next chapter Makespan Minimization on Unrelated Parallel Machines with Simple Job-Intersection Structure and Bounded Job Assignments

Bräsel, H., Kluge, D., Werner, F.: A polynomial algorithm for the \([n/m/0, t_{ij}=1, tree/C_{\max }]\) open shop problem. Eur. J. Oper. Res. 72, 125–134 (1994)CrossRef

Brucker, P.: Scheduling Algorithms. Springer, New York (2007). https://doi.org/10.1007/978-3-540-69516-5CrossRefMATH

Brucker, P., Jurisch, B., Jurisch, M.Z.: Open shop problems with unit time operations. Oper. Res. 37, 59–73 (1993)MathSciNetMATH

Brucker, P., Knust, S.: Complexity results for scheduling problems (2009). http://www2.informatik.uni-osnabrueck.de/knust/class/

Dürr, C.: The scheduling zoo (2016). http://schedulingzoo.lip6.fr

Gonzalez, T., Sahni, S.: Open shop scheduling to minimize finish time. J. ACM 23, 665–679 (1976)MathSciNetCrossRef

Graham, R.L.: Combinatorial scheduling theory. In: Steen, L.A. (ed.) Mathematics Today Twelve Informal Essays. Springer, New York (1978). https://doi.org/10.1007/978-1-4613-9435-8_8CrossRefMATH

Lenstra, J.K., Rinnooy Kan, A.H.G.: Complexity of scheduling under precedence constraints. Oper. Res. 26, 22–35 (1978)MathSciNetCrossRef

Pinedo, M.L.: Scheduling: Theory, Algorithm and Systems. Springer, New York (2016). https://doi.org/10.1007/978-3-319-26580-3CrossRefMATH

10.

Prot, D., Bellenguez-Morinea, O.: A survey on how the structure of precedence constraints may change the complexity class of scheduling problems. J. Sched. 21, 3–16 (2018)MathSciNetCrossRef

11.

Sevastianov, S.V., Woeginger, G.J.: Makespan minimization in open shops: a polynomial time approximation scheme. Math. Program. 82, 191–198 (1998)MathSciNetMATH

12.

Sevastianov, S.V., Woeginger, G.J.: Linear time approximation scheme for the multiprocessor open shop problem. Discrete Appl. Math. 114, 273–288 (2001)MathSciNetCrossRef

13.

Tanaev, V.S., Sotskov, Y.N., Strusevich, V.A.: Scheduling Theory: Multi-Stage Systems. Springer, Heidelberg (1994). https://doi.org/10.1007/978-94-011-1192-8CrossRefMATH

14.

Timkovsky, V.G.: Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity. Eur. J. Oper. Res. 149, 355–376 (2003)MathSciNetCrossRef

15.

Williamson, D.P., et al.: Short shop schedules. Oper. Res. 45, 288–294 (1997)MathSciNetCrossRef

Title: Open-Shop Scheduling for Unit Jobs Under Precedence Constraints
Authors: An Zhang
Yong Chen
Randy Goebel
Guohui Lin
Publisher: Springer International Publishing
Book: Combinatorial Optimization and Applications
Print ISBN: 978-3-030-04650-7

Electronic ISBN: 978-3-030-04651-4

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-030-04651-4_22

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"

Springer Professional "Wirtschaft"

Premium Partner