一种求解置换flowshop调度问题的drpfsp算法

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