Article ID: | iaor20084409 |
Country: | Brazil |
Volume: | 23 |
Issue: | 3 |
Start Page Number: | 443 |
End Page Number: | 456 |
Publication Date: | Sep 2003 |
Journal: | Pesquisa Operacional |
Authors: | Valente Jorge M.S., Alves Rui A.F.S. |
In this paper we consider a single machine scheduling problem with integer release dates and a common due date. The objective is to minimise the weighted sum of the jobs' earliness and tardiness costs. We present an efficient polynomial algorithm for the unit processing time case. We also show how to calculate, for the general case, the minimum non-restrictive due date.