Online scheduling with migration on two hierarchical machines

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

Journal of Combinatorial Optimization, 2022, vol. 44, issue 5, No 17, 3535-3548

Abstract: Abstract We consider online scheduling with migration on two hierarchical machines, with the goal of minimizing the makespan. In this model, one of the machines can run any job, while the other machine can only receive jobs from a subset of the input jobs. In addition, in this problem, there is a constant parameter $$M \ge 0$$ M ≥ 0 , called the migration factor. Jobs are presented one by one, and every arrival of a new job of size x does not only require the algorithm to assign the job to one of the machines, but it also allows the algorithm to reassign any subset of previously presented jobs, whose total size is at most $$M \cdot x$$ M · x . We show that no algorithm with a finite migration factor has a competitive ratio below $$\frac{3}{2}$$ 3 2 , and design an algorithm with this competitive ratio and migration factor 1. We prove that this is the best possible result, in the sense that no algorithm with a smaller migration factor can have a competitive ratio of $$\frac{3}{2}$$ 3 2 . This provides tight bounds on the competitive ratio for all values $$M\ge 1$$ M ≥ 1 . We also find tight bounds on the competitive ratio for many other values of M.

Keywords: Hierarchical machines; Competitive ratio; Migration factor. (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-022-00906-6 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:44:y:2022:i:5:d:10.1007_s10878-022-00906-6

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

DOI: 10.1007/s10878-022-00906-6

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