基于布谷鸟搜索算法求解流水车间调度

张珊靓+王庆喜

摘要：調度是研究资源如何配置问题的理论，流水车间问题是车间调度问题领域的一个子问题，是通过对制造过程作业计划，以实现流水车间环境下生产过程的优化调度，其广泛应用于实际生产，尤其适用于单件大批量生产背景的制造企业。该文主要研究的是使用布谷鸟搜索算法优化车间调度中的流水车间调度的问题。

关键词：布谷鸟搜索算法；流程车间；调度

中图分类号：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 布谷鸟求解流水车间问题

在用布谷鸟求解流水车间调度问题时，经过随机键编码方式，布谷鸟找到的每个鸟巢代表了调度问题的一个解，主要代码如下。……