Depending on the amount of data to process, file generation may take longer.

If it takes too long to generate, you can limit the data by, for example, reducing the range of years.


Download BibTeX


Single Machine Scheduling with Due Date Assignment to Minimize the Total Weighted Lead Time Penalty and Late Work


[ 1 ] Instytut Informatyki, Wydział Informatyki i Telekomunikacji, Politechnika Poznańska | [ P ] employee

Scientific discipline (Law 2.0)

[2.3] Information and communication technology

Year of publication


Published in


Journal year: 2023 | Journal volume: vol. 121

Article type

scientific article

Publication language


  • Scheduling
  • Due Date Assignment
  • Lead Time Penalty
  • Late Work
  • NP-hard

EN 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(n log n) 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 [Image 1]-shape function, where [Image 1] 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 [Image 1]-shape function, and show that its two special cases are binary NP-hard by proving that they are pseudo-polynomially solvable.

Date of online publication






Article Number: 102923

Ministry points / journal


Impact Factor

6.9 [List 2022]

This website uses cookies to remember the authenticated session of the user. For more information, read about Cookies and Privacy Policy.