具有等间隔工期的2台机器流水作业调度问题的强NP难性  

Strong NP-hardness of two-machine flow-shop scheduling with periodic due dates

作　　者：崔晓龙 何周力 梅嘉杰 万龙[1] CUI Xiaolong;HE Zhouli;MEI Jiajie;WAN Long(School of Information Management,Jiangxi University of Finance and Economics,Nanchang 330013,China)

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

出　　处：《浙江大学学报（理学版）》2024年第5期593-598,共6页Journal of Zhejiang University（Science Edition）

基　　金：国家自然科学基金地区科学基金项目(12261039).

摘　　要：考虑3个具有等间隔工期的双机流水作业调度问题,其中按照调度方案中工件的加工顺序给每个工期分配工件,且2个连续工期之间的间隔长度相同,目标分别为最小化最大延误、总延误和总误工工件数。证明了此三问题均为强NP-难的。此外,结果表明,如果P≠NP,那么这些问题没有伪多项式时间算法和完全多项式时间近似方案(FPTAS)。we consider three two-machine flow-shop scheduling problems with periodic due dates,where each due date is assigned not to a specific job but to the processing order and the lengths of the intervals between two consecutive due dates are identical.The objectives are to minimize the maximum tardiness,the total tardiness and the total number of tardy jobs,respectively.In this paper,we show that all three problems are strongly NP-hard.Furthermore,our results also mean that if P≠NP,there is no pseudo polynomial-time algorithm and fully polynomial-time approximation scheme(FPTAS)to solve these problems.

关 键 词：2台机器调度 等间隔工期 延误 NP-难 

分 类 号：O226[理学—运筹学与控制论]