作业车间调度问题(job-shop scheduling problem，JSP)具有广泛的应用背景[1-2]，可以简单描述为：n个工件须分别在m台机器上加工，且每个工件依次历经的机器顺序不同，须确定每台机器上工件的加工顺序，使目标函数达到最优[3-6]．JSP就是在析取图中确定所有虚线双向线段的指向，且保证在析取图不产生闭合回路的基础上使得目标函数最优．易知，当析取图中产生闭合回路时，产生的解为不可行解．只有当析取图中不存在闭合回路时，该解为可行解．JSP被证明是NP难问题，因此现在的研究大多数使用智能算法对JSP进行求解，以期望在合理的时间内获得满意解[7-10]．局部搜索是算法能否取得高质量解的关键，而邻域结构作为局部搜索的核心，能极大地影响算法的效率和质量．文献[11]提出交换关键路径块上相邻工序的邻域结构；文献[12]将关键路径块内的工序在保证生成的解为可行解的情况下，尽量插入到靠近该关键路径块首或块尾的位置；文献[13]提出了交换关键路径块上块首两工序或块尾两工序的邻域结构；文献[14]提出一种确保邻域解为可行解的邻域结构；文献[15]综述了已有的邻域结构，并将典型的邻域结构分别命名为N1~N6．文献[7]在N6基础上，使用对称性思想提出了一种新型邻域结构N7．文献[16]提出了一种多工序联动邻域结构．基于已有的工作，本研究对N7做了进一步拓展，将N7中包含的约束条件进行松弛，并在此基础上提出了一种新型的邻域结构，使得在局部搜索过程中可以获得更多的邻域解．通过反证法证明了根据松弛后的约束条件的充分性，同时用实验证明了新型邻域结构相对于现有的几种邻域结构更加优越．1 新型邻域结构分析与证明邻域结构是指对当前解产生一个小的扰动从而生成新解的一种规则．在现有研究中，针对JSP的邻域结构有很多，其中最常用的有N5，N6和N7.首先对相关概念和符号进行介绍．关键路径指在可行解的析取图中由节点s到节点e的最长路径；关键路径块指在关键路径中在同一机器上连续加工的工序组成的集合．u和v为同一关键路径块上的两个工序；Oi,j为第j个工件上的第i道工序；MOi,j为Oi,j的加工机器；POi,j为Oi,j的加工时间；js[Oi,j]为与Oi,j同工件的下一道工序；jp[Oi,j]为与Oi,j同工件的上一道工序；ms[Oi,j]为与Oi,j在同一台机器上加工的下一道工序；mp[Oi,j]为与Oi,j在同一台机器上加工的上一道工序；L(s,Oi,j)为在析取图中从节点s到节点Oi,j的最长路径长度；L(Oi,j,e)为在析取图中从节点Oi,j到节点e的最长路径长度．N5，N6和N7都是通过改变关键路径块上的首尾工序的加工顺序来产生邻域解，其原因是当关键路径块上的首尾工序不发生变化时，得到的邻域解不会比原来的解更优，因此N5，N6和N7都是在关键路径块上扰动，从而产生邻域解．N5邻域结构[13]为交换关键路径块上前两个工序或后两个工序产生邻域解的邻域结构，但在第一个关键路径块只交换后两个工序，在最后一个关键路径块上只交换前两个工序．N6邻域结构[14]即关键路径块中存在两工序u和v，u在v之前加工，且u和v至少有一个工序为该关键路径块的第一个工序或最后一个工序．当u为该关键路径块上的第一个工序且满足约束条件L(s,u)+pu≥L(s,jp[v])+pjp[v]时，v移动至u之前加工产生邻域解；当v为该关键路径块上的最后一个工序且满足约束条件L(v,e)≥L(js[u],e)时，u移动至v之后产生邻域解．N7邻域结构［7］即关键路径块中存在两工序u和v，u在v之前加工，且u和v至少有一个工序为该关键路径块的第一个工序或最后一个工序．当满足约束条件L(s,u)+pu≥L(s,jp[v])+pjp[v]时，v移动至u之前加工产生邻域解；当满足约束条件L(v,e)≥L(js[u],e)时，u移动至v之后产生邻域解．N6与N7的约束条件相同，两者之间的差异在于：在N6邻域中，当u为关键路径块上的第一个工序时，只有将v插入u之前加工才能产生邻域解；而在N7邻域中，当u为关键路径块上的第一个工序时，将v插入到u之前加工或将u插入到v之后加工都能产生邻域解．当v为关键路径块上的最后一个工序时也同理．由此易知：N7邻域结构是N6邻域结构的拓展，其在保证邻域解为可行解的基础上，扩大了邻域的搜索空间．然而，N7中的约束条件并不是保证邻域解为可行解的充分必要条件．对N7的约束条件进行松弛，在保证邻域解为可行解的基础上获得更多的邻域解．为了保证新型邻域结构产生的解为可行解，证明了以下两条定理．定理1 关键路径块中存在两工序u和v，且u在v之前加工．当满足约束条件L(s,u)+pu≥L(s,jp[v])时，v移动至u之前加工产生的邻域解为可行解．证明 使用反证法证明．假设将v移动到u之前加工产生不可行解，即产生邻域解的析取图中存在环.由于析取图中只改变了与v相关的弧，因此出现的环中必然包含弧(v，u)，则出现的环只可能为v-u-mp[u]-v或v-u-jp[v]-v．由于原解为可行解，则在解中不存在弧(u-mp[u])，同时由于约束条件L(s，u)+pu≥L(s,jp[v])，在解中不存在弧(u-jp[v])，因此在邻域解中不存在环，即邻域解为可行解，与原假设冲突，定理一得证．定理2 关键路径块中存在两工序u和v，且u在v之前加工．当满足约束条件L(v,e)≥L(js[u],e)-pjs[u]，u移动至v之后产生邻域解．证明同定理一的证明．由以上两条定理，提出了一种新型邻域结构，并将其命名为NS，表述如下：关键路径块中存在两工序u和v，u在v之前加工，且u和v至少有一个工序为该关键路径块的第一个工序或最后一个工序．当满足约束条件L(s,u)+pu≥L(s,jp[v])时，v移动至u之前加工产生邻域解；当满足约束条件L(v,e)≥L(js[u],e)-pjs[u]时，u移动至v之后产生邻域解．2 禁忌搜索算法为了对比新型邻域结构(NS)与N5，N6和N7的优劣性，使用禁忌搜索算法为载体，在保持其他算法结构与参数不变的前提下，使用不同的邻域结构进行实验，对比实验结果．2.1　生成初始解现有研究中有许多生成初始解的策略，如先到先加工、随机生成等．使用随机生成的策略，在保证工件的工艺加工约束不冲突的前提下，随机生成各加工机器上的工件加工顺序．2.2　禁忌内容及长度禁忌内容是指若解中的某部分加工顺序信息被禁忌后，则这部分加工顺序信息在禁忌的步长(即此后进化的次数)内不允许再次出现在新解中．本研究使用的禁忌内容与步长与文献[13]类似，即禁忌内容包含在机器上加工次序发生变化的所有工序以及其所在的加工位置．如某机器上须加工O1，O2，O3和O4四个工序，则这些工序的加工顺序为1，2，3，4．若将O2插入O4后加工，则机器上的加工顺序为O1，O3，O4，O2．这时，须禁忌的内容包含工序O2，O3，O4及这3个工序所在位置2，3，4．禁忌步长能保证算法搜索方向在一定程度上不会迂回，是禁忌搜索算法的一个重要参数．使用的禁忌步长是在一个范围内的随机整数，其最小值为Lmin=[10+n/m]，最大值为Lmax=[1.4(10+n/m)]．2.3　选择策略使用的选择策略是若邻域解中存在比当前最优解更优的解，则选取所有邻域解中最优的作为当前解；若邻域解中不存在比当前解更优的解，则选取未被禁忌的最优解；若所有的邻域解都被禁忌或迭代一定次数没有更新解，则随机选取邻域解中的一个作为当前解．在选择策略中最重要的是对所有的当前解进行评估．若使用精确评估方法则会消耗需要计算资源，则使用文献[11]提出的近似评估算法，以提高求解效率．2.4　终止条件为了比较不同邻域结构在搜索过程中邻域解数量及消耗的总运行时间，使用的终止条件为总的进化次数达到一定数值时，停止计算．具体的进化次数与问题规模相关，为1 000mn．3 实验结果与分析使用经典的TA数据集中的TA01~TA50算例来验证NS的优越性．实验使用禁忌搜索算法，除了邻域结构有所差异外，其他实验参数均相同．算法用C++编写运行，使用的个人电脑的CPU为i7-9750H处理器(2.6 GHz)．为保证实验的公平性，在每一次对比实验中使用相同的初始解进行实验．每个算例运行10次，取其中的最优值(Cb)和平均值(Ca)进行对比．4种邻域结构求解结果对比如表1所示．10.13245/j.hust.210718.T001表14种邻域结构求解结果对比规模N5N6N7NSCbCaCbCaCbCaCbCa15×151 237.51 244.91 235.31 240.81 233.71 240.61 233.71 239.020×151 386.61 396.51 382.91 398.21 382.41 398.21 378.71 392.520×201 637.71 648.81 631.11 639.41 632.91 639.71 630.11 639.030×151 811.71 828.51 806.61 828.51 808.31 825.71 806.41 821.230×201 989.62 005.61 982.01 994.21 981.61 997.11 980.21 993.9由表1可知：在TA数据集的前50个算例中，NS在34个算例得到的最优解结果优于其他3种邻域结构；NS有34个算例得到的平均结果优于其他3种邻域结构．对同一规模的算例求得的最优解和平均值做了统计处理．使用平均相对偏差(MRE)来评估计算结果与理论最优值的差距，其中偏差计算公式为100(实验结果－理论最优值)/理论最优值．同样，给出4种邻域结构的平均相对偏差，如表2所示，其中：Mb为最优的平均相对偏差；Ma为平均的平均相对偏差．同时，对同一规模下，单个解在不同邻域结构下可以获得的可行邻域解数量(Na)和禁忌搜索算法使用不同邻域结构迭代相同次数所使用的求解时间(t)进行了统计分析，结果如表3所示．10.13245/j.hust.210718.T002表24种邻域结构的平均相对偏差对比规模N5N6N7NSMbMaMbMaMbMaMbMa15×150.907 91.297 80.516 50.960 70.388 10.946 60.388 30.816 220×151.738 62.461 41.462 82.579 61.418 42.575 61.156 02.164 920×203.156 83.859 42.740 53.265 12.853 43.286 72.678 73.241 230×151.417 52.347 01.121 12.312 51.223 52.173 31.118 51.921 530×204.851 55.696 34.447 05.089 64.423 35.244 34.351 45.079 110.13245/j.hust.210718.T003表34种邻域结构求解的邻域解数量及求解时间对比规模N5N6N7NSNat/sNat/sNat/sNat/s15×157.518.6211.4521.7414.8048.1119.6786.9920×157.4312.2911.7531.8417.9179.4124.60150.2720×209.5421.6613.9653.3317.62121.9924.46214.6230×155.8719.9911.9155.0820.77156.9028.25303.0730×2010.1341.5116.11106.7921.83255.3330.76491.96由表2可见：在同一问题规模下，NS具有最好的平均相对偏差，具有更好的稳定性．由表3可知：NS可以获得最多的可行邻域解，但搜索时间最长．然而，由于在可行解的评估中使用了近似评估算法，因此其求解时间也在可接受的范围内．4 结语在现有邻域结构N7的基础上进行拓展，提出了用于求解JSP的NS，并证明了在可行解上使用该邻域结构所得到的邻域解均为可行解．使用禁忌搜索算法将NS与现有的3种常见的邻域结构进行了对比，实验结果表明：NS相对于其他3种邻域结构具有明显优势，在同一规模下的平均值中，NS也具有显著优势．实验还比较了单个可行解在不同邻域结构获得的可行解的数量和运行时间，表明：NS能够获得最多的可行邻域解的数量，同时也消耗最长的搜索时间．但由于使用了近似评估方法，因此搜索时间也在可以接受的范围内．除此以外，所提的约束条件仍然不是获得可行解的充分必要条件，即约束条件可以进一步进行松弛；同时，在约束松弛的过程中必然会产生许多对当前解没有改进的邻域解，这就会使得计算时间大大增加．后期可以通过添加新的约束条件，去除对当前解没有改进的邻域解，提高求解效率．