调度优化以最小化时隙数量（有约束）

Question

我正在研究调度优化问题，其中我们有一组需要在特定时间范围内完成的任务。

每个任务都有一个时间表，指定可以执行该任务的时间段列表。每个任务的时间表可能会因工作日而异。

这是小样本（减少任务和时间段的数量）：

task_availability_map = {
    "T1" : [0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    "T2" : [0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    "T3" : [0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    "T4" : [0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    "T5" : [0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    "T6" : [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0],
    "T7" : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0],
    "T8" : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0],
    "T9" : [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
    "T10": [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]
}

限制是同一时间段内最多只能并行执行 N 个任务（如果它们重叠）。无论完成 1 个还是 N 个任务，这组并行任务总是花费相同的时间。

目标是尽量减少时隙数量。

我尝试过一种强力方法来生成所有时隙索引排列。对于给定排列中的每个索引，获取所有可以调度的任务并将它们添加到要在下一次迭代中排除的任务列表中。完成给定排列的所有迭代后，将时隙数量和索引组合添加到列表中。

def get_tasks_by_timeslot(timeslot, tasks_to_exclude):
    for task in task_availability_map.keys():
        if task in tasks_to_exclude:
            continue
        if task_availability_map[task][timeslot] == 1:
            yield task

total_timeslot_count = len(task_availability_map.values()[0]) # 17
timeslot_indices = range(total_timeslot_count)

timeslot_index_permutations = list(itertools.permutations(timeslot_indices))

possible_schedules = []

for timeslot_variation in timeslot_index_permutations:
    tasks_already_scheduled = []
    current_schedule = []
    for t in timeslot_variation:
        tasks = list(get_tasks_by_timeslot(t, tasks_already_scheduled))
        if len(tasks) == 0:
            continue
        elif len(tasks) > MAX_PARALLEL_TASKS:
            break
        tasks_already_scheduled += tasks
        current_schedule.append(tasks)

    time_slot_count = np.sum([len(t) for t in current_schedule])
    possible_schedules.append([time_slot_count, timeslot_variation])

...

按照时段数对可能的日程进行排序，这就是解决方案。然而，该算法的复杂性随着时隙的数量呈指数增长。鉴于有数百个任务和数百个时间段，我需要一种不同的方法。

有人建议使用 LP MIP（例如 Google OR Tools），但我对它不是很熟悉，并且很难在代码中制定约束。非常感谢任何有关 LP 或其他解决方案的帮助，可以帮助我朝着正确的方向开始（不一定是 Python，甚至可以是 Excel）。

Answer 1

我对 MIP 模型的建议：

引入二元变量：

x(i,t) = 1 if task i is assigned to slot t
         0 otherwise

y(t) = 1 if slot t has at least one task assigned to it
       0 otherwise

进一步让：

N = max number of tasks per slot
ok(i,t) = 1 if we are allowed to assign task i to slot t
          0 otherwise

那么模型可以是这样的：

minimize sum(t,y(t))                    (minimize used slots)    
sum(t, ok(i,t)*x(i,t)) = 1   for all i  (each task is assigned to exactly one slot)      
sum(i, ok(i,t)*x(i,t)) <= N  for all t  (capacity constraint for each slot)
y(t) >= x(i,t)  for all (i,t) such that ok(i,t)=1
x(i,t),y(t) in {0,1}                    (binary variables)

使用

N=3

，我得到如下解决方案：

----     45 VARIABLE x.L  assignment

                s5          s6          s7         s13

task1                    1.000
task2                                1.000
task3                    1.000
task4                    1.000
task5        1.000
task6                                            1.000
task7                                            1.000
task8                                            1.000
task9                                1.000
task10                               1.000

该模型相当简单，使用您最喜欢的 MIP 求解器进行编码和求解应该不会很困难。您要确保的一件事是，当

x(i,t)

时，仅存在变量

ok(i,t)=1

。换句话说，确保当

ok(i,t)=0

时变量不会出现在模型中。它可以帮助将分配约束解释为：

sum(t | ok(i,t)=1, x(i,t)) = 1   for all i  (each task is assigned to exactly one slot)      
sum(i | ok(i,t)=1, x(i,t)) <= N  for all t  (capacity constraint for each slot)

哪里 |意思是“这样”或“哪里”。如果你做得正确，你的模型应该有 50 个变量

x(i,t)

，而不是 10 x 17 = 170。此外，我们可以放松

y(t)

使其在 0 和 1 之间连续。它将自动为 0 或 1。取决于可能影响性能的求解器。

我没有理由相信这更容易建模为约束规划模型，或者更容易以这种方式解决。我的经验法则是，如果很容易将 MIP 建模为 MIP，那就坚持 MIP。如果我们需要经过大量的努力才能使其成为合适的 MIP，并且 CP 配方使事情变得更轻松，那么就使用 CP。在许多情况下，这个简单的规则非常有效。