Minimizing maximum absolute lateness and range of lateness under generalizeddue dates on a single machine

K. Tanaka and M. Vlach

Annals of Operations Research, 1999, vol. 86, issue 0, 507-526

Abstract: We investigate the problems of minimizing the maximum absolute lateness and range oflateness under generalized due dates on a single machine. In contrast to the traditional duedate cases, we show that these problems are unary NP‐hard. Furthermore, we present simpleapproximation algorithms for these problems, and show that they achieve the performanceratios of n for the problem of minimizing the maximum absolute lateness and of [ n/2 ] forthe problem of minimizing the range of lateness, where [ x ] is the smallest integer no lessthan x. Copyright Kluwer Academic Publishers 1999

Date: 1999
References: Add references at CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://hdl.handle.net/10.1023/A:1018987625819 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:86:y:1999:i:0:p:507-526:10.1023/a:1018987625819

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1023/A:1018987625819

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().