Abstract:

For the job shop scheduling problem with processing time variability, a conservative and robust Minimax analysis method was proposed to estimate the worst scenario and its corresponding bound of scheduling performance indicator. A Minimax model was formulated based on the earli E/T penalty cost of each job. To solve the huge search space problem of traditional traversal or enumeration methods, a convex function theorem was proposed and proved, which can constrict and filter the processing time ranges effectively for a given scheduling sequence, and a kind of job processing times filtering mechanism was proposed based on this convex function theorem. Based on the feature of two space optimization in solving Minimax problem, a two space co-evolutionary genetic algorithm was designed with the consideration of the alternate evolutions between scheduling sequence population and processing time population. Finally, the test results demonstrate that both of the proposed filtering mechanism and two space co-evolutionary algorithm perform effectively.

Key words: job shop scheduling, processing time variability, earliness/tardiness(E/T), Minimax, two space co-evolution

摘要：

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

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