中文摘要：

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

英文摘要：

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 enumera- tion 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.