对于Job Shop调度问题，大多数研究都不考虑搬运设备，而仅仅对机床进行调度.考虑物料搬运的Job Shop调度问题更贴近实际生产.

近年来，一些学者在研究传统Job Shop调度的基础上，对考虑物料搬运的Job Shop调度问题进行了研究.文献[1]提出了考虑物料搬运的Job Shop调度问题，但未研究求解算法.文献[2, 3]针对考虑一个搬运设备的Job Shop调度问题，分别提出了基于禁忌搜索算法的两阶段算法和并行禁忌搜索算法.文献[4]针对含有一个机器人的制造单元调度问题，提出了改进遗传算法.近来，有学者对考虑多个物料搬运设备的Job Shop调度问题进行了研究.文献[5]针对带多个搬运设备的Job Shop调度问题，提出了一个局域搜索算法.文献[6]针对带多个搬运设备的Job Shop调度问题，设计了一种文化基因算法.文献[7]对带多个搬运设备的柔性Job Shop调度问题进行了研究，同时构造了局域搜索算法.文献[8]对考虑多个搬运设备的加工时间不确定的柔性Job Shop调度问题进行了研究，同时提出了遗传算法和禁忌搜索算法的混合算法.上述对考虑物料搬运的Job Shop调度问题的研究均使用元启发式算法(meta heuristic algorithms)，求解比较耗时.结构式启发式算法(structured heuristic algorithms)求解速度快，然而关于此类算法的研究却较为少见.

本文在上述文献研究的基础上，以最小化最大完工时间makespan为调度目标，利用改进析取图建立调度模型，在引入析取子图的基础上，构建了两阶段构造式启发式算法.

带物料搬运设备的Job Shop调度问题可以描述为：n个工件{J₁,J₂,…,J_n}在m台机床{M₁,M₂,…,M_m}上加工，工件J_i包括n_i个工序O_i，j(j=1,2,…,n_i)，每个工序O_i,j对应一台机床M(O_i,j)，其加工时间p_i,j为定值.当工序O_i,j在机床M(O_i,j)上完成加工之后，触发搬运工序T_i,j.搬运过程如下：工件J_i在机床M(O_i,j)上等待搬运，发出搬运请求之后，搬运设备R先从当前位置空载行驶到机床M(O_i,j)，加载工件，然后负载将工件J_i搬运至下一道工序O_i，j+1对应的机床M(O_i，j+1)处.考虑搬运工序之后，工件的实际工序顺序可以表示为 O_i,j < T_i,jO_i,j+1 <T_i,j+1 <… <O_i,ni (O_i,j < T_i,j表示O_i,j在T_i,j之前完成).调度目标是使总完工时间t_f,max最小.

针对以上问题，作如下假设：1)每台机床的缓冲区均足够大；2)搬运设备一次只能搬运一个工件；3)搬运设备在两台机床之间的搬运时间只取决于机床的位置，与工件无关；4)t_k,h^L表示负载搬运设备从M_k到M_h的时间，运输时间满足约束关系t_k,h^L+t_h,l^L≥t_k,l^L；5)t_k,h^E表示空载搬运设备从M_k到M_h的时间，空载时间满足约束关系t_k,h^E+t_h,l^E≥t_k,l^E,t_k,k^E=0；6)不考虑工件的加载和卸载时间.

为了清晰地表述调度问题，定义以下符号和变量：t_f,i表示工件J_i的完成时间；t_s,oi,j表示工序O_i,j开始时间；t_s,i,j表示工序T_i,j开始时间；Q为一个任意大的正数；X_j,j′ⁱ =1表示O_i,j在O_i,j′之前完成，否则，X_j,j′ⁱ =0；DP_i,j^k = 1表示工序O_i,j由机床M_k完成，否则，DP_i,j^k=0；YDP_{i,j,i′,j′}^k=1表示DP_i,j^k=1，DP_i′,j′^k=1且O_i,j先于O_i′,j′在M_k上加工，否则，YDP_{i,j,i′,j′}^k = 0； DT_i,j^R=1表示加工任务O_i,j由搬运设备R运送至下一个对应的加工机床，否则，DT_i,j^R=0；YDT_{i,j,i′,j′}^R=1表示T_i,j先于T_i′,j′被R搬运，否则，YDT_{i,j,i′,j′}^R =0.

由上述假设可得如下约束关系：

当两个工序O_i,j和O_i′,j′共用一台机床时，约束关系可表示为

工序T_i,j和T_i′,j′共用搬运设备R搬运，约束关系可表示为

搬运设备要有足够的时间完成两个连续搬运任务，约束关系可以表示为

调度目标为

本文的调度问题是以式(8)为目标，以式(1)~式(7)为约束条件的非线性规划问题.

为了更清晰表述上述调度问题，对析取图模型进行改进，利用G=(N_m∪N_t，C∪D_m∪D_R)进行建模.N_m表示加工工序对应的节点集合；N_t表示搬运工序对应的节点集合；C是连接弧集合，表示工序顺序；析取边D_m表示在同一台机床上完成的工序之间的约束关系；析取边D_R表示搬运工序之间的约束关系.

加工工序节点指向运输工序节点的弧的权值为加工工序的加工时间.运输节点指向加工节点的弧的权值为运输时间.析取边D_m转为有向弧之后，权值等于有向弧始端的工序的加工时间，析取边D_R转为有向弧之后，权值计算见图 1.

图 1(Figure 1)

Fig. 1

图 1 运输节点之间析取弧权值 Fig. 1 The weight of the disjunctive arc between transportation nodes

析取子图^[9]是从析取全图中分离出来的图形，可以更清晰地表述子问题.用M₀表示已调度的机床集合，初始值为空集，M表示所有机床集合，SG(m)表示机床m的析取子图，AS(m)表示析取子图SG(m)中所有节点集合，US(m)表示SG(m)中未调度节点集合，URS(m)表示SG(m)中可以调度的节点集合，S(m)表示SG(m)中已经调度的节点集合.用最长路径算法计算各节点的投放时间 r_i,j和工期d_i,j，t_i,j表示节点的实际开始加工时间，tf,i,j表示完成时间.

定理1 调度析取子图SG(m)时，如果优先调度的节点O_i,j满足r_i,j≥mino_i′,j′∈US(m)(max(t_i′,j′,r_i′,j′)+p_i′,j′)，则析取子图的最大完工时间tf,max会增加.

证明：设O_i′,j′是使不等式右侧式子值最小的节点，O_i,j满足r_i,j≥max(t_i′,j′,r_i′,j′)+p_i′,j′.

若优先调度O_i,j，易知t_i,j=r_i,j，t_f,i,j=r_i,j+p_i,j.因为r_i,j≥max(t_i′,j′,r_i′,j′)+p_i′,j′，所以t_f,i,j>r_i′,j′，t_i′,j′=t_f,i,j，t_f,i′,j′=t_i′,j′+p_i′,j′=r_i,j+p_i,j+p_i′,j′.故t_f,max1 = max(t_f,i,j ,t_{f ,i′,j′}) = r_i,j + p_i,j + p_i′,j′ .

若优先调度O_i′,j′，易知，t_i′,j′=r_i′,j′，t_f,i′,j′=r_i′,j′+p_i′,j′，因为r_i,j≥max(t_i′,j′,r_i′,j′)+p_i′,j′，所以r_i,j>t_f,i′,j′，t_i,j=r_i,j，t_f,i,j=r_i,j+p_i,j.故t_f,max2=max(t_f,i,j,t_f,i′,j′)=r_i,j+p_i,j.

显然，t_f,max1>t_f,max2，即析取子图的最大完工时间t_f,max增加.

定理2 调度析取子图SG(m)时，设r_i,j^d表示当前调度时刻节点T_i,j的动态投放时间，如果优先调度r_i,j^d最小的节点，则必然能得到可行解.

证明：图 2表示当前状态下的析取子图SG(R)局部简图，当前未调度节点集合为{T_i,j,T_i′,j′+1}.p(0→x→T_i′,j′+1)表示从起点0到节点T_i′,j′+1的所有路径的集合，l(p)表示路径p的长度,r_i′,j′+1^d=max{l(p)|p∈p(0→x→T_i′,j′+1)}.又因为当前析取子图中，存在路径p(0→T_i,j→T_i,j+1→T_i′,j′→T_i′,j′+1)∈p(0→x→T_i′,j′+1)，所以，r_{i′,j′ +1}^d≥l(p(0→T_i,j→T_i,j+1→T_i′,j′→T_i′,j′+1))>

图 2(Figure 2)

Fig. 2

图 2 SG(R)局部简图 Fig. 2 Partial diagram of SG(R)

l(p(0→T_i,j))=r_i,j^d.所以，若按照r_i,j^d对节点进行排序，则T_i,j必然排在T_i′,j′+1之前，这样可以避免析取子图中出现环，即必然能得到可行解.

定理3^[2] s是一个可行解，最大完工时间为t_f,max(s)，如果存在另一个可行解s′,有t_f,max(s′)<t_f,max(s),那么有1)某个机床块中，至少有一个节点排在首节点之前或者在尾节点之后；2)搬运块中至少有两道搬运工序可交换顺序.

基于以上3个定理，构造了两阶段结构式启发式算法，算法构造描述如下.

步骤1    创建析取图并初始化.

步骤2    根据机床总负载 TWL=∑p_i,j 从大到小，确定机床调度顺序.

步骤3    按照机床调度顺序，确定机床m的析取子图SG(m).

步骤4    调度SG(m).

1) 初始化US(m)= AS(m),URS(m)=S(m)=ø ；

2) 若S(m)= AS(m) ，则转步骤5，否则，URS(m)={O_i,j|r_i,j≤{ max(t_i′,j′，r_i′,j′)+p_i′,j′ ，O_i，j∈ US(m)} ；

3) 对URS(m) 中的所有节点，按照d_i,j 从小到大的顺序进行排列，所得序列中的节点为O_i,j ，更新S(m)=S(m)∪O_i,j，US(m)= US(m)O_i,j,URS(m)=ø ，转步骤4中的2).

步骤5   将析取子图SG(m) 调度结果插入析取图中.

步骤    6&forauL;m′∈{M₀－m}，若m′上的工序出现在关键路径中，则重新调度m′，如果制造期缩短则更新m′的工序顺序；否则，保持m′的工序顺序不变.

步骤7    如果M₀≠M，则转步骤3.

步骤8    基于机床调度结果分离搬运设备析取子图SG(R).

步骤9    调度SG(R).

步骤10    对步骤1~9得到的解s第一层优化.

步骤11    对s第二层优化.

步骤12    算法结束.

定义，其中t_f,max^B表示利用文献[9]提出的改进转换瓶颈算法(MSBH)所求得的最大完工时间.

用m×n×1表示问题规模，参考文献[2, 3]设计4×4×1，6×6×1，10×5×1三种中小规模算例和15×5×1，10×10×1两种大规模算例.4×4×1，6×6×1类算例的加工时间p_i,j=^{[1, 10]}；10×5×1，15×5×1，10×10×1类算例的p_i,j=[1,100].各规模算例的运输时间设置如下：T_i,j^L=[0,P]，T_i,j^E=D|cur－k|.cur表示当前调度时刻搬运设备所处的机床序号；k表示当前调度时刻待搬运工件所处的机床序号；D为空载运输时间系数，.

用C++语言编程实现上述算法，并在硬件环境为320 G硬盘、2 GB RAM和2.27 GHz主频intel core(TM) i3处理器的Lenovo笔记本电脑上进行仿真实验.

设定pror=0.2，设计各问题规模的实例,实验结果见图 3.

图 3(Figure 3)

Fig. 3

图 3 问题规模对算法运行时间的影响 Fig. 3 Influence of problem scales on algorithm running time

从图 3可以看出，当pror=0.2时，随着问题规模的增大，Gap值在10%~21%之间波动，趋于平稳.总体来看，算法求解质量相对稳定，且相比文献[9]中的算法优势较显著.

令pror取^{[0, 1]}区间内不同的值，对不同规模的算例进行多次仿真实验，分析搬运时间对算法的影响，见图 4和图 5.

图 4(Figure 4)

Fig. 4

图 4 中小问题规模搬运时间对算法运行时间的影响 Fig. 4 Influence of transporting time in small and medium problem scales on algorithm running time

图 5(Figure 5)

Fig. 5

图 5 大问题规模搬运时间对算法运行时间的影响 Fig. 5 Influence of transporting time in large problem scales on algorithm running time

由图 4和图 5可知，随着搬运时间与加工时间的比值pror的增大，Gap值呈减小趋势.当pror小于0.5时，Gap值在5%~20%之间，算法相对文献[9]中的算法的优势比较明显，求解质量较高.当pror大于0.5小于1时，两种算法所求结果的差异较小.实际的生产中，搬运时间一般小于加工时间的50%，即pror小于0.5，因此，本文算法有较高的实用价值.

1) 在构建数学模型和改进型析取图的基础上，提出的两阶段构造式启发式算法能够有效地求解带物料搬运设备的Job Shop调度问题，为此类问题的调度提供了新思路.

2) 仿真结果表明，当搬运时间与加工时间的比值pror一定时，算法的求解质量相对稳定，并且能够较好地平衡求解质量和求解时间之间的矛盾.

3) 搬运时间与加工时间的比值pror小于0.5时，本文算法与文献[9]的算法的Gap值在5%~20%之间，求解质量明显高于文献[9].