Minimizing total tardiness on parallel machines with preemptions |
| |
Authors: | Svetlana A Kravchenko Frank Werner |
| |
Affiliation: | 1. United Institute of Informatics Problems, Surganova St. 6, 220012, Minsk, Belarus 2. Fakult?t f??r Mathematik, Otto-von-Guericke-Universit?t, 39106, Magdeburg, Germany
|
| |
Abstract: | The basic scheduling problem we are dealing with in this paper is the following one. A set of jobs has to be scheduled on
a set of parallel uniform machines. Each machine can handle at most one job at a time. Each job becomes available for processing
at its release date. All jobs have the same execution requirement and arbitrary due dates. Each machine has a known speed.
The processing of any job may be interrupted arbitrarily often and resumed later on any machine. The goal is to find a schedule
that minimizes the sum of tardiness, i.e., we consider problem Q∣r
j
,p
j
=p, pmtn∣∑T
j
whose complexity status was open. Recently, Tian et al. (J. Sched. 9:343–364, 2006) proposed a polynomial algorithm for problem 1∣r
j
,p
j
=p, pmtn∣∑T
j
. We show that both the problem P∣ pmtn∣∑T
j
of minimizing total tardiness on a set of parallel machines with allowed preemptions and the problem P∣r
j
,p
j
=p, pmtn∣∑T
j
of minimizing total tardiness on a set of parallel machines with release dates, equal processing times and allowed preemptions
are NP-hard. Moreover, we give a polynomial algorithm for the case of uniform machines without release dates, i.e., for problem
Q∣p
j
=p, pmtn∣∑T
j
. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|