Minimizing total tardiness on parallel machines with preemptions

Minimizing total tardiness on parallel machines with preemptions

0.00 Avg rating0 Votes
Article ID: iaor20122812
Volume: 15
Issue: 2
Start Page Number: 193
End Page Number: 200
Publication Date: Apr 2012
Journal: Journal of Scheduling
Authors: ,
Keywords: combinatorial optimization
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 Qr 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 Pr 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 Qp j =p, pmtn∣ΣT j .

Reviews

Required fields are marked *. Your email address will not be published.