问题标签 [resource-scheduling]

在加权间隔调度问题中，有一个间隔 {i_1, i_2, ..., i_n}序列，其中每个间隔i_x代表一个连续的范围（在我的例子中，一个非负整数的范围；例如i_x = [5,9)）。通常的目标是将每个区间的权重设置为等于其宽度，然后确定总权重最大的非重叠区间的子集。我刚刚提供的链接给出了一个很好的解决方案。

我已经用 C++ 实现了该解决方案，从给定链接中提供的算法开始（在此处的 GitHub 存储库中用 Python 编写。

但是，给出的链接上的当前解决方案 - 以及我在其他任何地方看到的讨论 - 只提供了一种捕获单个 maximal fit的方法。当然，在某些情况下，可以有多个最大拟合，每个都具有相同的总（全局最大）权重。

我已经实现了一种“蛮力”方法来捕获所有最大拟合，我将在下面进行描述。

然而，在讨论我使用的蛮力方法的具体细节之前，我想解决的蛮力方法中的关键问题是，除了真正的最大拟合之外，我的蛮力方法还捕获了许多误报. 如果您可以回答以下问题，则无需深入研究我的蛮力方法的细节：

我想知道支持捕获所有最大拟合的基本O(n log(n))解决方案的（或一个）最有效的增强是什么，而不仅仅是一个最大拟合（但如果有人能回答如何避免误报，那也会让我满意）。

我在这方面没有取得任何进展，并且我使用的蛮力方法在最大拟合数超过数千（也许更少）的情况下开始变得难以控制。

谢谢！

我正在使用的蛮力方法的详细信息，仅在感兴趣或有用的情况下：

在我上面链接的现有源代码中有一行代码负责算法选择单个最大拟合的事实，而不是沿着可以捕获所有最大拟合的路径前进。 单击此处查看该行代码。 这里是：

注意>（大于号）。这行代码成功地保证了总权重高于给定子问题的任何其他区间组合的任何区间组合。通过更改>为>=，可以捕获所考虑的当前间隔集的总权重与之前的最高总权重相等的场景，这将使得捕获所有最大拟合成为可能。我希望捕捉到这种情况，所以在我的 C++ 迁移中，我使用了and，在等式成立的情况下，我通过递归函数调用>=沿着fork 中的两条路径前进。

下面是（关键）函数的 C++ 代码，该函数捕获每个子问题的所有最佳间隔集（和权重）（注意最终解决方案是在子问题对应于整个问题的最后一个索引处获得的）。

请注意，它OPTs是list所有潜在解决方案中的一个（最大间隔集）（即，其中的每个元素OPTs本身就是所有子问题的单个完整解决方案，由一组间隔和每个子问题的相应权重组成），而OPT用于描述单个这样的完整解决方案 - 与用于构造它的所有间隔的潜在最大拟合，每个子问题一个。

对于我上面指出的加权间隔调度问题的标准解决方案，获得的解决方案只是OPT（单个，而不是列表）。

下面RangeElement代码中的类型只是与我正在讨论的问题无关的元数据。

RangesVec包含作为问题输入的区间集（按结束值正确排序）。 PreviousIntervalVec对应于compute_previous_intervals上面链接中的讨论。

（注意：对于正在查看上面链接的 Python 代码的任何人，请注意，我认为我在其中发现了一个与保存最大集合中的间隔有关的错误；请参阅此处以获取有关此错误的评论，我已经在我下面的 C++ 代码中修复。）

这是我捕获所有最大拟合的“蛮力”实现。 我的蛮力方法还捕获了一些需要在最后删除的误报，我会对任何给出最有效方法来排除误报但使用与以下算法等效的算法的答案感到满意。

我试图了解资源分配是如何在火花中发生的。我了解 taskScheduler 中的 resourceOffer 方法。此方法在分配资源时会考虑局部性因素。此 resourceOffer 方法由相应的集群管理器调用。

我正在研究独立的火花簇。但我无法找到资源分配的起点。考虑到 Spark 的新应用程序，我想从头到尾了解资源分配究竟是如何发生的。此外，除了 mesos，Scheduler 中还有一个名为 Local 的文件夹。有人可以告诉我应该查看哪些所有文件以了解独立 Spark 集群中的资源分配以及这个“本地”是什么？

提前致谢！！卡提克。

我试图模拟以下问题：一组人（现实中的学校老师）必须在不同的时间到达办公室（即人 1 在 2 小时进入并在 7 小时离开，人 2 在 4 小时进入在 6 小时退出，依此类推）。这些时间根据给定时间表后的一周中的哪一天而变化。为了到达办公室，上班时间相同的人在一个共同的地方见面并共用一辆车。同样，当他们必须从办公室回来时，他们会在给定时间离开的司机的汽车中进行分类，以到达他们家附近的公共场所。问题是如何为每个转弯分配一名司机和一名工作人员，以便：

1. 所有人都可以轮流找到位置（出发和返回）
2. 每轮有最大人数（由于车位有限）
3. 尽量减少使用的汽车总数
4. 每个人都应该驾驶相同数量的汽车（或尽可能均匀地使用每辆汽车/司机）

因此，输入是一个表格，如：
周一：Andrew 1-3（出发-返回时间），Bill 2-5，Cindy 1-7 ...
Tue：Andrew 2-7，Bill 1-6，Cindy 2-4 ...
周三：...

而输出应该是
周一：出发：第 1 小时（司机安德鲁，船员：Cindy，史蒂夫），第 2 小时（司机比尔，船员：史蒂夫，弗兰克）...返回：第 3 小时（司机安德鲁，船员：吉姆，丽莎)，第 4 小时（司机 Mary，工作人员：David，Pete）...
周二：出发时间 1（司机 Bill，工作人员：Richard，Dan，Pete），第 2 小时（司机 Andrew，工作人员：Cindy，Bob）...
周三...

我正在尝试清理当前正在使用优先级 FIFO 调度算法的企业 BI 系统（因此周二的优先级 4 报告将在周四的优先级 4 报告和周一的优先级 3 报告之前执行。）其他详细信息：

• 队列永远不会为空，总是在添加作业
• 作业的执行时间从不到一分钟到超过 24 小时不等
• 有 40 个奇怪的相同应用服务器用于执行作业

我想我可以让 optaPlanner 启动并运行这种情况，围绕优先级制定硬性规则，围绕队列中的平均时间制定一些软性规则。我是调度优化的新手，所以我想我的问题是在这种情况下我应该寻找什么来决定 optaPlanner 是否会帮助我？

我想开发一个应用程序，用户可以在其上注册警报（多个），以便每当票价低于某个阈值时，他都会收到通知。票价是从第三方网站获取的。我想在 google app-engine 上执行此操作。

现在据我了解，我需要一个 24/7 运行的进程，它每隔 30 分钟检查一次票价，并在低于阈值时发出通知。可能 app-engine 的 cron 作业可用于此任务？但是最多可以安排 100 个 cron 作业，这将是更好的方法。同样为每个用户设置一个进程会浪费资源，有什么更好的调度算法来提高效率？

我正在尝试使用 SWI prolog 和 CLP 进行项目调度。我设法支持顺序依赖，但我正在努力避免重复预订人。

我有一个名为 Schedule 的列表，其中包含 [taskname, starttime] 等元素，其中 starttime 是约束求解器的自由变量。它们已经受到顺序依赖的约束。

我正在尝试编写这样的循环来排除重复预订：

使用 foreach 总是失败，使用 forall 总是成功，没有任何限制。

就这个循环而言，Schedule 是全局的，目的是使用序列化来约束它的 starttime 元素。OTOH、HisSchedule、Sts 和 Dus 取决于特定的人。所以我认为我需要 foreach 来让 Schedule 开心，但为了让 HisSchedule 等开心。那是问题吗？如果是这样，我该如何解决？

我是路由优化的新手，非常感谢您在使用 jsprit 解决以下业务需求方面的帮助。我从 Stefan Schröder 那里得到了一些反馈，他帮助我学习了一些关于 jsprit 的基础知识。我将首先解释业务需求，然后问几个问题。

目标是安排需要在一个月内完成的维护工作列表。需要为整个月准备每日时间表。这里的目标是每天执行最大数量的工作。

• 一个地区有 4 个仓库，每个仓库
• 每个区域有大约 70 个仓库，总共 300 个仓库
• 该区域内每个仓库与仓库之间的距离是已知的
• 每个区域有3-4辆不同类型的车辆，共12辆
• 区域内的车辆只能服务于该区域内的仓库
• 区域内的车辆具有相同的起点，恰好是终点
• 车辆没有任何容量、取货或交付要求
• 车辆仅用于运输将执行维护工作的工人
• 每辆车的平均速度已知
• 大约有 80 种维护工作类型
• 每种作业类型都需要以分钟为单位的已知时间
• 维护作业不必在特定时间开始
• 每月大约有 200 项维护工作需要执行
• 这些工作可以在任何仓库
• 同一个仓库可以在同一天或不同天进行不止一项工作
• 一天内有 3 个八小时班次。上午 6 点至下午 2 点、下午 2 点至晚上 10 点和晚上 10 点至上午 6 点
• 车辆将在轮班开始时离开仓库仓库，并在八小时轮班内访问尽可能多的仓库
• 车辆在执行作业时必须在仓库等待，然后才能移动到下一个仓库或返回到堆场仓库

我的基本理解是，维护工作可以定义为jsprit中的服务，并且可以为每辆车设置启动/返回时间。此外，成本矩阵可用于增加车辆和仓库之间关系的时间和距离。我的问题是：

1. 每个维护作业都需要定义为一项服务，因此将有 200 个服务对象传递给 VRP 求解器，对吗？
2. VehicleTypeImpl 具有 addCapacityDimension()、setCostPerDistance() 和 setCostPerTime() 方法。这些到底是什么以及它们如何应用上述案例？
3. Service.Builder 有 addSizeDimension() 方法。它有什么作用？
4. costMatrixBuilder 具有添加 TransportDistance 和 TransportTime 的方法。这些方法使用了哪些单位，我该如何使用它们？
5. 对于每个站点，需要定义一个坐标并将其传递给每个 VehicleImpl 的 setStartLocationCoordinate() 方法。这是正确的吗？
6. vehicleBuilder 有 setLatestArrival(double maxDuration); 这里使用哪个单位？

我非常感谢解决上述案例的任何帮助。

谢谢，亚当

编辑1：

几个问题

A. setEarliestStart() 和 setLatestArrival() 方法接受双精度值，如何将最早出发和最晚到达的日期指定为这些方法的实际日期？例如，开始时间是 2014 年 11 月 28 日下午 2 点，结束时间是当天晚上 10 点。

B. 有没有办法以分钟为单位指定服务时间？

C. VehicleTypeImpl.Builder.setMaxVelocity(double inMeterPerSeconds) 方法期望最大速度，有没有办法指定车辆的平均速度？

D、所有车辆实行三班倒；这是否意味着我必须定义同一辆车三次，每个班次都有不同的最早出发和最晚到达时间？

E. 由于作业可以在一个月内的任何时间执行，每个作业的时间窗口是否会作为月份的开始和结束传递给 Service.Builder.setTimeWindow() 方法？

背景：我正在为面向服务架构 ( SOA )中的系统开发一个调度程序，其框架类似于Internet 通信引擎 ( ICE )。

系统中的服务根据其工作负载在多台机器上运行。例如，当工作负载为 1000/秒时，服务 A 将在 10 台机器上运行，而当工作负载为 10000/秒时，服务 A 将在 100 台机器上运行。

在系统中，一个服务也调用其他服务。因此，服务 A 的响应时间不仅取决于每台机器上的工作量，还取决于服务 A 调用的服务 B、C、D 的响应时间。如果服务 B 出错，则服务 A 出错，也。当服务调用网络复杂时，当一个服务开始出错时，就会有很多服务出错。很难确定哪个服务应该有更多的机器。

由于系统性能的原因，我们在调度时无法对所有服务有一个全貌。因此，我们需要根据服务 A 的本地信息做出决策。

问题是我们能否对服务 A 建模以在给定服务 A 的情况下预测服务 A 的性能（服务 A 的当前工作负载、服务 B、C、D 的当前性能以及机器上的当前资源利用率）。

目的：我们可以通过模型找出导致服务A性能下降的因素（服务B/C/D的性能下降还是资源限制？）。

给定：训练数据可以是服务 A、B、C、D 的历史性能（平均响应时间、工作负载）以及运行服务 A 的机器上的资源利用率。

操作系统版本信息：

test.slice 的配置如下：

我像这样创建了另一个文件（称为 testhigh.slice）并给它 CPU 份额 = 128。当我在任一切片中启动 CPU 饥饿进程时，我看到 CPU 按比例分配，正如预期的那样。

但是，似乎没有办法实际将一个切片的 CPU 限制为一个常数，例如 10%。systemd无法识别 CPUQuota 选项：

原则上，能够精确地分配资源会很棒，但现在我无法让它发挥作用。请帮忙; 如果可能的话，我想要一个来自 systemd 框架内部的解决方案。

这是我要解决的问题：

• 有一个城镇在位置 (x,y) 有病人，他们会死去。
• 患者需要在死前到达医院才能获救。
• (x,y) 的一堆医院，有一些救护车，一次最多可以接 4 名患者，并将他们送到任何医院。
• 救护车从医院出发，经过多次旅行，最终可以到达任何医院。
• 我们应该尽可能多地挽救患者。
• 完整的问题描述在这里：http ://cs.nyu.edu/courses/fall15/CSCI-GA.2965-001/ambulance.html

我正在尝试使用jsprit来解决这个问题，但无法弄清楚如何执行以下操作：（我想知道我应该查看 API 的哪一部分）

1) 指定有有限的救护车，但它们可以进行多次旅行。

• 设置 VehicleRoutingProblem.Builder.setFleetSize(FleetSize.INFINITE) 会这样做吗？该代码没有记录确切的功能。

2) 限制病人在死前送到医院，或离开他们。

• Shipment.Builder.newInstance("...").setDeliveryTimeWindow(time_of_patient_dying) 能做到这一点吗？

3) 为任何到达医院分娩的救护车增加 1 分钟的卸载时间。

• 不知道要查看 API 的哪个部分。

4）让救护车选择更好的路线，让他们把病人送到任何医院。

• 不知道要查看 API 的哪个部分。

到目前为止，这是我的代码：