问题标签 [resource-scheduling]

问题 ：

五个批处理作业 A 到 E 几乎同时到达计算机中心。他们估计运行时间为 10、6、2、4 和 8 分钟。它们的（外部确定的）优先级分别为 3、5、2、1 和 4，其中 5 是最高优先级。确定平均过程周转时间。忽略进程切换开销。对于 Round Robin Scheduling，假设系统是多道程序，并且每个作业都获得了 CPU 的公平份额。所有作业都完全受 CPU 限制。

解决方案 #1以下解决方案来自此页面：

对于循环，在前 10 分钟内，每个作业获得 1/5 的 CPU。在 10 分钟结束时，C 结束。在接下来的 8 分钟内，每个作业获得 1/4 的 CPU，之后 D 完成。然后剩下的三个作业中的每一个都在 6 分钟内获得 1/3 的 CPU，直到 B 完成，依此类推。五项作业的完成时间分别为 10、18、24、28、30，平均为 22 分钟。

解决方案 #2以下解决方案来自康奈尔大学，这是不同的（这对我来说更有意义）：

请记住，周转时间是作业到达和作业完成之间经过的时间量。由于我们假设所有作业都在时间 0 到达，因此周转时间将只是它们完成的时间。(a) 循环：下表列出了在每个时间段内将处理哪些作业。* 表示作业在该时间段内完成。

结果不同：例如，在第一个 C 中，10 分钟后完成，而在第二个中，C 在 8 分钟后完成。

哪一个是正确的，为什么？我很困惑..提前谢谢！

我有一个优化问题。这是关于包含 20 个零件的产品（生产顺序无关紧要）。我有 3 台类似的机器，可以生产所有 20 个零件。

我已经得到了以分钟为单位的 20 个部分（即生产第一部分需要 3 分钟，生产第二部分需要 75 分钟，等等）

因此，生产 1 个产品需要 730 分钟。

目的是通过将好的产品分配给三台机器来最小化一种产品的生产。

所以实际上我需要接近 243.333 分钟 (730/3)

可能性很大 3^20

我想有许多不同的最佳解决方案。我希望 R 给我所有这些。我不仅需要知道需要机器 1 2 和 3 的总时间：我还需要知道将哪些物品提供给机器 1、机器 2 和机器 3。

或者，如果它太长，我想选择一个尽可能合理的不重复样本......

我可以用 R 语言解决我的问题吗？

给定一家软件公司，其中开发人员在多个不同项目的团队中工作。项目需要指定开发人员的特定技能。出于我的目的，我想保持简单并将其限制为一种技能，即编程语言。所以有些项目需要Java，有些需要C等。项目有固定的持续时间，每个项目应该有两个开发人员分配给它。

在任何时间点，一些项目正在进行中，新项目进来，需要在未来的某个时间点进行计划。我想计算一个时间表，哪些开发人员应该在什么时间和什么项目上工作。

我不是在寻找最佳解决方案（如果可能的话）。我对人类经理可以创建的时间表感到满意。

我读过关于资源约束调度问题和分配问题的文章，但我很少接受正式的 CS 培训，而且我经常迷失在这些问题的不同变体中的所有细微差别中。

我认为我的问题是作业车间调度的一个更简单的变体，其中作业是项目，开发人员是机器，因此作业需要同时多台机器。只有一个先例约束，即运行中的项目不能中止，因此必须先完成。

从我读过的所有可能的解决方案中，我倾向于使用遗传算法，主要是因为我读过人们使用它们得到了很好的结果，并且因为我前一段时间将一个用于另一个项目。我也读过线性规划的好结果，但我对此知之甚少。

遗传算法是否是此类问题的可行解决方案？还是有更好的解决方案？

我在 Ubuntu 12.04 下观察到以下行为：

在具有 24GB RAM 和 24 个 CPU 的系统上，如果单个进程获得 ~12GB 的 RAM，则属于高内存进程所有者的所有其他进程都会在没有警告的情况下被杀死，使用看似 SIGKILL 的方法，并且高内存进程允许运行直到终止。此外，所有者尝试启动新进程将失败。

这有点麻烦，但我更好奇它为什么会发生。大概这是内核中资源调度决策的结果。有没有地方可以找到这方面的文档？

我有以下问题，我需要一些想法来处理它：

1. 我有许多公共汽车（大约 150 辆）个人所有 每个人都开自己的公共汽车（或负责公共汽车司机）所以我不需要关心公共汽车司机，因为公共汽车和司机是一回事。

2. 上述巴士每天必须“执行/执行”巴士路线（约 200 辆）。

3. 一辆公共汽车每天可以走一条或多条路线

4. 公共汽车可以每周正常工作5天，每天（或每月）可以正常工作一定时间

5. 我必须找到一种公平的方式来每 3 个月分发一次每日路线。公平意味着在 3 个月的期限结束时，所有公交车必须行驶相同的公里数（每条公交路线都分配了固定的公里数）

6. 一开始，我无法安排整个 3 个月的时间，因为每天都会发生“特殊的事情”。就像公共汽车有问题，司机有问题等等。这意味着我今天做下一天的时间表。

有任何想法吗？

我必须写一篇关于调度非 CPU 资源的文章。我找不到任何关于这究竟意味着什么的信息，谁能给我一个关于这是什么的想法。

我们计划举办一场由 8 支球队组成的锦标赛，每支球队都与其他球队比赛一次。比赛为期 7 天，每支球队每天比赛。比赛安排在7个场馆，每支球队在每个场馆都必须打一场。作为电视安排的一部分，我们已经完成了一些预先安排：我们可以将两支特定球队之间的比赛固定在一个固定的日期和场地，或者只规定某些球队必须在特定的一天在给定场地进行比赛。目标是完成进度表，以便满足所有约束条件。

我需要帮助才能在 minizinc 中解决这个问题。谢谢

我一直在考虑调度和负载平衡算法，我想出了一个我认为很有趣的问题。

有 N 个笼子和 M 个饲养员。每个笼子的大小为 S，动物数量为 A。笼子必须清洁的频率被计算为 A / S 的某个函数（具有更多动物的较小笼子会更快变脏）。清洁笼子的难度被计算为 A 和 S 的一些其他函数，其中的细节并不重要（笼子的大小贡献了大部分的难度，动物的数量贡献了一点点）。每三天一次，清洁任何需要清洁的笼子（“清洁日”）。Zookeepers 是完全一样的并且可以互换。动物园管理员在每个清洁日都需要做类似的工作量，并且不必比任何其他动物园管理员做更多的工作。清理笼子所需的时间不是问题的一部分（假设时间大致反映在难度上，

调度算法必须告诉每个动物园管理员在每个清洁日要清洁哪些笼子，这样

• 每个笼子都以理想的频率或尽可能接近的频率进行清洁，
• 为每个动物园管理员每个清洁日分配最少且大致相等的清洁次数，
• 并确保所有 zookeepers 的工作量尽可能相等（即，在一段时间内，每个 zookeeper 工作量的总难度尽可能接近相等，笼子以大约 1/M 的概率分布在 zookeepers 中）。

我想知道这种优化问题的近似算法是什么样的。它与 NP-hard 调度/资源利用问题的几个不同经典示例相似；也许它可以简化为一个这样的问题，而我只是想念它。如果我们去掉任务的频率/周期元素，它类似于经典的多处理器调度或有限装箱问题。

我需要你的帮助来解决这个问题。我有一组任务，每个任务都有其执行时间。我有两种类型的约束。第一种是任务之间的优先关系。第二种约束类型是允许一组任务同时执行。例如：我有一个包含 6 个任务和以下边 (T1,T2)、(T2,T3)、(T4,T3)、(T4,T5) 和 (T6,T5) 的图 G。假设 T1,T4 能够一起执行，T1,T6 也可以执行，但 T4,T6 不能。考虑到每个任务的执行时间。考虑到某些任务的并行执行，如何找到满足任务之间优先关系的调度，同时最小化调度的长度。

我有一个问题与查找最长非重叠序列的算法非常相似。

与链接问题的唯一区别是，我不需要找到代表最长序列的非重叠元组集，而是需要找到代表最大覆盖率的非重叠元组集，我的意思是总和元组长度最大（元组长度在下一句中last - first + 1给出元组的定义）。

我表示我的元组与链接问题不同。而不是(starting index, length)，我将我的元组表示为(first, last); 例如，元组(3,7)表示数字的集合[3, 4, 5, 6, 7]。（即使端点匹配，一个元组也会与另一个元组重叠；即重叠(2,6)，因此不能同时出现在解决方案中。）(6,8)

例如，考虑以下一组元组，按 排序first：

[(0,100), (2,50), (30,150), (60,95), (110,190), (120,150), (191,200)]

此处的最大值将[(0,100), (110,190), (191,200)]覆盖101 + 81 + 10 = 192. （请注意，此解决方案中的元组是不重叠的。）

解决此问题的最简单算法的示例是什么，该算法的复杂性是多少？（如果这个问题可以解决就好了O(N)，但我目前不知道是否可以。）

附录：回想起来，事实证明我在这里提出的问题等同于加权间隔调度问题。这是间隔调度问题的一个特例。

@j_random_hacker 下面的答案实际上是加权间隔调度问题的已知解决方案，其时间复杂度为O(N log(N)).