96-02
Single Machine Scheduling with Deadlines, Release and Due Dates
by Gordon, V.; Potapneva, E.; Werner, F.
Preprint series: 96-02, Preprints
The paper is published: Optimization, Vol. 42, 1997, 219 - 244.
- MSC:
- 90B35 Scheduling theory, See also {68M20}
- 90C60 Abstract computational complexity for mathematical programming problems, See also {68Q25}
Abstract: In this paper we consider a single machine preemptive scheduling problem tominimize the weighted number of late jobs. There are given n jobs and for each job we have arelease date, a processing time and a due date. It is assumed that certain specified jobs haveto be completed on time. The due dates for these jobs are considered as deadlines, whilefor the other jobs due dates may be violated. For the case of similarly ordered release anddue dates (when there is no advantage to preemption) as well as for the case of embeddedrelease and due date intervals and preemption allowed, we transform the initial problem intoa reduced problem, where all jobs with deadlines are eliminated. It gives an opportunity topropose O(n log n) algorithms for some special cases of the considered problems.
Keywords: single machine scheduling, deadlines, release and due dates
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.