Strong NP-hardness of two-machine flow-shop scheduling with periodic due dates(具有等间隔工期的2台机器流水作业调度问题的强NP难性)

Abstract

we consider three two-machine flow-shop scheduling problems with periodic due dates, where each due date is assigned not to a specific job but to the processing order and the lengths of the intervals between two consecutive due dates are identical. The objectives are to minimize the maximum tardiness, the total tardiness and the total number of tardy jobs, respectively. In this paper, we show that all three problems are strongly NP-hard. Furthermore, our results also mean that if P≠NP, there is no pseudo polynomial-time algorithm and fully polynomial-time approximation scheme (FPTAS) to solve these problems.(考虑3个具有等间隔工期的双机流水作业调度问题，其中按照调度方案中工件的加工顺序给每个工期分配工件，且2个连续工期之间的间隔长度相同，目标分别为最小化最大延误、总延误和总误工工件数。证明了此三问题均为强NP-难的。此外，结果表明，如果P≠NP，那么这些问题没有伪多项式时间算法和完全多项式时间近似方案（FPTAS）。)

Keywords

• two-machine flow-shop scheduling(2台机器调度)
• periodic due dates(等间隔工期)
• tardiness(延误)
• np-hardness(np-难)