一种求解作业车间JIT调度问题的混合TS/MP算法

A Hybrid Algorithm for Just-in-time Job-shop Scheduling Problem Based on TS/MP

作业车间JIT调度属于一类典型的非正规性能指标调度问题,该类问题为每道工序设置了交货期约束,工序的提前或拖期完工均会产生相应的惩罚成本。采用禁忌搜索和数学规划相结合的混合调度方法进行求解。在算法的迭代搜索过程中,首先,由每个个体产生各机器上的工件加工序列,由此松弛了调度模型中的机器能力析取约束,然后,调用数学规划方法来优化各机器的空闲时间和各工序的开工时间。为提高禁忌搜索算法的计算效率,设计了一种包含交换和插入操作的邻域结构产生方案。最后,用JIT调度领域的32个标准测试算例验证了该调度算法的有效性。

A hybrid algorithm based on Tabu Search （TS） and Mathematical Programming （MP） for Just-in-time Job-shop Scheduling Problem （JIT-JSP） is introduced in this paper, in which each operation has an earliness and a tardiness cost with respect to its due date and the objective is to find a feasible scheduling minimizing the total earli- ness and tardiness costs. During search process, any individual offers the sequence orders in which the operations should be scheduled to the machines, and then MP method optimizes the completion times of the operations for the generated sequences. In order to reduce computational time, we introduce an excellent neighborhood structure based on swap and insertion operator. The experimental results finally demonstrate the effectiveness of the proposed hybrid algorithm over a wide range of benchmarks.