混合离散粒子群算法在混流装配线生产调度中的应用

周康渠，赵慧真

(重庆理工大学 机械工程学院，重庆 400054)



混合离散粒子群算法在混流装配线生产调度中的应用

周康渠，赵慧真

(重庆理工大学 机械工程学院，重庆 400054)

为使混流装配线有效运作，研究了混流装配线的生产调度问题。以最小化最大完工时间为优化目标，建立了调度模型。针对算法中存在的“早熟”现象，提出了一种与基于NEH方法的领域搜索策略结合的混合离散粒子群算法，并通过实例验证了算法的有效性。经与其他算法比较后发现：混合离散粒子群算法在求解摩托车混流装配线生产调度问题上具有优势，能快速搜索到最优解，具有较好的收敛性。

混合离散粒子群算法；混流装配线；生产调度

混流装配线可以在基本不改变生产组织方式的前提下，同时生产出多种不同型号、不同数量的产品，是应对大规模定制生产的一种有效的组织方式[1]。目前，为满足顾客的多样化和个性化需求，我国的摩托车企业采用按订单生产(MTO)方式。订单多品种、小批量的特点决定企业必须采用混流装配线组织生产，增加了生产调度的难度。混流装配线的生产调度合理与否直接影响企业的生产效率，本文对混流装配线的生产调度问题进行研究。

混流装配线的成功应用得到了企业界和学术界的极大关注，混流装配线的生产调度问题也成为研究热点。文献[2]对混流装配线生产调度问题的研究现状进行了综述，指出了启发式算法的缺陷；文献[3]分析了混流装配线生产调度问题的几种优化目标，并对最优解算法、试探算法、循环改进算法进行了对比研究；文献[4]建立了JIT环境下以混流装配线停线时间最小为调度优化目标的数学模型；文献[5]建立了以零部件使用速率均匀化为调度优化目标的单级混流装配线生产调度模型，并尝试用目标追随法求解。总的来说，混流生产线调度问题考虑的优化目标主要有作业域负荷均衡化[6-7]、零部件使用速率均匀化[8-9]、最小更换工装夹具次数[10-11]、流水线最短停线时间等[12-13]。混流装配线的生产调度问题是组合优化问题，是一类典型的NP难题，目前有很多种方法来研究这个问题，如最优解算法、启发式算法、智能优化算法、混合算法等。由于各种算法本身的局限性，出现了很多混合、改进的算法。本文主要研究混合离散粒子群算法在混流装配线生产调度中的应用，并与其他算法进行比较。

1 粒子群算法

粒子群优化算法(PSO)是一种有效的全局寻优算法，最早由美国的Kenedy和Eberhart于1995年提出，设想模拟鸟群觅食的过程，后来从这种模型中得到启示，并将粒子群算法用于解决优化问题。该算法保留了种群的全局搜索策略，避免了复杂的遗传操作，具有不依赖问题信息、通用性强、原理简单、易于实现等优点。同时，粒子群算法具有较强的扩展性，容易与其他算法结合，将其进行离散化适合于求解混流装配线的生产高度问题。

粒子群算法把每一个优化问题的解看作是搜索空间中的一只鸟，即“粒子”。首先生成初始种群，即在可行解空间中随机初始化一群粒子，每个粒子都为优化问题的一个可行解，并由目标函数评价其适应度值。每个粒子都在解空间中运动，并由一个速度决定其飞行方向和距离，通常粒子追随当前的最优粒子在解空间中进行搜索。每经一次迭代，粒子将跟踪2个“极值”来更新自己，一个是粒子本身找到的最优解，另一个是整个种群当下找到的最优解，即为全局最优解[14]。

2 混流装配线生产调度模型

摩托车混流装配线的生产调度问题属于一种典型的PFSP问题，可以描述为：n辆摩托车在m个工位上进行装配，确定车辆的排产顺序，使某项调度性能最优。如果不同型号的产品之间具有很高的工艺相似性，则可将问题简化为单级混流调度问题。为简化运算，模型只考虑一个MPS内待装配产品的优化。为应对市场竞争，摩托车生产企业应尽可能提高生产率，缩短生产时间，减少交货延迟，因此，最大完工时间是摩托车装配车间必须考虑的一项重要优化指标之一，其计算公式如下：

(1)

(2)

(3)

(4)

其中：n为一个MPS内生产的摩托车数；m为摩托车混流装配线的工位数；cmax为最大完工时间，即最后一辆摩托车在最后一个工位完成装配的时间；ci,j为摩托车i在工位j上的装配时间；c为摩托车混流装配线的生产节拍；ti,j为摩托车i在工位j上的装配时间。

在以上公式基础上，增加以下新的变量：

k:一个MPS中摩托车的位置编号，k=1,2,…,n；

u：一个MPS中生产的车型数，u=1,2,…,U；

du：一个MPS中待生产u型车的数量；

令决策变量为

最大完工时间计算逻辑图如图1所示。

图1 最大完工时间计算逻辑图

图1中，Q(n)表示摩托车一个生产序列Q(1,2,…,n) 中第n个产品。 则摩托车混流装配线的最小化最大完工时间调度模型如下：

目标函数为

(5)

约束条件为：

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

目标函数(5)保证最大完工时间最小；约束条件(6)和(7)保证在生产循环中各摩托车出现并且只能出现一次；约束条件(8)为第一辆车在首个工位上的装配完成时间；约束条件(9)和(10)保证每辆车不能同时在多个工位上装配且每个工位在某个时刻仅装配一辆车；约束条件(11)表示在一次生产循环中所有车型的数量和等于摩托车总数；约束条件(12)限定所有工位的装配完成时间均大于零；约束条件(13)为决策变量的取值范围。

3 混合离散粒子群算法在混流装配线中的应用

3.1 混合离散离子群算法设计

一般粒子群算法多用于求解连续最优化问题，而生产调度属于离散性问题，必须将其进行离散化，建立粒子群的位置向量与摩托车混流装配线的调度排序方案之间的映射关系。本文将摩托车排队序列作为粒子群的位置矢量，利用遗传算法的交叉和变异操作实现粒子群的位置更新，通过一种混合离散粒子群算法(HDPSO)进行求解，最后得到最优的生产调度方案。

1) 解的表达

解的表达是设计和操作粒子群算法的关键，决定了算法的复杂程度和解的质量。本文采用基于车型的实数编码，即用数字1，2，3分别表示车型u1，u2，u3。粒子的每一维分量表示一辆在制摩托车，一个粒子矢量代表一个车辆队列。

2) 基于NEH算法的初始解改造

初始解的好坏和分散度决定着混合离散粒子群算法的搜索效率。NEH算法是解决PFSP问题最有效的启发式方法之一，常被用于群体搜索的初始化。本文首先采用NEH算法产生一个或多个初始粒子，其余粒子随机产生，从而实现快速收敛。

NEH算法的流程如下：

② 根据总加工时间TTi非递增的顺序排列，计算得到一个初始化的序列：Q0={Q0(1),Q0(2),…,Q0(n)}；

③ 取出Q0的前两辆车Q0(1)，Q0(2)，将其排序得：{Q0(1),Q0(2)}、{Q0(2)，Q0(1)}，得出最大完工时间最小的作为当前调度，记为Q={Q(1),Q(2)}；

④ 令i=3，取出Q0的第三辆车，将其插入Q所有可能的位置，可得到i个部分排列的调度，得出最大完工时间最小的一个作为当前调度；

⑤ 令i=i+1，如果i≤n，重复④，直到所有辆车全部取出，输出最大完工时间最小的调度方案，作为NEH算法的最优解。

3) 粒子群的位置更新

由于标准粒子群算法在迭代时受当前速度、自身认知和社会认知的影响，加之粒子群算法的速度和位置更新策略无法直接用于摩托车混流装配线调度问题中，因此本文借鉴遗传算法中的交叉和变异操作，通过粒子当前位置与个体极值或群体极值之间的交叉实现更新迭代，完成进化搜索。

4) 局部搜索策略

一些研究表明，粒子群算法有很好的并行性和全局粗搜索能力，收敛速度快，但在实验中发现其在计算过程中，局部精搜索能力较弱，使得算法不能向最优解方向进化，在进化后期易陷入“早熟”现象。基于NEH方法的领域搜索以种群最优值gBk作为操作对象，根据NEH算法原理，有较高的局部开发能力，可以平衡粒子群算法的收敛性和搜索精度，其基本步骤如下：

① 取gBk为初始序列，记为Q0={Q0(1),Q0(2),…,Q0(n)}；

② 取出Q0的前两辆车Q0(1),Q0(2)，将其排序得{Q0(1),Q0(2)}、{Q0(2)，Q0(1)}，得出最大完工时间最小的作为当前调度，记为Q={Q(1),Q(2)}；

③ 令i=3，取出Q0的第三辆车，将其插入Q所有可能的位置，可得到i个部分排列的调度，评价各个调度方案，将最大完工时间最小的一个作为当前调度；

④ 令i=i+1，如果i≤n，重复③，直至所有辆摩托车全部取出，输出最大完工时间最小的调度方案，更新gBk。

综上所述，解决摩托车混流装配线最小完工时间生产调度的混合离散粒子群算法的流程如下：

① 设置混合离散粒子群算法参数：种群规模SwarmSize、粒子维数ParticleSize、运行时间trun、惯性权重ω和学习因子c1，c2；

② 对粒子群进行初始化，采用NEH算法产生一个初始序列，其余粒子随机产生；

③ 计算每辆车排列的最大完工时间，作为每个粒子的适应度值；

④ 根据每个粒子的适应度值更新个体最佳位置pBk和种群最佳位置gBk；

⑤ 更新粒子群的位置矢量；

⑥ 对种群最佳位置gBk执行基于NEH方法的局部搜索策略，更新gBk值；

⑦ 判断是否满足迭代终止条件(达到预设的迭代次数或在一定的迭代次数中未发现更好的解)。若是，则输出最优解gB；若不是，则返回③；

混合离散粒子群算法的流程如图2所示。

图2 混合离散离子粒算法流程

3.2 实例计算及分析

为验证混合离散粒子群算法解决混流装配线调度问题的有效性和实用性，通过下面的实例进行验证。实例数据采集来源于某摩托车企业，由于摩托车装配工艺较复杂，现简化其工艺，只就主要车型及其关键工序来考虑。采用Matlab R2012b进行算例相关计算。

本算例需要验证两部分：一是调度模型的有效性；二是本文提出的基于NEH的局部搜索策略的HDPSO算法的有效性。采用Taillard测试基准进行验证。

3.2.1 调度模型的有效性

某摩托车混流装配线的生产节拍c为140 s，有3种主要车型u1，u2，u3待进行生产，一个MPS中3种车型的个数如表1所示。摩托车装配线有10个工位，各个车型在各工位的装配时间矩阵如表2所示。

表1 MPS构成

表2 装配时间矩阵

实验时，设置HDPSO算法的参数分别为：种群规模SwarmSize=20；粒子维数ParticleSize=n(n为车辆数)；运行时间trun=10*n*m(ms)；惯性权重ω=0.8；学习因子c1=c2=0.5。经运行得到的最优解为2 974 s，对应的摩托混流装配线车排产序列为：112312233112。

3.2.2 混合离散粒子群算法的有效性

选取12组不同规模(即n·m)的Taillard PFSP问题作为测试基础，其规模分别为：20×5，20×10，20×20，50×5，50×10，50×20，100×5，100×10，100×20，200×10，200×20和500×20。对各算法不同规模下的算例均运行5次，分别得出其平均偏差和均方差，并给出各算法不同规模下的算例的不同指标值。

定义相对偏差(average relative deviation，ARD)：

(14)

其中：N为运行次数，本例中取N=5；S为算例集合，根据规模不同共有12组；Bi,j为第j次运算时，算例i的最优解；Bi为算例i的最优解。ARD表示计算所得最优解与已知最优解的相对偏离程度。ARD的值越小，表明所得最优解越接近已知最优解。当ARD=0时，表示所得最优解与已知最优解一致。

1) 算法设置及其性能比较

粒子群算法中粒子更新位置的方法有插入、互换、逆序3种变异操作和单点交叉、两点交叉、次序交叉、单点相似工件交叉及两点相似工件交叉5种交叉操作，一共有15种不同的HDPSO算法。对这15个组合算法采用Taillard算例进行仿真实验，并计算其平均偏差，结果如表3所示。通过表3可以得出以下结论：

① HDPSO1～HDPSO15相对于NEH算法，ARD性能在一定程度上均有所改善，证明HDPSO算法在解决生产调度问题的有效性。

② 3种变异操作中逆序变异最优，插入变异次之，互换变异最差。

③ 交叉操作中两点交叉优于单点交叉，两点相似工件交叉优于单点相似工件交叉，次序交叉性能最差。

④ 从总体来看，HDPSO15得到了最小的平均相对偏差，说明其性能最优。

⑤ 从数据分析结果可以看出，不同的位置更新方式对HDPSO算法的性能影响较大，因此，设计最优的粒子群位置更新方式可提升HDPSO算法的性能。

2) HDPSO与其他算法的比较

为了验证HDPSO算法在求解摩托车混流装配线调度问题上的有效性，将其与模拟退火算法(simulated annealing，SA)、禁忌搜索算法(taboo search，TS)、贪婪算法(greedy algorithm，GrA)、蚁群算法(ant colony optimization，ACO)和遗传算法进行比较，计算其平均偏差，结果如表4所示。对比表3和表4，得出如下结论：

① HDPSO2，HDPSO5，HDPSO7，HDPSO12，HDPSO14的性能略优于GA，与SA，TS，GrA和ACO相比，均优于所选的对比算法；

② HDPSO1，HDPSO4，HDPSO10，HDPSO11，HDPSO14的平均相对偏差GA稍大，但优于SA，TS，GrA和ACO；

③ 平均偏差最大的HDPSO(2.971%)也优于ACO(3.005%)，SA(3.295%)和GrA(3.409%)算法；

④ 综上，对于摩托车混流装配线调度问题，HDPSO是一种有效的优化算法，其性能明显优于ACO，SA，GrA算法。

表3 HDPSO算法的性能比较

表4 各算法的性能比较

3) 初始化方法对算法性能的影响

以性能最优的HDPSO15算法为例，分析初始化方法对HDPSO算法性能的影响。在HDPSO15算法中，用NEH方法产生初始粒子，其余粒子随机产生。同时，设计一个对比算法HDPSO15C，初始粒子随机产生。通过在相同的仿真环境下设置相同的实验参数、测试算例和运行时间，记录最大偏差MAX和最小偏差MIN并按式(14)计算其平均偏差，结果如表5所示。从数据可看出：HDPSO15的各项性能优于HDPSO15C，说明NEH方法对部分初始解改造策略的有效性。随着运算时间的增加，算法的优越性逐渐减弱，初始化方法对执行后期的影响越来越小。考虑到摩托车混流装配线生产调度的实时性特点，基于NEH方法的初始化策略能较好地满足实际生产调度的需求。

表5 初始化方法对算法性能的影响

4) 局部搜索策略对算法性能的影响

在HDPSO15中采用NEH领域搜索方法对种群最优值进行更新，对比算法HDPSO15U对种群最优值不作处理。采用相同的仿真环境、实验参数、测试算例和运行时间，记录最大偏差MAX和最小偏差MIN并按式(14)计算得平均偏差，结果如表6。从表6中数据可看出：HDPSO15的各项性能均优于对比算法，具有较小的相对偏差，说明基于NEH算法的局部搜索策略具有较好的有效性。

表6 局部搜索策略对算法性能的影响

4 结束语

本文通过分析摩托车混流装配线生产调度问题的优化目标和约束条件，建立以最小化最大完工时间为优化目标的数学模型。在此基础上，设计了一种混合离散粒子群算法HDPSO，对初始化方法、粒子位置更新和局部搜索策略进行了设计。HDPSO算法是在粒子群算法的基础上设计的，粒子群算法自身具有较好的全局搜索能力，可避免局部最优。然后通过对种群最佳位置执行基于NEH方法的局部搜索策略，使HDPSO算法在局部搜索中具有优势，平衡了粒子群算法的收敛性和搜索能力，避免了“早熟”现象。仿真实验的结果表明：该算法在求解摩托车混流装配线最小完工时间调度问题时具有较强的优势，能快速搜索到最优解，具有较好的收敛性，是解决混流装配线优化调度问题的一种理想方法。

[1] 邵新宇,饶运清.制造系统运行优化理论与方法[M].北京：科学出版社,2010:91-93.

[2] KUBIAK W.Minimizing variation of production rates in just-in-time systems:a survey [J].European Journal of Operational Research,1993,66(3):259-271.

[3] 赵晓波,周兆英.混合车型组装线的投入顺序问题[J].中国机械工程,1998,9(3):28-31.

[4] ZHAO X B,KATSUHISA O.Algorithms for sequencing mixed models on an assembly line in a JIT production system[J].Computers and Industry Engineering,1997,32(1):47-56.

[5] LEU Y,MATHESON L A,RESS L P.Sequencing mixed model assembly lines with genetic algorithms [J].Computers & Industry Engineering,1996,30(4):1027-1036.

[6] BOYSEN N,FLIEDNERB.Review and comparison of three methods for the solution of the car sequencing problem [J].Journal of the Operational Research,2006,57:1497-1498.

[7] SCHOLL A,KLEIN R.Pattern based vocabulary building for effectively sequencing mixed-model assembly lines [J].Journal of Heuristics,1998(4):359-381.

[8] SCHOLL A,KLEIN R.Pattern based vocabulary building for effectively sequencing mixed-model assembly lines [J].Journal of Heuristics.1998(4):359-381.

[9] MILTENBURG J.Level schedules for mixed-model assembly lines in just-in-time Production systems [J].Management Science,1989,35:192-207.

[10]SUMICHRAST R T,RUSSELL R S.Evaluating mixed-model assembly line sequencing heuristics for just-in-time production systems [J].J.Operational.Manage,1990,9:371-389.

[11]LAHMAR M,ERGAN H,BENJAAFAR S.Resequencing and feature assignment on an automated assembly line [J].IEEE Transactions on Robotics and Automation,2003,19(1):89-102.

[12] MANSOURI.A Multi-Objective Genetic Algorithm for mixed-model sequencing on JIT assembly lines [J].European Journal of Operational Research,2004,167:696-716.

[13]MCMULLEN P R,PETER T.A beam search heuristic method for mixed-model scheduling with setups [J].International Journal of Production Economics,2005,96:273-283.

[14]杨淑莹,张桦.群体智能与仿生计算—Matlab技术实现[M].北京:电子工业出版社,2012:157-161.

(责任编辑 杨黎丽)

Application on Scheduling of Mixed Model Assembly Lines with Hybrid Distribution Particle Swarm Optimization Algorithm

ZHOU Kang-qu, ZHAO Hui-zhen

(College of Mechanical Engineering, Chongqing University of Technology,Chongqing 400054, China)

To realize the effective operation of mixed assembly line, the mixed scheduling problem was studied. The objective of minimizing the make-span was considered and its mathematical model was described. To avoid premature convergence in particle swarm optimization algorithm, a hybrid distribution particle swarm optimization algorithm (HDPSO) was proposed. This algorithm was based on the Nawaz-Enscore-Ham algorithm of neighborhood searching strategy. The HDPSO was effective by an instance. Compared with other algorithm, the optimization results showed that the HDPSO had the advantage on the scheduling of motorcycle mixed model assembly lines. It could get the best method and had the better Astringency.

hybrid distribution particle swarm optimization algorithm; mixed model assembly; scheduling

2014-11-25 基金项目：重庆市科委基础与前沿研究项目(CSTC2013jcyjA0564)

周康渠(1967—)，女，四川达州人，博士，教授，主要从事生产系统优化技术、制造业信息化等方面研究。

周康渠，赵慧真.混合离散粒子群算法在混流装配线生产调度中的应用[J].重庆理工大学学报：自然科学版，2015(3):58-64.

format：ZHOU Kang-qu, ZHAO Hui-zhen.Application on Scheduling of Mixed Model Assembly Lines with Hybrid Distribution Particle Swarm Optimization Algorithm[J].Journal of Chongqing University of Technology:Natural Science,2015(3):58-64.

10.3969/j.issn.1674-8425(z).2015.03.012

TP393；TH165

A

1674-8425(2015)03-0058-07