计算机工程与应用 ›› 2007, Vol. 43 ›› Issue (19): 7-9.

• 博士论坛 • 上一篇    下一篇

基于约束传播的HFS调度研究

孙 玲,李铁克   

  1. 北京科技大学 管理学院,北京 100083
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2007-07-01 发布日期:2007-07-01
  • 通讯作者: 孙 玲

Algorithm for Hybrid Flow shop Scheduling based constraint propagation

SUN Ling,LI Tie-ke   

  1. Management School,University of Science and Technology Beijing,Beijing 100083,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2007-07-01 Published:2007-07-01
  • Contact: SUN Ling

摘要: 将约束传播技术同分枝定界法相结合求解优化目标为最小最大完工时间的混合流水车间调度问题。算法核心是根据资源松弛度确定关键阶段,通过在分枝定界算法中嵌入动态可调的开工时间窗口,用顺序传播、资源传播、上下游工序传播,动态修改每个操作的开工时间窗上下界,并在算法特点基础上给出相应的剪枝下界,以减小搜索空间,提高分枝定界法的优化能力。实验结果证明了算法的有效性。

Abstract: Proposes a hybrid algorithm that integrates constraint propagation technique and branch and bound algorithm to solve the hybrid flow shop scheduling problem.The critical stage is selected by the resource slack.Dynamicly adjusts the time window of each activity by embedding the time window and using constraint propagation in branch and bound.The lower bound is proposed to cut the search space and improve the optimization performance of branch and bound.Experiments show that the algorithm is promising.