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

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，这组并行任务总是花费相同的时间。

objective是为了尽量减少时隙数

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

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 工具），但我对它不是很熟悉并且很难在代码中制定约束条件。非常感谢任何有关 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 求解器进行编码和求解应该不是很困难。您要确保的一件事是 ok(i,t)=1 时仅存在变量 x(i,t)。换句话说，确保变量在 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)

在哪里 |表示 'such that' 或 'where'。如果你这样做正确，你的模型应该有 50 个变量 x(i,t) 而不是 10 x 17 = 170。此外，我们可以放宽 y(t) 以在 0 和 1 之间连续。它将自动为 0 或 1 .取决于可能影响性能的求解器。

我没有理由相信这更容易建模为约束规划模型，或者更容易解决这种方式。我的经验法则是，如果很容易建模为 MIP，那么就坚持使用 MIP。如果我们需要经过很多步骤才能使其成为合适的 MIP，而 CP 公式让生活更轻松，那么请使用 CP。在许多情况下，这个简单的规则非常有效。

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

Scheduling optimization to minimize the number of timeslots (with constraints)

python

algorithm

linear-programming

job-scheduling

minimization