An optimal online algorithm for scheduling with general machine cost functions

Islam Akaria () and Leah Epstein ()
Additional contact information
Islam Akaria: University of Haifa
Leah Epstein: University of Haifa

Journal of Scheduling, 2020, vol. 23, issue 2, No 1, 155-162

Abstract: Abstract We present two deterministic online algorithms for the problem of scheduling with a general machine cost function. In this problem, every machine has a cost that is given by a nonnegative cost function, and the objective function is the sum of makespan and the cost of the purchased machines. In previous work by Imreh, it was shown that no deterministic algorithm has competitive ratio below 2, and an algorithm whose competitive ratio does not exceed $$(3+\sqrt{5})/2 \approx 2.618$$(3+5)/2≈2.618 was presented. Our first algorithm imitates an optimal offline solution with respect to the number of machines used, and we show that its competitive ratio is exactly 2.5. Then, we modify our algorithm by imitating a preemptive optimal offline solution instead of a non-preemptive one. This leads to the design of a 2-competitive algorithm, which is the best possible.

Keywords: Online scheduling; Competitive ratio; Machine cost; Preemptive scheduling (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10951-019-00629-3 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:23:y:2020:i:2:d:10.1007_s10951-019-00629-3

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

DOI: 10.1007/s10951-019-00629-3

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