快捷導(dǎo)航

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

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

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

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

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

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

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

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

在這里插入圖片描述

有若干工件，每個(gè)工件有若干工序，有多個(gè)加工機(jī)器，但是每道工序只能在一臺機(jī)器上加工。對應(yīng)到上面表格中的實(shí)例就是，兩個(gè)工件，工件J1有三道工序，工序Q11只能在M3上加工，加工時(shí)間是5小時(shí)。
約束是對于一個(gè)工件來說，工序的相對順序不能變。O11->O12->O13。每時(shí)刻，每個(gè)工件只能在一臺機(jī)器上加工；每個(gè)機(jī)器上只能有一個(gè)工件。
調(diào)度的任務(wù)則是安排出工序的加工順序，加工順序確定了，因?yàn)槊康拦ば蛑挥幸慌_機(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之后才開始加工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)度問題》——機(jī)械工程學(xué)報(bào)）

在這里插入圖片描述

相比于傳統(tǒng)作業(yè)車間調(diào)度，柔性作業(yè)車間調(diào)度放寬了對加工機(jī)器的約束，更符合現(xiàn)實(shí)生產(chǎn)情況，每個(gè)工序可選加工機(jī)器變成了多個(gè)，可以由多個(gè)加工機(jī)器中的一個(gè)加工。比如上表中的實(shí)例，J1的O12工序可以選擇M2和M4加工，加工時(shí)間分別是8小時(shí)和4小時(shí)，但是并不一定選擇M4加工，最后得出來的總的完工時(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)該確定對應(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ù)荷最短）

二、模擬退火算法簡介

在這里插入圖片描述

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

三、部分源代碼

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;