含装配约束的作业调度问题及遗传解码算法  

Job-shop scheduling problem incorporating assembly constraint and its solution using genetic decoding approach

作　　者：王林平[1,2] 贾振元[1] 王福吉[1] 孟凡斌[1] 

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

出　　处：《大连理工大学学报》2010年第4期535-539,共5页Journal of Dalian University of Technology

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

摘　　要：传统上加工与装配是分开研究的,而且很少涉及作业装配问题.为此,描述了一种包含加工与装配的作业调度问题.利用FT10基准调度问题的工序数据构造了调度问题及其产品结构.初步进行了以经典作业调度问题(JSSP)为对照的研究.采用基于字符串直接解码的遗传算法,解决了染色体对应不可行调度解的问题.仿真实验验证了遗传解码算法的可行性和有效性,而且进一步表明装配约束改变了JSSP;近优值2046也优于关键路径规则算法的结果.Scheduling for fabrication and assembly operations is researched independently. So far there are relatively less scheduling studies concerning job-shop assembly operation. To solve this problem,a job-shop scheduling problem （JSSP） including both fabrication and assembly constraint operations is described. The problem instance is established on the basis of benchmark FT10 operation data. It was preliminarily investigated by contrasting it to classical JSSP. A selective decoding string was constructed to overcome the unfeasible solutions resulting from chromosomes. Simulation tests indicate that the genetic decoding approach is both feasible and effective. Furthermore,they demonstrate that the assembly constraints have made a great difference in JSSP. Moreover,a near-optimal makespan of 2 046 is obtained,which is better than the result of CP dispatching rule.

关 键 词：装配约束 加工 遗传算法 解码 作业调度问题 

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