基于可行作业序列的遗传算法求解第二类装配线平衡问题.pdf

39 7 上 海 交 通 大 学 学 报 V ol. 39 N o . 7 2005 7 J O U RN A L O F SHA N GHA I J IA O T O NG U N IV ERSIT Y J ul. 2005 : 1006-24 67( 2005 07-1123-05 皮兴忠, 　范秀敏, 　严隽琪 ( , 200030 : 从作业顺序图出发, 定义了作业的序关系. 此为基础, 分析了工位数固定时作业序列与 最小节拍的对应关系, 并针对第二类装配线平衡问题, 提出一种基于可行作业序列的遗传算法. 该 算法直接依据作业顺序图生成初始群体, 并构造交叉和变异算子; 初始群体和交叉变异的结果都是 可行解, 从而保证只在可行作业序列子空间中进行最优解搜索, 效率较高; 在染色体的适应值定义 中还考虑了最小节拍时间和工位工时标准差的综合影响, 可用来比较最小节拍时间相同的不同作 业分配方案间优劣, 提高了解的可信度. 应用该算法, 对一实例进行了多种工位数的验证, 结果较 优. : 装配线平衡; 遗传算法; 单元作业; 可行作业序列 : T H 391. 9 : A Applying t he Genet ic Algorit hm Based on 2 Feasible Task Sequence to ALB - , - , - PI X ing z hong FA N X iu m in YA N J un qi ( Inst . of Com put er Int egrat ed Manuf act uring , Shanghai Jiaot ong Univ. , Shanghai 200030, China Abstract: A cco rding t o t ask sequence diagr am , t his paper def ined sequence oper at ions bet w een diff erent t asks. A nd t he relationship bet w een t he t ask sequence and t he minim al cycl e tim e w as present ed w hile w orkpl ace number is given . T hen a genet ic alg orit hm based o n f easible t ask sequence w as developed fo r t he seco nd t ype of assem bly line balancing ( A L B2 problem. T he init ial po pulat io n, cro ssover operato r and mut ation operato r in t he algorit hm are all const ruct ed f rom t he t ask sequence diag ram. A l l sol ut ions in t he init ial population or resul ts of cro sso ver and mutat ion operat ions are feasible. Fo r t he algo rithm o nly hunt s t he o pt imal solut