Series: 2011-32, Preprints
Abstract:
We consider the problem of scheduling jobs with given release times and due dates on a single machine to minimize the maximal job lateness. This problem is NP-hard, and its version when the job processing times are restricted to $p,2p,3p,4p,\dots$, for an integer $p$, is also NP-hard. We consider the case when the maximal job processing time is $kp$, for any constant $k$, and propose its polynomial-time solution. We easily establish that the version of this problem with unrestricted $k$ is NP-hard. Moreover, it is strongly NP-hard if $p$ has no exponential-time dependence on the maximal job due date. From a practical point of view, this is a realistic assumption.
Keywords:
Scheduling, Single machine, Release time, Due date, Lateness