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 N P-hard in the ordinary sense by showing that it is N P-hard, and deriving a pseudo-polynomial algorithm for it.
Original language | English |
---|---|
Pages (from-to) | 368-374 |
Number of pages | 7 |
Journal | Operations Research Letters |
Volume | 37 |
Issue number | 5 |
DOIs | |
Publication status | Published - 1 Sept 2009 |
Keywords
- Preemptive scheduling
- Single machine
- Total tardiness
ASJC Scopus subject areas
- Management Science and Operations Research
- Applied Mathematics
- Industrial and Manufacturing Engineering
- Software