Approximation for scheduling on uniform nonsimultaneous parallel machines

Liliana Grigoriu () and Donald K. Friesen ()
Additional contact information
Liliana Grigoriu: Fakultät für Wirtschaftswissenschaften, Wirtschaftsinformatik und Wirtschaftsrecht, Universität Siegen
Donald K. Friesen: Texas A&M University

Journal of Scheduling, 2017, vol. 20, issue 6, No 5, 593-600

Abstract: Abstract We consider the problem of scheduling on uniform machines which may not start processing at the same time with the purpose of minimizing the maximum completion time. We propose using a variant of the MULTIFIT algorithm, LMULTIFIT, which generates schedules which end within 1.382 times the optimal maximum completion time for the general problem, and within $$\sqrt{6}/2$$ 6 / 2 times the optimal maximum completion time for problem instances with two machines. Both developments represent improvements over previous results. We prove that LMULTIFIT worst-case bounds for scheduling on simultaneous uniform machines are also LMULTIFIT worst-case approximation bounds for scheduling on nonsimultaneous uniform machines and show that worst-case approximation bounds of MULTIFIT variants for simultaneous uniform machines from previous literature also apply to LMULTIFIT. We also comment on how a PTAS for scheduling on a constant number of uniform machines with fixed jobs can be used to obtain a PTAS for scheduling on a constant number of uniform nonsimultaneous parallel machines.

Keywords: Multiprocessor scheduling; Uniform processors; MULTIFIT; Nonsimultaneous start times; Worst-case bounds; Makespan (search for similar items in EconPapers)
Date: 2017
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10951-016-0501-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:20:y:2017:i:6:d:10.1007_s10951-016-0501-1

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-016-0501-1

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().