Job Shop 调度问题的 Minimax 模型及双空间协同遗传算法

摘要：

针对工序加工时间不确定环境下的 Job Shop 调度问题，为了预估最差调度工况及其对应的调度性能指标边界，采用一类保守、稳健的 Minimax 分析方法，建立了基于提前/拖期惩罚成本的 Min-imax 调度模型；为了解决传统基于遍历或枚举方法存在的搜索空间巨大的问题，提出并证明了给定调度顺序条件下，关于内层 Max 优化过程的凸函数定理，并依此定理提出了一种工序加工时间搜索空间过滤机制。针对 Minimax 调度问题存在的双空间寻优特性，在分析调度顺序种群和工序加工时间种群的交替进化机制的基础上，设计了一种高效的双空间协同遗传算法。最后通过仿真算例验证了该过滤机制和双空间协同遗传算法的有效性。

关键词：作业车间调度、工序加工时间不确定、提前/拖期、Minimax、双空间协同进化

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目50705076;西北工业大学研究生创业种子基金资助项目Z2013047

在线出版日期：2015-03-06（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：330-338