作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2008, Vol. 34 ›› Issue (1): 256-258. doi: 10.3969/j.issn.1000-3428.2008.01.088

• 工程应用技术与实现 • 上一篇    下一篇

柔性作业车间调度问题的集成启发式算法

陈 亮,王世进,周炳海   

  1. (上海交通大学机械与动力工程学院,上海 200240)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2008-01-05 发布日期:2008-01-05

Integrated Heuristic Algorithm for Flexible Job-shop Scheduling Problems

CHEN Liang, WANG Shi-jin, ZHOU Bing-hai   

  1. (School of Mechanical Engineering, Shanghai Jiaotong University, Shanghai 200240)
  • Received:1900-01-01 Revised:1900-01-01 Online:2008-01-05 Published:2008-01-05

摘要: 柔性作业车间调度问题,包括路径分配和加工排序2大子问题,是组合优化理论和实际生产管理的重要研究方向。作为传统作业车间调度的扩展,柔性作业车间调度问题的内在复杂性(强NP-Hard)使得传统的最优化方法难以有效求解。文章针对以多目标权重和最优为目标的柔性作业车间调度问题,提出基于过滤定向搜索的集成启发式算法,设计改进了节点分枝策略和局部/全局评价函数,能同时解决2大子问题。通过实例仿真,对算法性能进行比较分析和评价,结果表明了算法的可行性和有效性。

关键词: 柔性作业车间调度, 过滤定向搜索, 启发式方法

Abstract: Flexible job-shop scheduling problem, containing routing sub-problem and sequencing sub-problem, is an important issue in both fields of combinatorial optimization and production operations. Being an extension of the classical job-shop scheduling problem, it presents additional complexity(NP-hard in strong sense), which makes traditional optimization approaches difficult to achieve an optimal solution in reasonable computational time. In this paper, a filtered-beam-search based heuristic algorithm is proposed to solve the flexible job-shop scheduling problem with the objective of optimal weighted sum of multiple measure performances. The proposed algorithm makes improvement in the generation procedures of branches and the local/global evaluation functions, which makes it possible to solve two sub-problems. the performance of the proposed algorithm is evaluated and compared with those of other representative approaches through simulations, and the results demonstrate the feasibility and efficiency of the proposed algorithm.

Key words: flexible job-shop scheduling, filtered beam search, heuristic algorithm

中图分类号: