使用可变资源映射对作业调度问题建模

Question

我是 google or-tools 的新手，我正在尝试解决以下问题：

一些具有优先约束的任务
N个资源池
资源按名称分组（a：[0, 1]，b：[2, 3, 4]，...）
每个作业都可以直接（作业 j 需要资源 13 和 14）或间接（作业 j 需要 a 组的 1 个资源和 b 组的 2 个资源）获取资源
如果优先级和资源限制允许，作业可以运行并行，机器数量不受限制
假定所有作业具有相同的执行时间

我想找到一个最小的完工时间并且我想知道：

哪个工作应该运行在任何时间 t
在时间 t 哪个作业使用了哪个资源

我通过以下方式实现了优先约束：

from ortools.sat.python import cp_model

njobs = 5
precedence_constraints = [
    (0, 3),
    (0, 2),
    (1, 2),
    (2, 3),
    (2, 4)
]

model = cp_model.CpModel()

job_time = [ model.NewIntVar(0, njobs-1, 'j{}'.format(i)) for i in range(njobs) ]

for p, n in precedence_constraints:
    model.Add(job_time[p] < job_time[n])

model.Minimize(sum(job_time))

solver = cp_model.CpSolver()
status = solver.Solve(model)

for i in range(0, njobs):
    print('j{} = {}'.format(i, solver.Value(job_time[i])))

我不明白如何实现资源映射。

Answer 1

您可以尝试将其建模为近乎经典的灵活作业车间：

https://github.com/google/or-tools/blob/stable/examples/python/flexible_job_shop_sat.py

此外，您还添加了一个累积资源来帮助传播（请参阅 or-tools 邮件列表上正在进行的讨论：https://groups.google.com/forum/?hl=kn#!topic/or-tools-discuss/0syUImixcFI），并且活动副本的总和可能会更大比 1.

这不是最有效的方法，但以这种方式开始更容易。如果所有持续时间不相等，它会更健壮。

使用可变资源映射对作业调度问题建模

Modeling a job-scheduling problem with variable resource mapping

job-scheduling

or-tools