Abstract:

An algorithm based on CA was proposed to solve  ALBP-Ⅱ problem,which minimized the production cycle time of assembly line for a given number of stations.The assembly line balancing problem can be divided into 3 parts:work station,task and task assignment rule.From the viewpoint of CA,work station was regarded as fixed grid node,task as moving particle,the mechanism of balancing assembly line as the evolution rule which included shift rule and swap rule.This paper also designed the rules of the execution conditions and the whole algorithm procedure.The results obtained by solving benchmark problems prove the feasibility of the algorithm,the comparison between results herein and those from related literature reveals that the proposed algorithm gets results with smaller relative error and has more chances to get optimal solution.

Key words: assembly line balancing, assembly line balancing problem of type Ⅱ(ALBP-Ⅱ), cellular automata(CA), evolution rule

摘要：

针对第Ⅱ类装配线平衡问题的特点,给出其数学描述,并提出了一种基于元胞自动机的动态仿真求解算法。将实际装配线平衡问题抽象成由操作、工位及操作分配规则构成的系统,定义工位为模型网络空间的固定格点,操作为移动粒子,平衡装配线的方式为状态演化规则，并细分为转移规则和交换规则;同时设计规则的执行条件以及算法的总流程。标杆问题的求解结果证明了该算法的可行性，与相关文献的比对试验说明该算法得到最优解的几率更大，所求解的相对误差更小，算法性能更优。



关键词: 装配线平衡, 第Ⅱ类装配线平衡问题, 元胞自动机, 演化规则