作业车间调度问题的布谷鸟搜索算法求解

姚远远，叶春明

上海理工大学 管理学院，上海 200093

1 引言

作业车间调度问题（Job-shop Scheduling Problem，JSP）是许多实际生产调度问题的简化模型，具有广泛应用背景，譬如生产制造、交通规划、邮电通信、大规模集成电路设计等问题。作为一类满足任务配置和顺序约束要求的资源分配问题，JSP已被证明是一个典型的NP-hard问题[1]，它的求解难度远大于流水线调度问题，针对其算法的研究一直是学术界和工程界共同关注的重要课题。目前，制造业的竞争日益激烈，制造企业正朝着有不同完工时间和产品要求的多类型、小批量的生产模式发展。如何利用现有资源，满足加工任务所需各种约束，使所有任务能尽量按时完成，即如何有效地解决JSP，成为一个十分现实和迫切的问题。高效调度算法，可以大大提高生产效益和资源利用率，从而增强企业的竞争能力，因此对JSP的研究有非常重要的理论和实用价值。

目前关于高效算法的研究与设计仍然是生产调度领域的重要研究内容，鉴于作业车间调度问题的复杂性，通常研究该问题的方法可分为三种类型：精确方法、启发式算法和现代元启发式算法。具体包括列举法（如分支定界策略）、基于优先规则的构造性启发式方法、移动瓶颈法、神经网络方法、Lagrangian松弛法、遗传算法、模拟退火、禁忌搜索、蚁群算法、粒子群算法、萤火虫算法以及各种混合调度算法等。其中仿生智能群算优化算法由于能够在较短时间内获得较高质量的解，广泛用于求解各种生产调度问题，成为复杂优化问题的有效解决途径和国际研究热点。

2009年，剑桥大学Yang和拉曼工程学院Deb提出了一种新型现代元启发式算法——布谷鸟搜索（Cuckoo Search，CS）算法[2]，该算法基于某些布谷鸟种类的巢寄生（brood parasitism）繁育行为和鸟类、果蝇等的莱维飞行（Lévy flight）行为特征提出，具有控制参数少和能够有效保持局部搜索和全局搜索之间平衡两个优点，已有研究表明该算法性能优于粒子群算法和遗传算法。目前，利用布谷鸟搜索算法求解优化问题的研究还处于初步阶段，其主要用于解决工程设计优化问题[3-4]。最近，Yang和Deb[5]又提出一种多目标布谷鸟搜索算法解决工程设计优化问题。纵观目前国内外关于CS算法的研究成果，多集中于对连续优化问题的研究，然而应用CS算法解决离散问题的研究非常少见，仅有少数几篇，如Ouyang Xinxin等[6]提出一种离散布谷鸟搜索算法解决球面旅行商问题，Burnwal等[7]提出基于布谷鸟搜索的方法解决柔性制造系统的调度优化问题，其目标函数是最小化延期惩罚成本和最大化机器时间利用率，但是还未见到采用该算法进行作业调度问题的研究。因此，本文将尝试应用CS算法解决作业车间调度问题。

本文分析了布谷鸟搜索算法的优化机理，在此基础上应用该算法求解作业车间调度的最小化最大完工时间问题，并介绍了具体的编码方式和求解作业车间调度问题的算法流程，通过仿真实例验证了算法的正确性和有效性，并对其在离散组合优化领域的优化性能进行评估。本文对生产调度问题高效调度算法的研究，有利于企业在生产过程中进行合理有效地组织与安排，大大提高生产效益和资源利用率，提升生产系统的操作最优性，并获得显著经济效益。

2 作业车间调度问题的数学描述

作为一类典型的加工调度问题，Job-shop调度问题可描述为[8]：n个工件在m台机器上加工，Oij表示第i个工件在第j台机器上的操作，相应的操作时间Tij为已知，事先给定各工件在各机器上的加工次序（称为技术约束条件），要求确定与技术约束条件相容的各机器上所有工件的加工次序，使加工性能指标达到最优。除技术约束外，通常还假定每一时刻每台机器只能加工一个工件，且每个工件只能被一台机器所加工，同时加工过程为不间断，机器间缓冲区容量为无限。若各工件的技术约束条件相同，一个Job-shop问题就转化为较简单的Flow-shop问题。当各机器上各工件的加工次序也相同，则问题可进一步转化为置换Flow-shop问题。

作业车间调度问题的求解远复杂于流水线调度问题，主要原因可归纳为如下几点：（1）由于调度解的编码很复杂，使搜索操作难以达到高效的设计效果；（2）大量的调度解，在不考虑可行性的情况下，n个工件m台机器的问题包含(n!)m种不同的排列；（3）工艺技术约束条件使得必须考虑解的可行性；（4）调度解的性能指标计算需要耗费大量时间，一次性能评价相当于一个离散时间的仿真过程；（5）缺少搜索空间的结构信息，通常存在多个分布无规则的局部极小解，最优解往往被大量相邻极小解所包围。

关于JSP的求解往往要考虑生产调度实际期望达到的优化指标，问题的目标函数是这些优化指标的抽象表示，JSP模型的目标函数随着企业所重点考虑因素的不同而改变。通常JSP所考虑的优化目标有三种[9]：任务的最大完工时间最短、任务的总的拖期最短和任务的提前/拖期惩罚代价最小。本文所考虑的优化目标是任务的最大完工时间最短，即完成所有任务所需的时间最短，对该指标的优化有利于提高单位时间内设备的利用率，从而提高生产的实际效率。常见的作业车间调度问题基本数学模型有三种[9]：整数规划模型、线性规划模型和析取图模型。本文采用Bake[10]给出的JSP整数规划模型，n/m/G/Cmax调度问题的数学模型描述如下：

其中，式（1）表示目标函数，即Makespan；式（2）表示工艺约束条件决定的每个工件的操作先后顺序；式（3）表示加工每个工件的每台机器的先后顺序；式（4）表示完工时间变量约束条件；式（5）表示指示变量可能的取值大小。上述公式中所涉及的符号含义如下：Cik和pik分别为工件i在机器k上的完成时间和加工时间；M是一个足够大的正数；aihk和xijk分别为指示系数和指示变量，其含义为：

3 布谷鸟搜索算法的优化机理

3.1 算法仿生原理

在自然界中，布谷鸟通过巢寄生的行为方式进行繁育，巢寄生是一种鸟类将卵产在其他鸟的鸟巢中，由其他鸟（义亲）代为孵化和育雏的一种特殊的繁殖行为。其优点是最大限度地提高鸟类成功繁殖的能力。在宿主的选择上，布谷鸟在繁殖期寻找与孵化期和育雏期相似、雏鸟食性基本相同、卵形与颜色易仿的宿主，多为雀形目鸟类。而且它每飞到一个巢窝里只产一个卵，布谷鸟在产卵前常把宿主一枚卵移走，或全部推出巢外，迫使宿主重新产卵，来增加其卵被孵化的概率。巢寄生行为对宿主种群的影响大小不一，多数情况都会使宿主鸟繁殖率下降。为了繁衍宿主鸟也进化出一套反寄生行为，宿主一旦识别出寄生卵，就将其扔出或弃巢，在其他地方另建新巢。巢寄生的协同进化表现在长期的适应选择中，寄生卵的大小、颜色、卵斑等特征都与其特定的宿主相似，这有利于降低其卵被抛弃的可能性从而提高繁殖率[11]。

在自然界中，很多动物以随机或者类似随机的方式觅食。通常动物的觅食路径实际上是一个随机游动的过程，随机游动是粒子的下一个位置只依赖于当前位置和转移概率的一个马氏链。不同研究已表明很多动物和昆虫的飞行行为表现出莱维飞行的典型特征[12]。莱维飞行属于随机游动的一种，在莱维飞行中步长分布满足一个厚尾的稳定分布，由莱维飞行产生的随机步长时大时小，在搜索过程中，大的步长易于搜索全局最优，小的步长有助于提高搜索精度。目前莱维飞行行为已被用于优化和最优搜索领域，在智能优化算法中采用莱维飞行，能扩大搜索范围、增加种群多样性，更容易跳出局部最优点[13]。另外研究还表明在不确定环境中莱维飞行可以最大化资源搜索效率。

3.2 算法的数学描述与分析

CS算法是一种随机全局搜索算法，像GA、PSO一样，CS是基于群体的优化算法，在自然界中，布谷鸟以随机或是类似随机的方式寻找适合自己产蛋的鸟窝位置，为了便于模拟布谷鸟的寻窝方式，Yang和Deb提出了以下3个假设[2]：（1）布谷鸟一次只产一个蛋，并随机选择鸟窝位置进行孵化；（2）在随机选择的一组鸟窝中，最好的鸟窝将会被保留到下一代；（3）可利用的宿主鸟窝数量n是固定的，宿主发现一个外来鸟蛋的概率为Pa∈[0，1]。Pa可以近似看作n个位置较差的鸟窝被随机产生的几个新鸟窝替换的概率，通常设Pa为一个固定值，本文取Pa=0.25。基于以上3条假设，布谷鸟搜索算法的基本步骤如下所示。

式中表示第i只布谷鸟在第t代的鸟窝位置，α＞0是步长大小参数，与所研究问题范围有关，此处取α=0.1可以使算法更高效。参数S是随机游动的步长，本文采用Mantegna算法执行莱维飞行[14]，步长S计算公式如下：

其中，β是一个[1，2]之间的参数，此处取β=1.5，u和v服从正态分布如下所示：

其中

在局部搜索阶段，用随机游动（点和矩阵的乘积：随机步长大小×概率矩阵）产生的新鸟窝替代位置较差部分的鸟窝，用参数Pa表示位置较差鸟窝被发现的概率，每一鸟窝按条件更新位置，如下概率矩阵所示：

其中，随机数Ra∈[0，1]，表示鸟窝主人发现外来鸟蛋的概率，Pi，j表示第i个鸟窝的第j维变量被发现的概率。具体操作如下程序所示（K是一个n行1列的矩阵，元素取值为1或0，取决于随机值Ra是否大于Pa，当元素取0时，下面公式运算时，鸟窝位置不移动，相当于乘零；当元素取1时，移动鸟窝位置）：

4 基于布谷鸟搜索算法的作业车间调度问题求解

4.1 编码方式

本文在求解JSP问题时采用基于工序的编码规则，即染色体由n×m个基因组成，它们表示一个工序的排列，在这个工序排列中每个工件号均出现且只能出现m次。例如4工件×3机器的示例，其染色体是121334412234。因此它对应的工序加工序列为：

其中Ji，j表示第i个工件的第j道工序，j表示工件i出现的次数。因此表达的意思为先加工第1个工件的第1道工序，再加工第2个工件的第1道工序，再加工第1个工件的第2道工序，再加工第3个工件的第1道工序，依此类推，最后加工第4个工件的第3道工序。因此在解码时就可以按照工件的出现顺序转化为一个调度方案。

4.2 算法流程

综上所述，求解作业车间调度问题的布谷鸟搜索算法流程如下（见图1）：

（1）初始化算法基本参数：设置鸟窝个数n、宿主发现外来鸟蛋的概率Pa，以及最大迭代次数MaxT或搜索精度ε。

（2）随机初始化鸟窝位置，按照4.1节所述基于工序的编码规则将鸟窝位置转换为工序排列，计算各鸟窝位置对应的目标函数值（本文目标函数为minCmax，根据公式（1）～（7）），并获得当前最优鸟窝位置。

（3）开始迭代，保留上代最优鸟窝位置不变，按位置更新公式（8）通过莱维飞行对其他所有鸟窝位置进行更新（即全局搜索），从而随机产生下一代鸟窝，并评估位置更新后每个鸟窝的目标函数值，记录当前最优鸟窝位置。在这一阶段中，具体通过公式（9）～（11）采用Mantegna算法执行莱维飞行。

（4）在局部搜索时对每一鸟窝位置按条件进行更新：用一个随机数Ra作为鸟窝主人发现外来鸟蛋的概率并与Pa进行比较，若Ra＞Pa，则随机改变鸟窝位置，否则保持原来位置不变（根据公式（12）进行判断），并计算位置移动后每个鸟窝的目标函数值，记录当前最优鸟窝位置。

（5）比较本次迭代和上一次迭代鸟窝位置的最优值，如果新的最优值小于原最优值，则把新的最优值赋予当前最优鸟窝位置的目标函数值。

（6）当达到最大搜索次数或满足搜索精度时转入（7），否则，转（3）进行下一次搜索。

（7）输出最优调度值和对应的调度解方案。

5 仿真实验

图1 CS算法流程图

鉴于JSP的重要性和代表性，许多研究工作者设计了若干典型问题（benchmarks），用以测试和比较不同方法的优化性能，典型的Job-shop调度问题有FT类、LA类、ABZ类、ORB类、SWV类、YN类、TD类和DMU类等，其中以FT类、LA类和TD类调度问题的研究居多。LA类问题由Lawrence（1984）给出，包括40个典型问题，命名为LA1～LA40，对应8个不同规模，每一规模包含 5个问题，分别为10×5，15×5，20×5，10×10，15×10，20×10，30×10，15×15。为了便于比较并验证布谷鸟搜算算法（CS）求解JSP的性能，本研究随机选取LA类10个基准问题作为算例进行仿真测试，并与基本粒子群算法（Basic Particle Swarm Optimization，BPSO）和萤火虫算法（Firefly Algorithm，FA）所得结果进行比较。

实验仿真环境为：操作系统Windows 7，处理器主频2.30 GHz，CPU Intel®CoreTMi3-2350M，和内存4 GB，采用MATLAB R2010a实现算法编程。算法参数设置如下：布谷鸟搜索算法中，鸟巢个数n=30，宿主发现外来鸟蛋的概率Pa=0.25；萤火虫算法中，萤火虫数n=30，光强吸引系数γ=1.0，最大吸引度β0=1.0，步长因子α=0.2；基本粒子群算法中，粒子数n=30，学习因子c1=0.8，c2=1.2，惯性权重w=0.5。最大迭代次数均为MaxT=300，每种算法均独立运行30次，测试结果如表1所示。

表1中，BPSO代表基本粒子群算法，FA代表萤火虫算法，CS是布谷鸟搜索算法。c*为问题已知最优值；Δmin为算法运行30次得到的最小完工时间；Δmax为最大完工时间；Δavg为平均完工时间；Δstd为完工时间标准方差（其中Δavg、Δstd为四舍五入后所得结果）；加粗的数字代表最优值。为比较各算法性能，本文对随机选择的LA类10个测试问题的4项指标进行衡量。从测试数据可以看出，CS算法的测试结果整体上效果优于BPSO和FA算法。其中CS算法有7个问题找到最优值，BPSO算法有6个问题找到最优值，FA算法仅有4个问题找到最优值。在独立运行30次中，CS算法对LA05、LA06、LA10和 LA14这4个问题都能达到100%的寻优率，其他两种算法均未能达到100%寻优率。虽然BPSO寻优能力优于FA算法，但是鲁棒性较差。另外，程序运行中还发现三种算法的运行时间是FA＜CS≅BPSO，对于每一个算例，FA运行耗时远少于其他两种算法，CS和BPSO的运行时间基本相同。

表1 BPSO、FA和CS三种算法测试结果分析 min

图2 LA01问题三种算法各独立运行30次的最优结果分布图

为了更深入分析CS算法解决作业车间调度问题的效果，本文重点对LA01问题具体分析（LA01问题时间加工矩阵见表2，该问题工艺约束见表3）。图2是三种算法各独立运行30次的最优结果分布图，算法参数设置如前面所述，由图可见，独立运行30次中，就寻优能力而言，CS算法有14次击中已知最优值，BPSO算法仅1次击中最优值，FA算法离最优值尚有一段距离。从解的稳定性方面考虑，CS算法鲁棒性最强，其最坏情况与最好情况差值为20，而BPSO和FA分别为164和67。

表2 LA01问题时间加工矩阵 min

表3 LA01问题工艺约束

为了验证CS算法的收敛性，基于LA01问题，将CS算法独立运行10次，每次迭代300代，鸟窝个数为30，Pa=0.25，10次独立运行的最优结果分别是：666、675、672、666、668、678、666、672、678和673，寻优曲线见图3，其中有3次结果最好，最好情况为666，最坏情况为678，平均值为671.40，标准方差为4.742 2。基于CS算法求解出的LA01问题最优解调度方案见表4。

图3 基于CS算法的LA01问题运行10次寻优曲线图

图4 CS算法当迭代次数分别为300和1 000时最优结果分布

表4 CS算法求解出的LA01问题最优解调度方案

从表1还可以发现，三种算法对于LA17和LA20这种规模稍大的10工件×10机器问题似乎无能为力，均不能搜索到最优值，但是相比较而言CS算法的寻优结果更接近已知最优值。为了测试参数设置对寻优能力的影响，以LA20为例进行实验，分别设置最大迭代次数为300和1 000两种情况，其他参数保持不变。实验结果如图4所示，由图可见，当迭代次数为1 000时，运行结果普遍好于300次的结果，但是对于寻找最优值方面见效不大。本文还尝试了测试鸟窝数量n对寻优能力的影响，发现增大鸟窝数量将大大增加程序运行时间，而且也不一定能获得更优值。总之，要解决大规模的作业车间作业调度问题还需对布谷鸟搜索算法的优化机理进行改进，这也是本文进一步的研究方向。

6 结束语

本文采用一种新型的仿生智能群算优化算法——布谷鸟搜索算法求解最小化最大完工时间的作业车间调度问题。通过仿真实验，验证了该算法与基本粒子群算法和萤火虫算法相比，具有实验参数少、收敛速度快、鲁棒性强等优点。虽然对于较大规模的Job-shop生产调度问题，布谷鸟搜索算法不能搜索到已知最优值，但是相比其他两种算法，更接近最优值。表明了布谷鸟搜索算法在解决生产调度问题中的可行性和有效性，并有着广泛的应用前景。今后CS搜索算法可进一步用于研究具有不同约束条件的多目标作业车间调度问题；也可以将CS算法和其他智能优化算法进行混合，从而产生更高效的混合优化算法。

[1]Garey M R，Johnson D S，Sethi R.The complexity of flowshop and jobshop scheduling[J].Mathematics of Operations Research，1976，1（2）：117-129.

[2]Yang Xinshe，Deb S.Cuckoo search via Lévy flights[C]//2009 World Congress on Nature&Biologically Inspired Computing.New York：IEEE Publications，2009：210-214.

[3]Gandomi A H，Yang Xinshe，Alavi A H.Cuckoo search algorithm：a metaheuristic approach to solve structural optimization problems[J].Engineering with Computers，2013，29（1）：17-35.

[4]Durgun I，Yildiz A R.Structural design optimization of vehicle componentsusing cuckoo search algorithm[J].Materials Testing，2012，54（3）：185-188.

[5]Yang Xinshe，Deb S.Multiobjective cuckoo search for design optimization[J].Computers&Operations Research，2013，40（6）：1616-1624.

[6]Ouyang Xinxin，Zhou Yongquan，Luo Qifang，et al.A novel discrete cuckoo search algorithm for spherical traveling salesman problem[J].Applied Mathematics& Information Sciences，2013，7（2）：777-784.

[7]Burnwal S，Deb S.Scheduling optimization of flexible manufacturing system using cuckoo search-based approach[J].The InternationalJournalofAdvanced Manufacturing Technology，2013，64（5/8）：951-959.

[8]王凌.智能优化算法及其应用[M].北京：清华大学出版社，2001：10-100.

[9]罗亚波.作业系统调度优化理论与方法[M].武汉：华中科技大学出版社，2011：1-10.

[10]Baker K.Inroduction to sequencing and scheduling[M].New York：John Wiley&Sons，1974：1-15.

[11]Payne R B，Sorenson M D，Klitz K.The cuckoos[M].New York：Oxford University Press，2005：1-20.

[12]Brown C T，Liebovitch L S，Glendon R.Lévy flights in Dobe Ju/'hoansi foraging patterns[J].Hum Ecol，2007，35：129-138.

[13]Shlesinger M F.Search research[J].Nature，2006，443：281-282.

[14]Yang Xinshe.Nature-inspired metaheuristic algorithms[M].2nd ed.Frome：Luniver Press，2010.