| 一种求解置换Flow Shop调度问题的DRPFSP算法 |
| |
| 引用本文： | 魏嘉银,秦永彬,许道云.一种求解置换Flow Shop调度问题的DRPFSP算法[J].计算机科学,2015,42(7):68-73, 107. |
| |
| 作者姓名： | 魏嘉银 秦永彬 许道云 |
| |
| 作者单位： | 贵州大学计算机科学与技术学院 贵阳550025 |
| |
| 基金项目： | 本文受国家自然科学基金(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调度问题进行求解。
|
| 关 键 词： | 置换Flow Shop调度问题 数据标准化 降维 |
DRPFSP Algorithm for Solving Permutation Flow Shop Scheduling Problem |
| |
| WEI Jia-yin QIN Yong-bin XU Dao-yun.DRPFSP Algorithm for Solving Permutation Flow Shop Scheduling Problem[J].Computer Science,2015,42(7):68-73, 107. |
| |
| Authors: | WEI Jia-yin QIN Yong-bin XU Dao-yun |
| |
| Affiliation: | Department of Computer Science & Technology,Guizhou University,Guiyang 550025,China |
| |
| Abstract: | |
| |
| Keywords: | Permutation Flow Shop scheduling problem Data normalization Dimensionality reduction |
|
|
点击此处可从《计算机科学》下载全文 |
|
