我需要找到一种合适的方法作为基础，用于开发执行以下操作的优化算法:
假设我们有 N 个任务要做，我们有 M 个房间，每个房间都包含一些特定数量的基础设施/条件。
每项任务都需要使用具有适合任务条件的房间。
例如，为了完成任务 A，我们需要使用水龙头和煤气管道，所以我们只能使用包含这些的房间。
此外，对于每项任务，我们都有一个预定义的截止日期。
我希望我已经解释得足够好。
所以，我需要开发一种算法，可以在适当的调度中为每个房间分配任务，这样我就可以在最短的总时间和不超过截止时间的情况下完成所有任务(如果超过是不可避免的，那么得到最少的最糟糕的答案)。
我可以基于哪些现有方法或算法并从中学习？
我虽然关于“工作坊”，但我想知道是否还有其他合适的算法可以处理这样的问题。
最佳答案
这不是算法，而是混合整数规划模型。我不确定这是否是您要查找的内容。
假设:在一个房间内只能同时执行一项作业。不同房间的作业可以并行执行。此外，为了简单起见，我假设问题是可行的(模型将检测不可行的问题，但如果是这种情况，我们不会返回解决方案)。
所以我们引入了一些决策变量:
assign(i,j) = 1 if task i is assigned to room j
0 otherwise
finish(i) = time job i is done processing
makespan = finishing time of the last job
有了这个，我们可以制定 MIP 模型:
使用以下数据:
Length(i) = processing time of job i
M = a large enough constant (say the planning horizon)
DueDate(i) = time job i must be finished
Allowed(i,j) = Yes if job i can be executed in room j
重要的是，我假设工作是按截止日期排序的。
第一个约束条件是:如果作业 i 在房间 j 中运行，那么它就在该房间中运行的前一个作业之后完成。第二个约束是一个界限:一项工作必须在截止日期之前完成。第三个约束是:每个作业必须准确分配到一个允许执行的房间。最后，makespan 是最后完成时间。
为了测试这一点，我生成了一些随机数据:
---- 37 SET use resource usage
resource1 resource2 resource3 resource4 resource5
task2 YES
task3 YES
task5 YES
task7 YES
task9 YES YES
task11 YES
task12 YES YES
task13 YES
task14 YES
task15 YES
task16 YES YES
task17 YES
task20 YES YES
task21 YES YES
task23 YES
task24 YES
task25 YES YES
task26 YES
task28 YES
---- 37 SET avail resource availability
resource1 resource2 resource3 resource4 resource5
room1 YES YES YES YES
room2 YES YES
room3 YES YES
room4 YES YES YES YES
room5 YES YES YES YES
套装
Allowed计算自 use(i,r)和 avail(j,r)数据:---- 41 SET allowed task is allowed to be executed in room
room1 room2 room3 room4 room5
task1 YES YES YES YES YES
task2 YES YES YES YES
task3 YES YES YES YES
task4 YES YES YES YES YES
task5 YES YES YES YES
task6 YES YES YES YES YES
task7 YES YES
task8 YES YES YES YES YES
task9 YES
task10 YES YES YES YES YES
task11 YES YES YES YES
task12 YES
task13 YES YES
task14 YES YES
task15 YES YES YES YES
task16 YES YES YES
task17 YES YES
task18 YES YES YES YES YES
task19 YES YES YES YES YES
task20 YES
task21 YES
task22 YES YES YES YES YES
task23 YES YES
task24 YES YES YES YES
task25 YES YES
task26 YES YES YES YES
task27 YES YES YES YES YES
task28 YES YES YES YES
task29 YES YES YES YES YES
task30 YES YES YES YES YES
我们还有随机的截止日期和处理时间:
---- 33 PARAMETER length job length
task1 2.335, task2 4.935, task3 4.066, task4 1.440, task5 4.979, task6 3.321, task7 1.666
task8 3.573, task9 2.377, task10 4.649, task11 4.600, task12 1.065, task13 2.475, task14 3.658
task15 3.374, task16 1.138, task17 4.367, task18 4.728, task19 3.032, task20 2.198, task21 2.986
task22 1.180, task23 4.095, task24 3.132, task25 3.987, task26 3.880, task27 3.526, task28 1.460
task29 4.885, task30 3.827
---- 33 PARAMETER due job due dates
task1 5.166, task2 5.333, task3 5.493, task4 5.540, task5 6.226, task6 8.105
task7 8.271, task8 8.556, task9 8.677, task10 8.922, task11 10.184, task12 11.711
task13 11.975, task14 12.814, task15 12.867, task16 14.023, task17 14.200, task18 15.820
task19 15.877, task20 16.156, task21 16.438, task22 16.885, task23 17.033, task24 17.813
task25 21.109, task26 21.713, task27 23.655, task28 23.977, task29 24.014, task30 24.507
当我运行这个模型时，我得到如下结果:
---- 129 PARAMETER results
start length finish duedate
room1.task1 2.335 2.335 5.166
room1.task9 2.335 2.377 4.712 8.677
room1.task11 4.712 4.600 9.312 10.184
room1.task20 9.312 2.198 11.510 16.156
room1.task23 11.510 4.095 15.605 17.033
room1.task30 15.605 3.827 19.432 24.507
room2.task6 3.321 3.321 8.105
room2.task10 3.321 4.649 7.971 8.922
room2.task15 7.971 3.374 11.344 12.867
room2.task24 11.344 3.132 14.476 17.813
room2.task29 14.476 4.885 19.361 24.014
room3.task2 4.935 4.935 5.333
room3.task8 4.935 3.573 8.508 8.556
room3.task18 8.508 4.728 13.237 15.820
room3.task22 13.237 1.180 14.416 16.885
room3.task27 14.416 3.526 17.943 23.655
room3.task28 17.943 1.460 19.403 23.977
room4.task3 4.066 4.066 5.493
room4.task4 4.066 1.440 5.506 5.540
room4.task13 5.506 2.475 7.981 11.975
room4.task17 7.981 4.367 12.348 14.200
room4.task21 12.348 2.986 15.335 16.438
room4.task25 15.335 3.987 19.322 21.109
room5.task5 4.979 4.979 6.226
room5.task7 4.979 1.666 6.645 8.271
room5.task12 6.645 1.065 7.710 11.711
room5.task14 7.710 3.658 11.367 12.814
room5.task16 11.367 1.138 12.506 14.023
room5.task19 12.506 3.032 15.538 15.877
room5.task26 15.538 3.880 19.418 21.713
细节:根据作业，我重新计算了开始和结束时间。只要模型不干扰目标和截止日期，模型就可以在这里和那里允许一些松弛。为了摆脱任何可能的懈怠，我只是尽可能早地执行所有作业。只需使用作业排序在同一房间内背靠背执行作业(请记住，我根据截止日期对作业进行了排序)。
这个有 30 个作业和 10 个房间的模型使用 Cplex 需要 20 秒。古罗比也差不多。
扩充模型以处理不可行的模型并不是很困难。允许工作违反截止日期但要付出代价。需要将惩罚项添加到目标中。截止日期约束在上面的例子中是一个硬约束，使用这种技术，我们把它变成一个软约束。
关于algorithm - 有条件的房间分配和调度任务——优化算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/61656492/