您的位置:js12345金沙官网登入 > 网络编程 > 遗传算法求解混合流水车间调度问题(HFSP【金沙

遗传算法求解混合流水车间调度问题(HFSP【金沙

2019-10-06 19:43

在第一道工序中,所有的工件同时等待被加工,则按照优先级进行加工;在第二道和之后的工序中,由于上一道工序中工件完工时间不同,上一道工序先加工完的工件先进行本工序加工。求出整体完工时间作为目标函数值,运用遗传算法求解以使目标函数值最小。

function main()piecetime = [2 4 6; ... % 设备加工时间 4 9 2; 4 2 8; 9 5 6; 5 2 7; 9 4 3];equsize = [2 2 2]; % 每个工序设备数目piecesize = size(piecetime, 1); % 工件数目prosize = size(piecetime, 2); % 工序数目popsize = 20; % 种群规模cr = 0.6; % 交叉概率mr = 0.05; % 变异概率maxgen = 100; % 迭代次数bestobjvalue = zeros(1, maxgen);bestpop = zeros(maxgen, piecesize);avgobjvalue = zeros(1, maxgen);bestptr = cell(1, maxgen);bestper = cell(1, maxgen);pop = initpop(popsize, piecesize);for gen = 1:maxgen [objvalue, ptr, per] = calobjvalue(pop, piecetime, equsize); [bobjvalue, bindex] = min; bestobjvalue = bobjvalue; bestpop = pop(bindex, :); avgobjvalue = sum / popsize; bestptr{1, gen} = ptr{1, bindex}; bestper{1, gen} = per{1, bindex}; fitness = calfitness; % 计算适应度值 pop = selection(pop, fitness); % 选择 pop = crossover; % 交叉 pop = mutation; % 变异end[~, finalindex] = min(bestobjvalue);finalptr = bestptr{1, finalindex};finalper = bestper{1, finalindex};fprintf("最优序列:n");disp(bestpop(finalindex, :));gantt = makegantt(finalptr, finalper, equsize);figure;imagesc;colorbar;title;figure;plot(1:maxgen, bestobjvalue);title("最优时间变化图");xlabel; ylabel;figure;plot(1:maxgen, avgobjvalue);title("平均时间变化图");xlabel; ylabel;end
  1. 一个工件在一道工序上被任意一个机器加工。
  2. 一个机器在某一时刻只能空闲或加工一个工件。
  3. 工件必须按照加工工序顺序进行加工。
  4. 同一道工序中机器都相同。
  5. 工件加工过程不允许中断。
  6. 如果多个工件同时需要被加工,则按优先级顺序进行加工。

在本例中,一共有6个设备,3道工序,设备必须按照1-2-3的工序进行加工,每个工序有2台机器。一共有6个工件。piecetime中行代表工件,列代表工序,内容是加工时间,比如第1行第1列,表示工件1在工序1加工时间为2.

确定零件的加工优先级,以使整体加工时间最短。

进行迭代:

混合流水车间调度问题(Hybrid Flow-shop Scheduling Problem, HFSP)是车间调度中的一类经典问题。混合流水车间调度问题,在一道工序有一台或多台机器,工件的加工需要满足一定的工艺顺序。

popsize = 20; % 种群规模cr = 0.6; % 交叉概率mr = 0.05; % 变异概率maxgen = 100; % 迭代次数
  • 编码:对工件进行优先级编码,编码越小,优先级越高。
  • 解码:按照工件优先级进行生产,求出整体完工时间。
  • 目标函数值:整体完工时间。
  • 适应度值:目标函数越小,适应度值越大。
  • 选择:按照轮盘赌方法进行选择。
  • 交叉:按照交叉概率,选择两个父代个体,交叉生成两个子代个体。生成一个随机的交换空间,交换空间内,子1基因来自于父2,子2基因来自于父1;交换空间外,子1基因来自于父1,子2基因来自于父2。注意任意两个零件优先级不能相等。
  • 变异:按照变异概率,随机交换两个基因。
  • 终止条件:迭代固定次数。

上图中,第1、2行是第1工序的2台设备,第3、4行是第2工序的2台设备,第5、6行是第3工序的两台设备,纵轴代表时间。按照最优序列3 4 6 2 1 5赋予每个零件优先级,一共用时25.

在本例中,有6个工件,有3道工序,每道工序有2台机器,下面是执行结果:

piecetime = [2 4 6; ... % 设备加工时间 4 9 2; 4 2 8; 9 5 6; 5 2 7; 9 4 3];equsize = [2 2 2]; % 每个工序设备数目piecesize = size(piecetime, 1); % 工件数目prosize = size(piecetime, 2); % 工序数目
pop = initpop(popsize, piecesize);for gen = 1:maxgen [objvalue, ptr, per] = calobjvalue(pop, piecetime, equsize); fitness = calfitness; % 计算适应度值 pop = selection(pop, fitness); % 选择 pop = crossover; % 交叉 pop = mutation; % 变异end
function spop = selection(pop, fitness)% 轮盘赌选择% pop input 种群% fitness input 适应度值% spop output 选择后生成的种群[popsize, piecesize] = size;spop = zeros(popsize, piecesize);sumfit = sum;fitness = fitness ./ sumfit;fitness = cumsum;r = rand(1, popsize);r = sort;j = 1;for i = 1:popsize while fitness < r j = j + 1; end spop = pop;end% 由于上面轮盘赌方法特殊性,一个个体在相邻位置多次重复,故随机排序rr = randperm;spop = spop;end
function mpop = mutation% 变异,交换两个随即位置的基因% pop input 种群% mr input 变异概率% mpop output 变异后种群[popsize, piecesize] = size;mpop = pop;for i = 1:popsize if rand > mr continue; end r1 = randi(piecesize); r2 = randi(piecesize); temp = mpop; mpop = mpop; mpop = temp;endend

本文由js12345金沙官网登入发布于网络编程,转载请注明出处:遗传算法求解混合流水车间调度问题(HFSP【金沙

关键词:

  • 上一篇:没有了
  • 下一篇:没有了