我知道有一些关于任务调度的问题是NP-hard/NP-complete的...然而,它们没有被陈述得足够清楚以展示该情况也属于NP。
如果您有一组受到“startAfter”、“startBy”和“duration”限制的任务,并且它们都试图使用单个资源...你能否解决一个时间表或确定需要进行详尽搜索才能解决它?
如果答案是"对不起,但这是NP-complete",最好的启发式算法是什么?有没有方法可以缩短a)解决时间表和b)识别无法解决的时间表所需的时间。
我已经在Prolog中实现了一个基本的冲突解决目标,通过递归实现了“最小窗口优先”启发式算法。它实际上可以快速找到解决方案,但在查找无效时间表方面非常慢。有没有办法克服这个问题?
好耶,这是复合问题!