求解模糊作业车间调度问题的混沌乌鸦搜索算法*

刘 凯，黄辉先，赵 骥,2

(1.湘潭大学 信息工程学院,湖南 湘潭 411105;2.清华大学 清华大学国家CIMS工程技术研究中心,北京 100084)

0 引 言

作业车间调度问题(JSSP)是一个典型的NP-hard问题[1]，在过去的五十几年里，一直受到许多学者的关注与研究，其研究成果被广泛应用于生产，工程管理，计算机等领域，因此研究JSSP具有重要的学术和实际意义。而作为JSSP的扩充，模糊作业车间调度问题(fuzzy job-shop sche-duling problem,FJSSP)在JSSP的基础上加入不确定性条件如模糊加工时间，使得问题更接近真实的生产情况，更具研究价值。Tsujimura Y等人[2]最先用遗传算法(genetic alorithm,GA)解决带模糊加工时间的FJSSP，Sakawa M等人[3]将GA进行了改进并应用于具有模糊加工时间和模糊交货期的FJSSP，Niu Q等人[4]通过将GA中的交叉和变异算子结合到粒子群优化(PSO)算法中对PSO进行改进并应用于FJSSP中，最后和GA进行比较验证了算法的优越性。Hu Y等人[5]用改进的差分进化算法(DE)对FJSSP进行了求解。Bustos-Tellez C A等人[6]利用线性规划(LP)的方法对FJSSP建立了模糊LP模型。然而，相比JSSP，对于FJSSP的研究还远远不够，并且多元启发式方法容易陷入局部最优解，而LP方法又在求解大规模问题上太过复杂，难以计算，所以仍须研究人员能够提出更多更好的解决方法来解决问题。

乌鸦搜索算法(crow search algorithm,CSA)是Askarzadeh A[7]提出的新群体智能算法。Sayed G I等人[8]对该算法引入了混沌机制,即混沌乌鸦搜索算法(chaotic crow search algorithm,CCSA)并成功应用于二进制特征选择问题，最终对比发现该算法具有优秀的全局优化能力和求解速度。刘雪静等人[9]将CCSA应用于0—1背包问题上同样得出其具有良好的全局寻优能力和收敛速度，这些应用都表现出CCSA值得在更多不同领域被研究，因此，本文提出将CCSA应用于求解带模糊加工时间的FJSSP上，并且通过对问题和算法的研究将算法做了改进，最后进行了对比仿真实验，验证了本文所提出的改进策略的有效性以及所提算法能够有效求解FJSSP。

1 FJSSP

FJSSP的描述和数学模型可参考文献[4]。而目标函数选用minCmax=max{C1,C2,…,Cj,…,Cn}，即最小化最大完成时间，其中Cj为工件j的模糊完成时间。

FJSSP中引入模糊三角数(triangular fuzzy number ,TFN)表示问题中的模糊加工时间[3]，TFN运算比较参考文献[3]。其中考虑到FJSSP的实际意义，本文提出如式(1)所示的取大运算方式

C=max{A,B}

=(max{a1,b1},max{a2,b2},max{a3,b3})

(1)

图1为两个TFN的取大操作图

图1 TFN取大操作准则

2 CCSA

CSA是受到乌鸦群藏匿食物的行为启发而来的[7]，而CCSA在CSA的基础上引入了混沌序列。假设乌鸦群的数量为N，yi,t为乌鸦i在第t次搜索之后的位置，此时它所找到的最佳藏匿食物的位置称为乌鸦的记忆位置，记为Mi,t，其中,i=1,2,…，N;t=1，2…，tmax,tmax表示最大搜索次数。算法主要步骤如下：

步骤1 初始化。初始化yt,1，Mi,1=yi,1。

步骤2 搜索新位置。群体中每只乌鸦会随机选择另一只乌鸦作为目标进行位置搜索。假设在第t次迭代中，乌鸦i进行跟随的是乌鸦z，则这时会出现两种情况：

1)乌鸦z没有发现自己被乌鸦i跟随

乌鸦i将靠近乌鸦z的记忆位置Mz,t，通过式(2)更新乌鸦i的位置

yi,t+1=yi,t+Ci×fl×(Mz,t-yi,t)

(2)

式中fl为表示搜索步长；Ci∈(0,1)，为混沌序列的第i个值，该混沌序列由Circle Map[10]来产生，其映射公式为

c=0.5,d=0.2

(3)

2)乌鸦z发现自己被乌鸦i跟随了

此时乌鸦i无法靠近乌鸦z的记忆位置，只能随机找一个新位置来更新自己的位置。

根据上述两种情况的描述可将乌鸦i的位置更新公式总结如下

(4)

式中APi,t为乌鸦z在第t次搜索时能够发现被乌鸦i跟随的概率。

步骤3 更新记忆位置。群体中的乌鸦在每次搜索更新完自己的位置之后，通过一个评价函数Fn判断是否替换记忆位置，具体更新公式为

(5)

步骤4 重复步骤(2)～步骤(3)搜索tMax次。

步骤5 输出优化结果。乌鸦群中最优的记忆位置即为算法的最终优化结果。

3 FJSSP的CCSA

基于针对FJSSP特点设计出可应用于求解FJSSP的CCSA。算法的编码策略采用基于工序的编码[2]。

3.1 修补与变异

由于CCSA的变量是连续的，要想求解FJSSP这类离散问题便需设计一个修补算子对位置更新公式计算出的新解进行修补操作，使算法能够在正确的解空间中进行搜索。同时，由于CCSA单单依靠式(4)进行搜索过于单一，无法对目标个体的邻域充分搜索。因此引入变异算子以概率Pmutate将新解进行变异，以此丰富个体的邻域搜索行为。变异方式采用自身交换策略：随机选择解中的两个编码不同的位置进行交换。具体算法描述如下：

算法1新解的修补与变异算法

输入：CCSA按式(4)计算出的新解，ynew。

输出：经过修补与变异之后的解，ymutate。

1)将ynew向上取整得到ycell。

2)分别统计ycell中范围在工件号内的各个编号出现的次数。

3)将ycell中小于1的数从小到大修正为工件号统计次数小于工序数的最小工件号，同理将大于工件数的编号从大到小修正为工件号统计次数小于工序数的最大工件号，得到ycorrect。

4)在ycorrect中随机选择两个不同的工件编号进行交换，得到ymutate。

3.2 多样最优个体集

原始CCSA中引导更新的目标个体为随机选择，为提高乌鸦的搜索效率并保证种群的多样性，本文提出基于相似性度量的多样性最优选择策略来优化和丰富目标集。

为了评估两个个体间的相似度，本文引入经常被用于信息检索当中的基于余弦(cosine)定理[11]的相似性度量方式。用X和Y来表示两个个体，其中用xi表示X的第i个分量，yi表示y的第i个分量，则

(6)

由于在FJSSP中，个体X和Y中的每个元素都是正整数，因此,任何两个个体之间的cosθ都在[0,1]之间，数值越接近1，则表示X和Y的相似度越大。因此，基于余弦相似度的多样最优个体集的选择算法如算法2。

算法2多样最优个体集选择算法

输入：第t代群体的记忆位置，Mt；最优的记忆位置个数，sp；多样的记忆位置个数，div；相似度阈值，R。

输出：多样最优个体目标集，set。

1)随机生成一个目标集set。

2)从Mt中选择评价值为前sp名的个体逐个对set进行随机替换。

3)从剩下的Mt中按顺序选择一个与Mt中所有个体的相似度平均值低于R的个体，然后随机替换set中除步骤(2)选中之外的个体。

4)重复步骤(3)j次，直到j等于div或者Mt遍历完成。

5)返回目标集set。

3.3 基于机器空闲时间缩小的搜索方法

由于FJSSP解空间极大且复杂，使得CCSA群体的搜索效率不高、收敛慢。为了进一步提升算法的搜索效率，本文提出一种基于机器空闲缩小的搜索方法以结合到CCSA中。在描述方法的具体步骤之前，先有如下定义：

令Stw和Etw分别表示任务w的开始时间和结束时间。

定义待优任务、待优工件、待优工序。假设w1和w2为机器队列中连续的两个任务，若有Etw1

该搜索方法是通过优先加工待优工序的前续工序所在的任务，使得待优任务的可开始加工时间提前来缩小机器的空闲时间。对于某个可行解，随机选择一个机器，对该机器的加工队列进行遍历(首个任务不进行调整)，判断每个任务是否为待优任务，若是则以一定的概率Prst进行空闲时间缩小，缩小的算法如算法3。

算法3空闲时间缩小算法

输入：问题的一个可行解，S；机器号，m；待优任务号，w。

输出：调整之后的新解，Snew。

1)寻找w所属工件和工序分别记为Jw和pnw。

2)判断Jw的工序pnw-1所在任务的可开始时间是否比当前开始时间小且不在自身机器队列的队首，若是则该任务为可提前任务，执行步骤(3)，否则执行步骤(6)。

3)将该可提前任务和所在队列中的前一个任务交换，刷新调度方案，若w之前的空闲时间为零，则退出计算返回新解Snew，否则执行步骤(4)。

4)若待缩小的空闲时间减少则执行步骤(5)，否则放弃此次交换并退出计算返回结果Snew。

5)若pnw-1>1，则保留此次交换，然后以Snew作为算法3的输入递归执行，否则保留交换，退出计算返回Snew。

6)令pnw=pnw-1，若pnw>1则重新执行步骤(2)。

7)返回结果Snew。

为避免因为引入规律导致种群个体过于集中，陷入局部最优，本文采用隔代搜索，每间隔eg代从种群中选择N×sr,(0

3.4 算法流程

根据上述设计，改进后的算法总体流程如图2所示。

图2 算法总体流程图

4 实验与分析

为了验证算法对于FJSSP的有效性，本文从文献[13]中选取了Job Shop调度中的5个典型的Benchmark并做模糊化的处理，模糊化的方式为T=(t-rand,t,t+rand)，其中rand表示小于t的随机整数，且当t越大时，rand占t的比重越小。同时为了方便比较，结果比较都采用最大模糊完成时间的中间数作为参考。

实验环境：算法编程平台为MATLAB R2016b,操作系统为Windows7_64位,CPU为Intel Core i7-7500U@2.70 GHZ,内存为8 GB。

本文分别将原始的CCSA,加入变异算子和多样最优个体集的XD-CCSA(X-diversity-chaotic crow search algorithm),本文所提算法RST-CCSA(reducing spare time-chaotic crow search algorithm)以及GA在5个实例上测试了各10次。所有测试中种群数量都设置为N=200，均进化2 000代，其余参数AP=0.2，fl=2.0，变异概率Pmutate=0.28，目标集中最优个体数sp=5，低相似度个体数div=20，相似度阈值R=0.86，基于机器空闲时间搜索方法的参数eg=50，sr=0.4，Prst=0.88。

实验结果如表1所示，表中给出了10次测试所得的最优值、最差值、平均值以及所占CPU平均值时间，表中各个实例编号下面的加粗数据为BKS值，即已知文献中的最优解。

表1 各算法的计算结果

从表中数据可看出相较于改进前的CCSA，XD-CCSA的寻优能力得到了加强，说明本文设计的变异算子和多样最优个体集为CCSA的搜索带来了更多的信息，增强了种群的多样性，提高了算法的寻优能力。而RST-CCSA相较于包括GA在内的其它三个，其寻优能力最强，在FT06,FT10和LA11上达到BKS值，且在FT10上只有RST-CCSA达到了best know solution(BKS)值，在FT20和LA16上虽没有达到BKS值，但较于GA来说表现更好，说明本文提出的基于机器空闲时间缩小的搜索方法能够在进化过程中提高种群个体的搜索能力，从而整体提高算法的寻优能力。但不足的是需牺牲一定的算法效率。从表2中数据可看出，RST-CCSA相较于CCSA来说CPU time消耗都比较大，但是较于GA来说，RST-CCSA的时间消耗还是可以接受的，甚至在FT06这种规模较小的问题上消耗要小于GA。

表2 各算法CPU平均时间 s

本文还做了收敛性对比，如图3中的进化曲线所示，由于FT06规模较小，各算法表现都不错，可比性不强，因此只对FT10,FT20,LA11,LA16进行了对比。从图中可以看出混沌乌鸦算法有较强的持续进化能力，而RST-CCSA虽然在前期的收敛速度上稍弱于GA，但是得益于CCSA的持续进化能力，RST-CCSA的最终优化结果要好于GA。同时也可以看出RST-CCSA相较于原始CCSA，其收敛速度有所提升，可见本文的改进既保留了CCSA的持续进化能力，同时还提高了收敛速度，从而使得算法整体性能有较大的提升。

图3 算法进化曲线

5 结束语

本文采用基于工序的编码方式并设计修补算子,成功地将CCSA应用于求解FJSSP上。并通过引入变异算子丰富了个体的搜索行为，通过设计多样最优个体集使算法在提高搜索效率的同时保证了种群信息的多样性，通过设计一种基于机器空闲时间缩小的新搜索方法融合进算法中进一步提高了算法的搜索效率和求解质量。通过对5个经典实例的测试、对比和分析，验证了所做出的改进有效提高了收敛速度和寻优能力，而且比GA具有更好的求解质量，为求解FJSSP提供了一种新的有效解决方式以及为求解其它类似问题提供了参考。本文所提算法在其收敛速度上还有提升的空间，值得进一步研究。