可能产生中断且考虑运输的两台平行机排序问题

• 作者: 叶赛英 沈灏 魏小兰
• 来源期刊: 浙江大学学报（理学版）
• 学科: 数学
• 关键词: 动态规划 平行机排序 中断 运输
• 年，卷（期）: 2009,（2）
• 所属期刊栏目: 数字与计算机科学
• 页码范围: 144-146,152
• 页数: 4页
• 分类号: O223
• 字数: 3905字
• 语种: 中文
• DOI: 10.3785/j.issn.1008-9497.2009.02.007

摘要

讨论两台平行机排序问题.有一台机器在某一个特定时刻可能产生中断,中断持续时间长短满足相应的概率,且工件转移到另一台机器上加工需要考虑运输时间.证明该问题是NP-困难的,设计一个复杂性为O(n3(TP)4)的动态规划算法,调整机器原有的工件排序,使得目标函数为带权重的总完工时间期望值最小.其中,n是工件的个数, TP是所有工件的加工时间之和.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	沈灏	杭州电子科技大学理学院	15	22	3.0	3.0
2	叶赛英	浙江科技学院理学院	8	31	3.0	5.0
3	魏小兰	杭州电子科技大学理学院	3	6	1.0	2.0