Abstract: In the paper, we consider novel scheduling problems under single-machine, parallel-machine and two-machine open-shop environment. The due date is assigned to a job according to its completion time and the intervals between consecutive due dates are identical. Generally, the due dates are referred as periodic due dates (PDD). The objectives we consider are all to minimize the maximum tardiness. For single machine environment, we give an optimal schedule in polynomial time; for two parallel-machine environment, we prove this problem is NP-hard; for parallel-machine environment, we prove this problem is strongly NP-hard; for two-machine open-shop environment, we prove this problem is strongly NP-hard.

Key words: scheduling, open shop, periodic due date, tardiness, NP-completeness