PDD规则下最小化最大延误的调度问题
Scheduling with Periodic Due Date to Minimize the Maximum Tardiness出 版 物：《管理科学》
年 卷 期：2023年第5期
主 题：调度 开放作业 等间隔工期 延误 NP-完全性 scheduling open shop periodic due date tardiness NP-completeness
摘 要：本文研究机器环境分别为单机、同型机和开放作业机器三种不同环境下的新型调度问题。其中工期根据工件的具体完工时间确定，且连续工期之间的间隔是相等的，一般称这种工期为等间隔工期（PDD）。本文考虑的目标函数都是最小化最大延误。对于单机环境，给出了多项式时间最优算法；对于两台同型机环境，证明了该问题是NP-难的；对于一般同型机环境，证明了该问题是强NP-难的；对于两台开放作业机器环境，证明了该问题是强NP-难的。