decomyque.m

遗传算法的小程序

% decomyque.m
function  fitness=decomyque(A,M,pt)
L=length(A);
B=zeros(1,L); 
B(1)=1;
a=zeros(1,L);
for i=2:L
    a(i)=A(i);
    b=find(A(1:(i-1))==a(i));
    B(i)=length(b)+1;        %求出染色体A中的每个基因A(i)对应的工件在该位置属于其第几个工序
end
[n,m]=size(M);
st=zeros(n,m);
et=zeros(n,m);
st(A(1),B(1))=0;et(A(1),B(1))=pt(A(1),B(1));
c=zeros(L);d=zeros(1,L);
for i=2:L
    for k=1:(i-1)
        if M(A(k),B(k))==M(A(i),B(i))
            c(i,k)=k;          %若基因A(k)表示的工件工序与基因A(i)表示的工件工序存在机器冲突
        else  c(i,k)=0;        %若基因A(k)表示的工件工序与基因A(i)表示的工件工序不存在机器冲突
        end
    end
    d(i)=max(c(i,:));
end
for i=2:L
    if (d(i)==0&B(i)==1)       %若基因A(i)前面没有工件工序与之存在机器冲突，且此工序为工件的首工序
            st(A(i),B(i))=0;
    elseif (d(i)==0&B(i)~=1)  %若基因A(i)前面没有工件工序与之存在机器冲突，且此工序不为工件的首工序
            st(A(i),B(i))=et(A(i),B(i)-1);
    elseif (d(i)~=0&B(i)==1)  %若基因A(i)前面有工件工序与之存在机器冲突，且此工序为工件的首工序
            [i_before,j_before]=find(M==M(A(i),B(i))&et>0);
            et_before=zeros(1,length(i_before));
            st_before=zeros(1,length(i_before));
            for s=1:length(i_before)
                et_before(s)=et(i_before(s),j_before(s));
                st_before(s)=st(i_before(s),j_before(s));
            end
            st(A(i),B(i))=max(et_before);
                tempst_before=st_before;
                st_before=sort(tempst_before);
                tempet_before=et_before;
                et_before=sort(tempet_before);
         if length(i_before)>1 
            for s=1:(length(i_before)-1)
                if pt(A(i),B(i))<=st_before(s+1)-et_before(s)
                    st(A(i),B(i))=et_before(s);
                    break;
                end
            end
        end
            if pt(A(i),B(i))<=st_before(1)
                st(A(i),B(i))=0;
            end
    else                       %若基因A(i)前面有工件工序与之存在机器冲突，且此工序不为工件的首工序
            [i_before,j_before]=find(M==M(A(i),B(i))&et>0);
            et_before=zeros(1,length(i_before));
            st_before=zeros(1,length(i_before));
            for s=1:length(i_before)
                et_before(s)=et(i_before(s),j_before(s));
                st_before(s)=st(i_before(s),j_before(s));
            end
                tempst_before=st_before;
                st_before=sort(tempst_before);
                tempet_before=et_before;
                et_before=sort(tempet_before);
         if max(et_before)<=et(A(i),B(i)-1)
            st(A(i),B(i))=et(A(i),B(i)-1);
        else
            st(A(i),B(i))=max(et_before);
            number_1=find(et_before>et(A(i),B(i)-1));
            if length(number_1)>1
                for s_1=1:(length(number_1)-1)
                    if pt(A(i),B(i))<=st_before(number_1(s_1+1))-et_before(number_1(s_1))
                         st(A(i),B(i))=et_before(number_1(s_1));
                         break;
                     end
                 end
             end
             if pt(A(i),B(i))<=st_before(number_1(1))-et(A(i),B(i)-1)
                 st(A(i),B(i))=et(A(i),B(i)-1);
             end
         end
     end
         et(A(i),B(i))=st(A(i),B(i))+pt(A(i),B(i));
   end
makespan=max(max(et));
const_a=2;
const_b=0.01;
fitness=const_a*exp(-const_b*makespan);