是否所有调度问题都是NP-Hard? [英] Are all scheduling problems NP-Hard?

问题描述

我知道那里存在一些调度问题，这些问题是NP难的/NP完整的...但是，这些问题都没有以表明这种情况也是NP的方式陈述.

I know there are some scheduling problems out there that are NP-hard/NP-complete ... however, none of them are stated in such a way to show this situation is also NP.

如果您有一组限制在 startAfter ， startBy 和 duration 的任务都试图使用单个资源 ... ...您可以解决时间表或确定没有详尽搜索无法解决的时间表吗?

If you have a set of tasks constrained to a startAfter, startBy, and duration all trying to use a single resource ... can you resolve a schedule or identify that it cannot be resolved without an exhaustive search?

如果答案是对不起朋友，但这是NP完全的" ，什么是最好的启发式方法?有什么方法可以减少花费在a)上的时间解决时间表，然后b)找出无法解决的时间表.

If the answer is "sorry pal, but this is NP-complete" what would be the best heuristic(s?) to use and are there ways to decrease the time it takes to a) resolve a schedule and b) to identify an unresolvable schedule.

我已经(通过序言)实现了一个基本的冲突解决目标，即通过递归实现了最小的窗口优先"启发式方法.这实际上可以很快找到解决方案，但是在发现无效的计划时异常缓慢.有办法克服吗?

I've implemented (in prolog) a basic conflict resolution goal through recursion that implements a "smallest window first" heuristic. This actually finds solutions rather quickly, but is exceptionally slow at finding invalid schedules. Is there a way to overcome this?

同意复合问题！

推荐答案

现实生活中大多数调度问题中最困难的部分是掌握可靠性和完整的约束条件.如果我们以创建大学时间表为例:

The hardest part of most scheduling problems in real life is getting hold of a reliability and complete set of constraints. If we take the example of creating a university timetable:

• A教授早上不会起床，他在许多委员会中任职，但是没人会告诉时间表办公室这种限制因素
• 第1部门在学期开始前需要时间表，但是使用相同房间的第2部门不愿意决定将要运行的课程，直到所有学生都到达为止
• 等等

然后，您需要一个可以应对变更的计划系统，因此，在最后一分钟更改一个约束时，您不必更改完整的时间表.

Then you need a schedule system that can cope with changes, so when one constraint is changed at the last minute you don’t have to change the complete timetable.

以上所有有关调度系统的论文通常都被忽略.对于给定调度问题的NP完整性，在您并不在意中，即使它不是NP完整，您也不太可能定义什么是最佳解决方案"，足够好就足够了.

All of the above is normally ignored in research papers about scheduling systems. As to NP completeness of a given scheduling problem, in real life you don’t care as even if it is not NP complete you are unlikely to even be able to define what the "best solution" is, so good enough is good enough.

请参见 http://www.asap.cs.nott .ac.uk/watt/resources/university.html 以获得可能帮助您入门的论文列表；调度软件中仍然有很多PHD.

See http://www.asap.cs.nott.ac.uk/watt/resources/university.html for a list of papers that may help get you started; there are still many PHDs to be had in scheduling software.

这篇关于是否所有调度问题都是NP-Hard?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！