赵晓飞， 郭秀萍

(1.西南交通大学 经济管理学院，四川 成都 610031; 2.重庆文理学院 经济管理学院，重庆 永川 402160)

0 引言

机器人制造单元是一种先进生产系统，广泛应用于机械制造、电路板印刷(Printed Circuit Board, PCB)、半导体制造以及计算机集成制造、纺织等行业[1～4]。随着技术进步和市场需求改变，机器人制造单元由生产同类型工件向生产多类型工件[5,6]转变。为了提高机器人制造单元生产效率和改进机器人制造单元利用率，将待加工多类型工件组成一个最小工件(Minimum Part Set, MPS)，按照混流生产方式周期生产。

混流生产机器人制造单元调度问题是NP难题[7]，为了优化该问题，启发式算法[8～10]和智能算法被提出[11～13]，但这些方法仅能解决两工作站或三工作站机器人制造单元调度问题，并且这些方法都针对求解结果进行分析，缺乏对机器人制造单元调度问题可行解性质进行探讨，使得提出算法难以适用于大规模机器人制造单元调度问题；从算法设计角度分析，已有算法基本都通过枚举机器人运行顺序实现，没有同时优化机器人运行顺序和工件加工顺序，易于陷入局部最优解。

因此，将机器人制造单元调度问题涉及的机器人运行顺序和工件加工顺序合二为一，变二维调度问题为一维调度问题就成为求解大规模机器人制造单元调度问题的关键。另外，由于机器人制造单元调度问题的NP难特性，探讨机器人制造单元调度问题可行解性质就成为解决该问题的重点。

本文针对混流生产机器人制造单元调度问题，利用机器人活动调度表示该问题的解，将二维调度问题转化为一维调度问题，探讨了可行解性质。

1 问题描述与模型建立

典型机器人制造单元由m个工作站P1,P2,…,Pm、一个由计算机控制的物料搬运机器人(本文称为机器人)、一个输入装置P0和一个输出装置Pm+1组成。总数为n的多类型工件J1,J2,…,Jn组成MPS同时在机器人制造单上被加工。Jj(1≤j≤n)从P0进入机器人制造单元，依次在P1,P2,…,Pm上加工，最后从Pm+1离开机器人制造单元。不同类型工件在同一工作站上的加工时间不同，Jj(1≤j≤n)在Pi(1≤i≤m)上的最小加工时间为ai,j(i≤i≤m,1≤j≤n)。机器人负责工件在工作站之间、输入装置和工作站之间以及工作站和输出装置之间的移动。任何时刻，机器人最多搬运一个工件，任意工作站最多加工一个工件。机器人将Jj(1≤j≤n)从Pf搬运到Pf+1记为rf,j(0≤f≤m)，包含三步操作：(1)从Pf卸下Jj；(2)将Jj移动到Pf+1；(3)将Jj装入Pf+1。

为了便于描述问题和避免混淆，定义以下符号。

决策变量：

ti,j：ri,j的开始时间(0≤i≤m,1≤j≤n)。

参数：

T：周期时间，即两个相邻MPS中第一个工件进入机器人制造单元所经过的时间。

di,j：常数，有载移动时间，即执行ri,j所耗费的时间(0≤i≤m;1≤j≤n)。

cq,k：空载移动时间，机器人在Pq与Pk之间不搬运工件移动耗费的时间(0≤q,k≤m+1)。

M：足够大的正实数。

τi：第i个机器人活动(0≤i≤n(m+1))。

job(i)：机器人活动τi搬运的工件(0≤i≤n(m+1))。

Q(i)：机器人活动τi起始工作站对应下标(0≤i≤n(m+1))。

σ：{1,2,…,n(m+1)-1}→{1,2,…,n(m+1)-1}的置换。

另外，本文假设以下两式成立。

df,j≥cf,f+1,1≤j≤n,0≤f≤m

(1)

cq,k≤cq,l+cl,k,0≤1,q,k≤m+1

(2)

式(1)表示相邻工作站之间，有载移动时间不小于空载移动时间；式(2)是三角不等式。为此本文研究问题的数学模型如下：

目标函数:MinimizeT

1≤i≤m,1≤j≤n

(3)

j≠h,1≤i≤m,1≤j,h≤n

(4)

1≤i≤m

(5)

0≤i,l≤m,1≤j,h≤n

(6)

0≤i,l≤m,1≤j,h≤n

(7)

ti,j≥d1,0+c1,i′,

i≠0或j≠1且0≤i≤m,1≤j≤n

(8)

T≥ti,j+di,j+c(i+1),0,

0≤i≤m,1≤j≤n

(9)

t0,1=0

(10)

(11)

ti,j≥0,0≤i≤m,1≤j≤n

(12)

T≥0

(13)

(14)

约束(3)保证了工件加工时间约束；约束(4)和约束(5)确保工作站容量约束不被违反；约束(6)和约束(7)避免机器人冲突；约束(8)给出了ri,j的开始时间不小于r0,1的开始时间；约束(9)给出了目标函数值下界；约束(10)和(11)界定了每个周期总是从r0,1开始；约束(12)和(13)是非负约束；约束(14)是0-1变量约束。

2 可行解性质

优化阻塞混流生产机器人制造单元调度问题，实质是找到机器人运行顺序和工件加工顺序这两个相互关联的顺序。已有研究中，要么固定工件加工顺序，优化机器人运行顺序；要么固定机器人运行顺序，优化工件加工顺序，导致可行解性质讨论不多。因此，要讨论可行解性质，首先将机器人运行顺序和工件加工顺序合二为一，变二维调度问题为一维调度问题。为此，给出定义1。

定义1τi+(m+1)(j-1)称为机器人活动，定义如下：

τi+(m+1)(j-1)=i+(m+1)(j-1),1≤j≤n,0≤i≤m

(15)

依据定义1，每个ri,j唯一对应一个τi+(m+1)(j-1)。例如，由4个工作站P1,P2,P3,P4、一个机器人、一个输入装置P0和一个输出装置P5组成的机器人制造单元。MPS由J1,J2,J3组成。ri,j与τi+(m+1)(j-1)对应情形见表1。

表1 ri,j与τi+(m+1)(j-1)对应情形

求解阻塞混流生产机器人制造单元调度问题的实质是对ri,j的开始时间ti,j(0≤i≤m;1≤j≤n)排序。依据定义1，决策变量ti,j也是机器人活动τi+(m+1)(j-1)的开始时间，又因为本文研究阻塞调度，因此ti,j排序可转化为机器人活动排序，将二维排序转化为一维排序。故，问题的解可表示为：S=(τ0,τσ(1),τσ(2),…,τσ(n(m+1)-1))。

为了判断解S是否可行，给出定义2。

定义2满足以下条件机器人活动排序，称为可行机器人活动调度。

(1)执行τi(0≤i≤n(m+1)-1)前，job(i)必须被装载在PQ(i)上，且完成加工；

(2)禁止机器人向非空工作站装载工件；

(3)禁止机器人向空工作站卸载工件。

依据定义1和定义2，如果确定了可行机器人活动调度，那么ti,j排序可以唯一确定。依据定义1，确定了可行机器人活动调度，机器人运行顺序和工件加工顺序被唯一确定。

机器人活动调度虽然是单排序，但是隐含了机器人运行顺序和工件加工顺序；本文研究周期调度，允许工件跨周期加工，因此，可行机器人活动调度涉及一些特殊性质。为了便于详细阐述这些性质，先给出加工同类型工件机器人制造单元调度问题可行解的性质。

针对时间窗约束加工两类型工件机器人制造单元调度问题，Lei和Liu[14]给出了如下结论：若S是可行机器人活动调度，那么两个连续Pi之间有且仅有一个Pi-1。本文将该结论拓展到加工同类型工件机器人制造单元调度问题和阻塞混流生产机器人制造单元调度问题。

性质1若机器人活动调度S是加工同类型工件机器人制造单元调度问题的可行机器人活动调度当且仅当每对连续Pi之间有且仅有一个Pi-1。

证明充分性证明。因为S是加工同类型工件机器人制造单元调度问题的可行机器人活动调度，所以，S中，Pi的个数与Pi-1的个数一样多。依据引理1[15]，每对连续Pi-1之间有且仅有一个Pi，意思是Pi与Pi-1交叉出现。那么每对连续Pi之间有且仅有一个Pi-1。性质1的充分性成立。

必要性证明。因为S是机器人活动调度，那么依据多度调度定义[16]，机器人活动调度S中，Pi的个数与Pi-1的个数一样多。又因为每对连续Pi之间有且仅有一个Pi-1，意思是Pi与Pi-1交替出现。那么每对连续Pi-1之间有且仅有一个Pi。依据引理1[15]，机器人活动调度S是可行的。必要性证得。性质1证毕。

文献[15]中引理2阐述了时间窗约束加工多类型工件机器人制造单元调度问题可行解的性质。本文将此结论拓展到阻塞混流生产机器人制造单元调度问题，并且证明了该结论为充要条件。

性质2若机器人活动调度S是阻塞混流生产机器人制造单元调度问题的可行解机器人活动调度当且仅当每对连续Pi之间有且仅有一个Pi+1，且Pi+1与紧前Pi加工相同工件。

证明充分性证明。由于引理2[15]在时间窗约束条件下得到，本文为阻塞约束，条件更宽松，因此，性质2的充分性证明详见引理2[15]。

必要性证明。因为S是机器人活动调度，依据多度调度定义[16]，机器人活动调度S中，Pi的个数与Pi+1的个数一样多。又因为每对连续Pi之间有且仅有一个Pi+1，意思是Pi与Pi+1交替出现。且Pi+1与紧前Pi加工相同工件。依据引理1[15]和定义2，机器人活动调度S是可行的。必要性证得。性质2证毕。

依据性质1和性质2，可得性质3。

性质3若机器人活动调度S是阻塞混流生产机器人制造单元调度问题的可行机器人活动调度当且仅当每对连续Pi之间有且仅有一个Pi-1，且Pi-1与紧后Pi加工的工件相同。

证明充分性证明。由性质2可以得到，可行机器人活动调度S中，Pi的个数与Pi-1的个数一样多，每对连续Pi-1之间有且仅有一个Pi，意思是Pi与Pi-1交替出现，而且Pi与Pi-1紧前加工的工件相同。又因为调度是周期进行的，所以，每对连续Pi之间有且仅有一个Pi-1，且Pi-1与紧后Pi加工相同工件。充分性证得。

必要性证明。因为S是机器人活动调度，那么依据多度调度定义[16]，S中，Pi的个数与Pi-1的个数一样多。又因为每对连续Pi之间有且仅有一个Pi-1，意思是Pi与Pi-1交替出现。那么每对连续Pi-1之间有且仅有一个Pi。由于是周期调度，且Pi-1与紧后Pi加工相同工件。保证机器人运行顺序和工件加工顺序可行。依据性质2，必要性成立。性质3证毕。

性质2和性质3研究了阻塞混流生产机器人制造单元调度问题的可行机器人活动调度的充要条件。接下来阐述，什么条件下，可行机器人活动调度，经过一定变化后得到的机器人活动调度仍然是可行的。

性质4S=(τ0,τσ(1),…,τσ(i),τσ(i+1),…,τσ(n(m+1)-1))是阻塞混流生产机器人制造单元调度问题的可行机器人活动调度。如果job(σ(i))≠job(σ(i+1))且|Q(σ(i))-Q(σ(i+1))|>1，那么交换τσ(i)与τσ(i+1)后，机器人活动调度S=(τ0,τσ(1),…,τσ(i),τσ(i+1),…,τσ(n(m+1)-1))是可行的。

证明由于S是阻塞混流生产机器人制造单元调度问题的可行机器人活动调度，因此，S满足性质2。也就是说，τσ(i)左边最靠近τσ(i)的机器人活动τσ(s)对应起始工作站为PQ(σ(s))，且Q(σ(s))+1=Q(σ(i))和job(σ(i))=job(σ(s))成立；同理τσ(i)，右边最靠近τσ(i)的机器人活动τσ(w)对应起始工作站为PQ(σ(w))，且Q(σ(w))+1=Q(σ(i))成立。由于τσ(i)与τσ(i+1)对应工作站不相邻，即Q(σ(w))≠Q(σ(i+1))，那么τσ(i+1)同样位于τσ(s)与τσ(w)之间，当τσ(i)与τσ(i+1)交换后，τσ(i)同样位于τσ(s)与τσ(w)之间，且有job(σ(i))=job(σ(s))。故，依据性质2，性质4成立。性质4证毕。

依据性质4，可以得到性质5。

性质5S=(τ0,τσ(1),…,τσ(i),τσ(i+1),…,τσ(n(m+1)-1))是阻塞混流生产机器人制造单元调度问题的可行机器人活动调度。如果job(σ(i))≠job(σ(i-1))且|Q(σ(i))-Q(σ(i-1))|>1，那么交换τσ(i)与τσ(i-1)后，机器人活动调度S=(τ0,τσ(1),…,τσ(i),τσ(i+1),…,τσ(n(m+1)-1))是可行的。

性质4和性质5通过交换相邻机器人活动，得到可行机器人活动调度。在这个过程中，工件加工顺序不变，机器人运行顺序改变。性质6工件加工顺序改变，机器人运行顺序不变。

性质6S=(τ0,τσ(1),…,τσ(i),τσ(i+1),…,τσ(n(m+1)-1))是阻塞混流生产机器人制造单元调度问题的可行机器人活动调度。如果(τσ(e0),τσ(e1),…,τσ(em))与(τσ(g0),τσ(g1),…,τσ(gm))分别是两个不同工件的所有机器人活动，且Q(σ(ef))=Q(σ(gf))(0≤f≤m)，依次交换τσ(ef)与τσ(gf)后，得到的机器人活动调度仍然可行。

证明S=(τ0,τσ(1),…,τσ(i),τσ(i+1),…,τσ(n(m+1)-1))是阻塞混流生产机器人制造单元调度问题的可行机器人活动调度，因此满足性质2的条件。又因为Q(σ(ef))=Q(σ(gf))(0≤f≤m)，所以依次交换τσ(ef)与τσ(gf)后，机器人运行顺序不变，同样满足性质2的条件，故，得到的机器人活动调度是可行的。性质6证毕。

3 结论

实际生产过程中，机器人制造单元调度问题具有阻塞约束和混流生产组织形式是常见情形。本文针对阻塞混流生产机器人制造单元调度问题的可行解基本性质进行了研究，得到以下结论：利用机器人活动概念，将二维调度问题转化为一维调度问题，降低了问题难度；重点分析了可行机器人活动调度的性质。

通过可行机器人活动调度性质研究，为算法设计提供了一条有效途径。利用可行机器人活动调度性质，可以设计有效的进化算子，提升进化算法求解效率，改善进化算法收敛速度。