Flow shop问题的嵌套分区优化调度方法  

Nested partition-optimization algorithm for flow shop scheduling

作　　者：武维[1] 管晓宏[1] 卫军胡[1] 

机构地区：[1]西安交通大学制造系统工程国家重点实验室,系统工程研究所,陕西西安710049

出　　处：《控制理论与应用》2009年第3期233-237,共5页Control Theory & Applications

基　　金：国家自然科学基金资助项目(60736027,60704033);863高科技计划项目(2007AA04Z154);陕西省自然科学基础研究计划项目(2007F41).

摘　　要：介绍了嵌套分区算法(NP)的基本思想,并用于求解流水作业优化调度问题.算法用嵌套分区树来描述流水作业调度问题,对可行域进行系统性分区,然后集中搜索有优良解的区域.在每一步迭代中,算法跟踪最有希望的分区,并结合启发式算法和邻域搜索来实现分区转移.仿真实验表明,该算法比单纯的启发式算法和邻域搜索有较好的寻优能力.A nested partition-algorithm and its application to the flow shop scheduling problem are addressed in this paper. In this application, the flow shop scheduling problem is considered as a partition tree. The algorithm performs an iterative process in which it partitions the feasible region and searches for the subset where the optimal solution is located. In the iteration, a heuristic algorithm and a neighborhood-search are employed to select a sample-point for estimating the promising index for each subset. Finally, computational experiments indicate that the algorithm outperforms the constructive heuristic algorithm and neighborhood-search in the performance of searching.

关 键 词：嵌套分区算法 流水作业调度 优化调度 启发式算法 

分 类 号：N945.15[自然科学总论—系统科学]