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美元以上约束进程。

0
下载
关闭预览

相关内容

迁移学习简明教程,11页ppt
专知会员服务
107+阅读 · 2020年8月4日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
【Google】无监督机器翻译,Unsupervised Machine Translation
专知会员服务
35+阅读 · 2020年3月3日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
动物脑的好奇心和强化学习的好奇心
CreateAMind
10+阅读 · 2019年1月26日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
已删除
将门创投
6+阅读 · 2019年1月11日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
条件GAN重大改进!cGANs with Projection Discriminator
CreateAMind
8+阅读 · 2018年2月7日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
0+阅读 · 2021年7月2日
Arxiv
0+阅读 · 2021年7月1日
Arxiv
6+阅读 · 2018年2月28日
VIP会员
相关VIP内容
迁移学习简明教程,11页ppt
专知会员服务
107+阅读 · 2020年8月4日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
【Google】无监督机器翻译,Unsupervised Machine Translation
专知会员服务
35+阅读 · 2020年3月3日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
相关资讯
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
动物脑的好奇心和强化学习的好奇心
CreateAMind
10+阅读 · 2019年1月26日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
已删除
将门创投
6+阅读 · 2019年1月11日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
条件GAN重大改进!cGANs with Projection Discriminator
CreateAMind
8+阅读 · 2018年2月7日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员