带强制工期的可中断单机排序问题

• 作者: 王国庆 程明宝 钟雪灵
• 来源期刊: 应用数学学报
• 学科: 数学
• 关键词: 单机排序 准备时间 强制工期 空闲时间 提前完工时间和
• 年，卷（期）: 2012,（1）
• 页码范围: 108-119
• 分类号: O223
• 字数: 8015字
• 语种: 中文
• DOI: 10.3969/j.issn.0254-3079.2012.01.008

摘要

工件带强制工期,指工件必须在已给定的工期内完工,不得延迟.这种环境在实际应用中随处可见.如果工件过早提前完工,意味着工件还需要保管,将会产生额外费用.本文讨论了在单机上,加工带准备时间与强制工期的n个可中断工件,在机器可空闲条件下,确定一个工件排序,使得提前完工时间和最小.先考虑了问题的复杂性,通过奇偶划分问题归约,证明了其是NP-complete的.而后,讨论了加工时间相等的特殊情形,由于工件不允许延迟,问题可能会无可行排序,因此提出了一个多项式时间算法,既能判定可行性,又能针对可行问题获得最优排序.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	钟雪灵	广东金融学院计算机系	28	93	6.0	9.0
2	王国庆	暨南大学管理学院	39	319	10.0	17.0
3	程明宝	广东工业大学管理学院	15	87	4.0	9.0