找到无资源插槽的算法

问题描述：

我正在为一家工厂设计一个项目管理应用程序。该应用程序预计将生成草案项目计划。要计划任务，应用程序应该检查三个条件：找到无资源插槽的算法

任务相关性 - 不要启动前，
机器的可用性，并
轮班工作小时

我跟踪机订婚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 
}

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

答

一次找到一个操作的最早日期时间可能不会给你最好的结果。考虑操作A长时间使用机器1的示例，操作B短时间使用机器1并且操作C短时间使用机器2，但操作C必须在B后完成。

在这种情况下，最好在机器1的A之前安排B，但是你的方法不会达到这个目的。当然，编写和使用软件来管理这些将比您建议的更困难，所以您需要决定是否值得付出额外的努力。

看一看Scheduling,Job Shop Scheduling和Scheduling algorithm。

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

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

一个相对简单的扩展将是一个优先级系统，它允许您向前推进优先级较低的任务（也可能需要调整其依赖关系），但更复杂的算法会一次考虑多个任务并尝试优化结果。最后，它归结为适合您的具体问题。

谢谢你的建议。我知道这样制定的计划不会是最佳的，这就是为什么我称之为“草案计划”。我不向客户承诺，它可以让他们摆脱手工调整时间表的需要。所以我正在接近它的方式来保持复杂性。因此，对于我计划提供的*有限效用值*，您是否发现该算法是最简单的？ –

我认为这个算法很简单*对它没有任何影响。如果你有一个简单的解决方案，不要浪费时间寻找最简单的解决方案，尤其是如果你的需求可能会改变...... – Artelius

*非常好的建议*。你是对的 - 我最好去实施它！ - 我会记得最后一个（我保证;））。 –

答

这取决于您何时计划工作。如果在开始工作之前，机器可能会通过Branch & Bound算法或类似的东西（mayby动态编程）。如果在机器工作时必须计划工作，并且您无法确定将执行哪些工作，那么为了获得最佳解决方案您无法计数（以及我无法考虑它）。 Mayby将最近一次的工作放在机器上最小时间？ Mayby是Ford-Bellmas alg的一个动态版本（如果你有几层生产）。很难说。我会做几个认识，并确定女巫是最好的。你可以写一篇关于这方面的文章:)

我想你没有正确地阅读这个问题。问题很具体 - 如何最好地实现'early_slot'函数。 – svick

@neosatan谢谢。每项任务将在第一时间计划;和*可能*在这里意味着我们应该满足三个条件：（i）在购买之前不要吃冰激凌，（ii）我们需要的机器在任务期间应该是免费的，（iii）不要将任务设置为非工作时间。 –

@svick我正确地阅读它，但是当它发挥作用时，所有可以获得的信息都非常重要。问题在我看来是不准确的，所以我在这里给出了一个普遍的答案。 Artelius提出了非常好的答案，我想获得更多信息。 –

找到无资源插槽的算法

相关推荐