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

考虑3个具有等间隔工期的双机流水作业调度问题,其中按照调度方案中工件的加工顺序给每个工期分配工件,且2个连续工期之间的间隔长度相同,目标分别为最小化最大延误、总延误和总误工工件数。证明了此三问题均为强NP-难的。此外,结果表明,如果P≠NP,那么这些问题没有伪多项式时间算法和完全多项式时间近似方案(FPTAS)。

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

本文研究机器环境分别为单机、同型机和开放作业机器三种不同环境下的新型调度问题。其中工期根据工件的具体完工时间确定,且连续工期之间的间隔是相等的,一般称这种工期为等间隔工期(PDD)。本文考虑的目标函数都是最小化最大延误。对于单机环境,给出了多项式时间最优算法;对于两台同型机环境,证明了该问题是NP-难的;对于一般同型机环境,证明了该问题是强NP-难的;对于两台开放作业机器环境,证明了该问题是强NP-难的。