期刊
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
卷 308, 期 1, 页码 76-83出版社
ELSEVIER
DOI: 10.1016/j.ejor.2022.10.047
关键词
Scheduling; Single machine; Late work; Assignable due dates; FPTAS
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据