单机调度
计算机科学
数学优化
动态规划
作业车间调度
缩小
调度(生产过程)
时间复杂性
到期日
算法
数学
地铁列车时刻表
操作系统
作者
Jan‐Erik Justkowiak,Sergey Kovalev,Mikhail Y. Kovalyov,Erwin Pesch
标识
DOI:10.1016/j.ejor.2022.10.047
摘要
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(nlogn) 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.
科研通智能强力驱动
Strongly Powered by AbleSci AI