基于SGRASP-LP算法的混流装配线排序问题*

刘巍巍，杨 浩，刘慧芳

(沈阳工业大学 机械工程学院，沈阳 110870)

0 引言

在实际生产过程中，只有对混流装配线[1-2]上的产品进行合理排序，才能有效地提高装配线的生产效率、物流效率、缩短生产周期[3-5]。混流装配线排序问题属于典型的NP难题，目前关于该问题的研究多集中于模型构建和算法研究两个方面。文献[6-8]建立了考虑装配线平衡相关因素的混流装配线排序问题模型，该模型比较符合生产实际，但没有考虑工作站上作业人员自主中断作业对装配线排序方案的影响；文献[9-11]都采用遗传算法求解了相应的模型，得到了较优的投产序列，但无法避免此类算法求解时容易陷入局部最优的局限性；文献[12]设计一种改进猫群算法求解多目标混流装配线排序问题，虽然猫群算法局部和全局搜索的能力较好，但将其应用在实际的混流装配线排序问题时需要提前离散化，求解过程相对复杂。

本文设计的SGRASP-LP算法在建模时引入的 “保持生产混合” 与“作业自主中断”两个约束条件，更符合实际生产要求；在求解时为基本的GRASP(Greedy Randomized Adaptive Search Procedures)算法增加了阈值参数选择机制，并将其与线性规划(Linear programming，LP)方法相结合，提升了算法的求解效率与精度，改善了算法的全局寻优性能。

1 模型设计

1.1 模型描述

混流装配线排序问题是指对于采用最小生产循环(Minimal Production Set，MPS)模式生产的混流装配线，确定一个MPS中产品的投产顺序的问题。假设装配线生产节拍固定，不同型号的产品在各个工作站上的加工时间不同。模型的变量符号说明如下：

R：产品类型集合R={1,…,r,…R} ；

J：工作站集合J={1,…,j,…J} ；

T：制造周期T={1,…,t,…T} ；

c：每个工作站的节拍时间；

lj：每个工作站的时间窗j∈J；

bj：分配给每个工作站的处理器数量j∈J；

p：产品在序列中的位置；

ρr,j：作业的处理时间(r∈R，j∈J)(正常的活动下的测量值)；

D：一个最小生产循环单元中，所有类型产品的总需求数量，且T≡D=Σ∀rdr；

θ：产品类型比例。θ=(θ1，…，θr,…θR)，其中θr是需求计划中r(r∈R)类产品所占的比例，θ=d/D；

Xr,t：表示包含在序列β(t)=(β1,…βt)⊆β(T) (∀t=1,…,T)中r(r∈R)类产品的单位数量。

1.2 模型建立

本文设计的的问题优化模型如下：

(1)

(2)

0≤wj,t(βt)≤max(0,sj,t(βt)+ρβt,j-ej,t(βt))

(3)

uj,t(βt)=sj,t(βt)-ej,t-1(βt-1)

(4)

sj,t(βt)=max(ej,t-1(βt-1),ej-1,t(βt),(j+t-2)c)

(5)

ej,t(βt)=sj,t(βt)+ρβt,j-wj,t(βt)

(6)

ej,t(βt)≤(j+t-2)c+lj

(7)

ej,0(β0)=e0,t(βt)=0

(8)

⎣θrt」≤Xr,t≤|θrt|,Xr,T=dr

∀j∈J∀t∈T∀r∈R∀t∈T

(9)

式(1)和式(2)分别确定由序列β(T)产生工作过载W和无效时间U；式(3)限制了所有工作站j上的所有周期时刻t对应的部分工作过载。等式(4)定义了在每个工作站和循环中关于序列β(T)的无效时间。方程(5)确定最小起始时刻sj,t，而式(6)、式(7)和式(8)确定J×D个作业的最小完成时刻ej,t，不等式(9)是“保持生产混合”约束，强制在整个周期内保持生产混合。

2 算法设计

2.1 初始解序列构造

初始解序列的具体的构造步骤如下：

(1)初始化

输入：L,R，J,D,c, (dr,ρr,j,wj)， ∀r∈R,∀j∈J；设定初始值：T=D,t=0,β(t)={∅}，

(nr=0,θr=dr/D)∀r∈R。

(2)候选产品类型集合创建

t←t+1

Cl(t)={r∈R:nr

CL(t)={∅}⟹CL(t)={r∈R:nr

(3)候选产品类型评定

∀r∈CL(t)，Xr,t-1

(4)候选产品排序

如果：

那么：

(5)从限制列表里选择产品类型

(6)更新Rr*Rr*←Rr*+1；β(t)≡β(t-1)∪{r*}

(7)记录Λi

(8)完成测试。如t

2.2 改进解决方案的局部搜索

本文设计了如下4种邻域结构，其中p位置与p′位置的产品类型相同。

(1)向前交换。如图1中产品类型4与产品类型9的交换。

图1 向前交换示意图

(2)向后交换。如图2中产品类型3与产品类型5的交换。

图2 向后交换示意图

(3)向后插入。如图3中，产品类型6从p+2位置插入到p′-2位置。

图3 向前插入示意图

(4)向后插入。如图4中，产品类型9从p-1位置插入到p′+3位置。

图4 向后插入示意图

2.3 整体工作过载及无效时间优化

LP阶段的目标函数为：

(10)

约束条件：

(11)

(j+t-2)c≤sj,t

(12)

sj,t-1+vj,t-1≤sj,t

(13)

sj-1,t+vj-1,t≤sj,t

(14)

sj,t+vj,t≤(j+t-2)c+lj

(15)

uj,t≤ej,t-sj,t

(16)

vj,t,wj,t,uj,t≥0

(17)

∀j=1,...,J;∀t=1,...,T。其中，vj,t代表第j个工作站的t时刻已完成的工作。

3 实例验证

以某汽车企业底盘装配线为例验证算法的有效性，相关数据如下：

工作站数量：J=16

产品类型数量：|R|=8(r=1,…,8)

节拍时间：c=150s，时间窗：l=170s(∀j=1,...,16)

同类处理器数量：bj=1(∀j=1,...,16)

工作站上产品的加工时间：ρr,j(∀∈R,∀j∈J)

订单数量：|E|=18(ε=1,...,18)所有的订单有相同的日需求量

日需求量：T=Dε=240×订单ε内产品的单位数量(∀ε=1,...,18)

程序在Lenovo(Intel i5，CPU3.5GHz，内存8GB)的PC上运行。

3.1 选择阈值参数Λ

通过实验确定阈值参数Λ的一组取值为A={0.00,0.15,0.25,0.35,0.45,0.55,0.65,0.75,0.85,0.95,1.00}，且每个Λi的选择概率相等。在算法运行结束后，统计每个Λ取值下解的平均值，统计结果如图5所示。

图5 阈值参数Λ取不同值时的平均解

由图5可知，按照平均解升序排列，参数Λ的取值排序为0.25，0.75，0.45，0.35，0.65，0.85，0.95，0.55，1.00，0.00。最后，确定Λ的取值范围列表A，A由能获得较好平均解的Λ值组成，其中a∈[1,11]。例如，当a=3时，A={0.25，0.75，0.45}。a∈[1,11]时统计结果如图6所示。

图6 阈值参数Λ取不同值时的平均解

由图6可知，a=3时SGRASP-LP算法的平均解最优。当a=6时算法平均解最差；当7≤a≤9时，平均解逐渐变优，但是仍然大于a=3时的平均解。因此，参数Λ的取值应选取得较好平均解的前3个值，即A={0.25,0.75,0.45}。

3.2 SGRASP-LP与GRASP对比

为验证增加阈值参数选择机制后的SGRASP-LP算法优势，将其与基本的GRASP算法进行比较。两种算法在最优解和求解时间方面的比较结果详见表1，TSG和TG分别代表两种算法的找到最优解的求解时间。

表1 两种算法的最优解和求解的平均时间

由表1可以看出，与GRASP算法相比，SGRASP-LP算法找到的最优解更优，所用时间更短。因此，SGRASP-LP算法能够利用历史信息，在迭代过程中更改Λ取值，提升整体求解速度与解的质量。

3.3 SGRASP-LP与MILP对比

两个程序均在Lenovo(Intel i5，CPU3.5GHz，内存8GB)的PC上使用MATLAB编程。调用8.0.1版Gurobi求解器对MILP方法进行求解；调用12.7.1版CPLEX对SGRASP-LP方法进行求解。

表2给出了两种算法计算出的目标函数值Z(ε)，以及18个需求计划下的优胜算法和两种算法的优势对比结果SGvM，SGvM计算公式如下：

表2 优势对比结果

从表2的分析可以看出：

(1)SGRASP-LP算法找到最优解的次数更多、找到的平均最优解更优，且两者在计划8中都找到最优解。

(2)SGRASP-LP与MILP的整体平均优势对比结果约为9%。SGRASP-LP优于MILP时的优势对比结果为15%，MILP优于SGRASP-LP时的优势对比结果为7.5%。

(3)MILP和SGRASP-LP平均分别需要2978.5s和311.6s。

此外，本文将每种类型产品在每个需求计划对应的生产周期下的理想生产量θr,εt和实际生产量Xr,t,ε之间的方差之和ΔQ作为评价指标，以比较采用两种算法产生的序列在生产时的装配线稳定性。

表3也总结了每个计划下的装配线稳定性ΔQM(X,ε)和ΔQ SG(X,ε)以及两者中的优胜算法和优势对比结果ΔSGvM。

∀ε∈E,∀δ∈{SG},∀δ′∈{M}

由表3可得：

(1)SGRASP-LP算法在18个需求计划中14次胜出，MILP算法4次胜出，两者在计划1中装配线稳定性一致。

(2)SGRASP-LP与MILP的整体平均优势对比结果约为4%。GRASP-LP优于MILP时的优势对比结果为6%，MILP优于SGRASP-LP时的优势对比结果为4%。

(3)最后，虽然SGRASP-LP和MILP在第8个需求计划中计算出的目标函数值相等，但是SGRASP-LP产生的序列在生产时装配线稳定性更高。

4 结论

本文结合混流装配线的生产实际情况建立了MASP-W&U/PPM/F问题模型，在考虑模型的线性目标函数和标准GRASP算法求解特点的基础上，设计了线性规划辅助下的带有阈值参数选择机制的SGRASP-LP算法。实例的分析及对比结果表明，本文提出的模型和算法更符合企业的生产实际，求解过程呈现出较好的可行性与规律性，而且算法求解速度较快，所求解的质量较高，是求解装配线投产顺序排列问题的有效方法。

DOI:10.1007/s00170-014-6153-4.