Improved approximation algorithms for non-preemptive multiprocessor scheduling with testing
Improved approximation algorithms for non-preemptive multiprocessor scheduling with testing
复制标题
DOI：
10.1007/s10878-022-00865-y
复制
发表时间：
2022-05
影响因子：
1
通讯作者：
Mingyang Gong;R. Goebel;Guohui Lin;Eiji Miyano
中科院分区：
文献类型：
--
作者：
Mingyang Gong;R. Goebel;Guohui Lin;Eiji Miyano
多处理机调度，又称并行相同机器上最小化最大完工时间的调度，是一个经典的优化问题，目前已得到广泛的研究。带测试的调度是一种在线变体，其中作业的处理时间由额外的测试操作显示，否则作业必须在给定的处理时间上限内执行。Albers和Eckl最近研究了带有测试的多处理器调度；其中，对于非抢占设置，他们提出了一种机器数量趋于无穷大时竞争比接近3.1016的近似算法，以及一种所有测试操作每次占用一个单位时间时竞争比接近3的改进近似算法。首先将作业按上界与测试时间之间最小值的非递增顺序进行排序，然后将作业分成三组，按照排序后的作业顺序进行分组处理。我们表明，我们的算法实现了更好的竞争比，在一般情况下，当机器数量趋于无穷大时，竞争比接近2.9513；当所有的测试操作都需要一个时间单位时，我们的算法实现了更好的竞争比，接近2.8081。
Multiprocessor scheduling, also called scheduling on parallel identical machines to minimize the makespan, is a classic optimization problem which has been extensively studied. Scheduling with testing is an online variant, where the processing time of a job is revealed by an extra test operation, otherwise the job has to be executed for a given upper bound on the processing time. Albers and Eckl recently studied the multiprocessor scheduling with testing; among others, for the non-preemptive setting they presented an approximation algorithm with competitive ratio approaching 3.1016 when the number of machines tends to infinity and an improved approximation algorithm with competitive ratio approaching 3 when all test operations take one unit of time each. We propose to first sort the jobs into non-increasing order of the minimum value between the upper bound and the testing time, then partition the jobs into three groups and process them group by group according to the sorted job order. We show that our algorithm achieves better competitive ratios, which approach 2.9513 when the number of machines tends to infinity in the general case; when all test operations each takes one time unit, our algorithm achieves even better competitive ratios approaching 2.8081.