一种改进的新型布谷鸟搜索算法在工业流水作业中调度问题的优化应用

边 倩

（山西交通职业技术学院，太原 030031）

0 引言

随着制造业的不断发展，产品质量提升的同时面临很多工业操作优化问题，其中，n个作业必须在m台机器上按顺序处理，就是非常典型的车间流调度问题。在一个置换流车间调度问题中，所有机器上的作业必须以相同的顺序进行处理，证明了该问题是非常困难的。因此，不能用常规的线性方法来解决这些问题。在过去的几十年里，研究人员开发了许多启发式和元启发式的流程车间调度问题，以找到最优的解决方案。重要的建设性启发法是由Campbell等人（1970）、Dannenbring（1977）和Nawaz等人（1983）提出的。调度可以定义为在一段时间内分配资源，以执行一组任务来优化一个或多个目标函数。调度是一个决策过程。资源可以称为机器，任务可以称为作业。在当今的竞争环境中，有效的调度在制造业和服务业中都扮演着重要的角色。本文研究了具有n个作业和m台机器的置换流车间调度问题。

1 优化算法在工业流水调度优化中的应用发展

Murata等人（1996）利用遗传算法解决了流水车间调度问题。Nowicki和Smutnicki（1998）应用禁忌搜索算法解决了并行机器的流程车间调度问题。Nearchou（2004）利用混合模拟退火算法解决了流水作业调度问题。自Johnson（1954）提出流程车间调度问题以来，它一直是过去几十年中最著名的问题之一。Johnson开发了一个精确的算法来最小化最大完工时间来解决n个工作和2台机器的流水车间调度问题。流程车间调度问题是一个组合优化问题。流程车间调度问题可能被陈述排序流车间调度问题中最小化最大完工时间和总流水时间的退火算法。Haq等人（2006）提出了一种分散搜索算法，使流水作业问题的最大完工时间最小化。Onwubolu和Davendra（2006）提出了一种差分演化算法来解决最小化完工时间的流水车间调度问题。Ruiz和Stutzle（2007）提出了一种新的置换流车间调度问题的迭代贪婪算法。Liao等人（2007）提出了一种用于流水车间调度问题的粒子群优化算法。刘集等人（2008）开发了一种有效的混合算法，该算法基于粒子群优化算法，以最大限度地缩短连续机器之间有限缓冲区的置换流车间调度问题的完成时间。Saravanan 等人（2008）评估了分散搜索算法对流水车间调度问题最大完工时间最小化的性能。Kuo等人（2009）提出了一种基于混合粒子群优化模型、随机密钥编码和个体增强（IE）方案的高效流水作业调度算法。Oian et al。（2009）对无等待流水作业调度问题提出了一种有效的混合微分演化，使最大完工时间最小化。最近，Lei和Wang（2016）提出了一种有效的邻域搜索算法，用于调度批量处理机器车间流，使其时间最小化。

2 一种改进的新型布谷鸟搜索算法的提出

2.1 布谷鸟搜索（Cuckoo Search，CS）算法

布谷鸟搜索（Cuckoo Search，CS）算法是Yang and Deb（2009）最新开发的一种基于种群的元启发式算法。Yang和Deb（2010）使用CS算法解决了各种优化问题。Noghrehabadi等（2011）采用幂级数和CS优化算法计算微固定-固定梁的屈曲。Valian等（201 1）将改进的CS算法应用于前馈神经网络的训练两个基准分类问题。他们提出了一种调整CS参数的正确策略，Divya等人（2011）开发了一种基于布谷鸟的粒子方法来实现高效节能的无线传感器网络和多模态目标函数，类似于许多元启发式算法，CS中的初始解也是随机生成的。但本文采用Nawaz等人（1983）开发的一种称为NEH算法的建设性启发式算法来生成初始解之一，以提高解的质量。此外，本文还对CS算法的参数进行了调整，提高了算法的效率。为此，本文提出了一种改进的混合布谷鸟搜索（IHCS）元启发式算法，使排序流车间调度问题的最大完工时间最小化。

CS算法的灵感来自于一些杜鹃物种的专孵育寄生行为，以及自然界中一些鸟类和果蝇的飞行行为。以下三条理想化的规则被考虑用于描述该算法：一是每只杜鹃一次产一个蛋（解决方案），并将蛋放在随机选择的巢中；二是最好的巢和高质量的蛋（解决方案）将进行到下一代；三是杜鹃下的蛋被寄主鸟发现的概率是Pa，然后鸟巢就建好了。对于最小化问题，质量或适应度函数值可能是目标函数的倒数。鸟巢中的每个蛋代表一个解决方案（一个新的杜鹃蛋代表一个新的解决方案）。较好的解决方案正在取代较差的解决方案。CS算法的伪代码在图1给出。

图1 布谷鸟搜索（Cuckoo Search，CS）算法伪代码示意

2.2 新型改进的杂交杜鹃搜索 （IHCS） 元启发式算法构架

一般情况下，初始解是随机生成的。为了提高解的质量，用构造启发式算法生成一个解。上节给出了重要启发式算法的构造。其中，采用Nawaz等人（1983）提出的一种建设性启发式算法，即NEH启发式算法生成一个初始解，其余解随机生成。CS算法由Pa（接受概率）、α（步长）等参数组成，这些对于获得更好的解非常重要。Valian等人（2011）讨论了这些参数值的影响。在文献中，CS算法的这些参数保持不变。在初始步骤中定义了参数Pa和α，并且不能更改这些值。由于参数的变化会降低算法的效率，因此本文中的参数都不是常数。

3 新型改进的杂交杜鹃搜索 （IHCS） 元启发式算法工业优化应用

3.1 问题描述

本文研究了流水车间调度问题。车间调度环境由m台成批的机器和n个作业组成。每个作业必须按照特定的顺序通过机器进行处理。此外，每个作业的处理将是连续的流程车间调度。该问题目标是最小化最大完工时间。最大完工时间可以定义为最后一项工作离开系统的完成时间。最大完工时间最小化对缩短生产时间和提高系统利用率具有重要意义。流程车间调度环境如图2所示。

图2 本文优化流水车间调度问题模型简图

流水车间调度问题假设：所有作业和机器在零时都可用；这些操作不是可抢占的；每台机器一次只能处理一项工作；每个作业一次只能在一台机器上处理；处理时间是已知的，并且是固定的；作业的设置时间包含在处理时间中，不依赖于操作的顺序；作业的操作顺序在每台机器上都是相同的，必须确定公共顺序；机器在整个调度期间都可用。

3.2 计算与优化结果

IHCS元启发式算法是用c++编写的，在PC上运行，CPU是英特尔酷睿2.4 GHz，2G。随机选择20个基准问题。测试问题涉及两个机器号值（m = 15，20）和4个作业编号值（n = 20，30，40，50）。并与由Demirkol等人（1998）提出的一个蚁群优化元启发式算法（MHD-ACS）进行了比较。这里不考虑计算时间比较不同的研究人员使用不同的软件硬件的配置可能会有变化。根据得到的结果和百分比改进后的IHCS算法提供比其他元启发式算法更好的结果。IHCS获得的改进百分比算法如图3所示。

图3 改良杂交杜鹃所获得的改良百分率

本文首次提出了一种最大完工时间最小化的置换流车间调度算法。在大多数的元启发式算法中，解是随机产生的。但在这项工作中，一个建设性的启发式称为NEH启发式纳入初始随机解决方案，以提高解决方案的质量。同时对CS算法的参数进行了优化，得到了较好的结果。文中提出的IHCS算法已经在一组基准问题上进行了测试，并与已有的结果进行了比较，证明了算法的有效性。

4 结束语

综上所述，这项工作可以扩展到许多方面。该算法只适用于单目标流水车间调度问题，可以推广到多目标流水车间调度问题。该算法也可用于解决实际工业调度问题。未来我们可能会对混合流车间调度问题进行研究。与到期日相关的性能度量的调度问题和包含设置时间的问题可能是这项工作的一些可能范围。