algorithm - 有条件的房间分配和调度任务—

algorithm - 有条件的房间分配和调度任务——优化算法

转载作者：行者123 更新时间：2023-12-03 23:11:49

我需要找到一种合适的方法作为基础，用于开发执行以下操作的优化算法:

假设我们有 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/

文章推荐：没有服务器的 Blazor(非无服务器)

文章推荐： angular - 异步管道向子组件发送 'null' 值

文章推荐： azure-ad-b2c - B2C 是否支持 PKCE 的授予流程？

算法~利用zset实现滑动窗口限流
滑动窗口限流滑动窗口限流是一种常用的限流算法，通过维护一个固定大小的窗口，在单位时间内允许通过的请求次数不超过设定的阈值。具体来说，滑动窗口限流算法通常包括以下几个步骤：初始化：设置窗口
【算法】表达式求值
表达式求值：一个只有+,-,*,/的表达式，没有括号一种神奇的做法：使用数组存储数字和运算符，先把优先级别高的乘法和除法计算出来，再计算加法和减法 int GetVal(string s){
【算法】前缀和
【算法】前缀和题目先来看一道题目：（前缀和模板题）已知一个数组A[]，现在想要求出其中一些数字的和。输入格式：先是整数N,M，表示一共有N个数字，有M组询问接下来有N个数，表示A[1]..
【算法】二叉树的各种遍历方式
1.前序遍历根-左-右的顺序遍历，可以使用递归 void preOrder(Node *u){ if(u==NULL)return; printf("%d ",u->val);
【算法】01背包
先看题目物品不能分隔，必须全部取走或者留下，因此称为01背包（只有不取和取两种状态）看第一个样例我们需要把4个物品装入一个容量为10的背包我们可以简化问题，从小到大入手分析 weightva
算法 - 矩阵中被另一种颜色包围的颜色
我最近在一次采访中遇到了这个问题: 给出以下矩阵: [[ R R R R R R], [ R B B B R R], [ B R R R B B], [ R B R R R R]] 找出是否有任
使用Outlook发送电子邮件的C++算法
我正在尝试通过 C++ 算法从我的 outlook 帐户发送一封电子邮件，该帐户已经打开并记录，但真的不知道从哪里开始(对于 outlook-c++ 集成)，谷歌也没有帮我这么多。任何提示将不胜感激。
容器上滑动窗口的C++算法
我发现自己像这样编写了一个手工制作的 while 循环: std::list foo; // In my case, map, but list is simpler auto currentPoin
检测正方形后运行命令的c++算法
我有用于检测正方形的 opencv 代码。现在我想在检测正方形后，代码运行另一个命令。代码如下: #include "cv.h" #include "cxcore.h" #include "high
二值图像的泛洪填充C++算法
我正在尝试模拟一个 matlab 函数“imfill”来填充二进制图像(1 和 0 的二维矩阵)。我想在矩阵中指定一个起点，并像 imfill 的 4 连接版本那样进行洪水填充。这是否已经存在于
算法递归公式
我正在阅读 Robert Sedgewick 的《C++ 算法》。 Basic recurrences section it was mentioned as 这种循环出现在循环输入以消除一个项目的递
算法 - 如何生成日期结构？
我正在思考如何在我的日历中生成代表任务的数据结构(仅供我个人使用)。我有来自 DBMS 的按日期排序的任务记录，如下所示: 买牛奶(18.1.2013) 任务日期 (2013-01-15) 任务标签(
算法:查找恰好出现两次的元素
输入一个未排序的整数数组A[1..n]只有 O(d) :(d int) 计算每个元素在单次迭代中出现在列表中的次数。 map 是balanced Binary Search Tree基于确保 O(nl
算法——基于寻找最大匹配数
我遇到了一个问题，但我仍然不知道如何解决。我想出了如何用蛮力的方式来做到这一点，但是当有成千上万的元素时它就不起作用了。 Problem: Say you are given the followin
算法 - 用于计算成对相互出现的次数
我有一个列表列表。 L1= [[...][...][.......].......]如果我在展平列表后获取所有元素并从中提取唯一值，那么我会得到一个列表 L2。我有另一个列表 L3，它是 L2 的某个
算法 - 在矩阵中求和
我们得到二维矩阵数组(假设长度为 i 和宽度为 j)和整数 k我们必须找到包含这个或更大总和的最小矩形的大小F.e k=7 4 1 1 1 1 1 4 4 Anwser是2，因为4+4=8 >= 7，
算法:根据周数获取下一年日期工作类次类型
我实行 3 类倒制，每周换类。顺序为早类 (m)、晚类 (n) 和下午类 (a)。我固定的订单，即它永远不会改变，即使那个星期不工作也是如此。我创建了一个函数来获取 ISO 周数。当我给它一个日期时
算法 - 找到满足输入元素任意组合的所有集合
假设我们有一个输入，它是一个元素列表: {a, b, c, d, e, f} 还有不同的集合，可能包含这些元素的任意组合，也可能包含不在输入列表中的其他元素: A:{e,f} B:{d,f,a} C:
算法:添加新元素时如何找到集合的子集？
我有一个子集算法，可以找到给定集合的所有子集。原始集合的问题在于它是一个不断增长的集合，如果向其中添加元素，我需要再次重新计算它的子集。有没有一种方法可以优化子集算法，该算法可以从最后一个计算点重新
算法:按预期频率将符号压缩成位串？
我有一个包含 100 万个符号及其预期频率的表格。我想通过为每个符号分配一个唯一(且前缀唯一)的可变长度位串来压缩这些符号的序列，然后将它们连接在一起以表示序列。我想分配这些位串，以使编码序列的预

行者123

个人简介

我是一名优秀的程序员,十分优秀！

作者热门文章

滴滴打车优惠券免费领取

全站热门文章

首页

博学

6Ren·AI

商城

algorithm - 有条件的房间分配和调度任务——优化算法