双边多工位装配线平衡的应用研究

【摘要】为克服传统算法求解效率和求解质量低的缺陷，针对装配线每个工作站左右两边各有多个工位的装配线平衡问题，提出一种基于可行作业序列的遗传算法，既保留了传统GA 的并行和随机搜索能力， 同时又只在可行解子空间进行搜索，这样可提高算法运算效率和计算结果的精度。

【关键词】装配线平衡 双边装配线 多工位 遗传算法

一、引言

装配线平衡问题（Assembly Line Balancing Problem，ALBP）源于装配线平衡能够提高劳动生产率、缩短生产时间、降低生产成本、提高生产稳定性、减少在制品数量等诸多优点，多年来装配线平衡技术一直受到人们的重视，尤其在我国，由于装配线不平衡引起的效率低下、成本浪费现象十分严重，装配线平衡在企业拥有很大的发展潜力和空间。

装配线可以分为单边装配线和双边装配线，双边装配线广泛应用于装载机、重型卡车、风力发电机等大中型产品的装配过程中，与单边装配线相比，具有缩短装配线长度、降低产品的生产周期、减少原材料运输与工人移动成本、降低工具和夹具费用等优点，能产生明显的经济效益。随着双边装配线的广泛应用，双边装配线平衡问题（two-sided assembly lines balancing problem，TALBP）也随之产生。因双边装配线布置方式的变化，在分配任务时，除需满足操作方位的要求，还需综合考虑同一工作站内不同工位的前序作业对后序作业开始时间的影响。因此，TALBP较单边装配线平衡问题更为复杂。

近年来，运用智能优化算法求解TALBP 成为一个重要趋势。文献提出了一种求解TALBP的遗传算法；文献提出了TALBP的一种基于任务序列的改进遗传算法；文献提出了求解TALBP的禁忌搜索算法；文献提出了一种蜂群算法求解带区域约束的TALBP；文献针对第Ⅰ类TALBP，提出了一种先产生任务排列序列、后按启发式分配规则产生可行解的蚁群算法。

以上TALBP的研究只是针对装配线一个工作站左右两边各有一个工位的情况，而实际上装配线上的每一个工作站往往有多个工位，如在重型汽车装配线上，一个车位（相当于工作站）一般有4～6个工位。本文提出一种基于可行作业序列的遗传算法（Genetic Algorithm，GA），它既保留了传统GA 的并行和随机搜索能力， 同时又只在可行解子空间进行搜索，并且所有可行作业序列都有可能被搜索到，这样可提高算法运算效率和计算结果的精度。本文通过双边多工位装配线平衡问题的实例对该算法进行了对比验证，表明了算法的有效性。

二 、改进遗传算法

给定装配线的生产节拍，通过作业序列来寻找最少的工作站数和工位数，适合采用GA。作业序列可直接用于GA编码，一个作业序列就对应一条染色体。作业序列也可以直接进行交叉和变异操作。装配线平衡问题本身是一个NP-Hard 问题，采用GA 可以充分发挥其并行和随机搜索能力，能够较快地找到较优解。

本文提出的基于可行作业序列的GA，依据作业顺序图生成初始群体和构造GA，保证GA搜索的所有作业序列及对应的单元作业分配方案都是可行的，并且保证所有可行作业序列都有可能被搜索到，进一步提高了算法运算效率和计算结果的精度。首先，生成可行作业序列作为初始群体，并将初始群体作为父群体；然后对父群体中的各个个体进行评价和选择，并对被选中的个体进行交叉和变异操作，生成下一代群体；最后，将下一代群体作为父群体，并重复上述过程至满足终止条件。它将输出整个搜索过程中目标函数值最大的个体作为最优解。

三、实例验证

文献[6]运用启发式算法求得的初始解结果为启用6个工作站和17个工位，经过重新调整后减少了一个工位，即启用6个工作站和16个工位；而本文的求解结果为启用5个工作站和16个工位，结果优于文献[6]的求解结果，且不需要二次调整。结果表明，本文采用的遗传算法在求解效率和求解质量上更优。

四、结论

本文针对装配线每个工作站左右两边各有多个工位的情况，即双边多工位装配线平衡问题进行了研究，提出一种改进的遗传算法，既保留了传统GA 的并行和随机搜索能力， 同时又只在可行解子空间进行搜索，并且所有可行作业序列都有可能被搜索到，这样可提高算法运算效率和计算结果的精度。通过实例与传统算法进行对比验证，表明了算法的优越性。

参考文献：

[1]KIM Y K， SONG W S， KIM J H. A mathematical model and a genetic algorithm for two-sided assembly line balancing [J].Computers & Operations Research， 2009，36（3）.

[2]WU Erfei， JIN Ye， XU Aimin， etc. Two-sided assembly line balancing based on modified genetic algorithm [J].Computer Integrated Manufacturing Systems，2007，13（2）.

[3]金烨，续爱民等.基于改进遗传算法的双边装配线平衡[J].计算机集成制造系统，2007，13（2）.

[4]ZCAN U， TOKLU B. A tabu search algorithm for two-sided assembly line balancing[J].The International Journal of Advanced Manufacturing Technology，2009，43（7 /8）.

[5]ZBAKIR L，TAPKAN P. Bee colony intelligence in zone constrained two-sided assembly line balancing problem [J].Expert Systems with Applications，2011，38（9）：11947-11957.

[6]张则强，胡俊逸，程文明.第Ⅰ类双边装配线平衡问题的改进蚁群算法[J].西南交通大学学报，2013，48（4）.

[7]张宏林，殷复鹏，吴爱华.双边多工位装配线平衡问题[J].计算机集成制造系统，2013，19（2）.