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

摘要

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