引用本文:武 维,管晓宏,卫军胡.Flow shop问题的嵌套分区优化调度方法[J].控制理论与应用,2009,26(3):233~237.[点击复制]
WU Wei,GUAN Xiao-hong,WEI Jun-hu.Nested partition-optimization algorithm for flow shop scheduling[J].Control Theory and Technology,2009,26(3):233~237.[点击复制]
Flow shop问题的嵌套分区优化调度方法
Nested partition-optimization algorithm for flow shop scheduling
摘要点击 2057  全文点击 2589  投稿时间：2007-12-26  修订日期：2008-10-13
查看全文  查看/发表评论  下载PDF阅读器
DOI编号  10.7641/j.issn.1000-8152.2009.3.001
  2009,26(3):233-237
中文关键词  嵌套分区算法  流水作业调度  优化调度  启发式算法
英文关键词  nested partition-algorithm  flow shop scheduling  optimization scheduling  heuristic algorithm
基金项目  国家自然科学基金资助项目(60736027, 60704033); 863高科技计划项目(2007AA04Z154); 陕西省自然科学基础研究计划项目(2007F41).
作者单位E-mail
武 维 西安交通大学 制造系统工程国家重点实验室, 系统工程研究所, 陕西 西安 710049 mr.allawn@gmail.com 
管晓宏 西安交通大学 制造系统工程国家重点实验室, 系统工程研究所, 陕西 西安 710049 xhguan@sei.xjtu.edu.cn 
卫军胡 西安交通大学 制造系统工程国家重点实验室, 系统工程研究所, 陕西 西安 710049 jhwei@sei.xjtu.edu.cn 
中文摘要
      介绍了嵌套分区算法(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.