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

摘要

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