MATLAB实现蚁群算法优化柔性车间调度(ACO-fjsp)

蚁群算法优化车间调度的步骤可以分为以下几个主要阶段：

1.初始化阶段：
设置算法参数，如信息素浓度、启发式因子等。这些参数将影响蚂蚁在选择路径时的决策过程。
确定车间调度的具体问题规模，包括工件数量、机器数量以及每个工件在各机器上的加工时间等。
2.构建解阶段：
将蚂蚁（即搜索代理）放置在初始位置，这通常代表调度的起始点。
每只蚂蚁根据路径上的信息素浓度和启发式信息，按概率选择下一个要访问的节点（在这里可能是指工件或机器）。这个过程模拟了蚂蚁在寻找食物时根据信息素和可见性（即距离、时间等因素）来选择路径的行为。
蚂蚁在车间调度问题中的移动，代表了对工件加工顺序和机器分配的探索。通过多次迭代，蚂蚁们能够逐渐发现更优的调度方案。
3.信息素更新阶段：
当所有蚂蚁都完成了一次路径搜索后，根据它们的搜索结果来更新路径上的信息素。这通常涉及到两个方面：一是增加找到较优解路径上的信息素（正反馈），二是减少其他路径上的信息素（由于挥发或负反馈）。
信息素的更新规则可能因具体实现而异，但通常都会考虑到路径的长度、质量以及蚂蚁走过的次数等因素。
4.收敛判断与优化阶段：
检查算法是否满足停止条件，如达到最大迭代次数、找到满足精度要求的解或解的质量在连续多次迭代中无明显改进等。
如果满足停止条件，则输出当前找到的最优解；否则，返回到构建解阶段继续搜索。
5.后处理与优化展示

柔性车间调度的模型如下:

1.目标函数：
柔性车间调度的目标函数通常包括多个方面，如最大完工时间最小、总完工时间最小、最大负荷的机器负荷最小等。这些目标可以根据实际需求进行选择或组合。一般采用最大完工时间最小：
$f_1 = \min(C_{\max})$
其中， $C_{\max}$ 表示所有工件中的最晚完工时间。

其中， $C_i$ 表示第i个工件的完工时间，n是工件的总数。

2.约束条件：
柔性车间调度的约束条件通常包括以下几点：

(1)同一台机器同一时刻只能加工一个工件。
(2)同一工件的同一道工序在同一时刻被加工的机器数是一。即，一个工序不能同时在多台机器上进行。
(3)任意工序开始加工后不能中断。这意味着一旦一个工序开始，就必须连续进行直到完成。
(4)各个工件之间不存在优先级的差别。除非特别指定，否则所有工件都被视为具有相同的优先级。
(5)同一工件的工序之间存在先后约束。即，一个工件的一个工序必须在它之前的工序完成后才能开始。
(6)所有工件在零时刻都可以被加工。这意味着没有工件在开始时就有延迟。
这些约束条件确保了调度方案的可行性和实际性。在实际应用中，可能还需要考虑其他特定的约束条件，如机器的可用性、工件的交货期等。

算例数据如下:

初始加工明细表
工件号	工序	M1	M2	M3	M4	M5	M6
1	1	3	4	6	-1	-1	-1
1	2	-1	-1	10	-1	-1	-1
1	3	-1	12	9	8	-1	5
1	4	-1	7	-1	2	3	-1
2	1	-1	11	-1	6	7	-1
2	2	-1	8	-1	-1	-1	6
2	3	-1	-1	5	11	-1	13
2	4	7	8	8	-1	-1	-1
3	1	-1	-1	3	-1	-1	-1
3	2	2	3	3	-1	-1	-1
3	3	-1	-1	10	4	5	-1
3	4	10	-1	11	-1	3	-1
4	1	-1	-1	12	-1	-1	7
4	2	8	9	9	-1	12	-1
4	3	-1	-1	2	-1	-1	-1
4	4	-1	-1	-1	11	12	-1
5	1	-1	-1	5	8	-1	9
5	2	-1	-1	-1	13	12	8
5	3	3	5	6	-1	-1	-1
5	4	-1	-1	-1	5	6	-1
6	1	5	7	9	-1	-1	-1
6	2	-1	-1	11	5	-1	10
6	3	-1	-1	-1	4	3	9
6	4	-1	-1	-1	5	10	-1

完整代码见:https://download.csdn.net/download/corn1949/89173025

MATLAB主程序如下:

%% 蚁群算法
clc;close all;clear all;warning off;% 清除变量
rand('seed', 100);
randn('seed', 100);
format long g;
addpath(genpath('mytoolbox'));

global jobtable mIDsetcell jobnumber machinenumber S20;
global N1 N2 indexM K;

filename='数据.xlsx';
[adata201,bdata201,cdata201]=xlsread(filename);
jobtable=adata201;% [工件号 工序 各个机器的时间]

N1=size(jobtable,1);% 工序总数
jobnumber=length(unique(jobtable(:,1)));% 工件数
machinenumber=size(jobtable,2)-2;% 机器数

S20=[];
for j=1:jobnumber
    opernumber=sum(jobtable(:,1)==j);
    Sj=j*ones(1,opernumber);
    S20=[S20,Sj];
end

% 变量范围
lb=1*ones(1,N1);
ub=zeros(1,N1);
mIDsetcell=cell(N1,1);
for i=1:N1
    index201= find(jobtable(i,3:end)>0);
    ub(i)=length(index201);% 可用机器数
    mIDsetcell{i,1}=index201;
end


S0=ub-lb+1;
indexM=S2indexMfun(S0);% 变量层分割
K=length(lb);
nodenumber=sum(S0);
E=nearfun(indexM,K,nodenumber);
N2=sum(S0);

%% 蚁群算法参数
maxgen=100;%蚁群迭代次数
popsize=20;%蚂蚁数
alpha=3;% xinx
beta=2;
rho=0.1;
Q=1;

dmat201=ones(N1,N1);
Eta201=1./dmat201;
index201=1:N1;
Tau201=ones(N1,N1)*0.1;%信息素初始化

dmat202=ones(N2,N2);
Eta202=1./dmat202;
Tau202=ones(N2,N2)*0.1;%信息素初始化

tracemataco=zeros(maxgen,2);
%% 蚁群算法构造路径
wait_hand = waitbar(0,'ACO running……', 'tag', 'TMWWaitbar');
for gen=1:maxgen
    % 蚁群1
    routemat201=zeros(popsize,N1);
    for i=1:popsize
        OpNodeSetLocal=index201;
        route=randi([1,N1],1,1);%初始化起点
        currNode=route(end);
        OpNodeSetLocal(OpNodeSetLocal==currNode)=[];
        while ~isempty(OpNodeSetLocal)%还没选完就要继续
            long1=length(OpNodeSetLocal);
            P=zeros(long1,1);
            %% 计算转移概率
            for j=1:long1
                tempnextnode=OpNodeSetLocal(j);
                P(j,1)=(Tau201(currNode,tempnextnode)^alpha)*(Eta201(currNode,tempnextnode)^beta);
            end
            P = P/sum(P);
            Pc =cumsum(P);
            index02 = find(Pc >= rand);
            next_node = OpNodeSetLocal(index02(1));%选择参数
            route=[route,next_node];%更新路径
            currNode=route(end);
            OpNodeSetLocal(OpNodeSetLocal==currNode)=[];
        end
        routemat201(i,:)=route;
    end
    
    % 蚁群2
    routemat202=zeros(popsize,N1);
    for i=1:popsize
        route=randi([1,S0(1)],1,1);%初始化起点
        currNode=route(end);
        OpNodeSetLocal= find(E(currNode,:));% 可选集
        while ~isempty(OpNodeSetLocal)%还没选完就要继续
            long1=length(OpNodeSetLocal);
            P201=zeros(long1,1);
            %% 计算转移概率
            for j=1:long1
                tempnextnode=OpNodeSetLocal(j);
                P201(j,1)=(Tau202(currNode,tempnextnode)^alpha)*(Eta202(currNode,tempnextnode)^beta);
            end
            P201=P201/sum(P201);
            Pc=cumsum(P201);
            index02= find(Pc >= rand);
            next_node =OpNodeSetLocal(index02(1));%选择参数
            route=[route,next_node];%更新路径
            currNode=route(end);
            OpNodeSetLocal= find(E(currNode,:));% 可选集
        end
        routemat202(i,:)=route;
    end
    
    chrom=[routemat201,routemat202];
    Value= decodingfun(chrom,popsize);%调用成本函数计算成本
    [vmin,indexmin]=min(Value);
    
    %% 更新信息素
    Tau201=updatetau(routemat201,popsize,rho,Q,Tau201,Value);% 更新全局信息素
    Tau202=updatetau(routemat201,popsize,rho,Q,Tau202,Value);% 更新全局信息素
    
    %% 记录最优
    if gen==1
        bestroute=chrom(indexmin,:);%记录最优染色体
        bestvalueaco=vmin;%记录的最优值
    end
    if bestvalueaco>vmin
        bestvalueaco=vmin;%记录的最优值
        bestroute=chrom(indexmin,:);
    end
    tracemataco(gen,1)=bestvalueaco;% 保留最优
    tracemataco(gen,2)=mean(Value);% 均值
    
    waitbar(gen/maxgen,wait_hand);%每循环一次更新一次进步条
end
delete(wait_hand);%执行完后删除该进度条

% 绘图
figure;
plot(tracemataco(:,1),'r-','linewidth',1);
legend({'蚁群最优值'},'fontname','宋体');
xlabel('迭代次数','fontName','宋体');
ylabel('目标函数','fontName','宋体');
title('蚁群算法优化目标函数曲线','fontName','宋体');

disp('显示蚁群算法优化得到的结果');
disp('蚁群算法优化得到最佳目标函数');
bestvalueaco
disp('蚁群算法优化得到最佳路径');
bestroute

x=bestroute;
[y,G]=myfun(x);
G
title201='蚁群算法优化得到的甘特图';
drawgattG(G,jobnumber,title201);



rmpath(genpath('mytoolbox'));

程序结果:

S20 =

1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 6

显示蚁群算法优化得到的结果
蚁群算法优化得到最佳目标函数

bestvalueaco =

蚁群算法优化得到最佳路径

bestroute =

1 至 28 列

12 22 7 15 11 18 4 10 13 8 5 19 20 21 9 14 6 23 2 17 16 1 3 24 1 4 8 11

29 至 48 列

13 15 17 20 23 25 29 32 34 35 39 41 42 47 49 52 54 58 61 62

G =

3 1 3 0 3
6 1 2 0 7
2 1 4 0 6
4 1 6 0 7
3 2 2 7 10
5 1 3 3 8
1 1 1 0 3
3 3 5 10 15
4 2 1 7 15
2 2 2 10 18
2 3 3 18 23
5 2 6 8 16
5 3 2 18 23
6 2 6 16 26
3 4 5 15 18
4 3 3 23 25
2 4 1 23 30
6 3 6 26 35
1 2 3 25 35
5 4 5 23 29
4 4 5 29 41
1 3 6 35 40
1 4 5 41 44
6 4 4 35 40