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