带时间延迟的极小化总完工时间的单机排序问题

• 作者: 王焕男 胡觉亮 蒋义伟
• 来源期刊: 浙江理工大学学报（自然科学版）
• 学科: 数学
• 关键词: 单台机 时间延迟 总完工时间 算法设计与分析 最优排序
• 年，卷（期）: 2014,（1）
• 所属期刊栏目: 数学
• 页码范围: 83-87
• 页数: 5页
• 分类号: O233
• 字数: 3608字
• 语种: 中文

摘要

研究工件带有两道工序的单台机排序问题.在该问题中,工件的第一道工序先于第二道工序加工,并且第二道工序的开工时间与第一道工序的完工时间至少间隔一定的延迟时间,目标是极小化所有工件的总完工时间.文章考虑所有工件相同且两道工序的加工时间均为单位时间的情形.通过引入k-连续加工的概念和分析最优解的性质,根据延迟时间的大小,分别设计了两个算法并证明了算法所得的排序为最优排序.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	胡觉亮	浙江理工大学理学院	81	456	12.0	17.0
2	蒋义伟	浙江理工大学理学院	19	25	3.0	4.0
3	王焕男	浙江理工大学理学院	2	1	1.0	1.0