问题标签 [resource-scheduling]

我想实现以下作业/资源调度问题：

• 边编码优先关系的作业的 DAG。
• 如果作业没有优先关系，则可以并行执行
• 多个资源池，每个池包含一个或多个类似资源。
• 一项作业可能依赖于一个或多个池中的一个或多个资源。即工作 J1 说类似：“我需要来自池 P1 的 2 个资源和来自池 P2 的 7 个资源。”
• 一项工作可能表示它需要与其直接前任之一完全相同的资源。即作业 J2 可能会说“我需要池 P1 中的 1 个资源，但它必须是作业 J1 分配的资源之一”。为简化起见，我假设作业 J2 必须是 J1 的直接继任者，以应对这种约束。
• 资源依赖可以被读取或写入或两者兼而有之或“不关心”
• 当作业 J1 说它从池 P1 写入资源时，其后续作业 J2 对“与 J1 从 P1 获得的相同资源”具有读取依赖性。在这两者之间，由于资源是有状态的，因此该资源不可用于其他作业进行写入。
• 我事先不知道每个作业的执行时间，也没有对作业的优先级和截止日期要求。

我在寻找：

1. 一种在正式领域表达这个问题的方法，
2. 一个离线可调度性测试，它回答了作业图是否可以在给定的要求和约束下执行的问题。
3. 一个在线调度算法的建议

如果没有资源池，但每种类型只有 1 个资源，问题可能会简单得多。我熟悉图论和简单数据流分析算法的基础知识。

根据不同的约束条件为给定任务安排劳动力。约束示例包括劳动力技能、时间、地点、轮班、假期、优先事项、能力等。

问题描述：假设12月25日有一个任务要在加利福尼亚设置Linux服务器，并且设置服务器需要5个小时的时间。要设置 Linus 服务器，我们需要熟练使用 Linux 服务器并留在加利福尼亚的劳动力，并且应该在 12 月 25 日上午 9 点到下午 3 点有空。总共六个小时。

那么，如果有大量的劳动力资源，如果我必须为多项任务找到合适的劳动力，我应该采用什么方法？

我 google 发现这是一个基于约束的编程问题，google OR Tools 和其他模型提供了解决它的方法。

所以我开始研究Google OR Tools Google OR Tools 文档。该文档提供了基本示例。

我在 git hub 上为 google 找到了另一个文档，或者比上面的链接更好。 谷歌或工具的 Git 中心文档

我尝试实施这里给出的护士调度程序谷歌或护士调度

我很难理解这个程序。这并不是说我在理解 python 或 java 上有困难。

所以我的问题是。

解决此类问题的方法是什么？Google OR 是正确的工具吗？如果是，谷歌的先决条件是什么，或者如果有人数学背景薄弱？我应该如何着手解决这样的问题？

我正在为 kubernetes 寻找一种解决方案，它允许对我的 POD 进行某种 CPU 固定（某种服务质量）。

我想从可用的 CPU 内核创建一个池，然后将 POD 分配给其中一个。CPU 池中的 POD 将相互竞争，而不同池中的 POD 将无法影响彼此的性能。

据我所知，Kubernetes 的当前 CPU 管理器解决方案可以在没有池抽象的情况下相互分配 CPU 内核和 POD。

一个特殊要求是主机是不可变的，因此无法更改 Kubernetes 之外的任何内容，但内部所有内容都应该可以按需管理。

谢谢！

我几乎没有关于显示每项任务以及任务持续时间的任务的数据，例如：

表格1：

在这里，我知道每项任务，任务多长时间，以及任务要在什么时间完成。现在我有 10 个工作人员，其中 7 个是合同制，他们的每小时工资单与普通员工不同。我需要将每项任务相应地分配给所有工作人员。不能有重叠。一项任务仅分配给单个船员。这样的任务有200个。是否有特定的 python 包甚至算法可以帮助我解决这个问题？我遇到了这个。但我不确定这是否可以相应地帮助我。有没有其他算法可以帮助我解决这个问题？

我正在寻找类似 calendly 的 Flutter 移动应用程序。Calendly 有 API:s 但它们实际上并不适用于移动应用程序，并且不允许创建和调用事件。

有什么可以推荐的吗？我正在尝试timekit atm，但它非常昂贵。

该应用程序适用于想要从专家那里购买和安排时间的客户。因此，应用程序中基本上列出了大约 20 位专家，用户应该能够看到他们的可用性、预订会话并能够在以后取消/重新安排它。

我正在尝试找到任何易于实现的算法，用于并行作业的离线调度，包括工人之间的有序任务，以在工人在他们可以做的事情上独一无二的特殊情况下（而不是工人可以做的典型情况）最小化制造时间。做任何任务，但可能需要不同的时间）受制于工人必须完成一项任务才能转移到另一项任务的约束。

我更关心实现的容易性而不是计算复杂性，因为每个工作的工人、工作和任务的数量都非常少（订单：分别为~10、<10 和 10-30）。

代理的特定属性在他们可以做什么而不是他们执行任务需要多长时间方面是不同的，这使得我很难找到一种算法（或我从接近的算法开始）。在搜索 algorithm 时，我尝试将其重铸为平铺问题（因为它类似于将甘特图堆叠在一起），并研究了如何将其转换为图形问题，但无济于事。

到目前为止，我发现的最接近的是dos Santos 2019、Spegal 2019、Schulz & Skutella 2002，但这些要求我将问题转换为一些机器花费无限时间进行不匹配的操作并考虑其他不适用于的调度属性这个问题——我对这些算法的了解还不够，不知道将它们设置为绕过的值是否会破坏它们。

PostgreSQL 如何从资源消耗的角度保护会话？

比如我写了一些存储过程：

1. 一个执行高度 cpu-bound 紧密循环的存储过程，PostgreSQL 如何防止它占用大部分可用 cpu？
2. 一个触发大量 IO 的存储过程，PostgreSQL 是如何让它不占用大部分 IO 带宽的呢？
3. 一个存储过程读取没有其他会话引用的广泛分散的页面，PostgreSQL如何防止它填满缓冲池？

此外，据我了解，每个 PostgreSQL 会话对应于不同的操作系统进程，所以我还想知道 PostgreSQL 明确处理的资源消耗隔离以及操作系统执行依赖于什么（作为操作系统调度机制的一部分）。

非常感谢。

皮亚卡

我在 miniKanren 学习关系编程，我决定实现一个时间调度系统。基本上，它归结为有限域上的三个关系。

首先，有一个时间带，它具有开始、持续时间、结束并出现在空间中：

然后，在条带列表（这是一个 4 元素列表的列表）上存在发生之前的关系。这是两个事件的结束和开始之间的成对关系：

最后，有一个非重叠关系，即两个时间带在共享相同空间时不能重叠：

我可以对关系链运行很长的查询happens-beforo，数千个时间带都可以。当我限制这些时间带的空间时，问题就开始出现了。这是一个功能：

对于条带 q 的列表，它在每两个元素之间建立non-overlappo关系。由于是双向关系，所以小于n^2。

当我constrain-spaco只使用 10 条时，搜索时间就会增加，我无法产生任何结果。

到目前为止，我一直在尝试减少这个时间的方法，似乎它与竞争一个空间的条带数量有关，而不管总共有多少条带。如果我创建两组条带，一组在空间 0 中，另一组在空间 1 中并应用于constrain-spaco整个条带列表，那么时间是这些条带分别计算的时间之和。

我的问题是：

1. 为什么有限域约束的数量会对时间产生如此大的影响？我的印象是约束的数量有助于搜索时间。
2. 有什么办法可以缩短搜索时间？也许改变数据表示？

我正在使用 Google OR-Tools 来解决技术人员处理机器修理任务的问题。机器一开始都是坏的，目标是修理机器并最小化总损失输出（即机器的累积停机时间）。任务之间有一个旅行时间，并且必须有车辆在任务之间运送技术人员。车辆比技术人员少，因此可能存在技术人员必须等待车辆空闲后再前往下一项任务的情况。例如：三名技术人员、八项任务、两辆车。

技术人员可以处理任何任务，并且任务持续时间是预先知道的。

我在下面制作了一个代码（基于带有旅行时间的作业车间），它以 2 个单位的固定旅行时间围绕任务安排技术人员。

但是，我不知道如何对可用的运输约束进行建模。（目前，技术人员可以在完成任务后立即移动）。谁能让我开始了解如何添加此功能？

我的想法是：

• 这实际上是一个车辆路线问题（而不是一个cp_sat）并且任务是一种时间窗口吗？或者它是部分车辆路线和部分调度 - 如果是这样，我会使用什么求解器？
• 我是否需要一个trans_for_tech变量，=1当车辆在使用时加上一个约束，trans_for_tech<=1以避免车辆被重复预订。然后这个变量会=1在电路的弧线被使用时（即它的布尔文字为真）。
• 车辆本身是否真的执行“任务”（即运输），这些“任务”（即运输）需要通过开始/结束/无重叠条件进行建模，NewOptionalInterval以便在使用电路的弧线时启用它们。这些的开始/结束实际上是任务间隔的补充吗？然后，从概念上讲，将有两组任务（技术人员工作和车辆运输），这些任务将被安排以最大限度地减少损失的时间。
• 由于运送技术人员的车辆访问不同的任务地点，因此这些车辆也有旅行时间，但我的想法是暂时忽略这一点，只是将车辆建模为可在任务中的任何地方立即可用但受到限制的资源，因此它不能t 同时在两个地方（即变量有 asum<=1或 aAddBoolOr或类似的东西）。

下面是我的代码，用于技术人员准备好后移动的情况（相当于每个人都有自己的交通工具）。

所以，我有一个问题。假设有 k 个处理器和 k*n 个作业。现在，每个处理器应该恰好完成 n 个工作，并且每个处理器都需要特定的时间来完成一个特定的工作。如下图所示，这里的时间 k 列是指处理器 k 完成不同工作所花费的时间。

任务是找到我们可以完成所有工作的最短时间。现在，对于 k=2，我发现贪婪的方法是有效的。我们可以计算每个工作的 T2-T1。如果我们在处理器 2 中执行任务，这是时间的净损失。因此，我们可以按非递减顺序对其进行排序，并将前 n 个作业分配给处理器 2 和其余处理器 1。我无法扩展解决方案对于更高的 k 值。有没有一个通用的算法呢？如果有人可以为此指出任何论文，或者指导我大致的方向，我将不胜感激。我需要一个精确的解决方案，但足够接近的解决方案也可以。

编辑：机器一个接一个地运行，而不是同时运行。因此，完成时间不是所有机器花费的最短时间，而是它们时间的总和。