Abstract: A constraint satisfaction optimization model is established for the problem of earliness/tardiness Job Shop scheduling problem.A hybrid algorithm combined with constraint satisfaction and tabu search is proposed.Based on constraint satisfaction，an entirely feasible scheduling is obtained by constraint propogation technology and heuristic repair method and is regarded as initial solution for tabu search algorithm.Current solution is optimized by neighborhood transformation on a critical path.The final optimizal solution is improved by adopting a global neighborhood swapping strategy.The data experiments show that the hybrid algorithm is feasible and effective.

摘要： 针对提前/拖期Job Shop调度问题，建立其约束满足优化问题模型，提出了一种约束满足与禁忌搜索结合的混合算法。该算法基于约束满足思想，通过约束传播技术和启发式修复算法，得到可行调度作为禁忌搜索算法的初始解；再进行关键路径上的邻域变换，优化当前解；并采用一种全局邻域交换策略，扩大搜索空间，改善优化结果。数据实验表明了该混合算法的可行性和有效性。