Abstract: Aiming at the complex informal performance index scheduling problem such as Just-In-Time Job-shop Scheduling Problem(JIT-JSP),a hybrid scheduling algorithm of Variable Neighborhood Search(VNS)and Mathematical Programming(MP)based on two-stage optimization strategy was proposed.In each iteration procedure of VNS,the better machine process sequence was obtained by searching between the two neighborhoods of Swap and Insertion.The MP method was used to optimize each procedure's start time in machine process sequence.To impose more diversification,the local search was developed as a threshold accepting method based on two mentioned neighborhood structures.Computational results on 72 benchmark JIT scheduling problems showed that the VNS/MP algorithm could find the best known solution for 35 problems,and the best known solutions for 25 problems were updated.

Key words: Job-shop, just-in-time scheduling, variable neighborhood search, mathematical programming, neighborhood structure

摘要： 针对作业车间准时制调度这类复杂的非正规性能指标调度问题,基于机器加工序列和工序开工时间的两阶段优化策略,提出一种结合变邻域搜索和数学规划的混合调度算法。在变领域搜索的每次迭代过程中,通过在Swap和Insertion两类邻域结构内跳转搜索获得较优的机器加工序列,由此松弛了调度模型中最难满足的机器析取约束;然后调用数学规划方法对当前机器加工序列上的各工序开工时间进行优化计算。以引导工序向各自交货期靠拢为邻域设计原则,提出以紧邻工序对为移动对象的Swap和Insertion邻域结构;为增加搜索空间的多样性,变领域搜索中的局域搜索算法采用基于调度目标值容许偏差的阈值接受策略。对72个准时制调度的Benchmark算例的仿真结果表明,变领域搜索/数学规划混合算法获得了35个算例的已知最好解,并且更新了其中25个算例的已知最好解。

关键词: 作业车间, 准时制调度, 变邻域搜索, 数学规划, 邻域结构