基于条件优化算法的任务分配与调度
我需要找到一个合适的方法来开发一个优化算法，它做以下工作：
假设我们有N个任务要做，我们有M个房间，每个房间都包含一些特定数量的基础设施/条件。每项任务都要求使用条件适合任务的房间。
例如，为了完成任务，我们需要使用水龙头和煤气管道，所以我们只能使用包含这些管道的房间。
此外，对于每项任务，我们都有一个预定义的截止日期。
我希望我已经解释得够清楚了。
所以，我需要开发一种算法，可以在适当的时间安排中为每个房间分配任务，这样我就可以在最小的总时间内完成所有任务，而不会超过截止时间（如果超过是不可避免的，那么得到最差的答案）。
我可以基于哪些现有方法或算法并从中学习？我对“Job Shop”很感兴趣，但我想知道是否还有其他合适的算法可以处理这样的问题。
共有3个答案
在CPLEX中，您可以依赖MIP，但也可以使用CPOptimizer调度。
在OPL中，你的模型看起来像
using CP;
int N = 30; // nbTasks
int M = 10; // rooms
range Tasks = 1..N;
range Rooms = 1..M;
int taskDuration[i in Tasks]=rand(20);
int dueDate[i in Tasks]=20+rand(20);
int possible[j in Tasks][m in Rooms] = (rand(10)>=8);
dvar interval itvs[j in Tasks][o in Rooms] optional in 0..100 size taskDuration[j] ;
dvar interval itvs_task[Tasks];
dvar sequence rooms[m in Rooms] in all(j in Tasks) itvs[j][m];
execute {
cp.param.FailLimit = 10000;
}
minimize max(j in Tasks) endOf(itvs_task[j]);
subject to {
// alternative
forall(t in Tasks) alternative(itvs_task[t],all(m in Rooms)itvs[t][m]);
// one room is for one task at most at the same time
forall (m in Rooms)
noOverlap(rooms[m]);
// due dates
forall(j in Tasks) endOf(itvs_task[j]) <=dueDate[j];
}
并给予
我在数据上使用了亚历克斯的OPL CP优化模型的一个小变体，它在几秒钟内找到了最佳解决方案（makespan=19.432），并在我的笔记本电脑上用了大约5秒的时间证明了最优性。我认为CP优化模型的一个很大的优势是，它可以扩展到更大的实例，并且很容易产生高质量的解决方案，即使对于大实例来说，证明最优性可能是一项挑战。
以下是我的CP优化器模型版本：
using CP;
int N = 30; // Number of tasks
int M = 5; // Number of rooms
int Length [1..N] = ...; // Task length
int DueDate[1..N] = ...; // Task due date
{int} Rooms[1..N] = ...; // Possible rooms for task
tuple Alloc { int job; int room; }
{Alloc} Allocs = {<i,r> | i in 1..N, r in Rooms[i]};
dvar interval task[i in 1..N] in 0..DueDate[i] size Length[i];
dvar interval alloc[a in Allocs] optional;
minimize max(i in 1..N) endOf(task[i]);
subject to {
forall(i in 1..N) { alternative(task[i], all(r in Rooms[i]) alloc[<i,r>]); }
forall(r in 1..M) { noOverlap(all(a in Allocs: a.room==r) alloc[a]); }
}
还要注意的是，MIP模型利用了一个特定于问题的支配规则，即分配给特定房间的任务可以通过增加截止日期来排序。虽然对于这个问题的简单版本来说这是完全正确的，但在存在其他约束（例如任务的最小开始时间）的情况下，这种假设可能不再成立。CP优化器公式不作此假设。
这不是一个算法，而是一个混合整数编程模型，我不确定这是不是你要找的。
假设：一个房间内只能同时执行一个作业。不同房间中的作业可以并行执行。此外，为了简单起见，我假设问题是可行的（模型将检测不可行的问题，但如果是这种情况，我们不会返回解决方案）。
因此，我们引入了一些决策变量：
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
设置允许的根据使用（i，r）和可用（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秒。古罗比也差不多。
扩充模型以处理不可行的模型并不十分困难。允许作业违反到期日，但要付出代价。需要在目标中添加惩罚条款。在上面的示例中，到期日约束是一个硬约束，通过这种技术，我们将其设置为软约束。
-
但是由于网络和其他一些技术问题，我在python脚本中的excel文件将无法在计划时间内更新，因此我需要手动运行python脚本，让我知道一旦文件更新，任何选项都是avl来运行任务调度程序。 例如：我运行python脚本的计划时间是每天上午9点，但我同意如果excel文件未在上午9点在python上更新，任务调度器需要在9点30分运行 提前谢谢。
-
我有一些与jdbc相关的通用代码，我想单独打包到一个可运行的jar中，其中已经包含了所需的jdbc库，因此每个数据库类型都有一个单独的可运行jar。源代码将保持不变，但打包的jdbc jar将不同。 例如jdbc app postgres。jar将只包含postgres jdbc jar，而jdbc应用程序mysql。jar将包含mysql jdbc jar。 是否可以使用gradle对任务或任何
-
本文向大家介绍Spring基于@Conditional条件化装配bean，包括了Spring基于@Conditional条件化装配bean的使用技巧和注意事项，需要的朋友参考一下 一 前言 理解spring的如何根据条件装配bean有助于我们更好使用springboot进行开发，和源码理解； 二 @Conditional 装配bean 思路如下 Spring中提供了@Conditional注解实现
-
尾部调用优化 (TCO) 正如我们早前简单提到的，ES6包含了一个冒险进入性能世界的具体需求。它是关于在函数调用时可能会发生的一种具体的优化形式：尾部调用优化（TCO）。 简单地说，一个“尾部调用”是一个出现在另一个函数“尾部”的函数调用，于是在这个调用完成后，就没有其他的事情要做了（除了也许要返回结果值）。 例如，这是一个带有尾部调用的非递归形式： function foo(x) { r
-
前言 上文讲到 HTTPS 对用户访问速度的影响。 本文就为大家介绍 HTTPS 在访问速度，计算性能，安全等方面基于协议和配置的优化。 HTTPS 访问速度优化 Tcp fast open HTTPS 和 HTTP 使用 TCP 协议进行传输，也就意味着必须通过三次握手建立 TCP 连接，但一个 RTT 的时间内只传输一个 syn 包是不是太浪费？能不能在 syn 包发出的同时捎上应用层的数据？
-
我有一些任务的持续时间是已知的整数长度。任务之间也有依赖关系。我也有任意数量的员工可以安排这些任务。 我想为他们找到一个最佳的时间表，首先我要最小化所有任务执行的总长度，其次我想在一个之前运行过大多数依赖项的工作人员身上安排任务，第三我想最小化所需的工作人员数量。 因此，如果任务具有依赖项A、B和C，并且worker1运行A和B，worker2运行C，那么我更希望将新任务添加到worker1。 我