0 引言

作业车间调度问题(Job-shop Scheduling Problem,JSP)是最困难的组合优化问题之一，也是经典的NP-hard问题^[1]。作业车间调度问题可以简单描述如下：给定n个作业，每个作业包含m个有预定加工顺序、加工机器和加工时间的工序。调度的目标就是合理安排所有工序在m台机器上的加工顺序，最小化最大完工时间，亦即最小化最后一个工序的完工时间。作业车间调度问题是许多实际生产调度问题的简化模型，具有广泛应用背景，如工业生产、交通规划、物流和网络通信等诸多方面的问题，都可借助于作业车间调度问题的求解结果。所以，高效、快速地求解作业车间调度问题，既有重要的理论意义，也有重大的应用价值。

求解作业车间调度问题的方法目前可以分为两大类型：精确算法和近似算法。精确算法主要通过运筹学的求解方法寻求问题的理论最优解，主要有分支定界方法(Branch and Bound,B&B)^[2]、整数规划方法(Integer Linear Programming,ILP)^[3]和拉格朗日松弛法(Lagrangian Relaxation,LR)^[4]等。精确算法虽然能得到理论最优解，但由于其计算复杂，运算时间长，因此只适用于小型实例。而对于大规模的调度问题，近似算法是更好的选择，近似算法主要有优先分配规则法(Priority Dispatch Rule,PDR)、瓶颈移动法(Shifting Bottleneck Procedure,SBP)、人工智能和元启发式算法等。 优先分配规则法是最早提出的近似算法，Giffler等^[5]提出的构造主动高度和无延迟调度的算法被认为是优先分配规则法的基础。瓶颈移动法由Adams等^[6]提出，并且是首次求出经典的FT10问题最优解的近似算法。 随后人们尝试将人工智能的研究成果，如约束满足技术、专家系统和人工神经网络等应用到解决调度问题中，其中比较经典的有文献[7-9]中应用Hopfield模型以及文献[10]中应用反向传播(Back Propagation,BP)神经网络模型求解调度问题。元启发式算法^[11]是近些年求解调度问题最热门、最高效的算法，主要包括基于生物启发的群体算法和局部搜索算法。其中基于生物启发的群体算法有遗传算法(Genetic Algorithm,GA)、蚁群优化(Ant Colony Optimization,ACO)算法和粒子群优化(Particle Swarm Optimization,PSO)算法等；局部搜索算法有禁忌搜索(Tabu Search,TS)算法和模拟退火(Simulated Annealing,SA)算法等。

帝国主义竞争算法(Imperialist Competitive Algorithm,ICA)是Atashpaz-Gargari等^[12]在2007年受历史上帝国之间的竞争启发而提出的一种新型进化算法。算法中的初始种群被分成两类：帝国和殖民地。殖民地通过不断向帝国学习进化自身，而帝国之间的竞争使得所有殖民地最终归附到一个最强的帝国之下。禁忌搜索(TS)算法是Glover^[13]在1986年提出的一种经典的局部搜索算法。禁忌搜索算法基于局部邻域搜索方法，通过设置禁忌表来避免迂回搜索，利用藐视准则来特赦被禁忌的优解，能够高效地求解优化问题。

近些年的研究显示，混合算法比单一算法能提供更高质量的解和更好的搜索效率。因此，将单一算法有机组合以弥补各自的不足成为了研究者关注的热点。文献[14]将树搜索算法与人工蜂群算法进行结合，强化对JSP的搜索能力；文献[15]在文化算法中融入了局部搜索，对求解JSP进行了研究；文献[16]将人工免疫系统与禁忌算法混合求解JSP，提出了带禁忌搜索的人工免疫系统(Artificial Immune System with Tabu Search,AIS-TS)算法；文献[17]将局部搜索和遗传算法结合求解JSP；文献[18]将空闲时间的邻域搜索融入到遗传算法中求解JSP。

本文将基于帝国主义竞争算法和禁忌搜索算法提出一种新型混合算法HICATS(Hybrid Imperialist Competitive Algorithm with Tabu Search)。帝国主义竞争算法拥有很强的全局优化能力，但缺乏局部搜索能力，而禁忌搜索算法虽然缺乏全局搜索能力，但具有很强的局部搜索能力，因此两者的结合能够达到优势互补。针对问题特性，混合算法还融入遗传算法的交叉和变异算子，使算法能够更高效地求解JSP。

1 问题模型

经典的作业车间调度问题可以描述如下：给定m台机器，n个作业，每个作业按指定顺序，依次在m台机器上加工，即每个作业都包含m个工序。对作业和机器的约束如下：

1) 每个工序有预先设置的加工时间与加工机器；

2) 每个工序有且只能在一台机器上加工一次；

3) 不同作业之间无先后约束关系；

4) 每个工序一旦开始就不能中断；

5) 每台机器同一时刻只能加工一个作业；

6) 不计工序开始前布置时间和工序之间交接时间；

本文约定符号如下：m台机器表示为{M₁,M₂,…,M_m}，n个作业表示为{J₁,J₂,…,J_n}，第i个作业的第j个工序表示为o_ij，工序o_ij对应的加工机器表示为p_ij，对应的加工时间表示为t_ij。每个作业最后一道工序的完工时间即是该作业的完成时间，表示为C_i。求解作业车间调度问题即是最小化所有作业的最大完工时间C_max，目标函数如式(1) 所示：

${{C}_{\max }}=\min \left\{ \underset{i=1}{\overset{n}{\mathop{\max }}}\,({{C}_{i}}) \right\}$

(1)

一个3×3的JSP实例如表 1所示，其中“—”代表工序在机器上无加工数据。

2 HICATS算法

帝国主义竞争算法是新型的进化算法，其中所有的国家将被分为两类：一是帝国；二是殖民地。具有较优适应度值的国家将成为帝国，拥有较差适应度值的国家将成为帝国的殖民地。各帝国之间不断展开竞争，强帝国以大几率从弱帝国中夺得殖民地。整个竞争过程到只剩一个帝国、达到算法迭代次数或找到最优解时停止。

本文提出的混合帝国主义禁忌搜索算法HICATS是一种新型的元启发式算法，算法集成了帝国主义竞争算法与禁忌搜索算法的优点，且融合了遗传算法的杂交算子和变异算子，使得该算法能够高效求解JSP。

2.1 初始化帝国与殖民地

本文使用基于工序的编码方式，并采用Zhang等^[19]提出的全主动调度(Full-Active Schedule,FAS)来提高初始解的质量。传统主动调度(Active Scheduling,AS)能够在不破坏优先顺序以及不延迟其他工序的条件下，使得没有工序可以提前；而全主动调度则是在主动调度的基础中，增加了反转调度，使得不仅可以将允许左移的工序左移，也可以将允许右移的工序右移，因此全主动调度的最大完工时间小于或者等于其对应的主动调度的最大完工时间。

以表 1中3×3实例为例，随机生成一个初始解{1,2,1,2,1,3,2,3,3}，解对应的工序编号为{1,4,2,5,3,7,6,8,9}，其AS结果如图 1所示，调度结果为11。

而对于同样的初始解，采用FAS调度结果如图 2所示。图 2(a)是将允许右移的工序右移的反转调度，即以初始解反向开始调度，调度顺序为{9,8,6,7,3,5,2,4,1}，同时也是基于主动调度方式，最终调度的结果是8；图 2(b)为基于反转调度结果的主动调度，使能够左移的工序左移，同时也得到各个工序正确的开工和结束时间，并形成最终的调度结果。从图 2中可知，对于同样的初始解，AS的调度结果是11，而FAS的调度结果是8。

示例演示了FAS的有效性，而在FT10实例上的实验进一步验证了FAS生成初始解的高质量。实验分别用FAS和AS随机生成100个FT10的初始解，从图 3的实验结果中可以看出，不论最优适应值还是平均适应值，FAS生成的初始国家都优于AS生成的初始国家。

本文中帝国主义竞争算法的符号与Atashpaz-Gargari等^[12]定义帝国主义竞争算法时保持一致。FAS调度生成的初始国家定义为N_pop，从中选择适应值最优的N_imp个国家为帝国，剩下的N_col个国家将作为殖民地并根据各帝国力量随机分配到各个帝国旗下。按照式(2) 标准化各帝国力量:

${{C}_{n}}={{c}_{n}}-\underset{i}{\mathop{\max }}\,\{{{c}_{i}}\}$

(2)

其中：c_n是第n个帝国的适应度值；C_n是其标准化后的适应度值。基于标准化后的适应度值，用式(3) 计算出各个帝国的力量：

${{p}_{n}}=\left| {{C}_{n}}/\left( \sum\limits_{i=1}^{{{N}_{imp}}}{{{C}_{i}}} \right) \right|$

(3)

其中p_n是一个比值，越大代表这个帝国拥有的力量越强，因此应该拥有的殖民地也就越多。基于p_n，按式(4) 给每个帝国划分应该拥有的殖民地数：

$N.C{{.}_{n}}=\text{round}\{{{p}_{n}}\times {{N}_{col}}\}$

(4)

其中N.C._n就是每个帝国初始拥有的殖民地数，按照这个数量将殖民地随机分配到各个帝国旗下。这样就完成对所有帝国及殖民地的初始化。

2.2 同化操作

在Atashpaz-Gargari等^[12]提出的帝国主义竞争算法中，采用距离公式实现殖民地向帝国的学习移动过程， 而本文则根据问题特性借鉴遗传算法的杂交思想作为学习过程。 在一个帝国集团中，每一组殖民地将按照概率P_s从以下两种杂交方式随机选择一种：

1) 任一殖民地与所在帝国按照优先工序交叉(Precedence Operation crossover,POX)算法交叉T次；

2) 两个殖民地按照POX算法交叉T次。

其中优先工序交叉(POX)算法是Zhang等^[19]在2008年提出的一种高效交叉算子。假设有父代Parent1和Parent2，POX产生两个子代的流程如下：

1) 随机划分工件集{1,2,…,n}为两个非空子集S₁和S₂；

2) 复制Parent1包含在S₁中的工件到Child1，Parent2包含在S₁中的工件到Child2，分别保留它们的位置；

3) 复制Parent2包含在S₂中的工件到Child1，Parent1包含在S₂中的工件到Child2，分别保留它们的顺序。

如图 4所示，Parent1={1,2,1,2,1,3,2,3,3}，Parent2={2,1,3,1,2,2,3,1,3}，S₁={2}，S₂={1,3}。最后生成的Child1={1,2,3,2,1,3,2,1,3}，Child2={2,1,1,1,2,2,3,3,3}。通过POX方法既能很好地保留父代的优良特征，而且产生的子代又能保证是可行解，因此是一种高效的交叉算子。

交叉结束后对最优的后代使用禁忌搜索算法，进一步探索邻域中更优的个体。

禁忌搜索算法中最重要的部分就是邻域结构，其中比较有效的结构有N4、N5、N6邻域结构^[20-22]。N4邻域结构要求把关键块内工序尽可能地移至块首或块尾位置；N5邻域结构仅交换块首和块尾两相邻工序以避免交换关键块内的工序；N6邻域结构是把内部工序移至块首之前和块尾之后。本文在N4、N5、N6邻域结构的基础上，采用混合的邻域结构，具体如下：

1) 关键块中含有两个工序，则直接交换。

2) 关键块中含有三个工序：

a) 非首工序移至块首；

b) 非尾工序移至块尾。

3) 关键块中含有四个及以上工序：

a) 随机选择部分非首工序移至块首；

b) 随机选择部分非尾工序移至块尾；

c) 首工序移至随机一个中间位置；

d) 尾工序移至随机一个中间位置；

e) 块首和块尾同时与其相邻工序交换位置。

通过以上的混合邻域结构，既能获得高质量的邻域解，又能使算法高效运行。

选择策略是禁忌搜索算法中下次迭代的开始。通常禁忌搜索算法会从非禁忌的最优解中选择最优的一个解作为下次算法的初始解，但在算法的后期容易陷入局部最优。本文禁忌搜索算法受模拟退火算法中以一定概率选择差解启发，提出一种新型选择策略，即下次初始解的产生是从L个非禁忌的最优解中随机选择，L是一个随迭代次数增加而增加的值，按式(5) 计算：

$L=iteration/cycle+1$

(5)

其中：iteration是算法运行代数，cycle是自定义的一个递增周期。通过此方法可使算法在初期加速收敛，而在后期扩大解的搜索范围，避免过早陷入局部最优。

禁忌搜索算法的流程如图 5所示。

当两个适应度值相同的个体被选择时，则对任一个体进行变异。变异算子的流程如图 6所示。首先随机选择K个位置，并且各个位置上的基因各不相同；再基于选择的K个基因作随机变换，从而得到变异个体。

同化操作是帝国主义竞争算法的核心。针对JSP特性，采用遗传算法的交叉思想实现进化；同时为了避免陷入局部最优，引入变异算子扩大搜索空间；最后再使用局部搜索能力强的禁忌搜索算法进一步优化后代，从而实现更全、更快的个体进化。当新的个体适应度值优于当前帝国时，则将更优个体取代旧帝国。此后该帝国下的同化操作将以新的帝国为基础，直到该帝国内的同化操作结束或有更优的后代取代该帝国。同化操作的整个流程如图 7所示。

2.3 帝国竞争

在帝国互相竞争之前，需要衡量各个帝国集团的力量，不仅需要考虑帝国的适应度值，还需要考虑其所拥有的殖民地对帝国集团力量的影响。而这个影响系数本文定义为ξ，第n个帝国集团的总力量定义为T.C._n，计算公式如式(6) 所示：

$\begin{align} & T.C{{.}_{n}}=Cost(imperialis{{t}_{n}})+ \\ & \xi \cdot mean\{Cost(colonies\text{ }of\text{ }empir{{e}_{n}})\} \\ \end{align}$

(6)

帝国竞争是实现帝国之间优胜劣汰的重要步骤。各帝国将基于各自的力量来争夺最弱帝国中的最弱殖民地。首先按式(7) 标准化各帝国集团的总力量：

$N.T.C{{.}_{n}}=T.C{{.}_{n}}-\underset{i}{\mathop{\max }}\,\{T.C{{.}_{i}}\}$

(7)

其中N.T.C._n代表第n个帝国集团标准化后的力量。基于标准化力量，各帝国集团能够获得殖民地的概率如式(8) 所示：

${{p}_{{{p}_{n}}}}=\left| N.T.C{{.}_{n}}/\left( \sum\limits_{i=1}^{{{N}_{imp}}}{N.T.C{{.}_{i}}} \right) \right|$

(8)

为了将最弱帝国下最弱殖民地按各帝国集团所应该拥有的概率来分配，首先基于之前计算的概率初始化一个向量P：

P=[p_p1,p_p2,…,p_pNimp]

然后随机初始化一个与向量P同样大小的向量R：

R=[r₁,r₂,…,r_Nimp]; r_1,r₂,…,r_Nimp~U(0,1) 最后通过将向量P与向量R相减来获得向量D:

D=P-R=[D₁,D₂,…,D_Nimp]=[p_p1-r₁,p_p2-r₂,…,p_pNimp-r_Nimp]

向量D中最大值对应的帝国将获得一个新的殖民地。

在每一次迭代中，将检查当前最弱帝国拥有的殖民地数，当其流失了所有的殖民地后，该帝国集团将被认为已崩塌，将删除该帝国。

算法终止准则是满足以下三个条件之一：一是找到最优解；二是算法达到最大迭代数；三是只剩一个帝国。帝国主义竞争算法的流程如图 8所示。

3 实验分析

为了验证本文算法的实际效果，在3.3 GHz CPU和4.0 GB内存的计算机上，采用Java编程进行实验；算法参数设置为：国家总数为100，其中初始帝国数为10，初始殖民地为90，帝国竞争次数为200，交叉概率P_c为0.8，变异率P_m为0.1，每代POX交叉次数T为200，每个实例求解20次。

本文算法选用13个经典实例与其他算法进行对比分析，这些实例在文献[22]中被认定为“难”级别，因此更具有代表性。 对比结果如表 2所示，其中：Instance是实例名；Size是由作业数和机器数表示的实例规模；BKS^*代表实例已知的最优解；C_max代表各算法求得实例的最优解；Re为C_max与BKS^*的相对偏差，即Re=(C_max-BKS^*)/BKS^*×100%； Av(Re)为各算法对13个实例相对偏差的平均值；“—”表示无对应数据。对比算法分别为文献[14]的混合人工蜂群(Hybrid Artificial Bee Colony,HABC)算法、文献[15]的文化基因算法(Memetic Algorithm,MA)、文献[17]的混合遗传算法(Hybrid Genetic Algorithm,HGA)和文献[18]的空闲时间邻域搜索遗传算法(Idle Time Neighborhood Search Genetic Algorithm,ITNSGA)。

从表 2中可以看出本文算法能够求解出13个实例中的3个最优解。与ITNSGA^[18]相比，除了结果相等的实例，并没有发现更优的实例，但与其他算法的对比可以发现各有优劣。进一步统计分析，本文算法与对比算法的求解优劣数统计对比如表 3所示。其中:AS表示本文算法求解的13个实例中优于对比算法的数量，LS表示本文算法差于对比算法的实例数，ES表示本文算法与对比算法相同的求解实例数。从表中可知，本文算法求解的实例质量是具有一定竞争力的，但是从LS列中也可以看出，本文算法除了优于MA算法外，与其他三个混合算法都有些差距，还有待完善。

根据表 2的Av(Re)结果也可以看出，本文算法的整体性能还有待进一步提高。

图 9给出了本文算法在解决FT10(10×10) 基准问题时的收敛曲线，从图中可以看出算法在第20代左右收敛到近似最优解，随后在第110代左右求得最优解，说明算法具有较快的收敛性。

在求解速度和平均结果方面，将本文算法与ITNSGA^[18]进行对比，结果如表 4所示，其中ITNSGA的求解环境是CPU主频为2.6 GHz、内存为2.0 GB的个人计算机。表 4中：pSize表示初始种群大小；Av(C_max)表示20次独立实验的平均结果；Av(t)表示20次独立实验的平均运行时间；γ是本文算法与对比算法在实例平均结果(Av(C_max))上的比值；λ是本文算法与对比算法在实例平均运行时间(Av(t))上的比值；Av(γ/λ)表示13个实例γ值的平均值和λ值的平均值；“—”表示无对应数据。从表 4中可见，尽管本文算法使用的CPU主频和内存较大，但在整体硬件环境相差不大的情况下，求得Av(λ)=0.34，说明本文算法的平均求解速度大约是对比算法的3倍，验证了本文算法的高效性。同时本文算法的初始种群在远小于对比算法初始种群的情况下，由Av(γ)=1可知两者算法的平均求解能力几乎相等，验证了算法的稳定性。

4 结语

本文针对作业车间调度问题展开研究，提出一种新型算法HICATS，混合了帝国主义竞争算法全局搜索能力和禁忌搜索算法的局部搜索能力。HICATS算法首先在帝国主义竞争算法的同化操作中融入了遗传算法的交叉算子和变异算子，有效地提高殖民地的学习能力；然后应用禁忌搜索算法进一步地优化后代，利用混合邻域结构使禁忌搜索更为有效；并借鉴模拟退火算法以一定概率接受差解的思想，提出一种新型选择策略克服禁忌搜索算法易陷入局部最优的缺陷。该混合算法在最后的实例验证中表现出了高效的求解能力，验证了算法的有效性和稳定性。今后将进一步研究该算法在大型实例中的设计与实现，进一步优化算法性能，并探索算法在相类似问题领域中的应用。