带有维修活动和交货期窗口的单机排序问题

【目的】带有维修活动和交货期窗口的单机排序问题在现实生活中有着广泛的应用。每个工件都有属于自己的交货期窗口,工件在交货期窗口外完工,就会产生相应的提前、延误惩罚。因此,确定交货期窗口位置具有重要意义。【方法】考虑了2种维修活动:依赖于时间、资源的维修活动;依赖于位置、资源的维修活动。针对不同的维修位置,将问题转化为指派问题。【结果】给出了计算复杂性是O(n4)的多项式时间算法。【结论】证明了该问题是多项式时间可解的。