具有作业排除和优先约束的多处理器调度
Multiprocessor scheduling with job exclusions and precedence constraints
我正在尝试 find/develop 一种算法，该算法可以最大限度地减少为机器安排作业（运行ning 次）的总时间。即标准多处理器调度算法。
但是我有两个额外的限制：一些工作必须在其他工作之前完成（优先级）。 只有某些机器可以运行某些工作（工作排除）。不过，作业并不是处理器独有的。
例如，我可能有 4 份工作 -
(cost): j1 (4) , j2 (2) , j3 (10), j4 (12)
3 machines: m1, m2, m3
Such that:
m1 can run j1, j2, j3
m2 can run j1, j2 and
m3 can run j3, j4
j1 must be run before j2 and j4
我的目标是为每台机器找到最佳调度，以最大限度地减少总时间。
我研究过对不相关的机器使用多处理器调度算法（将排除的任务设置为无限成本）但这并不理想，因为成本实际上不是可变的（无限或正常成本）。
使用 DAG 应该适用于优先约束，但我不知道如何包含排除项。
目前我正在使用一种贪婪算法，该算法可以最大化所有其他处理器中释放（不再受约束）作业的成本。但是我不知道这是否是最佳的，甚至是好的。
我相当确定这是 NP-hard，所以我不假设存在最佳算法。使用多处理器调度可能是这里的问题，因为使用背包或最小路径算法可能更好。
最好能帮助解决这两个限制，但关于处理被排除的工作的文献很少（根据一些谷歌搜索），所以关于处理这个问题的建议将是有益的。
I aim to find the optimal schedule for each machine in order to minimise total time.
不要。
假设的教科书场景之外；调度程序通常不知道何时会启动更多作业，任何作业可能需要多长时间，任何计算机（或 CPU）何时会改变速度，when/if 会有硬件故障，if/when 作业将被取消（或崩溃），...
唯一的 sane/practical 方法是忘记 "optimal in theory for a fictional scenario" 并动态适应不断变化的/"unknowable in advance" 条件，同时做出 "good enough" 的决定，因为你不能可以浪费 CPU 时间来寻找 "perfect for a fraction of a millisecond maybe but now it's too late to matter because it took too long to decide" 解决方案。
大多数情况下，"events" 会影响调度（作业开始、停止、等待 IO、由于 IO 发生而继续、电源管理更改等）；并且调度程序必须在这些事件发生时以 fast/efficient 方式对其做出反应。
如果某些作业必须先于其他作业完成，那么这不是调度程序的问题 - 这是为这些任务编写代码的人必须处理的问题（在适当的地方添加 "wait for the other job to complete before I continue" - 例如也许一个 waitpid()).
如果只有某些机器可以 运行 某些工作，那么这应该是微不足道的（您只需要某种 "affinity mask" 来控制工作能够 运行 的地方）。
一种处理方法如下。
引入一个二进制变量assign(j,m)来指示我们是否将作业j分配给机器m。然后只需修复所有不允许的组合的所有变量 assign(j,m)=0。一个好的 MIP 求解器会在预求解阶段从模型中移除相应的变量。
当我这样做并完成 MIP 公式并求解时，我看到：
---- 63 --------------- data ---
---- 63 SET ok allowed job/machine combinations
machine1 machine2 machine3
job1 YES YES
job2 YES YES
job3 YES YES
job4 YES
---- 63 PARAMETER proctime processing time
job1 4.000, job2 2.000, job3 10.000, job4 12.000
---- 63 SET prec precedence
job2 job4
job1 YES YES
---- 63 --------------- solution -----
---- 63 VARIABLE assign.L assign job to machine
machine1 machine2 machine3
job1 1.000
job2 1.000
job3 1.000
job4 1.000
---- 63 VARIABLE start.L job start time
job2 4.000, job4 4.000
---- 63 VARIABLE finish.L job finish time
job1 4.000, job2 6.000, job3 10.000, job4 16.000
---- 63 VARIABLE makespan.L = 16.000 time last job is finished
（注意没有打印零的开始时间）
完整模型为here。
您可以使用 OR-Tools CP-SAT 求解器。
见
https://developers.google.com/optimization/scheduling/job_shop
如果每个任务只能在一台机器上执行，或者
https://github.com/google/or-tools/blob/master/examples/python/flexible_job_shop_sat.py
如果每个任务都可以有替代机器，那么必须选择一个。
我正在尝试 find/develop 一种算法，该算法可以最大限度地减少为机器安排作业（运行ning 次）的总时间。即标准多处理器调度算法。
但是我有两个额外的限制：一些工作必须在其他工作之前完成（优先级）。 只有某些机器可以运行某些工作（工作排除）。不过，作业并不是处理器独有的。
例如，我可能有 4 份工作 -
(cost): j1 (4) , j2 (2) , j3 (10), j4 (12)
3 machines: m1, m2, m3
Such that:
m1 can run j1, j2, j3
m2 can run j1, j2 and
m3 can run j3, j4
j1 must be run before j2 and j4
我的目标是为每台机器找到最佳调度，以最大限度地减少总时间。
我研究过对不相关的机器使用多处理器调度算法（将排除的任务设置为无限成本）但这并不理想，因为成本实际上不是可变的（无限或正常成本）。
使用 DAG 应该适用于优先约束，但我不知道如何包含排除项。
目前我正在使用一种贪婪算法，该算法可以最大化所有其他处理器中释放（不再受约束）作业的成本。但是我不知道这是否是最佳的，甚至是好的。
我相当确定这是 NP-hard，所以我不假设存在最佳算法。使用多处理器调度可能是这里的问题，因为使用背包或最小路径算法可能更好。
最好能帮助解决这两个限制，但关于处理被排除的工作的文献很少（根据一些谷歌搜索），所以关于处理这个问题的建议将是有益的。
I aim to find the optimal schedule for each machine in order to minimise total time.
不要。
假设的教科书场景之外；调度程序通常不知道何时会启动更多作业，任何作业可能需要多长时间，任何计算机（或 CPU）何时会改变速度，when/if 会有硬件故障，if/when 作业将被取消（或崩溃），...
唯一的 sane/practical 方法是忘记 "optimal in theory for a fictional scenario" 并动态适应不断变化的/"unknowable in advance" 条件，同时做出 "good enough" 的决定，因为你不能可以浪费 CPU 时间来寻找 "perfect for a fraction of a millisecond maybe but now it's too late to matter because it took too long to decide" 解决方案。
大多数情况下，"events" 会影响调度（作业开始、停止、等待 IO、由于 IO 发生而继续、电源管理更改等）；并且调度程序必须在这些事件发生时以 fast/efficient 方式对其做出反应。
如果某些作业必须先于其他作业完成，那么这不是调度程序的问题 - 这是为这些任务编写代码的人必须处理的问题（在适当的地方添加 "wait for the other job to complete before I continue" - 例如也许一个 waitpid()).
如果只有某些机器可以 运行 某些工作，那么这应该是微不足道的（您只需要某种 "affinity mask" 来控制工作能够 运行 的地方）。
一种处理方法如下。
引入一个二进制变量assign(j,m)来指示我们是否将作业j分配给机器m。然后只需修复所有不允许的组合的所有变量 assign(j,m)=0。一个好的 MIP 求解器会在预求解阶段从模型中移除相应的变量。
当我这样做并完成 MIP 公式并求解时，我看到：
---- 63 --------------- data ---
---- 63 SET ok allowed job/machine combinations
machine1 machine2 machine3
job1 YES YES
job2 YES YES
job3 YES YES
job4 YES
---- 63 PARAMETER proctime processing time
job1 4.000, job2 2.000, job3 10.000, job4 12.000
---- 63 SET prec precedence
job2 job4
job1 YES YES
---- 63 --------------- solution -----
---- 63 VARIABLE assign.L assign job to machine
machine1 machine2 machine3
job1 1.000
job2 1.000
job3 1.000
job4 1.000
---- 63 VARIABLE start.L job start time
job2 4.000, job4 4.000
---- 63 VARIABLE finish.L job finish time
job1 4.000, job2 6.000, job3 10.000, job4 16.000
---- 63 VARIABLE makespan.L = 16.000 time last job is finished
（注意没有打印零的开始时间）
完整模型为here。
您可以使用 OR-Tools CP-SAT 求解器。
见
https://developers.google.com/optimization/scheduling/job_shop
如果每个任务只能在一台机器上执行，或者
https://github.com/google/or-tools/blob/master/examples/python/flexible_job_shop_sat.py
如果每个任务都可以有替代机器，那么必须选择一个。