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

DRPFSP Algorithm for Solving Permutation Flow Shop Scheduling Problem

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

For the permutation Flow Shop scheduling problem,a new algorithm named DRPFSP,which is based on the study of the classic heuristic algorithms,was proposed in this paper.The algorithm normalizes the matrix Aof processing times firstly.Secondly,it transforms the original problem containing m machines into a new problem containing 2 machines by introducing aprobability matrix P2×m and a corresponding dimension reduction function fp（A）=PA.Thirdly,it uses the Johnson algorithm to solve the new problem and finds a scheduling sequence π 0.Finally,it processes π0 with the insert neighborhood fast evaluation method to obtain a scheduling schemeπfor the original problem.The experiment results show that,compared with the classical heuristic algorithms,DRPFSP algorithm is more effective for the permutation Flow Shop scheduling problem.