aiwa 发表于 2011-7-31 17:36:08

流水线型车间作业调度问题的遗传算法通用MATLAB源码

流水线型车间作业调度问题可以描述如下:n个任务在流水线上进行m个阶段的加工,每一阶段至少有一台机器且至少有一个阶段存在多台机器,并且同一阶段上各机器的处理性能相同,在每一阶段各任务均要完成一道工序,各任务的每道工序可以在相应阶段上的任意一台机器上加工,已知任务各道工序的处理时间,要求确定所有任务的排序以及每一阶段上机器的分配情况,使得调度指标(一般求Makespan)最小。下面的源码是求解流水线型车间作业调度问题的遗传算法通用MATLAB源码,属于GreenSim团队原创作品,转载请注明。
function =JSPGA(M,N,Pm,T,P)
%--------------------------------------------------------------------------
%JSPGA.m
%流水线型车间作业调度遗传算法
%GreenSim团队原创作品,转载请注明
%Email:greensim@163.com
%GreenSim团队主页:http://blog.sina.com.cn/greensim
%欢迎访问GreenSim——算法仿真团队→http://blog.sina.com.cn/greensim
%--------------------------------------------------------------------------
%输入参数列表
%M       遗传进化迭代次数
%N       种群规模(取偶数)
%Pm      变异概率
%T       m×n的矩阵,存储m个工件n个工序的加工时间
%P       1×n的向量,n个工序中,每一个工序所具有的机床数目
%输出参数列表
%Zp      最优的Makespan值
%Y1p   最优方案中,各工件各工序的开始时刻,可根据它绘出甘特图
%Y2p   最优方案中,各工件各工序的结束时刻,可根据它绘出甘特图
%Y3p   最优方案中,各工件各工序使用的机器编号
%Xp      最优决策变量的值,决策变量是一个实数编码的m×n矩阵
%LC1   收敛曲线1,各代最优个体适应值的记录
%LC2   收敛曲线2,各代群体平均适应值的记录
%最后,程序还将绘出三副图片:两条收敛曲线图和甘特图(各工件的调度时序图)
%第一步:变量初始化
=size(T);%m是总工件数,n是总工序数
Xp=zeros(m,n);%最优决策变量
LC1=zeros(1,M);%收敛曲线1
LC2=zeros(1,N);%收敛曲线2
%第二步:随机产生初始种群
farm=cell(1,N);%采用细胞结构存储种群
for k=1:N
    X=zeros(m,n);
    for j=1:n
      for i=1:m
            X(i,j)=1+(P(j)-eps)*rand;
      end
    end
    farm{k}=X;
end
counter=0;%设置迭代计数器
while counter<M%停止条件为达到最大迭代次数
   
    %第三步:交叉
    newfarm=cell(1,N);%交叉产生的新种群存在其中
    Ser=randperm(N);
    for i=1:2:(N-1)
      A=farm{Ser(i)};%父代个体
      Manner=unidrnd(2);%随机选择交叉方式
      if Manner==1
            cp=unidrnd(m-1);%随机选择交叉点
            %双亲双子单点交叉
            a=;%子代个体
            b=;
      else
            cp=unidrnd(n-1);%随机选择交叉点
            b=;
      end
      newfarm{i}=a;%交叉后的子代存入newfarm
      newfarm{i+1}=b;
    end
    %新旧种群合并
    FARM=;
   
    %第四步:选择复制
    FITNESS=zeros(1,2*N);
    fitness=zeros(1,N);
    plotif=0;
    for i=1:(2*N)
      X=FARM{i};
      Z=COST(X,T,P,plotif);%调用计算费用的子函数
      FITNESS(i)=Z;
    end
    %选择复制采取两两随机配对竞争的方式,具有保留最优个体的能力
    Ser=randperm(2*N);
    for i=1:N
      f2=FITNESS(Ser(2*i));
      if f1<=f2
            farm{i}=FARM{Ser(2*i-1)};
            fitness(i)=FITNESS(Ser(2*i-1));
      else
            farm{i}=FARM{Ser(2*i)};
      end
    end
    %记录最佳个体和收敛曲线
    minfitness=min(fitness)
    meanfitness=mean(fitness)
    LC1(counter+1)=minfitness;%收敛曲线1,各代最优个体适应值的记录
    LC2(counter+1)=meanfitness;%收敛曲线2,各代群体平均适应值的记录
    pos=find(fitness==minfitness);
    Xp=farm{pos(1)};
   
    %第五步:变异
    for i=1:N
      if Pm>rand;%变异概率为Pm
            X=farm{i};
            I=unidrnd(m);
            J=unidrnd(n);
            X(I,J)=1+(P(J)-eps)*rand;
            farm{i}=X;
      end
    end
    farm{pos(1)}=Xp;
   
    counter=counter+1
end
%输出结果并绘图
figure(1);
plotif=1;
X=Xp;
=COST(X,T,P,plotif);
figure(2);
plot(LC1);
figure(3);
plot(LC2);


function =COST(X,T,P,plotif)
%JSPGA的内联子函数,用于求调度方案的Makespan值
%输入参数列表
%X       调度方案的编码矩阵,是一个实数编码的m×n矩阵
%T       m×n的矩阵,存储m个工件n个工序的加工时间
%P       1×n的向量,n个工序中,每一个工序所具有的机床数目
%plotif是否绘甘特图的控制参数
%输出参数列表
%Zp      最优的Makespan值
%Y1p   最优方案中,各工件各工序的开始时刻
%Y2p   最优方案中,各工件各工序的结束时刻
%Y3p   最优方案中,各工件各工序使用的机器编号
%第一步:变量初始化
=size(X);
Y1p=zeros(m,n);
Y2p=zeros(m,n);
Y3p=zeros(m,n);
%第二步:计算第一道工序的安排
Q1=zeros(m,1);
Q2=zeros(m,1);
R=X(:,1);%取出第一道工序
Q3=floor(R);%向下取整即得到各工件在第一道工序使用的机器的编号
%下面计算各工件第一道工序的开始时刻和结束时刻
for i=1:P(1)%取出机器编号
    pos=find(Q3==i);%取出使用编号为i的机器为其加工的工件的编号
    lenpos=length(pos);
    if lenpos>=1
      Q1(pos(1))=0;
      if lenpos>=2
            for j=2:lenpos
                Q1(pos(j))=Q2(pos(j-1));
                Q2(pos(j))=Q2(pos(j-1))+T(pos(j),1);
            end
      end
    end
end
Y1p(:,1)=Q1;
Y3p(:,1)=Q3;
%第三步:计算剩余工序的安排
for k=2:n
    R=X(:,k);%取出第k道工序
    Q3=floor(R);%向下取整即得到各工件在第k道工序使用的机器的编号
    %下面计算各工件第k道工序的开始时刻和结束时刻
    for i=1:P(k)%取出机器编号
      pos=find(Q3==i);%取出使用编号为i的机器为其加工的工件的编号
      lenpos=length(pos);
      if lenpos>=1
            EndTime=Y2p(pos,k-1);%取出这些机器在上一个工序中的结束时刻
            POS=zeros(1,lenpos);%上一个工序完成时间由早到晚的排序
            for jj=1:lenpos
                POS(jj)=ppp(1);
                EndTime(ppp(1))=Inf;
            end            
            %根据上一个工序完成时刻的早晚,计算各工件第k道工序的开始时刻和结束时刻
            Q1(pos(POS(1)))=Y2p(pos(POS(1)),k-1);
            Q2(pos(POS(1)))=Q1(pos(POS(1)))+T(pos(POS(1)),k);%前一个工件的结束时刻
            if lenpos>=2
                for j=2:lenpos
                  Q1(pos(POS(j)))=Y2p(pos(POS(j)),k-1);%预定的开始时刻为上一个工序的结束时刻
                  if Q1(pos(POS(j)))<Q2(pos(POS(j-1)))%如果比前面的工件的结束时刻还早
                        Q1(pos(POS(j)))=Q2(pos(POS(j-1)));
                  end
                end
            end
      end
    end
    Y1p(:,k)=Q1;
    Y2p(:,k)=Q2;
    Y3p(:,k)=Q3;
end
%第四步:计算最优的Makespan值
Y2m=Y2p(:,n);
Zp=max(Y2m);
%第五步:绘甘特图
if plotif
    for i=1:m
      for j=1:n
            mPoint1=Y1p(i,j);
            mPoint2=Y2p(i,j);
            mText=m+1-i;
            PlotRec(mPoint1,mPoint2,mText);
            Word=num2str(Y3p(i,j));
            %text(0.5*mPoint1+0.5*mPoint2,mText-0.5,Word);
            hold on
            x1=mPoint1;y1=mText-1;
            x2=mPoint2;y2=mText-1;
            x4=mPoint1;y4=mText;
            %fill(,,'r');
            fill(,,);
            text(0.5*mPoint1+0.5*mPoint2,mText-0.5,Word);
      end
    end
end
function PlotRec(mPoint1,mPoint2,mText)
%此函数画出小矩形
%输入:
%mPoint1    输入点1,较小,横坐标
%mPoint2    输入点2,较大,横坐标
%mText      输入的文本,序号,纵坐标
vPoint = zeros(4,2) ;
vPoint(1,:) = ;
vPoint(2,:) = ;
vPoint(3,:) = ;
vPoint(4,:) = ;
plot(,);
hold on ;
plot(,);
plot(,);
plot(,);

欢迎访问GreenSim团队主页:http://blog.sina.com.cn/greensim
欢迎访问GreenSim——算法仿真团队→http://blog.sina.com.cn/greensim
页: [1]
查看完整版本: 流水线型车间作业调度问题的遗传算法通用MATLAB源码