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

刘 凯，黄辉先，赵 骥,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背包问题上同样得出其具有良好的全局寻优能力和……