求解阻塞混流生产机器人制造单元调度问题的分支定界算法

赵晓飞，郭秀萍

(1.西南交通大学 经济管理学院，成都 610031； 2.重庆文理学院 经济管理学院，重庆402160)(*通信作者电子邮箱guoxiuping0029@sina.com)

0 引言

机器人制造单元是一种先进生产系统，广泛应用于机械制造、电路板印刷(Printed Circuit Board, PCB)以及半导体制造等行业[1-4]。典型机器人制造单元由一个输入装置、一个输出装置、多个工作站以及一个由计算机控制的机器人组成。

由于市场需求由大批量、少品种向小批量、多品种转变，且机器人制造单元技术改进，使得机器人制造单元由生产同类型工件向生产多类型工件转换[5-6]。为了合理生产多类型工件，提高系统效率，将待加工的多类型工件组成一个最小工件集(Minimum Part Set, MPS)，按照混流方式周期生产。

由于文献[7]证明了工作站数大于2的混流生产机器人制造单元调度问题是非确定性多项式(Non-Deterministic Polynomial， NP)难的，因此以工作站个数为分类标准，将该问题分为两大类：一类是工作站数等于2；一类是工作站数大于2。工作站数等于2时，该问题可以转化为推销员旅行问题(Travel Saleman Problem, TSP)[8-10]，易于求解，但仅限于1-度生产策略情形。工作站数等于3时，研究者通过枚举机器人运行顺序[7,9,11-12]，设计了多种启发式方法，但这些方法没能同时优化工件加工顺序和机器人运行顺序。文献[13]首次同时优化了工件加工顺序和机器人运行顺序，并证实了同时优化工件加工顺序和机器人运行顺序优于固定一个顺序优化另一个顺序，但该研究前提是工作站数等于3。文献[14-15]在文献[13]研究基础上，首次设计化学反应优化求解该问题，得到了更好解。

以上优化方法仅适用于工作站数为2或3时的阻塞混流生产机器人制造单元调度问题，很难推广到更多工作站情形；因此，设计新的优化方法，同时优化机器人运行顺序和工件加工顺序，求解阻塞混流生产机器人制造单元调度问题就显得尤为重要。文献[16]研究了阻塞单件车间(Job-shop)机器人制造单元调度问题，给出了可行解构建条件，同时优化了工件加工顺序和机器人活动顺序。由于混流生产和单件车间的不同，以文献[16]研究为基础，本文首先构建了工作站编号与工件编号与机器人活动之间的数量关系；其次，提出了顺序插入规则修正文献[16]给出的可行解构建条件；第三，文献[16]限定了跨周期加工工件数，本文放松了该假设，认为跨周期加工工件理论上来说可以有无限多个，增加了顺序插入规则适用性。

本文针对阻塞混流生产机器人制造单元调度问题，构建了顺序插入规则，生成可行解。以顺序插入规则为基础，构建了分支定界算法求解该问题。

1 问题描述与模型构建

本文研究的机器人制造单元由m个工作站P1,P2,…,Pm；一个由计算机控制的物料搬运机器人；一个输入装置P0和一个输出装置Pm+1组成。由n个多类型工件J1,J2,…,Jn组成的MPS同时在机器人制造单元上被加工。Jj(1≤j≤n)从P0进入机器人制造单元，依次在m个工作站P1,P2,…,Pm上加工，最后从Pm+1离开机器人制造单元，不考虑重入和平行工作站情形，不考虑加工中断情形，且同一时间，每个工作站最多加工一个工件。Jj在Pi上的加工时间ai, j(1≤i≤m，1≤j≤n)为常数，工件类型不同，加工时间ai, j一般不同。机器人负责工件在工作站之间、输入装置和工作站以及工作站和输出装置之间的移动。同一时刻，机器人最多能搬运一个工件。机器人移动ri, j包含3步操作：1)机器人从Pi卸下Jj；2)机器人搬运Jj从Pi到Pi+1；3)机器人将Jj装入Pi+1(0≤i≤m，1≤j≤n)，其开始时间为ti, j。执行ri, j耗时di, j，也称为有载移动时间，为常数。cq,k是机器人在Pq与Pk之间不搬运工件移动耗费的时间(0≤q,k≤m+1)，即空载移动时间。目标是最小化两个相邻MPS中第一个工件进入机器人制造单元所经过的时间，即加工周期T。另外本文假设以下两式成立：

dh, j≥ch,h+1； 1≤j≤n,0≤h≤m

(1)

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

(2)

式(1)表示相邻工作站之间，有载移动时间不小于空载移动时间；式(2)是三角不等式。

为了便于数学模型构建，给出以下符号定义。

M表示足够大的正实数。

数学模型如下。

目标函数:

MinimizeT

约束：

1≤i≤m,1≤j≤n

(3)

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

(4)

(5)

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

(6)

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

(7)

ti, j≥d0,1+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 基础理论

针对混流生产机器人制造单元调度问题，文献[8]证明了1-度机器人运行顺序共有m!个，因此，随着工作站个数增多，通过枚举机器人运行顺序优化工件加工顺序的求解策略基本不可行；当然，如果枚举工件加工顺序，优化机器人运行顺序也仅在理论上有可能。为此，构建混流生产机器人制造单元调度问题的可行解就成为求解该问题的关键。为了构建可行解，先给出机器人活动定义。

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

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

(15)

依据定义1，τi+(m+1)(j-1)与ri, j一一对应，因此，每个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的开始时间排序。依据定义1，对ri, j的开始时间排序，可以转化为对机器人活动τi+(m+1)(j-1)调度。因为本文考虑周期调度，总认为每个机器人活动调度中，τ0排第一个，因此，S=(τ0,τσ(1),τσ(2),…,τσ(n(m+1)-1))为问题的解，其中σ是{1,2,…,n(m+1)-1} → {1,2,…,n(m+1)-1}的置换。为了便于表述，假设job(h)为机器人活动τh搬运的工件；Q(h)为机器人活动τh起始工作站对应下标(0≤h≤n(m+1))。为了判断解S是否可行，给出定义2。

定义2 满足以下条件的机器人活动调度称为可行机器人活动调度：

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

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

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

依据表1，解S1=(τ0,τ12,τ13,τ1,τ2,τ5,τ14,τ6,τ3,τ4,τ7,τ10,τ8,τ9,τ11)是可行机器人活动调度。

3 顺序插入规则

定义2可以判断给定解是否可行，但不能构建可行解，因此，本章给出构建可行解的规则：顺序插入规则。

文献[16]给出了阻塞作业车间机器人制造单元调度问题可行解构建规则，但是由于作业车间和混流生产的区别，仅利用文献[16]给出的规则会产生不可行解。令Rdone为部分可行机器人活动集合，Rtodo为未排序机器人活动集合。例如：利用文献[16]提出规则，Rdone={τ0,τ9,τ14}满足可行性要求；但是，Rdone={τ0,τ9,τ14}不满足定义2中条件3)，故Rdone={τ0,τ9,τ14}不是部分可行机器人活动调度。

阻塞混流生产机器人制造单元调度问题是阻塞作业车间机器人制造单元调度问题的特殊情形，故本文以文献[16]提出规则为基础，提出了顺序插入规则构建阻塞混流生产机器人制造单元调度问题可行解。顺序插入规则的条件1、条件2由文献[16]提出，余下条件下文给出，满足这6个条件之一的Rdone是不可行的。

条件1 在Rtodo中任意选择机器人活动τf、τf-1存在，且job(f)=job(f-1)，将τf插入Rdone末端，若对任意τh、τh+1存在，有job(h)=job(h+1)和Q(f-1)=Q(h)成立，但τh∈Rdone而τh+1∈Rtodo或τh+1∈Rdone而τf-1∈Rtodo。

条件2 在Rtodo中任意选择机器人活动τf，且τf+1存在，job(f)=job(f+1)，将τf插入Rdone末端，若对任意τh，τh+1存在，有job(h)=job(h+1)和Q(f)=Q(h)≠m成立，但τh∈Rdone而τh+1∈Rtodo或τf+1∈Rdone而τh∈Rtodo。

条件3 在Rtodo中任意选择机器人活动τf，将τf插入Rdone末端，对任意τh∈Rdone，若Q(f)=Q(h)=m，但τf-1∈Rtodo。

条件4 在Rtodo中任意选择机器人活动τf，将τf插入Rdone末端，对任意τh∈Rdone，若Q(f)≠Q(h)，且Q(f)=m，job(f)=job(h)，但τf-1∈Rtodo。

条件5 在Rtodo中任意选择机器人活动τf，将τf插入Rdone末端，对任意τh∈Rdone，若Q(f)≠Q(h)，且Q(h)=m，job(f)=job(h)，但τh-τf

条件6 若Jδ(1),Jδ(2),…,Jδ(l)(l

条件3、条件4和条件5关注工作站是否冲突，条件6关注跨周期加工工件的加工顺序是否一致。条件3保证两个连续的Pm之间，一定存在一个Pm-1；条件4和条件5确保混流生产性质不被违反。

利用顺序插入规则构建可行解的步骤如下：

步骤1 令Rdone={τ0}，Rtodo包含余下机器人活动，假设除P1外，所有工作站为空。

步骤2 利用顺序插入规则，选择插入Rdone末端，并使得Rdone是部分可行的机器人活动，从Rtodo中删除该机器人活动。

步骤3 重复步骤2，直到Rtodo为空集。

例如，考虑表1给出的机器人活动。初始状态：Rtodo={τ1,τ2,τ3,τ4,τ5,τ6,τ7,τ8,τ9,τ10,τ11,τ12,τ13,τ14}，Rdone={τ0}。假设工作站Pi为空(2≤i≤4)。

接下来，选择Rtodo中所有可能机器人活动插入Rdone中第2个位置，可能的部分可行机器人活动分别为：{τ0,τ1}、{τ0,τ7}、{τ0,τ8}、{τ0,τ9}、{τ0,τ12}、{τ0,τ13}、{τ0,τ14}。余下机器人活动不能排在Rdone中第2个位置。因为，如果排τ2,τ3,τ4中的一个，τ1未排，违反流水线性质；如果排τ6或τ11，机器人从P0搬运J2或J3，但是P1被J1占用，违反文献[16]给出的条件1；如果排τ5或τ10，违反文献[16]给出的条件2。

然后，令Rtodo={τ1,τ2,τ3,τ4,τ5,τ6,τ7,τ8,τ10,τ11,τ12,τ13,τ14},Rdone={τ0,τ9}。此时P1被占用，其余工作站为空。从Rtodo中选择所有可能机器人活动插入Rdone中第3个位置，可能的部分可行机器人活动分别为：{τ0,τ9,τ1}、{τ0,τ9,τ12}、{τ0,τ9,τ13}。余下机器人活动不能排在第3个位置。因为，如果排τ2,τ3,τ4中的一个，τ1未排，违反流水线性质；如果排τ5或τ10，违反文献[16]给出的条件2；如果排τ6或τ11，机器人从P0搬运J2或J3，但是P1被J1占用，违反文献[16]给出的条件1；如果插入τ7或τ8，虽然满足文献[16]给出的条件1和条件2，但是不满足条件5；如果插入τ14，虽然满足文献[16]给出的条件1和条件2，但是不满足条件3。依据顺序插入规则，得可行机器人活动调度为：S2=(τ0,τ9,τ1,τ2,τ10,τ11,τ3,τ4,τ12,τ5,τ13,τ14,τ6,τ7,τ8)。以上可行机器人活动调度构建过程如图1。

图1 可行机器人活动调度构建过程示意图

理论上，阻塞混流生产机器人制造单元调度问题解的个数为(n(m+1)-1)!。表2给出了小规模时理论解个数与可行解个数的比较。从表2可以发现，利用顺序插入规则生成可行解的个数远远小于解的个数，可以有效减少搜索空间。

表2 理论解个数与可行解个数比较

4 分支定界算法

分支定界算法两个关键点是：剪枝策略与上界的确定。首先，利用文献[16]给出的下界计算方法，选择使得部分可行机器人活动调度下界最小的节点继续分支，即通过深度优先搜索找到问题的一个上界；然后，在分支过程中，再次利用文献[16]给出的下界计算方法，计算部分可行机器人活动的下界；最后，利用上界和下界进行剪枝，继续搜索，求得该问题的最好解。具体步骤如下：

步骤1 令Rdone={τ0}，Rtodo包含余下机器人活动，假设除P1外，所有工作站为空。

步骤2 利用顺序插入规则，选择插入Rdone末端，并使得Rdone是部分可行的所有机器人活动，组成集合Ω。

步骤3 利用文献[16]给出的下界计算方法，计算集合Ω中每个机器人活动插入Rdone后的下界。

步骤4 选择最小下界对应的机器人活动插入Rdone末端，从Rtodo中删除该机器人活动。

步骤5 重复步骤2～4，直到Rtodo为空集。计算获得可行解的目标函数值，作为分支定界算法的上界，记为当前最好解。

步骤6 利用回溯算法和文献[16]给出的下界计算方法，计算其他分支的下界：若下界大于上界，则剪枝；否则，利用顺序插入规则，继续分支。

步骤7 若得到的目标函数值小于当前最好解，更新当前最好解。

步骤8 若搜索完所有分支或满足算法终止条件，输出最优解或满意解。

5 结果比较

以顺序插入规则构建的分支定界(Branch and Bound, BB)算法利用C++语言编程，在CPU为Intel Core i5- 4460 CPU@ 3.20 GHz，内存为8 GB的环境下运行。运行时间为以秒计的CPU时间。终止条件为CPU时间600 s。

本文借鉴文献[17]中算例生成方式。ai, j为整数，且ai, j～U[20,99](1≤i≤m,1≤j≤n)；dh, j=6(1≤j≤n,0≤h≤m)；cq,k=4|q-k|(0≤q,k≤m+1)。其中：inf表示给定时间内未求得可行解；CT表示计算时间，单位为s。

表3给出了n为4、5、6时，m为3、4时，分支定算法(BB)和CPLEX12.5的计算结果比较。在表3中，P表示问题，例如J6P1表示6个工件时的第一个问题。给定m值和n随机生成5个算例，每个算例每种算法运行10次，取平均计算时间和平均目标函数值进行比较。从表3中可以发现，两种方法都能在合理的时间求得最优解，且随着工件数或工作站数增多，计算时间变长，证实了算法的有效性。

表3 不同m值时两种算法的运行时间和目标函数值对比

表4给出了n∈[7,15]且为整数；m∈[4,20]且为偶数时，分支定算法和CPLEX12.5的计算结果比较。每个算例每种算法运行10次，取平均计算时间和平均目标函数值进行比较。

在总共81个算例中，CPLEX给出了14个算例的可行解，占比17.28%，随着算例规模变大，在给定时间内不能求得可行解；而分支定界算法给出了所有算例的可行解。CPLEX给出了两个算例的最优解，分别为n=7，m=4和n=8，m=4；分支定界算法给出了n=7，m=4算例的最优解。两种方法都给出解的算例中，仅有两个算例，分别为n=7，m=4和n=7，m=8，是分支定界算法的解不劣于CPLEX。总的来说，小规模算例时，CPLEX的求解效率和精度高于分支定界算法，当算例规模变大，分支定界算法的效率高于CPLEX，因此，利用顺序插入规则构建的分支定界算法具有求解大规模问题的能力。

6 结语

本文针对阻塞混流生产机器人制造单元调度问题，利用机器人活动将工件加工顺序和机器人运行顺序合二为一，将二维调度问题转化为一维调度问题。为了同时优化该问题的工件加工顺序和机器人运行顺序，提出了顺序插入规则构建可行解。以顺序插入规则为基础，构建了分支定界算法。通过计算随机生成的算例表明，分支定界算法相对于CPLEX在求解大规模问题时更有优势。后续研究可以从以下两方面考虑：一是研究分支定界算法的剪枝策略和下界计算方式，提高算法效率；一是利用顺序插入规则构建可行解，设计启发式算法或智能优化算法，提高解的质量。

表4 不同n值时两种算法的运行时间和目标函数值比较