.png){kind=icon}
.png){kind=icon}
Return
Online speed-robust scheduling
.png){kind=icon}
PRE
AI
DOI：10.1016/j.disopt.2026.100954.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We consider online speed-robust scheduling on a multiprocessor consisting of m uniformly related machines. Jobs of arbitrary sizes arriving one by one are to be assigned to a fixed number of M = m bags immediately and without any information on machine speeds. When the sequence of jobs is completed, the list of speeds is provided to the algorithm, and it assigns its entire collection of bags to the machines. For each bag, all jobs assigned to this bag are assigned to the same machine. In the offline variant of the problem, the sequence of jobs is given as a set, but the speeds are also revealed only after the bags are created. The quality of algorithms is measured similarly to approximation algorithms and online algorithms, and we study two objectives which are makespan minimization and maximization of the minimum load. Even though we allow jobs to arrive one by one, we match the best known result for offline speed-robust makespan minimization. For most cases that we study, we prove results that are significantly better than those known for the corresponding standard online problems, where each new job is assigned to a machine irrevocably. However, we show that not all cases allow such an improved result. Some of our results are extended to the situation where one can use M> m bags. Finally, we consider the offline problem on two machines and three classes of jobs that were studied in previous work. We show that arbitrary job sizes differ from unit job sizes for two machines and two bags, even though the known result for unit job sizes is the same as that of infinitesimal jobs. Moreover, we show that the best possible results for the three job classes are all different for three bags. This is the first variant for which there is evidence that the case of jobs of arbitrary sizes is harder than that of unit sizes.
Keywords:
Uniformly related machines
Speed-robust
Makespan minimization