快捷導(dǎo)航

matlab模擬退火算法單約束車間流水線調(diào)度解決實現(xiàn)及示例

更新時間：2022年02月07日 12:00:49 作者：紫極神光

這篇文章主要為大家介紹了matlab模擬退火算法求解單約束車間流水線調(diào)度的實現(xiàn)及示例，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步

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

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

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

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

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

在這里插入圖片描述

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

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

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

在這里插入圖片描述

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

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

二、模擬退火算法簡介

在這里插入圖片描述

5 模擬退火算法的參數(shù)
模擬退火是一種優(yōu)化算法，它本身是不能獨立存在的，需要有一個應(yīng)用場合，其中溫度就是模擬退火需要優(yōu)化的參數(shù)，如果它應(yīng)用到了聚類分析中，那么就是說聚類分析中有某個或者某幾個參數(shù)需要優(yōu)化，而這個參數(shù)，或者參數(shù)集就是溫度所代表的。它可以是某項指標(biāo)，某項關(guān)聯(lián)度，某個距離等等。

三、部分源代碼

clc;
clear;
close all;
%% Problem Definition
model=CreateModel();        % Create Model of the Problem
CostFunction=@(q) MyCost(q,model);       % Cost Function
nVar=model.nVar;        % Number of Decision Variables
VarSize=[1 nVar];       % Size of Decision Variables Matrix
%% SA Parameters
MaxIt=100;      % Maximum Number of Iterations
MaxIt2=25;      % Maximum Number of Inner Iterations
T0=10;          % Initial Temperature
alpha=0.97;     % Temperature Damping Rate
%% Initialization
% Create Initial Solution
x.Position=CreateRandomSolution(model);
[x.Cost, x.Sol]=CostFunction(x.Position);
% Update Best Solution Ever Found
BestSol=x;
% Array to Hold Best Cost Values
BestCost=zeros(MaxIt,1);
% Set Initial Temperature
T=T0;
%% SA Main Loop
for it=1:MaxIt
    for it2=1:MaxIt2
        % Create Neighbor
        xnew.Position=CreateNeighbor(x.Position);
        [xnew.Cost, xnew.Sol]=CostFunction(xnew.Position);
        if xnew.Cost<=x.Cost
            % xnew is better, so it is accepted
            x=xnew;
        else
            % xnew is not better, so it is accepted conditionally
            delta=xnew.Cost-x.Cost;
            p=exp(-delta/T);
            
            if rand<=p
                x=xnew;
            end
        end
        % Update Best Solution
        if x.Cost<=BestSol.Cost
            BestSol=x;
        end
    end
    % Store Best Cost
    BestCost(it)=BestSol.Cost;
    % Display Iteration Information
    disp(['Iteration ' num2str(it) ': Best Cost = ' num2str(BestCost(it))]);
    % Reduce Temperature
    T=alpha*T;
    % Plot Solution
    figure(1);
    PlotSolution(BestSol.Sol,model);
    pause(0.01);
end
%% Results
figure;
plot(BestCost,'LineWidth',2);
xlabel('Iteration');
ylabel('Best Cost');
grid on;