【车间调度】基于matlab遗传算法求解车间调度问题【含Matlab源码 1396期】

一、车间调度简介

1 车间调度定义 车间调度是指根据产品制作的合理需求分配加工车间次序，然后达到合理运用产品制作资源、进步企业经济效益的意图。车间调度问题从数学上能够描绘为有n个待加工的零件要在m台机器上加工。问题需求满意的条件包含每个零件的各道工序运用每台机器不多于1次，每个零件都按照一定的次序进行加工。

2 传统作业车间调度 传统作业车间带调度实例

有若干工件，每个工件有若干工序，有多个加工机器，可是每道工序只能在一台机器上加工。对应到上面表格中的实例便是，两个工件，工件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 柔性作业车间调度 柔性作业车间带调度实例（参阅自高亮教师论文 《改进遗传算法求解柔性作业车间调度问题》——机械工程学报）

相比于传统作业车间调度，柔性作业车间调度放宽了对加工机器的束缚，更符合实践出产情况，每个工序可选加工机器变成了多个，能够由多个加工机器中的一个加工。比方上表中的实例，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]的机器组合。调度的意图还是总的竣工时刻最短（也可所以其他方针，比方机器最大负荷最短、总的机器负荷最短）

二、遗传算法简介

1 遗传算法概述 遗传算法（Genetic Algorithm，GA）是进化核算的一部分，是仿照达尔文的遗传挑选和天然筛选的生物进化进程的核算模型，是一种经过仿照天然进化进程查找最优解的办法。该算法简略、通用，鲁棒性强，适于并行处理。

2 遗传算法的特点和运用 遗传算法是一类可用于杂乱体系优化的具有鲁棒性的查找算法，与传统的优化算法相比，具有以下特点： （1）以决议计划变量的编码作为运算方针。传统的优化算法往往直接运用决议计划变量的实践值本身来进行优化核算，但遗传算法是运用决议计划变量的某种办法的编码作为运算方针。这种对决议计划变量的编码处理办法，使得咱们在优化核算中可学习生物学中染色体和基因等概念，能够仿照天然界中生物的遗传和进化鼓励，也能够很方便地运用遗传操作算子。 （2）直接以习惯度作为查找信息。传统的优化算法不只需求运用方针函数值，并且查找进程往往受方针函数的连续性束缚，有或许还需求满意“方针函数的导数有必要存在”的要求以确认查找方向。遗传算法仅运用由方针函数值变换来的习惯度函数值就可确认进一步的查找规模，无需方针函数的导数值等其他辅助信息。直接运用方针函数值或个别习惯度值也能够将查找规模集中到习惯度较高部分的查找空间中，然后进步查找功率。 （3）运用多个点的查找信息，具有隐含并行性。传统的优化算法往往是从解空间的一个初始点开端最优解的迭代查找进程。单个点所提供的查找信息不多，所以查找功率不高，还有或许堕入部分最优解而停滞；遗传算法从由许多个别组成的初始种群开端最优解的查找进程，而不是从单个个别开端查找。对初始集体进行的、挑选、穿插、变异等运算，发生出新一代集体，其中包含了许多集体信息。这些信息能够防止查找一些不必要的点，然后防止堕入部分最优，逐步迫临大局最优解。 （4） 运用概率查找而非确认性规则。传统的优化算法往往运用确认性的查找办法，一个查找点到另一个查找点的搬运有确认的搬运方向和搬运联系，这种确认性或许使得查找达不到最优店，约束了算法的运用规模。遗传算法是一种自习惯查找技术，其挑选、穿插、变异等运算都是以一种概率办法进行的，增加了查找进程的灵活性，并且能以较大概率收敛于最优解，具有较好的大局优化求解才能。但，穿插概率、变异概率等参数也会影响算法的查找成果和查找功率，所以怎么挑选遗传算法的参数在其运用中是一个比较重要的问题。 综上，因为遗传算法的全体查找战略和优化查找办法在核算时不依赖于梯度信息或其他辅助常识，只需求求解影响查找方向的方针函数和相应的习惯度函数，所以遗传算法提供了一种求解杂乱体系问题的通用结构。它不依赖于问题的详细领域，对问题的品种有很强的鲁棒性，所以广泛运用于各种领域，包含：函数优化、组合优化出产调度问题、自动控制 、机器人学、图画处理（图画康复、图画边际特征提取……)、人工生命、遗传编程、机器学习。

3 遗传算法的根本流程及完结技术 根本遗传算法（Simple Genetic Algorithms,SGA）只运用挑选算子、穿插算子和变异算子这三种遗传算子，进化进程简略，是其他遗传算法的根底。

3.1 遗传算法的根本流程 经过随机办法发生若干由确认长度（长度与待求解问题的精度有关）编码的初始集体； 经过习惯度函数对每个个别进行点评，挑选习惯度值高的个别参加遗传操作，习惯度低的个别被筛选； 经遗传操作（复制、穿插、变异）的个别集合构成新一代种群，直到满意停止准则（进化代数GEN>=?）； 将子孙中变现最好的个别作为遗传算法的执行成果。

其中，GEN是当时代数；M是种群规模，i代表种群数量。

3.2 遗传算法的完结技术 根本遗传算法（SGA）由编码、习惯度函数、遗传算子（挑选、穿插、变异）及运转参数组成。 3.2.1 编码 （1）二进制编码 二进制编码的字符串长度与问题所求解的精度有关。需求确保所求解空间内的每一个个别都能够被编码。 长处：编、解码操作简略，遗传、穿插便于完结 缺陷：长度大 （2）其他编码办法 格雷码、浮点数编码、符号编码、多参数编码等 3.2.2 习惯度函数 习惯度函数要有用反映每一个染色体与问题的最优解染色体之间的距离。 3.2.3挑选算子

3.2.4 穿插算子 穿插运算是指对两个彼此配对的染色体按某种办法彼此交流其部分基因，然后构成两个新的个别；穿插运算是遗传算法差异于其他进化算法的重要特征，是发生新个别的首要办法。在穿插之前需求将集体中的个别进行配对，一般采取随机配对原则。 常用的穿插办法： 单点穿插 双点穿插（多点穿插，穿插点数越多，个别的结构被破坏的或许性越大，一般不选用多点穿插的办法） 均匀穿插 算术穿插 3.2.5 变异算子 遗传算法中的变异运算是指将个别染色体编码串中的某些基因座上的基因值用该基因座的其他等位基因来替换，然后构成一个新的个别。

就遗传算法运算进程中发生新个别的才能方面来说，穿插运算是发生新个别的首要办法，它决议了遗传算法的大局查找才能；而变异运算仅仅发生新个别的辅助办法，但也是必不可少的一个运算进程，它决议了遗传算法的部分查找才能。穿插算子与变异算子的共同合作完结了其对查找空间的大局查找和部分查找，然后使遗传算法能以良好的查找功能完结最优化问题的寻优进程。

3.2.6 运转参数

4 遗传算法的根本原理 4.1 形式定理

4.2 积木块假定 具有低阶、定义长度短，且习惯度值高于集体均匀习惯度值的形式称为基因块或积木块。 积木块假定：个别的基因块经过挑选、穿插、变异等遗传算子的效果，能够彼此拼接在一起，构成习惯度更高的个别编码串。 积木块假定说明晰用遗传算法求解各类问题的根本思想，即经过积木块直接彼此拼接在一起能够发生更好的解。

三、部分源代码

clc;clear
%% 下载数据
% 加工数据包含加工时刻，加工机器，机器数，各机器权重，工件数，各工件对应的工序数
load data operation_time operation_machine num_machine machine_weight num_job num_op
%% 根本参数
MAXGEN = 200;               % 最大迭代次数
Ps = 0.8;                   % 挑选率
Pc = 0.7;                   % 穿插率
Pm = 0.3;                   % 变异率
sizepop = 200;              % 个别数目
e = 0.5;                    % 方针值权重
trace = zeros(2,MAXGEN);
%% ===========================种群初始化============================
total_op_num=sum(num_op);
chroms=initialization(num_op,num_job,total_op_num,sizepop,operation_machine,operation_time);
[Z,~,~]=fitness(chroms,num_machine,e,num_job,num_op);
%% ============================迭代进程=============================
for gen=1:MAXGEN
    fprintf('当时迭代次数：'),disp(gen)
    % 轮盘赌挑选
    chroms_new=selection(chroms,Z,Ps);
    % 穿插操作
    chroms_new=crossover(chroms_new,Pc,total_op_num,num_job,num_op);
    % 变异操作
    chroms_new=mutation(chroms_new,total_op_num,Pm,num_machine,e,num_job,num_op,operation_machine,operation_time);
    % 核算挑选穿插变异后个别的习惯度
    [Z_new,~,~]=fitness(chroms_new,num_machine,e,num_job,num_op);
    % 根据习惯度在原种群和遗传操作后的种群中选出sizepop个更优个别
    [chroms,Z,chrom_best]=update_chroms(chroms,chroms_new,Z,Z_new,sizepop);
    % 记载每代的最优习惯度与均匀习惯度
    trace(1, gen)=Z(1);       
    trace(2, gen)=mean(Z);  
    % 更新大局最优习惯度
    if gen==1 || MinVal>trace(1,gen)
        MinVal=trace(1,gen);
function [Z,machine_weight,pvals] = fitness(chroms,num_machine,e,num_job,num_op)
sizepop=size(chroms,1);
pvals=cell(1,sizepop);
Z1=zeros(1,sizepop);
Z2=Z1;
total_op_num=sum(num_op);  % 总工序数
for k=1:sizepop
    chrom=chroms(k,:);
    machine=zeros(1,num_machine);  % 记载各机器改变时刻
    job=zeros(1,num_job);  % 记载各工件改变时刻
    machine_time=zeros(1,num_machine);  % 核算各机器的实践加工时刻
    pval=zeros(2,total_op_num);  % 记载各工序开端和完毕时刻
    for i=1:total_op_num
        % 机器时刻大于工件时刻
        if machine(chrom(total_op_num+i))>=job(chrom(i))
            pval(1,i)=machine(chrom(total_op_num+i));  % 记载工件开端时刻
            machine(chrom(total_op_num+i))=machine(chrom(total_op_num+i))+chrom(total_op_num*2+i);
            job(chrom(i))=machine(chrom(total_op_num+i));
            pval(2,i)=machine(chrom(total_op_num+i));  % 记载工件完毕时刻
            % 机器时刻小于工件时刻
        else
            pval(1,i)=job(chrom(i));
            job(chrom(i))=job(chrom(i))+chrom(total_op_num*2+i);
            machine(chrom(total_op_num+i))=job(chrom(i));
            pval(2,i)=job(chrom(i));
        end
        machine_time(chrom(total_op_num+i))=machine_time(chrom(total_op_num+i))+chrom(total_op_num*2+i);
    end
    Z1(k)=max(machine);  % 最大机器时刻值，对应makespan
    % machine_weight=machine_time/sum(machine_time);  % 核算各机器的负荷
    machine_weight=machine_time;
    Z2(k)=max(machine_weight)-min(machine_weight);
    pvals{k}=pval;
end
% min_makespan=min(Z1);%一切染色体的makespan最优值
% max_makespan=max(Z1);
% min_weight=min(Z2);%负载最优值
% max_weight=max(Z2);
% Z=e*((Z1-min_makespan)./(max_makespan-min_makespan))+(1-e)*((Z2-min_weight)./(max_weight-min_weight));%核算习惯度
Z=e*Z1+(1-e)*Z2;
function [ chroms_new] = crossover(chroms,Pc,total_op_num,num_job,num_op)
size_chrom=size(chroms,1);  % 染色体数
chroms_new=chroms;
%% 面向工序码的穿插操作
for i=1:2:size_chrom-1 
    if Pc>rand
        % 父代染色体
        parent1=chroms(i,:);
        parent2=chroms(i+1,:);
        Job=randperm(num_job);
        % 将工件随机分红两个集合
        J1=Job(1:round(num_job/2));
        J2=Job(length(J1)+1:end);
        % 子代染色体
        child1=parent1;
        child2=parent2;
        op_p1=[];
        op_p2=[];
        for j=1:length(J2)
            %找出父代中J2片段对应的方位
            op_p1=[op_p1,find(parent1(1:total_op_num)==J2(j))];
            op_p2=[op_p2,find(parent2(1:total_op_num)==J2(j))];
        end
        op_s1=sort(op_p1);
        op_s2=sort(op_p2);
        % 子代1交流J2片段的基因，机器码对应方位的基因，工时码对应方位的基因
        child1(op_s1)=parent2(op_s2);
        child1(total_op_num+op_s1)=parent2(total_op_num+op_s2);
        child1(total_op_num*2+op_s1)=parent2(total_op_num*2+op_s2);
        % 子代2同理
        child2(op_s2)=parent1(op_s1);
        child2(total_op_num+op_s2)=parent1(total_op_num+op_s1);
        child2(total_op_num*2+op_s2)=parent1(total_op_num*2+op_s1);
        chroms_new(i,:)=child1;
        chroms_new(i+1,:)=child2;
    end
end
%% 面向机器码的穿插操作
for k=1:2:size_chrom-1
    if Pc>rand
        parent1=chroms_new(k,:);
        parent2=chroms_new(k+1,:);
        child1=parent1;
        child2=parent2;
        % 随机发生与染色体长度持平的0,1序列
        rand0_1=randi([0,1],1,total_op_num);
        for n=1:num_job
            ind_0=find(rand0_1(num_op(n)*(n-1)+1:num_op(n)*n)==0);
            if ~isempty(ind_0)
                temp1=find(parent1(1:total_op_num)==n);
                temp2=find(parent2(1:total_op_num)==n);
                child1(total_op_num+temp1(ind_0))=parent2(total_op_num+temp2(ind_0));
                child2(total_op_num+temp2(ind_0))=parent1(total_op_num+temp1(ind_0));
                child1(total_op_num*2+temp1(ind_0))=parent2(total_op_num*2+temp2(ind_0));
                child2(total_op_num*2+temp2(ind_0))=parent1(total_op_num*2+temp1(ind_0));
            end
        end
        chroms_new(k,:)=child1;
        chroms_new(k+1,:)=child2;
    end
end
end

四、运转成果

五、matlab版别及参阅文献

1 matlab版别 2014a

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