Preemptive scheduling of jobs with agreeable due dates on a single machine to minimize total tardiness

Preemptive scheduling of jobs with agreeable due dates on a single machine to minimize total tardiness

0.00 Avg rating0 Votes
Article ID: iaor20102985
Volume: 37
Issue: 5
Start Page Number: 368
End Page Number: 374
Publication Date: Sep 2009
Journal: Operations Research Letters
Authors: , ,
Abstract:

We consider the problem of scheduling n preemptive jobs on a single machine to minimize total tardiness, subject to agreeable due dates, i.e., a later release date corresponds to a later due date. We prove that the problem is NP-hard in the ordinary sense by showing that it is NP-hard, and deriving a pseudo-polynomial algorithm for it.

Reviews

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