Strong NP-hardness of two-machine flow-shop scheduling with periodic due dates
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.
two-machine flow-shop schedulingperiodic due datestardinessNP-hardness
万方数据
维普
