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

Minimax model and Two Space Co-evolutionary Genetic Algorithm for Job Shop Scheduling Problem

作　　者：杨宏安[1] 席志成[1] 夏常凯 王经国[1] 

机构地区：[1]西北工业大学现代设计与集成制造教育部重点实验室,西安710072

出　　处：《中国机械工程》2015年第3期330-338,共9页China Mechanical Engineering

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

摘　　要：针对工序加工时间不确定环境下的Job Shop调度问题,为了预估最差调度工况及其对应的调度性能指标边界,采用一类保守、稳健的Minimax分析方法,建立了基于提前/拖期惩罚成本的Minimax调度模型;为了解决传统基于遍历或枚举方法存在的搜索空间巨大的问题,提出并证明了给定调度顺序条件下,关于内层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.

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]