带时间窗口的单工件排序问题

摘要

排序是为加工若干个工件或者完成若干项任务而对资源按时间进行高效率的分配,本文讨论一个工件的情况下对多台机器进行排序,从而使加工时间最短的问题。在这个问题中给定一个时间窗口作为约束,机器只能在规定的时间窗口内运行。分析该问题是NP-难问题,并给出一个近似算法,讨论该近似算法的近似比不超过3/2,该近似算法的时间复杂度为O(m2)。