寻找无资源插槽的算法

Question

我正在为一家工厂设计一个项目管理应用程序。该应用程序有望生成项目计划草案。要安排任务，应用程序应检查三个条件:

1. 任务依赖——不先开始，
2. 机器可用性，以及
3. 轮类工作时间

我在 machine_allocations 表中跟踪机器参与情况:

machine_allocations
+------------+--------------+-----------------+---------------+
| machine_id | operation_id | start_timestamp | end_timestamp |
+------------+--------------+-----------------+---------------+

轮类时间遵循一种模式。

现在，为了找到操作的最早可能日期时间，我正在考虑一个函数:

function earliest_slot($machine_id, $for_duration, $no_sooner_than) {
   // pseudo code
   1. get records for the machine in question for after $no_sooner_than 
   2. put start and end timestamps into $unavailable array
   3. add non-working times as new elements to the array
   4. in a loop find timeslots which are not in the array
   5. if a timeslot is found which is equal to or bigger than $for_duration, return that
}

我的问题是，这是一个好方法吗？有没有更简单的方法来做到这一点？

Answer 1

一次查找一项操作的最早日期时间可能不会给您最好的结果。考虑操作A长时间使用机器1，操作B短时间使用机器1，操作C短时间使用机器2，但操作C必须在B之后完成。

在这种情况下，最好在机器 1 上将 B 安排在 A 之前，但您的方法无法实现这一点。当然，编写和使用软件来管理它会比您建议的更困难，因此您需要决定是否值得为此付出额外的努力。

看看Scheduling , Job Shop Scheduling和 Scheduling algorithm .

首先，您需要考虑可以收集哪些有关任务的信息(例如依赖关系、优先级、截止日期)，然后决定如何最好地将它们组合在一起。

您可能会发现，您提出的这种方法在您的情况下已经足够好了。我对你提出的算法的补充是对现有机器操作列表进行排序，以便更快地搜索它们，也就是说，你可以在找到适合你的操作的时间后立即停止，因为它保证是最早的时间。

一个相对简单的扩展将是一个优先级系统，它允许您将优先级较低的任务向前推进(这可能还需要调整它们的依赖关系)，但更复杂的算法会同时考虑多个任务并尝试优化结果。最后，它归结为适合您的特定问题的方法。