Online machine minimization with lookahead

Cong Chen, Huili Zhang () and Yinfeng Xu
Additional contact information
Cong Chen: South China University of Technology
Huili Zhang: Xi’an Jiaotong University
Yinfeng Xu: Xi’an Jiaotong University

Journal of Combinatorial Optimization, 2022, vol. 43, issue 5, No 11, 1149-1172

Abstract: Abstract This paper studies the online machine minimization problem, where the jobs have real release times, uniform processing times and a common deadline. We investigate how the lookahead ability improves the performance of online algorithms. Two lookahead models are studied, that is, the additive lookahead and the multiplicative lookahead. At any time t, the online algorithm knows all the jobs to be released before time $$t+L$$ t + L (or $$\beta \cdot t$$ β · t ) in the additive (or multiplicative) lookahead model. We propose a $$\frac{e}{\alpha (e-1)+1}$$ e α ( e - 1 ) + 1 -competitive online algorithm with the additive lookahead, where $$\alpha = \frac{L}{T} \le 1$$ α = L T ≤ 1 and T is the common deadline of the jobs. For the multiplicative lookahead, we provide an online algorithm with a competitive ratio of $$\frac{\beta e}{(\beta -1) e +1}$$ β e ( β - 1 ) e + 1 , where $$\beta \ge 1$$ β ≥ 1 . Lower bounds are also provided for both of the two models, which show that our algorithms are optimal for two extreme cases, that is, $$\alpha = 0$$ α = 0 (or $$\beta = 1$$ β = 1 ) and $$\alpha = 1$$ α = 1 (or $$\beta \rightarrow \infty $$ β → ∞ ), and remain a small gap for the cases in between. Particularly, for $$\alpha = 0$$ α = 0 (or $$\beta = 1$$ β = 1 ), the competitive ratio is e, which corresponds to the problem without lookahead. For $$\alpha = 1$$ α = 1 (or $$\beta \rightarrow \infty $$ β → ∞ ), the competitive ratio is 1, which corresponds to the offline version (with full information).

Keywords: Online machine minimization; Online scheduling; Online algorithm; Lookahead (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00633-w 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:jcomop:v:43:y:2022:i:5:d:10.1007_s10878-020-00633-w

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-020-00633-w

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

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