Zurück zu den Preprints des Jahres 2011


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

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

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.

Scheduling, Single machine, Release time, Due date, Lateness