Single machine scheduling with due date assignment to minimize the total weighted lead time penalty and late work

Yao-Wen Sang, Jun-Qiang Wang, Małgorzata Sterna and Jacek Błażewicz

Omega, 2023, vol. 121, issue C

Abstract: We study a single machine scheduling problem with due date assignment for minimizing the total weighted lead time penalty and late work, where the lead time penalty is the excess of an assigned due date over a given lead time, and the late work is the part of a job executed after the assigned due date. For the problem with common due date assignment, we show that it is solvable in O(nlogn) time. For the problem with unrestricted due date assignment, we determine an optimal due date assignment for a given schedule, and transform the problem to an equivalent problem for minimizing the total ▪-shape function, where ▪ depicts the shape of the penalty function for a job in relation to its completion time. Furthermore, we show that the problem with unrestricted due date assignment is unary NP-hard by proving the unary NP-hardness of the equivalent problem, and study two special cases. For the case with identical lead times, we show that it is binary NP-hard by providing a dynamic programming algorithm. While for the case with identical processing times, we prove that it is solvable in O(n3) time. Finally, we study the problem of minimizing the total ▪-shape function, and show that its two special cases are binary NP-hard by proving that they are pseudo-polynomially solvable.

Keywords: Scheduling; Due date assignment; Lead time penalty; Late work; NP-hard (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0305048323000877
Full text for ScienceDirect subscribers only

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:eee:jomega:v:121:y:2023:i:c:s0305048323000877

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.omega.2023.102923

Access Statistics for this article

Omega is currently edited by B. Lev

More articles in Omega from Elsevier
Bibliographic data for series maintained by Catherine Liu ().