Zurück zu den Preprints des Jahres 1996


1996-02

Single Machine Scheduling with Deadlines, Release and Due Dates

by Gordon, V., Potapneva, E., Werner, F..


Series: 1996-02, Preprints

MSC:
90B35 Scheduling theory, deterministic
90C60 Abstract computational complexity for mathematical programming problems

Abstract:
In this paper we consider a single machine preemptive scheduling problem to
minimize the weighted number of late jobs. There are given n jobs and for each job we have a
release date, a processing time and a due date. It is assumed that certain specified jobs have
to be completed on time. The due dates for these jobs are considered as deadlines, while
for the other jobs due dates may be violated. For the case of similarly ordered release and
due dates (when there is no advantage to preemption) as well as for the case of embedded
release and due date intervals and preemption allowed, we transform the initial problem into
a reduced problem, where all jobs with deadlines are eliminated. It gives an opportunity to
propose O(n log n) algorithms for some special cases of the considered problems.

Keywords:
single machine scheduling, deadlines, release and due dates

This paper was published in:
Optimization, Vol. 42, 1997, 219 - 244.