机器带有循环时间窗口的排序问题

给定一个在有限数量机器上加工的作业集合,如何合理地安排作业在机器上加工以达到最优解就称之为排序问题,排序问题是经典的组合优化问题之一。机器带有循环时间窗口的排序问题是在我们已知的经典排序问题基础上,给定机器上的循环时间窗口,目标是求解机器带有循环时间窗口的排序问题的最小化最大完工时间所用的天数。本文分析了问题的NP困难性,给出了一种求解机器带有循环时间窗口的排序问题的近似算法,最后证明了当k】m时,算法的最坏情况近似比为3/2,当k≤m时,算法具有一个最优平凡解。

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

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