一种求解置换Flow Shop调度问题的DRPFSP算法

• 作者: 秦永彬 许道云 魏嘉银
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: 置换Flow Shop调度问题 数据标准化 降维
• 年，卷（期）: 2015,（7）
• 所属期刊栏目: 2014'全国理论计算机科学年会
• 页码范围: 68-73,107
• 页数: 7页
• 分类号: TP393
• 字数: 6702字
• 语种: 中文
• DOI: 10.11896/j.issn.1002-137X.2015.7.015

摘要

针对置换Flow Shop调度问题,在对经典启发式算法进行研究的基础上,提出了一种用于求解此类问题的DRPFSP算法.算法首先对加工时间矩阵A进行数据标准化处理;然后通过引入一个概率矩阵P2×m和相应的降维函数fp(A)=PA,将含有m台机器的原问题转化为含2台机器的新问题;再运用Johnson算法对新问题进行求解得到一个调度序列π0;最后结合插入邻域快速评价法对π0进行处理以获得原问题的一个调度方案π.实验结果表明,相对于经典的启发式算法,DRPFSP算法能更有效地对置换Flow Shop调度问题进行求解.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	许道云	贵州大学计算机科学与技术学院	125	460	12.0	16.0
2	秦永彬	贵州大学计算机科学与技术学院	63	213	8.0	10.0
3	魏嘉银	贵州大学计算机科学与技术学院	7	38	3.0	6.0