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

摘要：

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

关键词：置换Flow Shop调度问题、数据标准化、降维

所属期刊栏目：42

分类号：TP393(计算技术、计算机技术)

资助基金：国家自然科学基金60863005,61262006;贵州省科学技术基金黔科合J字[2012]2125号;贵州省科技厅制造业信息化项目黔科合GY20113074

在线出版日期：2016-05-13（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：68-73,107