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

从作业顺序图出发，定义了作业的序关系．以此为基础，分析了工位数固定时作业序列与最小节拍的对应关系，并针对第二类装配线平衡问题，提出一种基于可行作业序列的遗传算法．该算法直接依据作业顺序图生成初始群体，并构造交叉和变异算子；初始群体和交叉变异的结果都是可行解，从而保证只在可行作业序列子空间中进行最优解搜索，效率较高；在染色体的适应值定义中还考虑了最小节拍时间和工位工时标准差的综合影响，可用来比较最小节拍时间相同的不同作业分配方案间优劣，提高了解的可信度．应用该算法，对一实例进行了多种工位数的验证，结果较优．

Applying the Genetic Algorithm Based on Feasible Task Sequence to ALB2

According to task sequence diagram, this paper defined sequence operations between different tasks. And the relationship between the task sequence and the minimal cycle time was presented while workplace number is given. Then a genetic algorithm based on feasible task sequence was developed for the second type of assembly line balancing (ALB_2) problem. The initial population, crossover operator and mutation operator in the algorithm are all constructed from the task sequence diagram. All solutions in the initial population or results of crossover and mutation operations are feasible. For the algorithm only hunts the optimal solution in the subspace of feasible solutions, it is high efficient. At the same time, it took into account the mixed effect of minimal cycle time and the standard deviation of workplaces' time to compare different task distribution solutions, even if their minimal cycle time is equal. So the result will be more credible. At last a case study was given for the algorithm, and the result is satisfactory.