We present a unified framework for minimizing average completion time for many seemingly disparate online scheduling problems, such as the traveling repairperson problems (TRP), dial-a-ride problems (DARP), and scheduling on unrelated machines. We construct a simple algorithm that handles all these scheduling problems, by computing and later executing auxiliary schedules, each optimizing a certain function on already seen prefix of the input. The optimized function resembles a prize-collecting variant of the original scheduling problem. By a careful analysis of the interplay between these auxiliary schedules, and later employing the resulting inequalities in a factor-revealing linear program, we obtain improved bounds on the competitive ratio for all these scheduling problems. In particular, our techniques yield a $4$-competitive deterministic algorithm for all previously studied variants of online TRP and DARP, and a $3$-competitive one for the scheduling on unrelated machines (also with precedence constraints). This improves over currently best ratios for these problems that are $5.14$ and $4$, respectively. We also show how to use randomization to further reduce the competitive ratios to $1+2/\ln 3 < 2.821$ and $1+1/\ln 2 < 2.443$, respectively. The randomized bounds also substantially improve the current state of the art. Our upper bound for DARP contradicts the lower bound of 3 given by Fink et al. (Inf. Process. Lett. 2009); we pinpoint a flaw in their proof.
翻译:我们提出了一个统一框架,以尽量减少许多看起来截然不同的在线日程安排问题的平均完成时间,例如旅行修理人问题(TRP)、拨车问题(DARP)和不相关机器的时间安排。我们建立了一个简单的算法,处理所有这些日程安排问题,计算和随后执行辅助时间表,每个在已经看到的投入的前缀上优化一定功能。优化功能类似于最初日程安排问题的一个奖赏收集变式。通过仔细分析这些辅助日程安排之间的相互作用,以及随后在元素反射线性程序中使用由此产生的不平等,我们获得了所有这些日程安排问题的竞争性比重的改进。特别是,我们的技术为以前研究过的在线日程安排和DARP的所有变式制作了一个4美元有竞争力的确定性算法,并为不相关机器的日程安排提供了3美元有竞争力的计算法(也存在先例限制)。这比目前这些问题的最佳比率分别是5.14美元和4美元。我们还展示了如何使用随机化来进一步将竞争比率降至1+2/0.00美元 < 2.8美元和1美元以上约束进程。