【车间调度】基于matlab模拟退火算法求解单约束车间流水线调度问题【含Matlab源码 1457期】

蔚落 2022-09-17 03:17 189阅读 0赞

## 一、车间调度简介 ##

**1 车间调度定义**  
车间调度是指根据产品制造的合理需求分配加工车间顺序，从而达到合理利用产品制造资源、提高企业经济效益的目的。车间调度问题从数学上可以描述为有n个待加工的零件要在m台机器上加工。问题需要满足的条件包括每个零件的各道工序使用每台机器不多于1次，每个零件都按照一定的顺序进行加工。

**2 传统作业车间调度**  
传统作业车间带调度实例  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RJUUNtYXRsYWI_size_16_color_FFFFFF_t_70]  
有若干工件，每个工件有若干工序，有多个加工机器，但是每道工序只能在一台机器上加工。对应到上面表格中的实例就是，两个工件，工件J1有三道工序，工序Q11只能在M3上加工，加工时间是5小时。  
约束是对于一个工件来说，工序的相对顺序不能变。O11->O12->O13。每时刻，每个工件只能在一台机器上加工；每个机器上只能有一个工件。  
调度的任务则是安排出工序的加工顺序，加工顺序确定了，因为每道工序只有一台机器可用，加工的机器也就确定了。  
调度的目的是总的完工时间最短（也可以是其他目标）。举个例子，比如确定了O21->O22->O11->O23->O12->O13的加工顺序之后，我们就可以根据加工机器的约束，计算出总的加工时间。  
M2加工O21消耗6小时，工件J2当前加工时间6小时。  
M1加工O22消耗9小时，工件J2当前加工时间6+9=15小时。  
M3加工O11消耗5小时，工件J1当前加工时间5小时。  
M4加工O23消耗7小时，工件J2加工时间15+7=22小时。  
M1加工O12消耗11小时，但是要等M1加工完O22之后才开始加工O12，所以工件J1的当前加工时间为max(5,9)+11=20小时。  
M5加工O13消耗8小时，工件J2加工时间20+8=28小时。  
总的完工时间就是max(22,28)=28小时。

**2 柔性作业车间调度**  
柔性作业车间带调度实例（参考自高亮老师论文  
《改进遗传算法求解柔性作业车间调度问题》——机械工程学报）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RJUUNtYXRsYWI_size_16_color_FFFFFF_t_70 1]  
相比于传统作业车间调度，柔性作业车间调度放宽了对加工机器的约束，更符合现实生产情况，每个工序可选加工机器变成了多个，可以由多个加工机器中的一个加工。比如上表中的实例，J1的O12工序可以选择M2和M4加工，加工时间分别是8小时和4小时，但是并不一定选择M4加工，最后得出来的总的完工时间就更短，所以，需要调度算法求解优化。

相比于传统作业车间，柔性车间作业调度的调度任务不仅要确定工序的加工顺序，而且需要确定每道工序的机器分配。比如，确定了O21->O22->O11->O23->O12->O13的加工顺序，我们并不能相应工序的加工机器，所以还应该确定对应的\[M1、M3、M5\]->\[M1、M2、M3\]->\[M1、M2、M3、M4、M5\]->\[M2、M3、M4、M5\]->\[M2、M4\]->\[M1、M3、M4、M5\]的机器组合。调度的目的还是总的完工时间最短（也可以是其他目标，比如机器最大负荷最短、总的机器负荷最短）

## 二、模拟退火算法简介 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RJUUNtYXRsYWI_size_16_color_FFFFFF_t_70 2]  
![3][]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RJUUNtYXRsYWI_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RJUUNtYXRsYWI_size_16_color_FFFFFF_t_70 4]  
**5 模拟退火算法的参数**  
模拟退火是一种优化算法，它本身是不能独立存在的，需要有一个应用场合，其中温度就是模拟退火需要优化的参数，如果它应用到了聚类分析中，那么就是说聚类分析中有某个或者某几个参数需要优化，而这个参数，或者参数集就是温度所代表的。它可以是某项指标，某项关联度，某个距离等等。

## 三、部分源代码 ##

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;

## 四、运行结果 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA57Sr5p6B56We5YWJ_size_19_color_FFFFFF_t_70_g_se_x_16_pic_center]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA57Sr5p6B56We5YWJ_size_19_color_FFFFFF_t_70_g_se_x_16_pic_center 1]

## 五、matlab版本及参考文献 ##

**1 matlab版本**  
2014a

**2 参考文献**  
\[1\] 包子阳,余继周,杨杉.智能优化算法及其MATLAB实例（第2版）\[M\].电子工业出版社，2016.  
\[2\]张岩,吴水根.MATLAB优化算法源代码\[M\].清华大学出版社，2017.

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RJUUNtYXRsYWI_size_16_color_FFFFFF_t_70]: /images/20220828/320275cf3b8a43dbbc451e9f78419a83.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RJUUNtYXRsYWI_size_16_color_FFFFFF_t_70 1]: /images/20220828/eea0f27650744c358b450d5af017d223.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RJUUNtYXRsYWI_size_16_color_FFFFFF_t_70 2]: /images/20220828/eec90640e95641a5ae29fcb72fcc7f66.png
[3]: /images/20220828/866834e2d956469ba7d2933aca9ffe03.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RJUUNtYXRsYWI_size_16_color_FFFFFF_t_70 3]: /images/20220828/cfffd76806394aab99eddbd38e8431a3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RJUUNtYXRsYWI_size_16_color_FFFFFF_t_70 4]: /images/20220828/96d60417ccf44c2e9e3a902150ad90b0.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA57Sr5p6B56We5YWJ_size_19_color_FFFFFF_t_70_g_se_x_16_pic_center]: /images/20220828/e0c8a65d8bcf4de4839310e4709f7045.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA57Sr5p6B56We5YWJ_size_19_color_FFFFFF_t_70_g_se_x_16_pic_center 1]: /images/20220828/0bff370065b44ba7ad2ee0861bcfcebc.png