恒速处理机的多机Flow shop最小和调度问题的启发式算法分析

• 作者: 古春生 陈华平
• 来源期刊: 小型微型计算机系统
• 学科: 工学
• 关键词: 调度 多机Flow shop调度 启发式算法 渐近性能分析
• 年，卷（期）: 2006,（2）
• 所属期刊栏目: 算法研究
• 页码范围: 320-324
• 页数: 5页
• 分类号: TP18
• 字数: 5702字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-1220.2006.02.032

摘要

本文研究有n个作业需在s个处理机中心进行加工,处理机中心i由li个恒速机组成的非抢占式多机flow shop调度最小和问题.每个作业有s个工序,每个工序需在对应的处理机中心的任一台机器上加工处理,作业到达前不能加工,所有作业通过处理机中心的路径相同.目标是确定一个作业在每个处理机中心机器上的可行调度序列,使所有作业在最后处理机中心的加权完成时间总和最小化.在作业处理时间需求、作业权重分别为独立同分布的有界随机变量时,通过特殊flow shop调度松弛方法,我们证明该问题在作业数趋于无穷时,一个基于有效作业最短加权平均处理时间需求的启发式算法是渐近最优的.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈华平	中国科学技术大学商学院	72	1503	19.0	36.0
2	古春生	中国科学技术大学商学院	26	248	9.0	15.0