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

The Scheduling Problem with Cyclic Time Windows on Machines

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

Given a set of jobs which would be processed on a limited number of machines, how to reasonably arrange the processing of jobs on machines to achieve the optimal solution is the scheduling problem. The scheduling problem with cyclic time windows on machines is based on the classic scheduling problem and given the cyclic time windows on machines, the aim is to minimize makespan for the scheduling problem with cyclic time windows on machines. We analyze the NP-Hardness and present an approximation algorithm for the problem. We prove that the algorithm has a worst-case approximation ratio 3/2 when k>m, and has a trivial optimal solution when k≤m.