Scheduling with periodic due date to minimize the maximum tardiness

In the paper, we consider novel scheduling problems under 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. The objectives this article consider is to minimize the maximum tardiness. For two-machine open-shop environment, we prove this problem is strong NP-hard.