【摘要】 介绍了嵌套分区算法(NP)的基本思想,并用于求解流水作业优化调度问题.算法用嵌套分区树来描述流水作业调度问题,对可行域进行系统性分区,然后集中搜索有优良解的区域.在每一步迭代中,算法跟踪最有希望的分区,并结合启发式算法和邻域搜索来实现分区转移.仿真实验表明,该算法比单纯的启发式算法和邻域搜索有较好的寻优能力.更多还原

【Abstract】 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.更多还原