基于遗传算法的柔性车间调度问题的求解（Flexible Job-shop scheduling problem based on genetic algorithm）

2024-03-19 06:38
文章标签 问题 调度 柔性 problem based 求解 job 遗传算法 algorithm flexible shop scheduling 车间 genetic

本文主要是介绍基于遗传算法的柔性车间调度问题的求解（Flexible Job-shop scheduling problem based on genetic algorithm），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1、前言

距离上次研究传统车间调度问题（Job-shop scheduling problem，JSP ），大约有一个月左右了，这期间研究了一下柔性作业车间调度（Flexible Job-shop scheduling problem，FJSP），并利用MATLAB实现了基于遗传算法的FJSP问题求解。在此与大家分享一下，有问题欢迎评论留言，共同交流学习，完整代码见基于遗传算法的FJSP问题求解（备注：该源码在原来的作业车间调度算法基础上修改，部分命名未及时修改，不影响代码质量）。

2、柔性车间调度问题描述

柔性作业车间调度问题是传统Job-Shop 调度问题的扩展。在传统的 Job-Shop 调度问题中，工件的每道工序只能在一台确定的机床上加工。而在柔性作业车间调度问题中，每道工序可以在多台机床上加工，并且在不同的机床上加工所需时间不同。柔性作业车间调度问题减少了机器约束，扩大了可行解的搜索范围，增加了问题的复杂性。
柔性作业车间调度问题的描述如下：一个加工系统有 m 台机器，要加工 n种工件。每个工件包含一道或多道工序，工件的工序顺序是预先确定的；每道工序可以在多台不同的机床上加工，工序的加工时间随机床的性能不同而变化。调度目标是为每道工序选择最合适的机器、确定每台机器上各工件工序的最佳加工顺序及开工时间，使系统的某些性能指标达到最优。此外，在加工过程中还需满足以下约束条件：

  1. 同一时刻同一台机器只能加工一个零件；
  2. 每个工件在某一时刻只能在一台机器上加工，不能中途中断每一个操作；
  3. 同一工件的工序之间有先后约束，不同工件的工序之间没有先后约束；
  4. 不同工件具有相同的优先级；

例如， 一个包括 3 个工件、5 台机器的柔性作业车间调度加工时间表如表 5.1 所示。柔性作业车间调度问题的求解过程包括两部分：选择各工序的加工机器和确定每台机器上工件的先后顺序。
在这里插入图片描述调度的目标就是确定每个机器上工序的加工顺序和每个工序的开工时间，使得最大完工时间 C m a x C_{max} Cmax​ (makspan)最小或者其他指标达到最优。

3、利用遗传算法求解柔性车间调度问题

3.1、遗传算法编码和解码

编码与解码是指染色体和调度解之间进行相互转换，是遗传算法成功实施优化的首要和关键问题。对于传统的作业车间调度问题，大多数研究采用基于工序的编码。但是柔性作业车间调度问题不仅要确定工序的加工顺序，还需为每道工序选择一台合适的机器，仅采用基于工序的编码方法不能得到问题的解。因此，对于柔性作业车间调度问题，遗传算法的编码由两部分组成，第一部分为基于工序的编码，用来确定工序的加工先后顺序；第二部分为基于机器分配的编码，用来选择每道工序的加工机器。融合这两种编码方法，即可得到柔性作业车间调度问题的一个可行解。结合两种编码方式的染色体如下图所示。
在这里插入图片描述其中基于工序编码的基因串确定工序加工的先后顺序，基于机器编码的基因串确定每个工件所有工序的加工机器。图中所示的染色体表示的工序和机器序列为( O 11 , M 1 O_{11},M_1 O11​,M1​)，( O 21 , M 1 O_{21},M_1 O21​,M1​)，( O 12 , M 3 O_{12},M_3 O12​,M3​），（ O 22 , M 4 O_{22},M_4 O22​,M4​)，( O 13 , M 4 O_{13},M_4 O13​,M4​)，( O 31 , M 3 O_{31},M_3 O31​,M3​)，( O 23 , M 5 O_{23},M_5 O23​,M5​)，( O 32 , M 2 O_{32},M_2 O32​,M2​)，( O 33 , M 2 O_{33},M_2 O33​,M2​)。
解码过程和编码过程相反，解码分为一般解码或者称为半主动解码、主动解码和全主动解码。本文使用半主动解码方式进行染色体解码。

编码代码如下：

function [Population] = Coding(T,PopSize)
%% INPUT：
% T--input matrix:
%  For example: 
%  A partial flexible scheduling problem in which 8 jobs are processed 
%  on 8 machines, in which the number of available machining machines per
%  step of job is less than or equal to the total number of machines
% J1 ={[5 3 5 3 3 0 10 9];[10 0 5 8 3 9 9 6];[0 10 0 5 6 2 4 5]};
% J2 ={[5 7 3 9 8 0 9 0];[0 8 5 2 6 7 10 9];[0 10 0 5 6 4 1 7];[10 8 9 6 4 7 0 0]};
% J3 ={[10 0 0 7 6 5 2 4];[0 10 6 4 8 9 10 0];[1 4 5 6 0 10 0 7]};
% J4 ={[3 1 6 5 9 7 8 4];[12 11 7 8 10 5 6 9];[4 6 2 10 3 9 5 7]}; 
% J5 ={[3 6 7 8 9 0 10 0];[10 0 7 4 9 8 6 0];[0 9 8 7 4 2 7 0];[11 9 0 6 7 5 3 6]};
% J6 ={[6 7 1 4 6 9 0 10];[11 0 9 9 9 7 6 4];[10 5 9 10 11 0 10 0]};
% J7 ={[5 4 2 6 7 0 10 0];[0 9 0 9 11 9 10 5];[0 8 9 3 8 6 0 10]};
% J8 ={[2 8 5 9 0 4 0 10];[7 4 7 8 9 0 10 0];[9 9 0 8 5 6 7 1];[9 0 3 7 1 5 8 0]};
% T={J1;J2;J3;J4;J5;J6;J7;J8}; 8*1 cell
% Popsize- Population size in genetic algorithms,2*PopSize+1
%% OUTPUT:
% Population-Popsize*1 cell
% chromosome-2*1 cell
%% variable declaration
num_of_jobs = length(T);                                                   %number of jobs
num_of_machines = length(T{1}{1});                                         %number of machines
steps_of_job =[];
machine_of_job=cell(num_of_jobs,1);% calculate the length of chromosome
for i = 1:num_of_jobssteps_of_job=[steps_of_job;length(T{i})];
end
len_of_chromosome = sum(steps_of_job);% calculate the machine set for each steps of each job
for i=1:num_of_jobssteps=cell(steps_of_job(i),1);for j = 1:steps_of_job(i)machineset=[];for k=1:length(T{i}{j})if T{i}{j}(k)~=0machineset=[machineset k]; endendsteps{j}=machineset;endmachine_of_job{i}=steps;
end%steps chromosome
%Coding is based on the step of the job
step_chromsome=[];
for i = 1:num_of_jobsfor j = 1:steps_of_job(i)step_chromsome=[step_chromsome i];end
end
step_population =[];
%Generate population with chromosome containing random genes 
for i = 1:PopSizestep_population(i,:)=step_chromsome(randperm(length(step_chromsome(:))));
end
%
%machine chromosome
%In each steps, the machine is randomly selected for two machines,
%and the machine that selects the short processing time is the gene with
%propability
machine_population =[];
for index = 1:PopSizemachine_chromsome=[];for i=1:num_of_jobsfor j=1:steps_of_job(i)pos= randperm(length(machine_of_job{i}{j}),2);machine1=machine_of_job{i}{j}(pos(1));machine2=machine_of_job{i}{j}(pos(2));if (rand(1)<0.8) && (T{i}{j}(machine1)>T{i}{j}(machine2))machine = machine2;elsemachine = machine1;endmachine_chromsome=[machine_chromsome machine];   endendmachine_population(index,:) = machine_chromsome;
endPopulation=cell(PopSize,1);
for i=1:PopSizePopulation{i} =[step_population(i,:);machine_population(i,:)]; 
end
end

解码代码如下

%% Flexible Job-shop scheduling problem based on genetic algorithm with POX selection
% Author：Eric.Wan
% Date：2019-12-8
% Add.：ShenYang,China
% Email:970301442@qq.com
% Version: v1.0
function [Jobs,Cmax,MachineList,ST,PT] = SemiActiveDecoding(T,Chromosome)
%% INPUT:% T--input matrix:%  For example: %  A partial flexible scheduling problem in which 8 jobs are processed %  on 8 machines, in which the number of available machining machines per%  step of job is less than or equal to the total number of machines% J1 ={[5 3 5 3 3 0 10 9];[10 0 5 8 3 9 9 6];[0 10 0 5 6 2 4 5]};% J2 ={[5 7 3 9 8 0 9 0];[0 8 5 2 6 7 10 9];[0 10 0 5 6 4 1 7];[10 8 9 6 4 7 0 0]};% J3 ={[10 0 0 7 6 5 2 4];[0 10 6 4 8 9 10 0];[1 4 5 6 0 10 0 7]};% J4 ={[3 1 6 5 9 7 8 4];[12 11 7 8 10 5 6 9];[4 6 2 10 3 9 5 7]}; % J5 ={[3 6 7 8 9 0 10 0];[10 0 7 4 9 8 6 0];[0 9 8 7 4 2 7 0];[11 9 0 6 7 5 3 6]};% J6 ={[6 7 1 4 6 9 0 10];[11 0 9 9 9 7 6 4];[10 5 9 10 11 0 10 0]};% J7 ={[5 4 2 6 7 0 10 0];[0 9 0 9 11 9 10 5];[0 8 9 3 8 6 0 10]};% J8 ={[2 8 5 9 0 4 0 10];[7 4 7 8 9 0 10 0];[9 9 0 8 5 6 7 1];[9 0 3 7 1 5 8 0]};% T={J1;J2;J3;J4;J5;J6;J7;J8}; 8*1 cell%Chromosome -- A chromosome to be decoded
%% OUTPUT:%JobList-- job sequences%Cmax --the max makespan%MachineList--The machine sequences corresponding to chromosome%ST --the start time for each job step in chromosome%PT --The operation time for each job step in chromome
%% start
num_of_jobs = length(T);                                                   %number of jobs
num_of_machines = length(T{1}{1});                                         %number of machines
len_of_chromosome = length(Chromosome);StepList = [];                                                             %steps for all genes
MachineList = zeros(1,len_of_chromosome);
ST = zeros(1,len_of_chromosome);
PT = zeros(1,len_of_chromosome);
DecodedGenes =[];steps_of_job =[];                                                       
for i = 1:num_of_jobssteps_of_job=[steps_of_job;length(T{i})];
end%% Caculate MachineList and PT
for index = 1:len_of_chromosomeDecodedGenes=[DecodedGenes Chromosome(1,index)];postion = length(find(DecodedGenes==Chromosome(1,index))); StepList = [StepList postion];MachineList(index)=Chromosome(2,sum(steps_of_job(1:(Chromosome(1,index)-1)))+postion);PT(index)=T{Chromosome(1,index)}{postion}(MachineList(index));
end%% Caculate ST
Machines = unique(MachineList);
Jobs = unique(Chromosome(1,:));job_start_time = cell(num_of_jobs,1);
job_end_time = cell(num_of_jobs,1);
machine_start_time = cell(num_of_machines,1);
machine_end_time   = cell(num_of_machines,1);
machine_state = zeros(1,num_of_machines);                                %0--FirstWork;1--NotFirst for index = 1:len_of_chromosomejob = Chromosome(1,index);machine = MachineList(index);pt = PT(index);step = StepList(index);pos_m = find(Machines==machine);pos_j = find(Jobs==job);if step==1                                                             %first step without considering the constrains between steps of same jobif machine_state(pos_m)==0                                         % The machine is first usedjob_start_time{pos_j}=[0,pos_m];job_end_time{pos_j}=[job_start_time{pos_j}(1)+pt,pos_m];elsejob_start_time{pos_j}=[machine_end_time{pos_m}(1),pos_m];job_end_time{pos_j}=[job_start_time{pos_j}(1)+pt,pos_m];endelseif machine_state(pos_m)==0                                         % The machine is first usedjob_start_time{pos_j}=[job_end_time{pos_j}(1),pos_m];job_end_time{pos_j}=[job_start_time{pos_j}(1)+pt,pos_m];elsejob_start_time{pos_j}=[max(machine_end_time{pos_m}(1),job_end_time{pos_j}(1)),pos_m];job_end_time{pos_j}=[job_start_time{pos_j}(1)+pt,pos_m];end       endmachine_start_time{pos_m}= job_start_time{pos_j}(1);machine_end_time{pos_m} = job_end_time{pos_j}(1); machine_state(pos_m)=1;ST(index)=job_start_time{pos_j}(1); 
end%% Caculate Cmax
end_time=cell2mat(job_end_time);
Cmax = max(end_time(:,1));
end

3.2、选择操作

在遗传算法中,适应度是个体对生存环境的适应程度，适应度高的个体将获得更多的生存机会。选择算子根据适应度的值选择个体遗传到下一代群体中。选择操作采用最佳个体保存（Elitist model）和锦标选择（Tournament selection）两种方法。在本章的改进遗传算法中，最佳个体保存方法是将父代群体中最优的 一个个体直接复制到下一代中。锦标选择是从种群中随机选择两个个体，如果随机值（在 0～1 之间随机产生）小于给定概率值 r（概率值 r是一个参数，一般设置为 0.8），则选择优的一个，否则就选择另一个。被选择的个体放回到种群，可以重新作为一个父染色体参与选择。

选择代码如下

BestFitness=min(FITNESS);                                              % find the best chromosomeposition=find(FITNESS==BestFitness);                                   % and the position,may be more than oneBestChromosome=Population{position(1)};                                % choose one chromosome from population%% Selection :Elitism and 2-tournament selection are usedParent = cell(PopSize,1);Pr =0.8;for index =1:PopSize-1pos = randperm(PopSize,2);chromosome1 = Population{pos(1)};chromosome2 = Population{pos(2)};if (rand(1)<Pr) && FITNESS(pos(1))>FITNESS(pos(2))chromosome = chromosome1;elsechromosome = chromosome2;endParent{index} = chromosome;endParent{PopSize}=BestChromosome;

3.3 交叉操作

交叉操作是将种群中两个个体随机地交换某些基因，产生新的基因组合，期望将有益的基因组合在一起。染色体中两部分基因串的交叉分别进行，其中第一部分基于工序编码基因串的交叉操作采用IPOX 交叉算子，第二部分基于机器分配编码基因串的交叉采用多点交叉MPX的方法。

3.3.1 IPOX交叉因子

IPOX操作是在POX操作基础上经改进而形成的（POX不了解的可以参考博文基于遗传算法的传统作业车间调度的问题求解），它仅仅交叉父代染色体中工序的加工序列，保留工件中工序分配的机器到子代。IPOX的具体操作过程如下图所示，其中 P 1 P_1 P1​和 P 2 P_2 P2​为调度问题的两个父代染色体，交叉产生子代 C 1 C_1 C1​和 C 2 C_2 C2​.IPOX交叉操作过程为：
1）把所有的工件随机分成两个集合 G 1 G_1 G1​和 G 2 G_2 G2​;
2) 复制 P 1 P_1 P1​包含在 G 1 G_1 G1​中的工件到 C 1 C_1 C1​，复制 P 2 P_2 P2​包含在 G 2 G_2 G2​中的工件到 C 2 C_2 C2​，保留它们的位置；
3）复制 P 1 P_1 P1​包含在 G 1 G_1 G1​中的工件到 C 2 C_2 C2​，复制 P 2 P_2 P2​包含在 G 2 G_2 G2​中的工件到 C 1 C_1 C1​，保留它们的顺序。
在这里插入图片描述

3.3.2 MPX交叉因子

MPX交叉父代染色体中工序选定的机器，工序的加工顺序保留到子代。多点交叉操作的过程如下图所示。对于某调度问题， P 1 P_1 P1​和 P 2 P_2 P2​为调度问题的两个父代染色体，交叉产生子代 C 1 C_1 C1​和 C 2 C_2 C2​.MPX交叉操作过程为：
1）首先随机产生一个有整数0、1组成的与染色体长度相等的rand[0,1]集；
2）依次在 P 2 P_2 P2​中选出 P 1 P_1 P1​与rand[0,1]集中1的位置对应相同的工序，交换他们分配的机器， P 1 P_1 P1​和 P 2 P_2 P2​ 中其他机器的加工顺序保留到子代，这样分别产生子代 C 1 C_1 C1​和 C 2 C_2 C2​。因为是同一工序的加工机器交换，生成的子代染色体必为可行解。
在这里插入图片描述

交叉操作的代码如下

   %% Crossover: IPOX for steps, MPX for machine Children_group1=cell(PopSize,1);for i=1:(PopSize-1)%Parent individuals are selected for crossover operation:%Parent1 is selected sequentially and Parent2 is selected randomly.index_parent2 = randi([1,(PopSize-1)]);Parent1=Parent{i};Parent2=Parent{index_parent2};Children1=zeros(2,len_of_chromosome);Children2=zeros(2,len_of_chromosome);if rand(1)<=Pc %Use the probability to determine if crossover is required%% Part1: IPX for step%Randomly divide the set of jobs {1,2,3...,n} into two non-empty sub-sets J1 and J2.num_J1 = randi([1,num_of_jobs]);   if num_J1==num_of_jobsnum_J1 = fix(num_of_jobs/2);  endJ = randperm(num_of_jobs);          J1 =J(1:num_J1);J2 =J(num_J1+1:num_of_jobs); % Copy the jobs that Parent1 contains in J1 to Children1, % and Parent2 contains in J2 to Children2, and keep them in place.for index = 1:num_J1                                            % look for jobs that Parent1 are included in J1job = J1(index);for j = 1:len_of_chromosomeif job == Parent1(1,j)Children1(1,j)=Parent1(1,j);end end   endfor index = 1:num_of_jobs-num_J1                                % look for jobs that Parent2 are included in J2job = J2(index);for j = 1:len_of_chromosomeif job == Parent2(1,j)Children2(1,j)=Parent2(1,j);end end   end           %Copy the jobs that Parent1 contains in J1 to Children2, %and Parent2 contains in J2 to Children1 in their order.for index = 1:len_of_chromosome                                            % look for jobs that Parent1 are included in J1job = Parent1(1,index);if ~isempty(find(J1==job, 1))for gene = 1:len_of_chromosomeif Children2(1,gene)==0Children2(1,gene)=job;break;endendendendfor index = 1:len_of_chromosome                                            % look for jobs that Parent1 are included in J1job = Parent2(1,index);if ~isempty(find(J2==job, 1))for gene = 1:len_of_chromosomeif Children1(1,gene)==0Children1(1,gene)=job;break;endendendend%%IPOX cross operation completed%% Part 2 MPX for machine %The process of crossover operation is as follows: firstly, a set rand0_1 %composed of 0 and 1 that is equal to the length of chromosome is randomly %generated, and then the genes at the same position of 1 in the set of rand0_1%in the two parental generations are interchanged, and two offspring are%obtained after the crossoverrand0_1 = zeros(1,len_of_chromosome);for gene = 1:len_of_chromosomeif rand(1)>0.5rand0_1(gene)=1;endendfor gene = 1:len_of_chromosomeif rand0_1(gene)==1Children1(2,gene) = Parent2(2,gene);Children2(2,gene) = Parent1(2,gene);elseChildren1(2,gene) = Parent1(2,gene);Children2(2,gene) = Parent2(2,gene);                   endend    %MOX cross operation completedelse  Children1 = Parent1;Children2 = Parent2;  end%% Select the Fitness value best retained to the next generation[Parent1_FitnessValue] = FitnessCalculator(T,Parent1);[Parent2_FitnessValue] = FitnessCalculator(T,Parent2);[Children1_FitnessValue] = FitnessCalculator(T,Children1);[Children2_FitnessValue] = FitnessCalculator(T,Children2);[~, pos] = max([Parent1_FitnessValue Parent2_FitnessValue Children1_FitnessValue Children2_FitnessValue]);temp_group ={Parent1 Parent2 Children1 Children2};endChildren_group1{PopSize}= BestChromosome;

3.4 变异操作

变异操作的目的是改善算法的局部搜索能力和维持群体多样性，同时防止出现早
熟现象。基于工序编码和基于机器分配编码的变异分别设计如下：

  1. 基于工序编码的变异
    对于这部分基因实施插入变异，即从染色体中随机选择一个基因，然后将之插入到一个随机的位置。
  2. 基于机器分配编码的变异
    由于每道工序都可以由多台机器完成，所以随机选择两道工序，然后在执行这两道工序的机器集合中选择一台机器（采用比例选择策略，加工时间短的优先选择），并将选择的机器号置入对应的基于机器分配编码的基因串中，这样得出的解能确保是可行解。

交叉操作的代码如下

 %% Mutation Children_group2=cell(PopSize,1);for i=1:(PopSize-1)temp_chromsome = Children_group1{i};%% Mutation for stepsif rand(1)<Pmfor j=1:4pos1=randi([1,len_of_chromosome]); % Choose the sequence number of a gene to be mutatedpos2=randi([1,len_of_chromosome]); %  Choose another the sequence number of a gene to be mutatedGene=temp_chromsome(1,pos1); temp_chromsome(1,pos1)=temp_chromsome(1,pos2);temp_chromsome(1,pos2)=Gene;endend%% Mutation for machineif rand(1)<Pmfor k=1:4job = randi([1,num_of_jobs]) ;                                  %random choose jobtempstep = randi([1,steps_of_job(job)]);                            %random choose stepnewmachine = machine_of_job{job}{tempstep}(randi([1,length(machine_of_job{job}{tempstep})]));%random choose machinetemp_chromsome(2,sum(steps_of_job(1:job-1))+1)= newmachine;     %replace the old oneendendChildren_group2{i} = temp_chromsome;    endChildren_group2{PopSize}= BestChromosome;% complete mutation

3.5 绘制甘特图

这部分就是将最优的染色体绘制出来，代码同基于遗传算法的作业车间调度问题求解。

3.6 实验验证

这里使用两个基准实例，即部分柔性实例 T 8 ∗ 8 T_{8*8} T8∗8​和完全柔性实例 T 10 ∗ 10 T_{10*10} T10∗10​.

%% T8x8 
% A partial flexible scheduling problem in which 8 jobs are processed 
% on 8 machines, in which the number of available machining machines per
% step of job is less than or equal to the total number of machines
J1 ={[5 3 5 3 3 0 10 9];[10 0 5 8 3 9 9 6];[0 10 0 5 6 2 4 5]};
J2 ={[5 7 3 9 8 0 9 0];[0 8 5 2 6 7 10 9];[0 10 0 5 6 4 1 7];[10 8 9 6 4 7 0 0]};
J3 ={[10 0 0 7 6 5 2 4];[0 10 6 4 8 9 10 0];[1 4 5 6 0 10 0 7]};
J4 ={[3 1 6 5 9 7 8 4];[12 11 7 8 10 5 6 9];[4 6 2 10 3 9 5 7]}; 
J5 ={[3 6 7 8 9 0 10 0];[10 0 7 4 9 8 6 0];[0 9 8 7 4 2 7 0];[11 9 0 6 7 5 3 6]};
J6 ={[6 7 1 4 6 9 0 10];[11 0 9 9 9 7 6 4];[10 5 9 10 11 0 10 0]};
J7 ={[5 4 2 6 7 0 10 0];[0 9 0 9 11 9 10 5];[0 8 9 3 8 6 0 10]};
J8 ={[2 8 5 9 0 4 0 10];[7 4 7 8 9 0 10 0];[9 9 0 8 5 6 7 1];[9 0 3 7 1 5 8 0]};T8x8={J1;J2;J3;J4;J5;J6;J7;J8};
%% T10x10
% For all flexible scheduling problems of 10 jobs and 10 machines,
% the number of available processing machines in each step of job is equal to 
% the total number of machines
G1={[1 4 6 9 3 5 2 8 9 5];[4 1 1 3 4 8 10 4 11 4];[3 2 5 1 5 6 9 5 10 3]};
G2={[2 10 4 5 9 8 4 15 8 4];[4 8 7 1 9 6 1 10 7 1];[6 11 2 7 5 3 5 14 9 2]};
G3={[8 5 8 9 4 3 5 3 8 1];[9 3 6 1 2 6 4 1 7 2];[7 1 8 5 4 9 1 2 3 4]};
G4={[5 10 6 4 9 5 1 7 1 6];[4 2 3 8 7 4 6 9 8 4];[7 3 12 1 6 5 8 3 5 2]};
G5={[7 10 4 5 6 3 5 15 2 6];[5 6 3 9 8 2 8 6 1 7];[6 1 4 1 10 4 3 11 13 9]};
G6={[8 9 10 8 4 2 7 8 3 10];[7 3 12 5 4 3 6 9 2 15];[4 7 3 6 3 4 1 5 1 11]};
G7={[1 7 8 3 4 9 4 13 10 7];[3 8 1 2 3 6 11 2 13 3];[5 4 2 1 2 1 8 14 5 7]};
G8={[5 7 11 3 2 9 8 5 12 8];[8 3 10 7 5 13 4 6 8 4];[6 2 13 5 4 3 5 7 9 5]};
G9={[3 9 1 3 8 1 6 7 5 4];[4 6 2 5 7 3 1 9 6 7];[8 5 4 8 6 1 2 3 10 12]};
G10={[4 3 1 6 7 1 2 6 20 6];[3 1 8 1 9 4 1 4 17 15];[9 2 4 2 3 5 2 4 10 23]};
T10x10 = {G1;G2;G3;G4;G5;G6;G7;G8;G9;G10};

这里贴上运行8*8实例的运行脚本程序入如下：

clear;
clc;
T = Tmatrix('8x8');
Iterations=100;
PopSize=50;
Pc=0.8;
Pm=0.5;
result=cell(1000,1);[Chromosome] = POX_GA(T,Iterations,PopSize,Pc,Pm);
[Jobs,Cmax,MachineList,ST,PT] = SemiActiveDecoding(T,Chromosome);
GanntGraf(Jobs,Chromosome(1,:),MachineList,ST,PT,Cmax,'FJSP') ;

实验结果如下：
在这里插入图片描述

4、 小结

通过对柔性作业车间调度的研究，一方面加深了对遗传算法解决NP难问题的有效性的体会，利用遗传算法解决这里问题难点在于使用比较好的编码和解码方式，其次是如何避免早熟，解决这两个问题是关键。本文中使用的源代码，存在早熟问题，有待进一步解决，也欢迎各位不吝赐教留言指导；另一方面对制造系统的调度过程有了更深一层次的认识，希望能对今后的学习和工作有所帮助。 以上便是近期对调度问题的入门级探索，不足之处欢迎留言批评指正！

Note：转发请注明出处。

这篇关于基于遗传算法的柔性车间调度问题的求解（Flexible Job-shop scheduling problem based on genetic algorithm）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/825107。

相关文章

关于@MapperScan和@ComponentScan的使用问题

关于@MapperScan和@ComponentScan的使用问题

《关于@MapperScan和@ComponentScan的使用问题》文章介绍了在使用`@MapperScan`和`@ComponentScan`时可能会遇到的包扫描冲突问题,并提供了解决方法,同时,... 目录@MapperScan和@ComponentScan的使用问题报错如下原因解决办法课外拓展总结@
阅读更多...
MybatisGenerator文件生成不出对应文件的问题

MybatisGenerator文件生成不出对应文件的问题

《MybatisGenerator文件生成不出对应文件的问题》本文介绍了使用MybatisGenerator生成文件时遇到的问题及解决方法,主要步骤包括检查目标表是否存在、是否能连接到数据库、配置生成... 目录MyBATisGenerator 文件生成不出对应文件先在项目结构里引入“targetProje
阅读更多...
C#使用HttpClient进行Post请求出现超时问题的解决及优化

C#使用HttpClient进行Post请求出现超时问题的解决及优化

《C#使用HttpClient进行Post请求出现超时问题的解决及优化》最近我的控制台程序发现有时候总是出现请求超时等问题,通常好几分钟最多只有3-4个请求,在使用apipost发现并发10个5分钟也... 目录优化结论单例HttpClient连接池耗尽和并发并发异步最终优化后优化结论我直接上优化结论吧，
阅读更多...
Java内存泄漏问题的排查、优化与最佳实践

Java内存泄漏问题的排查、优化与最佳实践

《Java内存泄漏问题的排查、优化与最佳实践》在Java开发中,内存泄漏是一个常见且令人头疼的问题,内存泄漏指的是程序在运行过程中,已经不再使用的对象没有被及时释放,从而导致内存占用不断增加,最终... 目录引言1. 什么是内存泄漏？常见的内存泄漏情况2. 如何排查 Java 中的内存泄漏？2.1 使用 J
阅读更多...
numpy求解线性代数相关问题

numpy求解线性代数相关问题

《numpy求解线性代数相关问题》本文主要介绍了numpy求解线性代数相关问题,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 在numpy中有numpy.array类型和numpy.mat类型，前者是数组类型，后者是矩阵类型。数组
阅读更多...
解决systemctl reload nginx重启Nginx服务报错:Job for nginx.service invalid问题

解决systemctl reload nginx重启Nginx服务报错:Job for nginx.service invalid问题

《解决systemctlreloadnginx重启Nginx服务报错:Jobfornginx.serviceinvalid问题》文章描述了通过`systemctlstatusnginx.se... 目录systemctl reload nginx重启Nginx服务报错:Job for nginx.javas
阅读更多...
Redis缓存问题与缓存更新机制详解

Redis缓存问题与缓存更新机制详解

《Redis缓存问题与缓存更新机制详解》本文主要介绍了缓存问题及其解决方案,包括缓存穿透、缓存击穿、缓存雪崩等问题的成因以及相应的预防和解决方法,同时,还详细探讨了缓存更新机制,包括不同情况下的缓存更... 目录一、缓存问题1.1 缓存穿透1.1.1 问题来源1.1.2 解决方案1.2 缓存击穿1.2.1
阅读更多...
vue解决子组件样式覆盖问题scoped deep

vue解决子组件样式覆盖问题scoped deep

《vue解决子组件样式覆盖问题scopeddeep》文章主要介绍了在Vue项目中处理全局样式和局部样式的方法,包括使用scoped属性和深度选择器（/deep/）来覆盖子组件的样式,作者建议所有组件... 目录前言scoped分析deep分析使用总结所有组件必须加scoped父组件覆盖子组件使用deep前言
阅读更多...
解决Cron定时任务中Pytest脚本无法发送邮件的问题

解决Cron定时任务中Pytest脚本无法发送邮件的问题

《解决Cron定时任务中Pytest脚本无法发送邮件的问题》文章探讨解决在Cron定时任务中运行Pytest脚本时邮件发送失败的问题,先优化环境变量,再检查Pytest邮件配置,接着配置文件确保SMT... 目录引言1. 环境变量优化：确保Cron任务可以正确执行解决方案：1.1. 创建一个脚本1.2. 修
阅读更多...
Python 标准库time时间的访问和转换问题小结

Python 标准库time时间的访问和转换问题小结

《Python标准库time时间的访问和转换问题小结》time模块为Python提供了处理时间和日期的多种功能,适用于多种与时间相关的场景,包括获取当前时间、格式化时间、暂停程序执行、计算程序运行时... 目录模块介绍使用场景主要类主要函数 - time()- sleep()- localtime()- g
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2