11-32
A Polynomially Solvable Case of a Single Machine Scheduling Problem When the Maximal Job Processing Time is a Constant
Preprint series: 11-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
The author(s) agree, that this abstract may be stored as full text and distributed as such by abstracting services.