Parallel solutions for preemptive makespan scheduling on two identical machines

Leah Epstein ()
Additional contact information
Leah Epstein: University of Haifa

Journal of Scheduling, 2023, vol. 26, issue 1, No 5, 76 pages

Abstract: Abstract We consider online preemptive scheduling of jobs arriving one by one, to be assigned to two identical machines, with the goal of makespan minimization. We study the effect of selecting the best solution out of two independent solutions constructed in parallel in an online fashion. Two cases are analyzed, where one case is purely online, and in the other one jobs are presented sorted by non-increasing sizes. We show that using two solutions rather than one improves the performance significantly, but that an optimal solution cannot be obtained for any constant number of solutions constructed in parallel. Our algorithms have the best possible competitive ratios out of algorithms for each one of the classes.

Keywords: Parallel solutions; Preemptive scheduling; Jobs arriving over a list; Competitive ratio (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10951-022-00764-4 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:26:y:2023:i:1:d:10.1007_s10951-022-00764-4

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

DOI: 10.1007/s10951-022-00764-4

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 ().