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:
An Optimal Expansion Strategy for the German Railway Network Until 2030 Read chapter Read first chapter

2018 | OriginalPaper | Chapter

Scheduling on Uniform Nonsimultaneous Parallel Machines

Authors : Liliana Grigoriu, Donald K. Friesen

Published in: Operations Research Proceedings 2016

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

We consider the problem of scheduling on uniform processors which may not start processing at the same time with the purpose of minimizing the maximum completion time. We provide a variant of the MULTIFIT algorithm which generates schedules which end within 1.382 times the optimal maximum completion time for the general problem, and within \(\sqrt{6}/2\) times the optimal maximum completion time for problem instances with two processors. Experimental results suggest that our algorithm is a viable option for addressing this problem in practice.

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 Optimizing Machine Spare Parts Inventory Using Condition Monitoring Data
next chapter Markov Models for System Throughput Analysis in Warehouse Design
Literature
1.
Coffman Jr., E.G., Garey, M.R., Johnson, D.S.: An application of Bin-Packing to multiprocessor scheduling. SIAM J. Comput. 7(1), 1–17 (1978)CrossRef
2.
Lee, C.Y.: Parallel Machine Scheduling with nonsimultaneous machine available time. Discrete Appl. Math. 30(1), 53–61 (1991)
3.
Chang, S.Y., Hwang, H.: The worst-case analysis of the MULTIFIT algorithm for scheduling nonsimultaneous parallel machines. Discrete Appl. Math. 92, 135–147 (1999)CrossRef
4.
5.
Friesen, D.K., Langston, M.A.: Bounds for multifit scheduling on uniform processors. SIAM J. Comput. 12(1), 60–69 (1983)CrossRef
6.
Chen, B.: Tighter bound for MULTIFIT scheduling on uniform processors. Discrete Appl. Math. 31(3), 227–260 (1991)
7.
Burkard, R.E., He, Y.: A note on MULTIFIT scheduling for uniform machines. Computing 61(3), 277–283 (1998)CrossRef
8.
He, Y.: Uniform machine scheduling with machine available constraints. Acta Math. Appl. Sin. (English Series), 16(2), 122–129 (2000)
9.
10.
Grigoriu, L., Friesen, D.K.: Scheduling on uniform processors with at most one downtime on each machine. Discrete Optim. 17, 14–24 (2015)CrossRef
11.
Grigoriu, L.: Scheduling on parallel machines with variable availability patterns. Ph.D. thesis, Politehnica University Bucharest (2012)
Metadata
Title
Scheduling on Uniform Nonsimultaneous Parallel Machines
Authors
Liliana Grigoriu
Donald K. Friesen
Copyright Year
2018
Book
Operations Research Proceedings 2016

Print ISBN: 978-3-319-55701-4

Electronic ISBN: 978-3-319-55702-1

Copyright Year: 2018

DOI
https://doi.org/10.1007/978-3-319-55702-1_62