Volltext-Downloads (blau) und Frontdoor-Views (grau)

Single machine scheduling with assignable due dates to minimize maximum and total late work

  • A single machine scheduling problem with assignable job due dates to minimize total late work has recently been introduced by Mosheiov, Oron, and Shabtay (2021). The problem was proved NP-hard in the ordinary sense, and no solution algorithm was proposed. In this note, we present two pseudo-polynomial dynamic programming algorithms and an FPTAS for this problem. Besides, we introduce a new single machine scheduling problem to minimize maximum late work of jobs with assignable due dates. We develop an O(n log n) time algorithm for it, where is the number of jobs. An optimal solution value of this new problem is a lower bound for the optimal value of the total late work minimization problem, and it is used in the FPTAS.

Export metadata

Additional Services

Search Google Scholar


Document Type:Article
Author:Jan-Erik JustkowiakORCiD, Sergey Kovalev, Mikhail Y. KovalyovORCiD, Erwin PeschORCiD
Center:Center for Advanced Studies in Management (CASiM)
Parent Title (English):European journal of operational research : EJOR
Issue:1 (July 2023)
Date of Publication (online):2022/11/07
First Page:76
Last Page:83
Year of first Publication:2022
Content Focus:Academic Audience
Peer Reviewed:Yes
Rankings:AJG Ranking / 4
VHB Ranking / A
SJR Ranking / Q1
Licence (German):License LogoUrheberrechtlich gesch├╝tzt