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

DRPFSP Algorithm for Solving Permutation Flow Shop Scheduling Problem

作　　者：魏嘉银[1] 秦永彬[1] 许道云[1] 

机构地区：[1]贵州大学计算机科学与技术学院,贵阳550025

出　　处：《计算机科学》2015年第7期68-73,107,共7页Computer Science

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

摘　　要：针对置换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.

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

分 类 号：TP393[自动化与计算机技术—计算机应用技术]