在异构机器上调度异构任务
我们有 n 个工作岗位和 m 台机器。每个作业 i 都有一个发布时间 r[i]。在机器 j 上处理作业 i 需要 p[i][j] 时间。对于一项工作 k，|{p[i][j] |我==k}| <= c，其中 c <<米。我们将作业 i 的延迟定义为 f[i] - r[i]，其中 f[i] 是作业 i 完成的时间。该系统不是抢占式的，即当一项作业在某台机器上启动时，在它完成之前不能被中断。目标是提供一种调度算法，使所有作业的延迟总和最小化。有什么想法吗？
We have n jobs and m machines. Each job i has a release time r[i]. Processing job i on machine j takes p[i][j] time. For one job k, |{p[i][j] | i == k}| <= c, where c << m. We define the delay of job i as f[i] - r[i], where f[i] is the time when job i is finished. The system is not preemptive, i.e., when one job is started on some machine, it cannot be interrupted before it finishes. The goal is to provide a scheduling algorithm that minimizes the delay sum of all jobs. Any idea?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
这是3 分区问题的简化。
令 S = {x1, …, x3m} 为 3 分区的实例，使得对于每个 i，B/4 < xi < B/2，其中 B = Σxi/m 是目标总和。
假设有 m 台相同 的机器。在时间 0，释放 3m 个长度为 x1、...、x3m 的作业。每次 B, B + 1, …, B + 4mB - 1，释放 m 个长度为 1 的作业，总共 4m2B 个作业。
当且仅当初始作业的 makespan 小于或等于 B 时，3 分区实例才有解。如果存在解，则初始作业对目标的贡献最多为 3mB。其他工作的贡献是4m2B。
如果完工时间比 B 长，则一系列 4mB 作业将延迟至少一个单位，从而为目标贡献 4mB。因此，如果 3 分区问题可解，则目标最多为 3mB + 4m2B；如果 3 分区问题不可解，则目标至少为 4mB + 4m2B 。
Here's a reduction from the 3-partition problem.
Let S = {x1, …, x3m} be the instance of 3-partition such that, for every i, B/4 < xi < B/2, where B = ∑xi/m is the target sum.
Let there be m identical machines. At time 0, release 3m jobs of lengths x1, …, x3m. At each time B, B + 1, …, B + 4mB - 1, release m jobs of length 1, for a total of 4m2B jobs.
The instance of 3-partition has a solution if and only if the makespan of the initial jobs is less than or equal to B. If there is a solution, then the contribution of the initial jobs to the objective is at most 3mB. The contribution of the other jobs is 4m2B.
If the makespan is longer than B, then a chain of 4mB jobs is delayed at least one unit, contributing 4mB to the objective. Thus the objective is at most 3mB + 4m2B if the 3-partition problem is solvable and at least 4mB + 4m2B if the 3-partition problem is not solvable.