PDD规则下最小化最大延误调度问题 |
| |
作者姓名: | 万龙 黄晓莉 梅嘉杰 |
| |
作者单位: | 江西财经大学信息管理学院 |
| |
基金项目: | 江西省教育厅科技项目(No.GJJ190250); |
| |
摘 要: | 本文研究机器环境分别为单机、同型机和开放作业机器三种不同环境下的新型调度问题。其中工期根据工件的具体完工时间确定,且连续工期之间的间隔是相等的,一般称这种工期为等间隔工期(PDD)。本文考虑的目标函数都是最小化最大延误。对于单机环境,给出了多项式时间最优算法;对于两台同型机环境,证明了该问题是NP-难的;对于一般同型机环境,证明了该问题是强NP-难的;对于两台开放作业机器环境,证明了该问题是强NP-难的。
|
关 键 词: | 调度 开放作业 等间隔工期 延误 NP-完全性 |
|
|