On the optimality of the TLS algorithm for solving the online-list scheduling problem with two job types on a set of multipurpose machines
On the optimality of the TLS algorithm for solving the online-list scheduling problem with two job types on a set of multipurpose machines
复制标题
DOI：
10.1007/s10878-012-9460-4
复制
发表时间：
2013-07
影响因子：
1
通讯作者：
Shlomo Karhi;D. Shabtay
中科院分区：
文献类型：
--
作者：
Shlomo Karhi;D. Shabtay
本文研究了TLS算法在一组多用途机器上最小化完工时间的在线调度问题的最优性，其中有两种不同的作业类型，并且每种作业类型只能在唯一的机器子集上加工。文献表明，对于m=2或所有处理时间限制为1的特殊情况，TLS算法是最优的。我们证明了TLS算法对于作业处理时间依赖于作业类型或机器集的特殊情况也是最优的。对于这两种情况，证明了TLS算法的最优性，证明了它的竞争比与任何处理集和处理时间参数的下界相匹配。
In this paper we study the optimality of theTLSalgorithm for solving the online scheduling problem of minimizing the makespan on a set ofmmultipurpose machines, where there are two different job types and each job type can only be processed on a unique subset of machines. The literature shows that theTLSalgorithm is optimal for the special cases where eitherm=2 or where all processing times are restricted to unity. We show that theTLSalgorithm is optimal also for the special cases where the job processing times are either job type or machine set dependent. For both cases, the optimality of theTLSalgorithm is proven by showing that its competitive ratio matches the lower bound foranyprocessing set and processing time parameters.