福州做网站企业,花都做网站公司,北仑网站推广,关键词排名优化公司地址PS#xff1a;本文章对于基于遗传算法的传统作业车间调度问题的求解#xff08;Job-shop scheduling problem based on genetic algorithm#xff09;_遗传算法求解调度问题仿真实验-CSDN博客
中提到的代码进行详细解释#xff0c;仅作为学习记录
#xff08;1#xff…PS本文章对于基于遗传算法的传统作业车间调度问题的求解Job-shop scheduling problem based on genetic algorithm_遗传算法求解调度问题仿真实验-CSDN博客
中提到的代码进行详细解释仅作为学习记录
1编码
% 初始化一个空列表
initial [];% 根据作业的步骤生成初始序列
for i 1 : num_of_jobsfor j 1 : number_of_machines% 将作业索引 i 添加到 initial 列表中initial [initial i];end
end% 生成包含随机基因的种群染色体
for i 1 : PopSize% 使用 randperm 函数对 initial 列表进行随机排列并将结果赋值给种群矩阵的当前行population(i, :) initial(randperm(length(initial(:))));
end
代码解释 initial[];初始化一个空列表initial用于存储作业的步骤。 for i 1:num_of_jobs外层循环遍历作业的步骤。 for j 1:number_of_machines内层循环遍历每个作业在机器上的执行顺序。 initial[initial i];将当前作业的索引i添加到initial列表中。这样做的目的是生成一个基本的作业顺序其中每个作业在每个机器上执行一次。在每次迭代中将作业索引添加到initial列表。 外层循环结束后initial列表中将包含按照作业步骤顺序生成的元素。 for i 1:PopSize循环生成种群。 population(i,:) initial(randperm(length(initial(:))));对initial列表进行随机排列并将结果赋值给种群矩阵的当前行。randperm(length(initial(:)))生成一个长度与initial列表相同的随机排列索引然后使用这些索引对initial列表进行重新排列。这样得到的结果就是一个随机的染色体即一种作业顺序的排列。 最终population矩阵的每一行代表一个随机生成的染色体即一种作业顺序的排列。这个种群矩阵将作为遗传算法的初始种群用于后续的进化和优化过程。
2解码
function [Jobs, Cmax, MachineList, ST, PT] SemiActiveDecoding(T, Chromosome)
% INPUT:
% T -- 输入矩阵
% 每个实例由一行描述组成一行包含作业数量和机器数量然后每个作业占用一行
% 列出每个作业的每个步骤的机器编号和处理时间。机器从0开始编号。
% Chromosome -- 要解码的染色体
% OUTPUT:
% Jobs -- 作业序列
% Cmax -- 最大完成时间
% MachineList -- 与染色体对应的机器序列
% ST -- 染色体中每个作业步骤的开始时间
% PT -- 染色体中每个作业步骤的处理时间% % Fisher和Thompson 6x6实例备用名称mt06% 6 6% 2 1 0 3 1 6 3 7 5 3 4 6% 1 8 2 5 4 10 5 10 0 10 3 4% 2 5 3 4 5 8 0 9 1 1 4 7% 1 5 0 5 2 5 3 3 4 8 5 9 % 2 9 1 3 4 5 5 4 0 3 3 1% 1 3 3 3 5 9 0 10 4 4 2 1% %% start
[num_of_jobs, number_of_machines] size(T);
%% 在这个例子中每个作业有6个步骤
%% 每个步骤包含机器编号和处理时间。因此
%%总共有12个列其中6列是机器编号6列是处理时间。
number_of_machines number_of_machines / 2; % 作业和机器的数量
Jobs unique(Chromosome);
StepList []; % 所有基因的步骤列表
MachineList [];
DecodedGenes [];
ST [];
PT [];
len_of_chromosome num_of_jobs * number_of_machines;%% 计算了 MachineList 和 PT即机器序列和处理时间。
for index 1:len_of_chromosomeDecodedGenes [DecodedGenes Chromosome(index)];postion length(find(DecodedGenes Chromosome(index)));StepList [StepList postion];pos1 postion * 2 - 1;pos2 postion * 2;MachineList [MachineList T(Chromosome(index), pos1)];PT [PT T(Chromosome(index), pos2)];
end%% 计算 ST即作业的开始时间
Machines unique(MachineList);
steps unique(StepList);job_start_time cell(num_of_jobs, 1);
job_end_time cell(num_of_jobs, 1);
machine_start_time cell(number_of_machines, 1);
machine_end_time cell(number_of_machines, 1);
machine_state zeros(1, number_of_machines); % 0--FirstWork; 1--NotFirstfor index 1:len_of_chromosomejob Chromosome(index);machine MachineList(index);pt PT(index);step StepList(index);pos_m find(Machines machine);pos_j find(Jobs job);if step 1 % 第一个步骤不考虑同一作业步骤之间的约束if machine_state(pos_m) 0 % 机器首次使用job_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 % 机器首次使用job_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];endendmachine_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 [ST, job_start_time{pos_j}(1)];
end%% 计算 Cmax即最大完成时间
end_time cell2mat(job_end_time);
Cmax max(end_time(:, 1));end 获取输入参数 T输入矩阵描述了作业和机器的相关信息。每个实例都由一行描述组成接下来一行包含作业数和机器数的信息然后是每个作业的描述包括每个步骤的机器编号和处理时间。Chromosome待解码的染色体。 初始化变量 num_of_jobs作业数量number_of_machines机器数量Jobs唯一的作业列表StepList每个基因的步骤列表MachineList每个基因的机器列表DecodedGenes已解码的基因序列ST每个作业步骤的开始时间PT每个作业步骤的持续时间len_of_chromosome染色体长度即基因数量 计算MachineList和PT 对于染色体中的每个基因将其添加到DecodedGenes中并计算其在DecodedGenes中的位置。然后根据位置计算步骤在T矩阵中的索引并将对应的机器和持续时间添加到MachineList和PT中。 计算ST 初始化变量 Machines唯一的机器列表steps唯一的步骤列表job_start_time和job_end_time用于存储每个作业的开始时间和结束时间的单元格数组machine_start_time和machine_end_time用于存储每个机器的开始时间和结束时间的单元格数组machine_state机器状态的数组用于跟踪机器是否是第一次使用遍历染色体中的每个基因 获取作业、机器、持续时间和步骤信息查找机器和作业在唯一列表中的位置根据步骤是否为第一步骤计算作业的开始时间和结束时间更新机器的开始时间和结束时间以及机器状态将作业的开始时间添加到ST中 计算Cmax 将所有作业的结束时间提取到一个矩阵中计算最大结束时间即最大完成时间 返回结果 Jobs作业序列Cmax最大完成时间MachineList机器序列ST作业步骤的开始时间PT作业步骤的持续时间
详细代码解释
部分1
for index 1:len_of_chromosomeDecodedGenes [DecodedGenes Chromosome(index)];position length(find(DecodedGenes Chromosome(index)));StepList [StepList position];pos1 position * 2 - 1;pos2 position * 2;MachineList [MachineList T(Chromosome(index), pos1)];PT [PT T(Chromosome(index), pos2)];
end
for循环迭代染色体中的每个基因index从1到len_of_chromosome。将当前基因Chromosome(index)添加到DecodedGenes列表中以构建解码后的基因序列。计算当前基因在DecodedGenes中的位置即该基因在已解码基因序列中的出现次数。使用find函数找到与当前基因相等的元素然后使用length函数计算找到的元素数量。将当前基因在已解码基因序列中的位置即出现次数添加到StepList列表中以记录每个基因的位置信息。根据基因在已解码基因序列中的位置计算机器编号在输入矩阵T中的索引。将pos1设置为当前位置乘以2减去1将pos2设置为当前位置乘以2。从输入矩阵T中获取对应的机器编号和处理时间。使用T(Chromosome(index), pos1)获取机器编号并将其添加到MachineList列表中。使用T(Chromosome(index), pos2)获取处理时间并将其添加到PT列表中。
部分2
%% Caculate ST
Machines unique(MachineList);
steps unique(StepList);
代码中使用unique函数获取MachineList中的唯一机器编号并将结果存储在Machines变量中。这样做是为了确定在解码后的基因序列中有多少台不同的机器参与。接下来使用unique函数获取StepList中的唯一步骤编号并将结果存储在steps变量中。这样做是为了确定在解码后的基因序列中有多少个不同的步骤。
部分3
job_start_time cell(num_of_jobs,1);
job_end_time cell(num_of_jobs,1);
machine_start_time cell(number_of_machines,1);
machine_end_time cell(number_of_machines,1);
machine_state zeros(1,number_of_machines);
创建一个大小为num_of_jobs的cell数组job_start_time用于存储每个作业的开始时间。创建一个大小为num_of_jobs的cell数组job_end_time用于存储每个作业的结束时间。创建一个大小为number_of_machines的cell数组machine_start_time用于存储每台机器的开始时间。创建一个大小为number_of_machines的cell数组machine_end_time用于存储每台机器的结束时间。创建一个大小为1xnumber_of_machines的零矩阵machine_state用于记录每台机器的状态。其中0表示该机器是第一次执行作业1表示该机器不是第一次执行作业。
部分4
for index 1:len_of_chromosomejob Chromosome(index);machine MachineList(index);pt PT(index);step StepList(index);pos_m find(Machinesmachine);pos_j find(Jobsjob);
for 循环遍历基因序列中的每个基因。job 变量存储当前基因对应的作业编号。machine 变量存储当前基因对应的机器编号。pt 变量存储当前基因对应的处理时间。step 变量存储当前基因对应的步骤编号。pos_m 变量记录机器编号在 Machines 数组中的位置。pos_j 变量记录作业编号在 Jobs 数组中的位置。
if step1if machine_state(pos_m)0job_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];end
elseif machine_state(pos_m)0job_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
end
如果 step 等于1表示当前基因是作业的第一个步骤不考虑作业内部步骤之间的约束。 如果机器状态 machine_state 在位置 pos_m 上为0表示该机器是第一次被使用。 将作业的开始时间设置为 [0, pos_m]。将作业的结束时间设置为 [job_start_time{pos_j}(1) pt, pos_m]。否则表示该机器已经被使用过。 将作业的开始时间设置为 [machine_end_time{pos_m}(1), pos_m]。将作业的结束时间设置为 [job_start_time{pos_j}(1) pt, pos_m]。否则表示当前基因是作业的其他步骤。 如果机器状态 machine_state 在位置 pos_m 上为0表示该机器是第一次被使用。 将作业的开始时间设置为 [job_end_time{pos_j}(1), pos_m]。将作业的结束时间设置为 [job_start_time{pos_j}(1) pt, pos_m]。否则表示该机器已经被使用过。 将作业的开始时间设置为 [max(machine_end_time{pos_m}(1), job_end_time{pos_j}(1)), pos_m]。将作业的结束时间设置为 [job_start_time{pos_j}(1) pt, pos_m]。
machine_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[ST, job_start_time{pos_j}(1)];
end
更新机器的开始时间 machine_start_time 为对应作业的开始时间的第一个元素。更新机器的结束时间 machine_end_time 为对应作业的结束时间的第一个元素。将机器状态 machine_state 在位置 pos_m 上设置为1表示该机器已被使用过。将作业的开始时间的第一个元素添加到 ST 数组中。结束循环。
以上代码段的目的是根据基因序列中的信息计算每个作业的开始时间和结束时间以及每台机器的开始时间和结束时间。根据不同的步骤和机器状态更新相应的时间记录。
部分5
end_time cell2mat(job_end_time);
将job_end_time这个cell数组转换为矩阵end_time。job_end_time中存储了每个作业的结束时间每个元素是一个包含开始时间和机器编号的向量。通过cell2mat函数将这些向量转换为矩阵形式。
Cmax max(end_time(:,1));
从矩阵end_time中选择所有行的第一列即所有作业的结束时间。通过max函数找到这些结束时间中的最大值。将最大值赋给变量Cmax表示任务调度中的最大完成时间。
