基于布谷鸟搜索算法求解流水车间调度
2018-01-06张珊靓王庆喜
张珊靓+王庆喜
摘要：調度是研究资源如何配置问题的理论，流水车间问题是车间调度问题领域的一个子问题，是通过对制造过程作业计划，以实现流水车间环境下生产过程的优化调度，其广泛应用于实际生产，尤其适用于单件大批量生产背景的制造企业。该文主要研究的是使用布谷鸟搜索算法优化车间调度中的流水车间调度的问题。
关键词：布谷鸟搜索算法；流程车间；调度
中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2017）35-0104-02
流水车间调度问题是一个经典的理论问题，拥有简洁的形式，广泛的关联性和高度的计算复杂度。该问题的简洁性体现在，任务集合上的一个排列就代表了一个调度序列。而关联性和复杂性体现在，该问题代表了一大类具有排列性质的问题，许多组合优化问题都可以归约到它。在计算理论中，它是NP-难的。
1 布谷鸟搜索算法
布谷鸟搜索算法自从2009年问世以来广泛医用于多个领域，已经成功优化多种问题，其搜索能力和优化能力被大量证明，该算法的思想可以从如下代码解释。
for i=1：n，
nest（i，：）=Lb+（Ub-Lb）.*rand（size（Lb））；
end
fitness=10^10*ones（n，1）；
[fmin，bestnest，nest，fitness]=get_best_nest（nest，nest，fitness）；
N_iter=0；
while （fmin>Tol），
new_nest=get_cuckoos（nest，bestnest，Lb，Ub）；
[fnew，best，nest，fitness]=get_best_nest（nest，new_nest，fitness）； N_iter=N_iter+n；
new_nest=empty_nests（nest，Lb，Ub，pa） ；
[fnew，best，nest，fitness]=get_best_nest（nest，new_nest，fitness）； N_iter=N_iter+n；
if fnew fmin=fnew； bestnest=best； end end 2 流水车间问题求解 流水车间调度问题是典型的组合优化问题。假设有N个工件，每个工件都按相同的顺序经过M台机器加工，求解各工件的加工顺序，使某种预先规定的目标函数达到最优。其最优时间求解在Matlab中的实现采用矩阵思想，主要代码如下。 function [F， PI] = FSPFitness（ Problem， x ） P = Problem'； [M， N] = size（Problem）； [aaa， ROV] = sort（x）； C = zeros（N， M）； C（ROV（1）， 1） = P（ROV（1）， 1）； for i = 2：N C（ROV（i）， 1） = C（ROV（i-1）， 1） + P（ROV（i）， 1）； end for k = 2：M C（ROV（1）， k） = C（ROV（1）， k-1） + P（ROV（1）， k）； end for i = 2：N for k = 2：M C（ROV（i）， k） = max（C（ROV（i-1）， k）， C（ROV（i）， k-1）） + P（ROV（i）， k）； end end F = C（ROV（N）， M）； PI = ROV； end 3 布谷鸟求解流水车间问题 在用布谷鸟求解流水车间调度问题时，经过随机键编码方式，布谷鸟找到的每个鸟巢代表了调度问题的一个解，主要代码如下。 function [fmin，bestnest]=cuckoo_search_fsp（Problem，params） [numMachines，numJobs] = size（Problem）； if size（params） == [1， 3] numNests = params（1）； pa=params（3）； MaxGeneration = params（2）； else numNests = 300； pa=0.25； MaxGeneration = 1000； end result = zeros（1， MaxGeneration）； nest = rand（numNests， numJobs）； fitness = 10e5*ones（1， numNests）； [fmin，bestnest，nest，fitness]=get_best_nest（nest，nest，fitness，Problem） for i=1：MaxGeneration， new_nest=get_cuckoos（nest，bestnest）； [fnew，best，nest，fitness]=get_best_nest（nest，new_nest，fitness，Problem）；
new_nest=empty_nests（nest，pa） ； [fnew，best，nest，fitness]=get_best_nest（nest，new_nest，fitness，Problem）；
if fnew fmin=fnew； bestnest=best； end result（i）=fmin； %fprintf（'best：%f＼n'，fmin）； end plot（result）； 4 仿真测试 仿真测试的测试函数采用Car问题和Rec问题。为了获得较好准确的结果，求解流水车间调度问题时独立运行程序20词，求出20词中求得最优解的次数，然后求出寻优率，根据寻优率，对比多种算法的优劣。主要代码 Car7=[692 310 832 630 258 147 255； 581 582 14 214 147 753 806； 475 475 785 578 852 2 699； 23 196 696 214 586 356 877； 158 325 530 785 325 565 412； 796 874 214 236 896 898 302； 542 205 578 963 325 800 120]'； Problem = Car7； BESTANSWER = 6590； runTimes = 20； for i=1：runTimes subplot（2，1，1）； hold on [Best（i）， paixu] = cuckoo_search_fsp（Problem， [25， 500， 0.25]）； hold off subplot（2，1，2）； xlim（[1，runTimes]）； hold on plot（Best）； hold off drawnow； end count = 0； for i=1：runTimes if Best（i） == BESTANSWER count = count + 1； end end 为了验证布谷鸟算法求解FSP的性能，对算法没有采取改进策略，完全依靠算法自身进化机制寻优。选择Car类基准测试问题进行仿真测试，并与萤火虫算法在离散空间的优化性能进行对比。仿真测试的一组结果如图1所示。 5 结论 本文将布谷鸟搜索算法这一优秀的元启发式算法应用于流水车间调度问题领域。虽然流水车间调度问题是一个古老的课题，但由于它不可忽略的现实和理论意义，对该问题进一步探索守非常有意义的。本文针对求解以最小时间跨度的流水车间调度问题，具体设计布谷鸟算法，所做的工作有。求解质量是指，在给定的迭代次数内所求解的质量的好坏。本文基于该考虑，观察和设计布谷鸟算法的各个组成要素，尽可能使算法能够得到较优的调度。 参考文献： [1] 王庆喜， 赵珊. 基于改进布谷鸟搜索算法的工程设计优化[J]. 黑龙江大学自然科学学报， 2017， 345（2）：247-52. [2] 陈超. 改进CS算法结合决策树的云工作流调度[J]. 电子科技大学学报， 2016， 46（6）：974-980. [3] 谢丽霞， 王志华. 基于布谷鸟搜索优化BP神经网络的网络安全态勢评估方法[J]. 计算机应用，2017， 37（7）：1926-1930. [4] 王庆喜， 魏胜利. 基于混沌和非线性规划的萤火虫算法[J]. 科技通报， 2017， 33（5）：120-123.
