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

by Vakhania, N.; Werner, F.


Preprint series: 11-32, Preprints

90B35 Scheduling theory, See also {68M20}
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

The author(s) agree, that this abstract may be stored as full text and distributed as such by abstracting services.

Letzte Änderung: 01.03.2018 - Ansprechpartner:

Sie können eine Nachricht versenden an: Pierre Krenzlin