Journal
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Volume 308, Issue 1, Pages 76-83Publisher
ELSEVIER
DOI: 10.1016/j.ejor.2022.10.047
Keywords
Scheduling; Single machine; Late work; Assignable due dates; FPTAS
Ask authors/readers for more resources
This study introduces a single machine scheduling problem with assignable job due dates to minimize total late work. The problem is proved to be NP-hard and no solution algorithm is proposed. Two pseudo-polynomial dynamic programming algorithms and an FPTAS are presented to solve this problem. In addition, a new single machine scheduling problem to minimize maximum late work of jobs with assignable due dates is introduced. An O(n log n) time algorithm is developed for this problem, where n is the number of jobs. The optimal solution value of this new problem serves as a lower bound for the optimal value of the total late work minimization problem and is utilized in the FPTAS.
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 n 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. (c) 2022 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available