PDD规则下最小化最大延误调度问题  

Scheduling with periodic due date to minimize the maximum tardiness

作　　者：万龙[1] 黄晓莉 梅嘉杰 WAN Long;HUANG Xiaoli;MEI Jiajie(School of Information Management,Jiangxi University of Finance and Economics,Nanchang 330013,Jiangxi,China)

机构地区：[1]江西财经大学信息管理学院,江西南昌330013

出　　处：《运筹学学报》2022年第4期75-86,共12页Operations Research Transactions

基　　金：江西省教育厅科技项目(No.GJJ190250)。

摘　　要：本文研究机器环境分别为单机、同型机和开放作业机器三种不同环境下的新型调度问题。其中工期根据工件的具体完工时间确定,且连续工期之间的间隔是相等的,一般称这种工期为等间隔工期(PDD)。本文考虑的目标函数都是最小化最大延误。对于单机环境,给出了多项式时间最优算法;对于两台同型机环境,证明了该问题是NP-难的;对于一般同型机环境,证明了该问题是强NP-难的;对于两台开放作业机器环境,证明了该问题是强NP-难的。In the paper,we consider novel scheduling problems under single-machine,parallel-machine and two-machine open-shop environment.The due date is assigned to a job according to its completion time and the intervals between consecutive due dates are identical.Generally,the due dates are referred as periodic due dates(PDD).The objectives we consider are all to minimize the maximum tardiness.For single machine environment,we give an optimal schedule in polynomial time;for two parallel-machine environment,we prove this problem is NP-hard;for parallel-machine environment,we prove this problem is strongly NP-hard;for two-machine open-shop environment,we prove this problem is strongly NP-hard.

关 键 词：调度 开放作业 等间隔工期 延误 NP-完全性 

分 类 号：O221.2[理学—运筹学与控制论]