一种求解置换Flow Shop调度问题的DRPFSP算法
Flow Shop调度问题(Flow-shop Scheduling Problem,FSP)是许多实际流水线生产调度问题的简化模型，亦是研究最为广泛的生产调度问题之一，具有很强的工程应用背景。置换Flow Shop调度问题是约定每台机器上所加工的各工件的顺序相同的一类Flow Shop调度问题，针对置换Flow Shop调度问题,在对经典启发式算法进行研究的基础上,提出了一种用于求解此类问题的DRPFSP算法.算法首先对加工时间矩阵A进行数据标准化处理;然后通过引入一个概率矩阵P2×m和相应的降维函数fp(A)=PA,将含有m台机器的原问题转化为含2台机器的新问题;再运用Johnson算法对新问题进行求解得到一个调度序列π0;最后结合插入邻域快速评价法对π0进行处理以获得原问题的一个调度方案π.实验结果表明,相对于经典的启发式算法,DRPFSP算法能更有效地对置换Flow Shop调度问题进行求解.
Flow Shop调度问题 DRPFSP算法 数学模型
魏嘉银 秦永彬 许道云
贵州大学 计算机科学与技术学院,贵州 贵阳 550025
国内会议
济南
中文
1-9
2014-10-16（万方平台首次上网日期，不代表论文的发表时间）