| Article ID: | iaor20043602 |
| Country: | Portugal |
| Volume: | 24 |
| Issue: | 1 |
| Start Page Number: | 63 |
| End Page Number: | 71 |
| Publication Date: | Jun 2004 |
| Journal: | Investigao Operacional |
| Authors: | Valente Jorge M.S., Alves Rui A.F.S. |
In this paper we consider the single machine scheduling problem with integer release dates and the objective of minimising the sum of deviations of jobs' completion times from a common integer due date. We present an efficient polynomial algorithm for the unit processing time case. We also show how to calculate in polynomial time the minimum non-restrictive due date for the general case.