| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 7543942 | Operations Research Letters | 2018 | 7 Pages |
Abstract
The online machine minimization problem seeks to design a preemptive scheduling algorithm on multiple machines - each job j arrives at its release time rj, has to be processed for pj time units, and must be completed by its deadline dj. The goal is to minimize the number of machines the algorithm uses. We improve the O(logm)-competitive algorithm by Chen, Megow and Schewior (SODA 2016) and provide an O(logmloglogm)-competitive algorithm.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Yossi Azar, Sarel Cohen,