一、車間調(diào)度簡(jiǎn)介

1 車間調(diào)度定義

車間調(diào)度是指根據(jù)產(chǎn)品制造的合理需求分配加工車間順序，從而達(dá)到合理利用產(chǎn)品制造資源、提高企業(yè)經(jīng)濟(jì)效益的目的。車間調(diào)度問(wèn)題從數(shù)學(xué)上可以描述為有n個(gè)待加工的零件要在m臺(tái)機(jī)器上加工。問(wèn)題需要滿足的條件包括每個(gè)零件的各道工序使用每臺(tái)機(jī)器不多于1次，每個(gè)零件都按照一定的順序進(jìn)行加工。

2 傳統(tǒng)作業(yè)車間調(diào)度

傳統(tǒng)作業(yè)車間帶調(diào)度實(shí)例

有若干工件，每個(gè)工件有若干工序，有多個(gè)加工機(jī)器，但是每道工序只能在一臺(tái)機(jī)器上加工。對(duì)應(yīng)到上面表格中的實(shí)例就是，兩個(gè)工件，工件J1有三道工序，工序Q11只能在M3上加工，加工時(shí)間是5小時(shí)。
約束是對(duì)于一個(gè)工件來(lái)說(shuō)，工序的相對(duì)順序不能變。O11->O12->O13。每時(shí)刻，每個(gè)工件只能在一臺(tái)機(jī)器上加工；每個(gè)機(jī)器上只能有一個(gè)工件。
調(diào)度的任務(wù)則是安排出工序的加工順序，加工順序確定了，因?yàn)槊康拦ば蛑挥幸慌_(tái)機(jī)器可用，加工的機(jī)器也就確定了。
調(diào)度的目的是總的完工時(shí)間最短（也可以是其他目標(biāo)）。舉個(gè)例子，比如確定了O21->O22->O11->O23->O12->O13的加工順序之后，我們就可以根據(jù)加工機(jī)器的約束，計(jì)算出總的加工時(shí)間。
M2加工O21消耗6小時(shí)，工件J2當(dāng)前加工時(shí)間6小時(shí)。
M1加工O22消耗9小時(shí)，工件J2當(dāng)前加工時(shí)間6+9=15小時(shí)。
M3加工O11消耗5小時(shí)，工件J1當(dāng)前加工時(shí)間5小時(shí)。
M4加工O23消耗7小時(shí)，工件J2加工時(shí)間15+7=22小時(shí)。
M1加工O12消耗11小時(shí)，但是要等M1加工完O22之后才開(kāi)始加工O12，所以工件J1的當(dāng)前加工時(shí)間為max(5,9)+11=20小時(shí)。
M5加工O13消耗8小時(shí)，工件J2加工時(shí)間20+8=28小時(shí)。
總的完工時(shí)間就是max(22,28)=28小時(shí)。

3 柔性作業(yè)車間調(diào)度

柔性作業(yè)車間帶調(diào)度實(shí)例（參考自高亮老師論文
《改進(jìn)遺傳算法求解柔性作業(yè)車間調(diào)度問(wèn)題》——機(jī)械工程學(xué)報(bào)）

相比于傳統(tǒng)作業(yè)車間調(diào)度，柔性作業(yè)車間調(diào)度放寬了對(duì)加工機(jī)器的約束，更符合現(xiàn)實(shí)生產(chǎn)情況，每個(gè)工序可選加工機(jī)器變成了多個(gè)，可以由多個(gè)加工機(jī)器中的一個(gè)加工。比如上表中的實(shí)例，J1的O12工序可以選擇M2和M4加工，加工時(shí)間分別是8小時(shí)和4小時(shí)，但是并不一定選擇M4加工，最后得出來(lái)的總的完工時(shí)間就更短，所以，需要調(diào)度算法求解優(yōu)化。

相比于傳統(tǒng)作業(yè)車間，柔性車間作業(yè)調(diào)度的調(diào)度任務(wù)不僅要確定工序的加工順序，而且需要確定每道工序的機(jī)器分配。比如，確定了O21->O22->O11->O23->O12->O13的加工順序，我們并不能相應(yīng)工序的加工機(jī)器，所以還應(yīng)該確定對(duì)應(yīng)的[M1、M3、M5]->[M1、M2、M3]->[M1、M2、M3、M4、M5]->[M2、M3、M4、M5]->[M2、M4]->[M1、M3、M4、M5]的機(jī)器組合。調(diào)度的目的還是總的完工時(shí)間最短（也可以是其他目標(biāo)，比如機(jī)器最大負(fù)荷最短、總的機(jī)器負(fù)荷最短）

二、蝴蝶優(yōu)化算法（MBO）簡(jiǎn)介

1 介紹

蝴蝶優(yōu)化算法(butterfly optimization algorithm, BOA)是Arora 等人于2019年提出的一種元啟發(fā)式智能算法。該算法受到了蝴蝶覓食和交配行為的啟發(fā)，蝴蝶接收/感知并分析空氣中的氣味，以確定食物來(lái)源/交配伙伴的潛在方向。
蝴蝶利用它們的嗅覺(jué)、視覺(jué)、味覺(jué)、觸覺(jué)和聽(tīng)覺(jué)來(lái)尋找食物和伴侶，這些感覺(jué)也有助于它們從一個(gè)地方遷徙到另一個(gè)地方，逃離捕食者并在合適的地方產(chǎn)卵。在所有感覺(jué)中，嗅覺(jué)是最重要的，它幫助蝴蝶尋找食物（通常是花蜜）。蝴蝶的嗅覺(jué)感受器分散在蝴蝶的身體部位，如觸角、腿、觸須等。這些感受器實(shí)際上是蝴蝶體表的神經(jīng)細(xì)胞，被稱為化學(xué)感受器。它引導(dǎo)蝴蝶尋找最佳的交配對(duì)象，以延續(xù)強(qiáng)大的遺傳基因。雄性蝴蝶能夠通過(guò)信息素識(shí)別雌性蝴蝶，信息素是雌性蝴蝶發(fā)出的氣味分泌物，會(huì)引起特定的反應(yīng)。
通過(guò)觀察，發(fā)現(xiàn)蝴蝶對(duì)這些來(lái)源的位置有非常準(zhǔn)確的判斷。此外，它們可以辨識(shí)出不同的香味，并感知它們的強(qiáng)度。蝴蝶會(huì)產(chǎn)生與其適應(yīng)度相關(guān)的某種強(qiáng)度的香味，即當(dāng)蝴蝶從一個(gè)位置移動(dòng)到另一個(gè)位置時(shí)，它的適應(yīng)度會(huì)相應(yīng)地變化。當(dāng)蝴蝶感覺(jué)到另一只蝴蝶在這個(gè)區(qū)域散發(fā)出更多的香味時(shí)，就會(huì)去靠近，這個(gè)階段被稱為全局搜索。另外一種情況，當(dāng)蝴蝶不能感知大于它自己的香味時(shí)，它會(huì)隨機(jī)移動(dòng)，這個(gè)階段稱為局部搜索。

2 香味

為了理解BOA中的香味是如何計(jì)算的，首先需要理解，像氣味、聲音、光、溫度等這樣的模態(tài)是如何計(jì)算的。感知、處理這些模態(tài)需要知道三個(gè)重要的術(shù)語(yǔ)：感覺(jué)模態(tài)C、刺激強(qiáng)度I和冪指數(shù)a。在感覺(jué)模態(tài)中，感覺(jué)意味著測(cè)量能量的形式并以類似方式對(duì)其進(jìn)行處理，而模態(tài)是指?jìng)鞲衅魇褂玫脑驾斎?。不同的形態(tài)可以是氣味，聲音，光線，溫度，在BOA中，模態(tài)是香味。I是物理刺激的大小。在BOA中，I與蝴蝶/解決方案的適應(yīng)度相關(guān)。這意味著，當(dāng)一只蝴蝶散發(fā)出更多的香味時(shí)，周圍的其他蝴蝶可以感知到并被吸引。冪是強(qiáng)度增加的指數(shù)。參數(shù)a允許正則表達(dá)式、線性響應(yīng)和響應(yīng)壓縮。響應(yīng)擴(kuò)展是當(dāng)I增加時(shí)，香味（f）比I增長(zhǎng)更快。響應(yīng)壓縮是當(dāng)I增加時(shí)，f比I增長(zhǎng)慢。線性響應(yīng)是當(dāng)I增加時(shí)，f成比例地增加。經(jīng)實(shí)驗(yàn)證明，有時(shí)隨著刺激的增強(qiáng)，昆蟲(chóng)對(duì)刺激變化的敏感性變得越來(lái)越低。因此在BOA中，為了估計(jì)I的大小，使用了響應(yīng)壓縮。
蝴蝶的自然現(xiàn)象基于兩個(gè)重要問(wèn)題：I的變化和f的表示。簡(jiǎn)單地說(shuō)，蝴蝶的I與編碼后的目標(biāo)函數(shù)相關(guān)聯(lián)。但是，f是相對(duì)的，即應(yīng)該由其他蝴蝶來(lái)感知。史蒂文斯冪定律中，為了將氣味與其他形式區(qū)別開(kāi)來(lái)，使用了C?，F(xiàn)在，當(dāng)I較少的蝴蝶向I較多的蝴蝶移動(dòng)時(shí)，f比I增加得更快。因此，我們應(yīng)該允許f隨冪指數(shù)參數(shù)a實(shí)現(xiàn)的吸收程度而變化。在BOA中，香味被表示為刺激物的物理強(qiáng)度的函數(shù)，如下所示：

3 具體算法

為了用搜索算法演示上述討論，將蝴蝶的上述特征理想化如下：

（1）所有的蝴蝶都可以發(fā)出氣味，這使蝴蝶間相互吸引。

（2）每只蝴蝶都會(huì)隨機(jī)移動(dòng)或朝最好的蝴蝶移動(dòng)，散發(fā)出更多的芳香。

（3）蝴蝶的刺激強(qiáng)度受目標(biāo)函數(shù)的景觀影響或決定。

該算法分為三個(gè)階段：(1)初始化階段、(2)迭代階段和(3)結(jié)束階段。

在BOA的每次運(yùn)行中，首先執(zhí)行初始化階段，然后進(jìn)行迭代搜索，最后在找到最優(yōu)解時(shí)終止算法。BOA中使用的參數(shù)值也會(huì)被分配，設(shè)置這些值后，算法將繼續(xù)創(chuàng)建初始蝴蝶種群以進(jìn)行優(yōu)化。由于在BOA的模擬過(guò)程中蝴蝶總數(shù)保持不變，分配了一個(gè)固定大小的內(nèi)存來(lái)存儲(chǔ)信息。蝴蝶的位置是在搜索空間中隨機(jī)生成的，并計(jì)算和存儲(chǔ)它們的香味和適應(yīng)值。這樣就完成了初始化階段，算法開(kāi)始了迭代階段，該階段使用創(chuàng)建的人工蝶形執(zhí)行搜索。算法的第二階段，即迭代階段，由算法執(zhí)行多次迭代。在每次迭代中，解空間中的所有蝶形都移到新位置，然后重新評(píng)估其適應(yīng)性值。算法首先計(jì)算解空間中不同位置的所有蝴蝶的適應(yīng)度值。那么這些蝴蝶就會(huì)利用式1在自己的位置產(chǎn)生香味。該算法有兩個(gè)關(guān)鍵步驟，即全局搜索階段和局部搜索階段。在全局搜索階段，蝴蝶向最合適的蝴蝶/解g∗邁出一步，該蝴蝶/解g可以用公式(2)來(lái)表示。

這里，g∗表示在當(dāng)前迭代的所有解中找到的當(dāng)前最佳解；fi表示第i只蝴蝶的香味，r是[0，1]中的隨機(jī)數(shù)。局部搜索階段可以表示為

其中，xjt和xkt是解空間中的第j個(gè)蝴蝶和第k個(gè)蝴蝶。
蝴蝶尋找食物、交配伙伴可以在局部和全局范圍內(nèi)發(fā)生?？紤]到地理上的接近和各種其他因素，如雨、風(fēng)等，在整個(gè)交配伙伴或蝴蝶的覓食活動(dòng)中，尋找食物可能占很大比例。因此，在BOA中使用切換概率p來(lái)在普通全局搜索和密集局部搜索之間切換。
在未達(dá)到停止標(biāo)準(zhǔn)之前，一直進(jìn)行迭代。迭代結(jié)束的標(biāo)準(zhǔn)可以有多個(gè)，如使用的最大CPU時(shí)間、達(dá)到的最大迭代次數(shù)、沒(méi)有改進(jìn)的最大迭代次數(shù)、達(dá)到錯(cuò)誤率的特定值或任何其他適當(dāng)?shù)臉?biāo)準(zhǔn)。當(dāng)?shù)A段結(jié)束時(shí)，算法輸出具有最佳適應(yīng)度的最優(yōu)解。

三、部分源代碼

clc;clear
%% 下載數(shù)據(jù)
% 加工數(shù)據(jù)包括加工時(shí)間，加工機(jī)器，機(jī)器數(shù)，各機(jī)器權(quán)重，工件數(shù)，各工件對(duì)應(yīng)的工序數(shù)
load data operation_time operation_machine num_machine machine_weight num_job num_op
%% 基本參數(shù)
MAXGEN=200;             % 最大迭代次數(shù)
sizepop=201;            % 種群規(guī)模
e=0.5;                  % 目標(biāo)值權(quán)重
N_size=30;              % 鄰域解數(shù)量
S_size=15;              % 共享解數(shù)量
G=5;                    % 巡回次數(shù)
G1=20;                  % 競(jìng)爭(zhēng)機(jī)制1參數(shù)
G2=10;                  % 競(jìng)爭(zhēng)機(jī)制2參數(shù)
trace=zeros(2,MAXGEN);
chrom_best=[];

%% ===========================種群初始化============================
total_op_num=sum(num_op);
chroms=initialization(num_op,num_job,total_op_num,sizepop,operation_machine,operation_time);
[Z,~,~,~,~]=fitness(chroms,num_machine,e,num_job,num_op);
% 將最好的解劃分為領(lǐng)飛鳥(niǎo)
[Z_leader,ind]=min(Z);
leader=chroms(ind,:); 
% 從chroms中移出領(lǐng)飛鳥(niǎo)，然后劃分左右兩個(gè)跟飛鳥(niǎo)種群
chroms(ind,:)=[];
Z(ind)=[];
sp=(sizepop-1)/2;
lefts=chroms(1:sp,:);
Z_left=Z(1:sp);
rights=chroms(sp+1:end,:);
Z_right=Z(sp+1:end);
%% 候鳥(niǎo)算法中的交叉函數(shù)與遺傳算法的不同
%% 候鳥(niǎo)算法輸入兩個(gè)染色體種群，分別來(lái)自左右隊(duì)列
%--------------------------------------------------------------------------
function [lefts,Z_left,rights,Z_right]= crossover(lefts,rights,Z_left,Z_right,total_op_num,num_machine,e,num_job,num_op)
chroms1=lefts;
chroms2=rights;
for i=1:size(chroms1,1)
    %% 面向工序碼的交叉操作
    % 父代染色體
    parent1=lefts(i,:);
    parent2=rights(i,:);
    Job=randperm(num_job);
    % 將工件隨機(jī)分成兩個(gè)集合
    J1=Job(1:round(num_job/2));
    J2=Job(length(J1)+1:end);
    op_p1=[];
    op_p2=[];
    for j=1:length(J2)
        %找出父代中J2片段對(duì)應(yīng)的位置
        op_p1=[op_p1,find(parent1(1:total_op_num)==J2(j))];
        op_p2=[op_p2,find(parent2(1:total_op_num)==J2(j))];
    end
    op_s1=sort(op_p1);
    op_s2=sort(op_p2);
    % 子代1交換J2片段的基因，機(jī)器碼對(duì)應(yīng)位置的基因，工時(shí)碼對(duì)應(yīng)位置的基因
    chroms1(i,op_s1)=parent2(op_s2);
    chroms1(i,total_op_num+op_s1)=parent2(total_op_num+op_s2);
    chroms1(i,total_op_num*2+op_s1)=parent2(total_op_num*2+op_s2);
    % 子代2同理
    chroms2(i,op_s2)=parent1(op_s1);
    chroms2(i,total_op_num+op_s2)=parent1(total_op_num+op_s1);
    chroms2(i,total_op_num*2+op_s2)=parent1(total_op_num*2+op_s1);
    %% 面向機(jī)器碼的交叉操作
    parent1=chroms1(i,:);
    parent2=chroms2(i,:);
    % 隨機(jī)產(chǎn)生與染色體長(zhǎng)度相等的0,1序列
    rand0_1=randi([0,1],1,total_op_num);
    for n=1:num_job
        ind_0=find(rand0_1(num_op(n)*(n-1)+1:num_op(n)*n)==0);
        if ~isempty(ind_0)
            ind1=find(parent1(1:total_op_num)==n);
            ind2=find(parent2(1:total_op_num)==n);
            chroms1(i,total_op_num+ind1(ind_0))=parent2(total_op_num+ind2(ind_0));
            chroms1(i,total_op_num*2+ind1(ind_0))=parent2(total_op_num*2+ind2(ind_0));
            chroms2(i,total_op_num+ind2(ind_0))=parent1(total_op_num+ind1(ind_0));
            chroms2(i,total_op_num*2+ind2(ind_0))=parent1(total_op_num*2+ind1(ind_0));
        end
    end
end
%% 判斷個(gè)體是否可以更新
[Z1,~,~,~,~]=fitness(chroms1,num_machine,e,num_job,num_op);
[Z2,~,~,~,~]=fitness(chroms2,num_machine,e,num_job,num_op);
lefts(Z1<Z_left,:)=chroms1(Z1<Z_left,:);
Z_left(Z1<Z_left)=Z1(Z1<Z_left);
rights(Z2<Z_right,:)=chroms2(Z2<Z_right,:);
Z_right(Z2<Z_right)=Z2(Z2<Z_right);
function [Z,makespan,machine_load,machine_weight,pvals] = fitness(chroms,num_machine,e,num_job,num_op)
sizepop=size(chroms,1);
pvals=cell(1,sizepop);
makespan=zeros(1,sizepop);
machine_load=makespan;
total_op_num=sum(num_op);  % 總工序數(shù)
for k=1:sizepop
    chrom=chroms(k,:);
    machine=zeros(1,num_machine);  % 記錄各機(jī)器變化時(shí)間
    job=zeros(1,num_job);  % 記錄各工件變化時(shí)間
    machine_time=zeros(1,num_machine);  % 計(jì)算各機(jī)器的實(shí)際加工時(shí)間
    pval=zeros(2,total_op_num);  % 記錄各工序開(kāi)始和結(jié)束時(shí)間
    for i=1:total_op_num
        else
            pval(1,i)=job(chrom(i));
            job(chrom(i))=job(chrom(i))+chrom(total_op_num*2+i);
            machine(chrom(total_op_num+i))=job(chrom(i));
            pval(2,i)=job(chrom(i));
        end
        machine_time(chrom(total_op_num+i))=machine_time(chrom(total_op_num+i))+chrom(total_op_num*2+i);
    end
    makespan(k)=max(machine);
    machine_weight=machine_time;
    machine_load(k)=max(machine_weight)-min(machine_weight);
    pvals{k}=pval;
end
Z=e*makespan+(1-e)*machine_load;

四、運(yùn)行結(jié)果

五、matlab版本及參考文獻(xiàn)

1 matlab版本
2014a

2 參考文獻(xiàn)
[1] 包子陽(yáng),余繼周,楊杉.智能優(yōu)化算法及其MATLAB實(shí)例（第2版）[M].電子工業(yè)出版社，2016.
[2]張巖,吳水根.MATLAB優(yōu)化算法源代碼[M].清華大學(xué)出版社，2017.
[3]蝴蝶優(yōu)化算法

以上就是matlab鳥(niǎo)群算法求解車間調(diào)度問(wèn)題詳解及實(shí)現(xiàn)源碼的詳細(xì)內(nèi)容，更多關(guān)于matlab鳥(niǎo)群算法求解車間調(diào)度問(wèn)題的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論