改进粒子群算法对钢卷混流包装线平衡问题的研究

王 强，张含叶，王 利

（1.九江学院 机械与材料工程学院，九江 332005；2.九江学院 教务处，九江 332005）

0 引言

钢卷的品种和数量随顾客需求的变化而变化，在最短的时间内，应该能最大限度地满足不同客户的个性化需求。钢卷的混流包装线能够适应多品种生产的需要，在基本不改变现有生产手段、生产条件和生产能力的前提下，通过改变生产组织方式，在一定的时间内，在同一条包装生产线上包装出不同代码的多品种钢卷产品。因此，钢卷混流包装生产线能够快速响应市场需求的变化，节约流动资金，降低成本，提高产品的竞争力。

混流包装生产线平衡问题属于NP-Hard问题[1]，采用传统的精确方法求解比较困难。随着科技的发展，许多人工智能方法被用来求解混流装配线平衡问题，例如：遗传算法[2～7]、蜂群算法[8,9]、蚁群算法[10～14]、差分进化算法[15]等。本文采用改进粒子群算法对对混流钢卷包装线平衡问题进行研究。

1 问题描述

混流钢卷包装线平衡问题可以描述为：在计划期内，在同一包装线上混合连续地包装M种系列产品的钢卷，这M种钢卷结构相似、工艺相近，每个品种钢卷的包装由若干任务组成，这些任务都有严格的顺序要求，产品包装中任务之间的关系可以用作业顺序图来描述。

图1 装配优先关系图

图1为三种产品A、B和C的装配优先关系图，因为不同品种产品的装配优先关系图之间存在差异，所以在研究混流产品装配线平衡问题时，常用的方法是将其合并为一个综合装配优先关系图，如图2所示。

图2 综合装配优先关系图

2 数学模型

2.1 变量定义

本文用到的变量及其含义如表1所示。

2.2 目标函数

其中：

w1和w2均为权重系数。

2.3 约束条件

其中，式(2)确保任一作业元素只能分配到某一工作站中；式(3)为装配优先关系约束；式(4)为节拍约束；式(5)表示变量的取值范围。

表1 变量定义

3 算法设计

3.1 基本粒子群算法

在每一代，粒子Xα的速度和位置更新公式分别为：

式(6)中右边第一项为粒子先前速度的继承；第二项为“认知”部分，是一个增强学习过程；第三项为“社会”部分，表示粒子间的信息共享与相互合作。在搜索过程中粒子一方面记忆它们自己的经验，同时考虑其同伴的经验。当单个粒子觉察同伴经验较好的时候，它将进行适应性的调整，寻求一致认知过程。

3.2 改进粒子群算法

对式(6)进行改进，改进后的粒子群算法如下：

改进粒子群算法的流程如下：

Step 1：确定参数：种群规模PS、加速常数c1和c2、权重系数w1和w2、最大迭代次数Tmax；

Step 2：产生初始种群；

Step 3：根据式(1)和约束条件(2)～(5)，计算适应度函数；

Step 5：判断是否满足终止条件（本文以迭代次数是否达到预设的代数Tmax作为终止条件），如果满足，则进入Step 6；否则，转入Step 2；

Step 6：输出最优解，算法结束。

4 实例求解

已知Z企业[16]现有的多条包装生产线均为单一品种包装生产线，由于各种产品需求量相差较大，表现在包装生产线上就是各条线有忙有闲，工作负荷分布不均，为了提高包装生产线的利用率，有必要引入混流包装生产线。通过调研发现A、B两种钢卷产品结构相似、工艺相近，因此对其混流包装生产线进行优化设计，其综合作业优先关系图和作业元素时间分别如图3和表2所示。

该企业一天的生产时间为8小时，采用两班制，即57600秒。根据需求量的要求，包装线每天至少生产产品480个。两种产品包装数量占总包装数量的比例分别为qA=2/3，qB=1/3，则初始生产节拍为C=57600/480=120秒。

[17]，将改进粒子群算法中的参数设置如下：PS=80，c1=c2=2.05，w1=10，w2=1，Tmax=100。将c1=c2=2.05代入式(10)和式(9)得：ϕ=4.1，χ=0.7298。

根据第3节中的求解流程，采用MATLAB软件对其进行编程求解，结果如表3所示。

则该钢卷混流包装线的平衡率为：

图3 产品A和产品B的综合作业优先关系图

表2 产品A和产品B的作业元素作业时间

表3 钢卷包装生产线平衡结果

由此可以看出，采用改进粒子群算法求解钢卷混流包装线平衡问题取得了较好的平衡效果。

5 结束语

针对钢卷混流包装生产线的平衡问题，以工作站数和各工作站作业时间均方差的线性组合最小化为目标函数，采用改进粒子群算法对其进行求解，结果表明改进粒子群算法可以有效地求解钢卷混流包装生产线的平衡问题。

参考文献：

[1]苑明海,李东波,于敏建.面向大规模定制的混流装配线平衡研究[J].计算机集成制造系统,2008,14(1):79-83.

[2]TANG Q H, LIANG Y L, ZHANG L P, et al. Balancing mixedmodel assembly lines with sequence-dependent tasks via hybrid genetic algorithm[J].Journal of Global Optimization, 2016,65(1):83-107.

[3]HAQ A N, RENGARAJAN K, JAYAPRAKASH J.A hybrid genetic algorithm approach to mixed-model assembly line balancing[J]. International Journal of Advanced Manufacturing Technology, 2006, 28(3-4): 337-341.

[4]TIACCI L, SAETTA S, MARTINI A. Balancing mixed-model assembly lines with parallel workstations through a genetic algorithm approach[J]. International Journal of Industrial Engineering:Theory Applications and Practice,2006,13(4):402-411.

[5]MAMUN A A, KHALED A A, ALI S M, et al. A heuristic approach for balancing mixed-model assembly line of type i using genetic algorithm[J].International Journal of Production Research,2012, 50(18): 5106-5116.

[6]YU JF, YINYH. Assembly line balancing based on an adaptive genetic algorithm[J].International journal of advanced manufacturing technology,2010,48(1-4):347-354.

[7]AKPINAR S, BAYHAN G M. A hybrid genetic algorithm for mixed model assembly line balancing problem with parallel workstations and zoning constraints[J].Engineering applications of artificial intelligence,2011,24(3): 449-457.

[8]YUAN B, ZHANG C Y, SHAO X Y, et al. An effective hybrid honey bee mating optimization algorithm for balancing mixedmodel two-sided assembly lines[J].Computers and Operations Research,2015,53:32-41.

[9]SAIF U, GUAN Z L, LIU W Q, et al. Multi-objective artificial bee colony algorithm for simultaneous sequencing and balancing of mixed model assembly line[J].International journal of advanced manufacturing technology,2014, 75(9-12):1809-1827.

[10]AKPINAR S, BAYHAN G M. Performance evaluation of ant colony optimization-based solution strategies on the mixed-model assembly line balancing problem[J].Engineering Optimization,2014,46(6):842-862.

[11]AKPINAR S, MIRAC B G, BAYKASOGLU A.Hybridizing ant colony optimization via genetic algorithm for mixed-model assembly line balancing problem with sequence dependent setup times between tasks[J].Applied Soft Computing Journal, 2013,13(1):574-589.

[12]YAGMAHAN B.Mixed-model assembly line balancing using a multi-objective ant colony optimization approach[J].Expert Systems with Applications. 2011, 38(10):12453-12461.

[13]ZHANG Z Q,CHENG W M,ZHONG B, et al. Hybrid behavior ant colony optimization for mixed-model assembly line balancing problem[J].Journal of Mechanical Engineering,2009,45(5):95-101.

[14]Blum C. Beam-ACO for Simple Assembly Line Balancing[J].Informs journal on computing, 2008, 20(4): 618-627.

[15]ZHANG X M, HAN X C. The Balance Problem Solving of the Car Mixed-model Assembly Line Based on Improved Differential Evolution Algorithm[J].Applied Mechanics and Materials, 2012(220-223):178-183.

[16]刘海江.宝发展钢产品包装工艺技术报告[R].上海:同济大学现代制造技术研究所,2012.

[17]段晓东,王存睿,刘向东.粒子群算法及其应用[M].沈阳:辽宁大学出版社,2007.