寻找无资源槽的算法
我正在为一家工厂设计一个项目管理应用程序。该应用程序预计将生成项目计划草案。要安排任务，应用程序应检查三个条件：
- 任务依赖性 - 之前不启动、
- 机器可用性和
- 轮班工作时间。
我在 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
}
我的问题是，这是一个好方法吗？有更简单的方法可以做到这一点吗？
I am designing a project management app for a factory. The app is expected to produce draft project plans. To schedule a task, the app should check three conditions:
- task dependency - do not start before,
- machine availability, and
- shift work hours
I keep track of machine engagement in machine_allocations table:
machine_allocations
+------------+--------------+-----------------+---------------+
| machine_id | operation_id | start_timestamp | end_timestamp |
+------------+--------------+-----------------+---------------+
Shift hours follow a pattern.
Now, to find the earliest possible date-time for an operation I am thinking of a function:
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
}
My question is, is this a good approach? Are there simpler ways to do this?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
一次查找一项操作的最早日期时间可能不会给您带来最佳结果。考虑这样的示例：操作 A 长时间使用机器 1，操作 B 短时间使用机器 1，操作 C 短时间使用机器 2，但操作 C 必须在 B 之后执行。
在这种情况下，最好是在机器 1 上将 B 安排在 A 之前，但您的方法无法实现此目的。当然，编写和使用软件来管理它会比您所建议的更困难，因此您需要决定这种好处是否值得付出额外的努力。
看看调度，作业车间调度 和 调度算法。
首先，您需要考虑可以收集哪些类型的有关任务的信息（例如依赖性、优先级、截止日期），然后决定如何最好地将它们组合在一起。
您可能会发现您提出的方法对于您的情况来说已经足够好了。我对您提出的算法的补充是对现有机器操作列表进行排序，以便更快地搜索它们，也就是说，您可以在找到适合您的操作的时间后立即停止，因为它保证是最早的时间。
一个相对简单的扩展是一个优先级系统，它允许您向前推进较低优先级的任务（这可能也需要调整它们的依赖关系），但更复杂的算法会同时考虑多个任务并尝试优化结果。最终取决于什么适合您的具体问题。
Finding the earliest date-time for one operation at a time may not give you the best result. Consider the example where operation A uses machine 1 for a long time, operation B uses machine 1 for a short time and operation C uses machine 2 for a short time, but operation C must be done after B.
In this case, it is better to schedule B before A on machine 1, but your approach would not achieve this. Of course, writing and using software to manage this would be more difficult than what you have suggested, so you need to decide whether the benefit is worth the extra effort.
Have a look at Scheduling, Job Shop Scheduling and Scheduling algorithm.
First you need to think about what sort of information you can collect about tasks (such as dependencies, priorities, deadlines) and then decide how best to put it together.
You may find that an approach like you propose is good enough in your case. My addition to your proposed algorithm would be to sort the list of existing machine operations to make searching through them faster, that is you can stop as soon as you find a time where your operation fits because it's guaranteed to be the earliest time.
A relatively simple extension would be a priority system that allows you to bump lower-priority tasks forward (which may require the adjustment of their dependencies as well), but more complicated algorithms would consider multiple tasks at once and try to optimise the outcome. In the end it comes down to what's appropriate for your specific problem.
这取决于您何时想要计划工作。如果在开始机器工作之前，则可能采用分支限界算法或类似的算法（可能采用动态编程）。如果机器工作时必须计划工作，并且您无法知道将执行哪些工作，那么对于最佳解决方案，您无法计算（好吧，我无法考虑它）。也许可以将下一个工作放在最大时间较小的机器上？也许是 Ford-Bellmas alg 的动态版本（如果您有几层生产）。很难说。
我会采取几种方法并确定女巫是最好的。您可以写一篇关于此的文章:)
That depends when You want to plan work. If before starting work of machines then mayby a Branch&Bound algorithm, or something like it (mayby dynamic programming). If work have to planned when machines are working and You can not tell what jobs would be performed then for optimal solution You can not count (well I can't think about it). Mayby put next jobs on machine with smalles max time? Mayby a dynamic version of Ford-Bellmas alg (if you have couple layers of production). Hard to say.
I would do couple of approches and determine witch are best. The You can write an article about this :)