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.

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