We study the scheduling problem of makespan minimization while taking machine conflicts into account. Machine conflicts arise in various settings, e.g., shared resources for pre- and post-processing of tasks or spatial restrictions. In this context, each job has a blocking time before and after its processing time, i.e., three parameters. We seek for conflict-free schedules in which the blocking times of no two jobs intersect on conflicting machines. Given a set of jobs, a set of machines, and a graph representing machine conflicts, the problem SchedulingWithMachineConflicts (SMC), asks for a conflict-free schedule of minimum makespan. We show that, unless $\textrm{P}=\textrm{NP}$, SMC on $m$ machines does not allow for a $\mathcal{O}(m^{1-\varepsilon})$-approximation algorithm for any $\varepsilon>0$, even in the case of identical jobs and every choice of fixed positive parameters, including the unit case. Complementary, we provide approximation algorithms when a suitable collection of independent sets is given. Finally, we present polynomial time algorithms to solve the problem for the case of unit jobs on special graph classes. Most prominently, we solve it for bipartite graphs by using structural insights for conflict graphs of star forests.


翻译:在考虑机器冲突的同时,我们研究最小化的排程问题。 机器冲突出现在各种环境中, 例如, 任务处理前和后或空间限制的共享资源。 在这方面, 每份工作在处理时间前后都有一个阻塞时间, 即三个参数。 我们寻求在冲突机器上不出现两个工作的阻塞时间相交的无冲突时间表。 在一系列工作、 一组机器和代表机器冲突的图表中, 与机器冲突( SMC ) 的问题, 要求设定一个最少的无冲突时间表 。 我们显示, 除非$\ textrm{ P{ textrm{NP} $, 否则, 以 $mmm 机器为单位的SMC 不允许使用$mathcal{O} (m ⁇ 1-\ varepslon}) $Approximation 算法, 任何 $\\ varepslon>0, 即使是相同的工作, 以及每个选择的固定肯定参数, 包括单位案例。 我们提供精确的算法, 当一个合适的独立结构图解算法 时, 我们用正平面的图表解的图表 的图表解解的图表, 最后我们给出的图表解式的图表解式的图表解算。

0
下载
关闭预览

相关内容

【UBC】高级机器学习课程,Advanced Machine Learning
专知会员服务
24+阅读 · 2021年1月26日
专知会员服务
159+阅读 · 2020年1月16日
【课程】纽约大学 DS-GA 1003 Machine Learning
专知会员服务
45+阅读 · 2019年10月29日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
动物脑的好奇心和强化学习的好奇心
CreateAMind
10+阅读 · 2019年1月26日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
CCF B类期刊IPM专刊截稿信息1条
Call4Papers
3+阅读 · 2018年10月11日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【推荐】手把手深度学习模型部署指南
机器学习研究会
5+阅读 · 2018年1月23日
【推荐】自然语言处理(NLP)指南
机器学习研究会
35+阅读 · 2017年11月17日
【推荐】决策树/随机森林深入解析
机器学习研究会
5+阅读 · 2017年9月21日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
0+阅读 · 2022年1月14日
Arxiv
0+阅读 · 2022年1月13日
Arxiv
7+阅读 · 2021年10月19日
Inductive Relation Prediction by Subgraph Reasoning
Arxiv
11+阅读 · 2020年2月12日
Knowledge Based Machine Reading Comprehension
Arxiv
4+阅读 · 2018年9月12日
VIP会员
相关资讯
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
动物脑的好奇心和强化学习的好奇心
CreateAMind
10+阅读 · 2019年1月26日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
CCF B类期刊IPM专刊截稿信息1条
Call4Papers
3+阅读 · 2018年10月11日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【推荐】手把手深度学习模型部署指南
机器学习研究会
5+阅读 · 2018年1月23日
【推荐】自然语言处理(NLP)指南
机器学习研究会
35+阅读 · 2017年11月17日
【推荐】决策树/随机森林深入解析
机器学习研究会
5+阅读 · 2017年9月21日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员