综合作业调度问题基于可行域的遗传算法  

Solving complete job shop scheduling problem using genetic algorithm in feasible domain

作　　者：王林平[1,2] 贾振元[1] 王福吉[1] 赵国凯[1] 

机构地区：[1]大连理工大学精密与特种加工教育部重点实验室,辽宁大连116024 [2]烟台大学机电汽车工程学院,山东烟台264005

出　　处：《大连理工大学学报》2011年第2期205-209,共5页Journal of Dalian University of Technology

基　　金："八六三"国家高技术研究发展计划资助项目(2003AA414022)

摘　　要：综合作业调度问题(CJSSP)同时考虑了加工约束与装配约束,成为约束严调度问题,而现有求解JSSP的遗传算法不能保证约束严问题染色体的可行性.描述了基本CJSSP,在定义的装配体分类和可操作基因串两个关键概念的基础上,设计出了基于可行域的交叉和变异方法.采用改编自JSSP的基准问题和实际调度问题进行了算法测试,并与规则算法的结果进行了比较,表明设计的遗传算法是可行和有效的.The complete job shop scheduling problem（CJSSP） considers machining and assembly constraints simultaneously and becomes tight-constraint problem.The existing genetic algorithms developed for JSSP can not maintain chromosome′s feasibility of this tight-constrained problem.The basic CJSSP is described.Two key concepts,constituent type and operable gene string,are defined and then applied to building crossover and mutation operation in the feasible domain.The genetic algorithm is tested in both practical instances and problems adapted from JSSP benchmarks.The computation result is compared with that of some heuristics and it is demonstrated that the proposed algorithm is both feasible and efficient.

关 键 词：综合作业调度问题 可行域 遗传算法 装配体分类 可操作基因串 

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