### 2011-32

**A Polynomially Solvable Case of a Single Machine Scheduling Problem When the Maximal Job Processing Time is a Constant**

by Vakhania, N.; Werner, F..

**Series:** 2011-32, Preprints

- MSC:
- 90B35 Scheduling theory, deterministic
- 68Q25 Analysis of algorithms and problem complexity

**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