查看: 6091|回复: 5

[求助]车间调度的遗传算法

字体大小: 正常放大

rhin

1 主题	0 听众	17 积分

升级 12.63%

该用户从未签到

电梯直达

1^#

发表于 2006-3-21 09:03 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

急需，大侠们帮帮忙吧

zan

转播0 淘帖0 分享0 收藏0 支持0 反对0 微信

使用道具举报

shenjian

0 主题	3 听众	21 积分

升级 16.84%

该用户从未签到

2^#

发表于 2006-4-14 00:34 |只看该作者 |招呼Ta 关注Ta

niu!!

我也说一句

发表

使用道具举报

tanwenyong1000

8 主题	5 听众	256 积分

升级 78%

该用户从未签到

群组: 数学建模

群组: 建模联盟

群组: 数模者

3^#

发表于 2009-8-22 00:51 |只看该作者 |招呼Ta 关注Ta

虽然很久了，给个答案吧，，车间作业调度问题遗传算法通用Matlab程序(2009-04-14 19:01:46)标签：杂谈
明：此程序包含本人的原创成果，尚不能完全公开发表，故随机删掉了其中的几行，一般人是很难将其补充完整并正确运行的。
function [Zp,Y1p,Y2p,Y3p,Xp,LC1,LC2]=JSPGA(M,N,Pm,T,P)
%--------------------------------------------------------------------------
%  JSPGA.m
%  车间作业调度问题遗传算法
%--------------------------------------------------------------------------
%  输入参数列表
%  M    遗传进化迭代次数
%  N    种群规模(取偶数)
%  Pm    变异概率
%  T    m×n的矩阵，存储m个工件n个工序的加工时间
%  P    1×n的向量，n个工序中，每一个工序所具有的机床数目
%  输出参数列表
%  Zp    最优的Makespan值
%  Y1p    最优方案中，各工件各工序的开始时刻，可根据它绘出甘特图
%  Y2p    最优方案中，各工件各工序的结束时刻，可根据它绘出甘特图
%  Y3p    最优方案中，各工件各工序使用的机器编号
%  Xp    最优决策变量的值，决策变量是一个实数编码的m×n矩阵
%  LC1    收敛曲线1，各代最优个体适应值的记录
%  LC2    收敛曲线2，各代群体平均适应值的记录
%  最后，程序还将绘出三副图片：两条收敛曲线图和甘特图（各工件的调度时序图）

%第一步：变量初始化
[m,n]=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

%第三步：交叉
newfarm=cell(1,N);%交叉产生的新种群存在其中
Ser=randperm(N);
for i=1:2

N-1)
      A=farm{Ser(i)};%父代个体
      B=farm{Ser(i+1)};
      Manner=unidrnd(2);%随机选择交叉方式
      if Manner==1
         cp=unidrnd(m-1);%随机选择交叉点
         %双亲双子单点交叉
         a=[A(1:cp,

;B((cp+1):m,

];%子代个体
b=[B(1:cp,

;A((cp+1):m,

];
      else
         cp=unidrnd(n-1);%随机选择交叉点
         a=[A(:,1:cp),B(:,(cp+1):n)];%双亲双子单点交叉
         b=[B(:,1:cp),A(:,(cp+1):n)];
      end
      newfarm{i}=a;%交叉后的子代存入newfarm
      newfarm{i+1}=b;
end
%新旧种群合并
FARM=[farm,newfarm];

%第四步：选择复制
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
      f1=FITNESS(Ser(2*i-1));
      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)};
         fitness(i)=FITNESS(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;
[Zp,Y1p,Y2p,Y3p]=COST(X,T,P,plotif);
figure(2);
plot(LC1);
figure(3);
plot(LC2);

function [Zp,Y1p,Y2p,Y3p]=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    最优方案中，各工件各工序使用的机器编号

%第一步：变量初始化
[m,n]=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

(1)%取出机器编号
pos=find(Q3==i);%取出使用编号为i的机器为其加工的工件的编号
lenpos=length(pos);
if lenpos>=1
      Q1(pos(1))=0;
      Q2(pos(1))=T(pos(1),1);
      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;
Y2p(:,1)=Q2;
Y3p(:,1)=Q3;

%第三步：计算剩余工序的安排
for k=2:n
R=X(:,k);%取出第k道工序
Q3=floor(R);%向下取整即得到各工件在第k道工序使用的机器的编号
%下面计算各工件第k道工序的开始时刻和结束时刻
for i=1

(k)%取出机器编号
      pos=find(Q3==i);%取出使用编号为i的机器为其加工的工件的编号
      lenpos=length(pos);
      if lenpos>=1
         POS=zeros(1,lenpos);%上一个工序完成时间由早到晚的排序
         for jj=1:lenpos
            MinEndTime=min(EndTime);
            ppp=find(EndTime==MinEndTime);
            POS(jj)=ppp(1);
            EndTime(ppp(1))=Inf;
         end
         %根据上一个工序完成时刻的早晚，计算各工件第k道工序的开始时刻和结束时刻
                     if lenpos>=2
            for j=2:lenpos
                  Q1(pos(POS(j)))=Y2p(pos(POS(j)),k-1);%预定的开始时刻为上一个工序的结束时刻
                  if Q1(pos(POS(j)))
                     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;
         x3=mPoint2;y3=mText;
         x4=mPoint1;y4=mText;
         %fill([x1,x2,x3,x4],[y1,y2,y3,y4],'r');
         fill([x1,x2,x3,x4],[y1,y2,y3,y4],[1,0.5,1]);
         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,

= [mPoint1,mText-1];
vPoint(2,

= [mPoint2,mText-1];
vPoint(3,

= [mPoint1,mText];
vPoint(4,

= [mPoint2,mText];
plot([vPoint(1,1),vPoint(2,1)],[vPoint(1,2),vPoint(2,2)]);
hold on ;
plot([vPoint(1,1),vPoint(3,1)],[vPoint(1,2),vPoint(3,2)]);
plot([vPoint(2,1),vPoint(4,1)],[vPoint(2,2),vPoint(4,2)]);
plot([vPoint(3,1),vPoint(4,1)],[vPoint(3,2),vPoint(4,2)]);

已投稿到：排行榜圈子阅读(39)|评论(0)|收藏(0)|打印|举报
前一篇：遗传算法matlab程序
后一篇：Matlab工具箱