Scheduling When You Don't Know the Number of Machines
Scheduling When You Don't Know the Number of Machines
复制标题
当您不知道机器数量时进行调度
DOI：
10.1137/1.9781611975031.82
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Zhong, Mingxian
中科院分区：
文献类型：
--
作者：
Stein, Clifford;Zhong, Mingxian
Often in a scheduling problem, there is uncertainty about the jobs to be processed. The issue of uncertainty regarding the machines has been much less studied. In this article, we study a scheduling environment in which jobs first need to be grouped into some sets before the number of machines is known, and then the sets need to be scheduled on machines without being separated. To evaluate algorithms in such an environment, we introduce the idea of an α-robust algorithm, one that is guaranteed to return a schedule on any numbermof machines that is within an α factor of the optimal schedule onmmachine, where the optimum is not subject to the restriction that the sets cannot be separated. Under such environment, we give a (5\3+ε)-robust algorithm for scheduling on parallel machines to minimize makespan and show a lower bound 4\3. For the special case when the jobs are infinitesimal, we give a 1.233-robust algorithm with an asymptotic lower bound of 1.207. We also study a case of fair allocation, where the objective is to minimize the difference between the maximum and minimum machine load.
