一种求解同顺序 Flowshop 排序问题的新的启发式算法

New Scheduling Heuristic for the Permutation Flowshop Problem

在生产调度中经常遇到工件排序问题，这类问题大多属于ＮＰ类问题．对此，目前无论在理论上还是在实际应用中，都尚未找到令人满意的一般求解方法．针对ＮＰ类问题中的一类——同顺序Ｆｌｏｗｓｈｏｐ排序问题，进行了广泛而深入的调查和比较研究，在此基础上，提出了一种新的启发式算法（简称为ＷＳＨ法），并通过大量的数据实验将该算法与目前已知较好的几种算法进行了比较．结果表明，ＷＳＨ法结构简单，计算效率高，是求解中、小规模问题的较好算法．

The permutation flowshop problem,which is a class of NP problems that are often encountered in scheduling of manufacturing systems,has not been completely solved either in theory or in application. A new heuristic method,named WSH,is proposed in this paper to solve the permutation flowshop problem. This heuristic aims to minimize the total process time of all jobs. The comparison between this method and others reported in literature until now,is presented on the basis of results from many numerical examples. The results show that WSH,simple in structure and excellent in computational efficiency,is a good method to solve small size and medium size problems.