基于POX交叉的遗传算法求解流水车间调度(J-Shop)问题二

对于一个6个工件,6台机器的流水车间调度问题,程序运行结果如下:

甘特图

下面是主程序、交叉算子程序、计算目标函数值程序,全部程序都可以下载(下载全部程序)。

主程序如下:

clc;
clear;

[jobN, machineN, taskDuration, taskUse, processSize] = readDataFile('ft06.txt');

popSize = 200;
chromLength = jobN * processSize;
pc = 0.85;
pm = 0.05;
maxGen = 100;

bestObjValue = 0;
objValues = zeros(1, maxGen);
avgObjValue = zeros(1, maxGen);
bestChrom = zeros(1, chromLength);

pop = initPop(popSize, chromLength, jobN);
objValue = calObjValue(pop, jobN, machineN, processSize, taskDuration, taskUse);
fitness = calFitness(objValue);
for gen = 1:maxGen
    pop = selection(pop, fitness);
    pop = crossover(pop, pc, jobN);
    pop = mutation(pop, pm);

    objValue = calObjValue(pop, jobN, machineN, processSize, taskDuration, taskUse);
    fitness = calFitness(objValue);

    avgObjValue(gen) = sum(objValue) / popSize;
    [objValues, bestObjValue, bestChrom] = bestValue(gen, pop, ...
        objValue, objValues, bestObjValue, bestChrom);
end
fprintf('最优染色体: %s\n', mat2str(bestChrom));
fprintf('最优时间: %d\n', bestObjValue);
figure();
plot(1:maxGen, objValues);
title('种群最优个体目标函数(时间)变化图');
figure();
plot(1:maxGen, avgObjValue);
title('种群目标函数值平均值(时间)变化图');
[taskSTime, taskETime] = calTaskTime(bestChrom, jobN, machineN, ...
    processSize, taskDuration, taskUse);
drawGantt(taskUse, taskSTime, taskETime);

POX交叉算子程序:

function cpop = crossover(pop, pc, jobN)
% 交叉,POX方法
cpop = pop;
for i = 1:2:size(pop, 1)
    if rand < pc
        [p1, p2] = deal(pop(i, :), pop(i+1, :));
        [c1, c2] = deal(p1, p2);
        canJ = randperm(jobN);
        J = canJ(1:randi(jobN-1));
        [c1Lia, c2Lia] = deal(ismember(p1, J), ismember(p2, J));
        [c1(c1Lia), c2(c2Lia)] = deal(p2(c2Lia), p1(c1Lia));
        [cpop(i, :), cpop(i+1, :)] = deal(c1, c2); 
    end
end
end

计算目标函数值程序:

function objValue = calObjValue(pop, jobN, machineN, processSize, taskDuration, taskUse)
% 计算种群目标函数值(总完工时间)
[popSize, ~] = size(pop);
objValue = zeros(1, popSize);
for i = 1:popSize
    [~, taskETime] = calTaskTime(pop(i, :), jobN, machineN, ...
        processSize, taskDuration, taskUse);
    objValue(i) = max(max(taskETime));
end
end

function [taskSTime, taskETime] = calTaskTime(chrom, jobN, machineN, processSize, taskDuration, taskUse) % 计算染色体目标函数值(总完工时间) jobProcess = zeros(1, jobN); machETime = zeros(1, machineN); [taskSTime, taskETime] = deal(zeros(jobN, processSize)); for j = 1:length(chrom) job = chrom(j); jobProcess(job) = jobProcess(job) + 1; process = jobProcess(job); machine = taskUse(job, process); if process == 1 startTime = max([0, machETime(machine)]); else startTime = max([taskETime(job, process-1), machETime(machine)]); end taskSTime(job, process) = startTime; endTime = startTime + taskDuration(job, process); [taskETime(job, process), machETime(machine)] = deal(endTime); end end

发表评论

电子邮件地址不会被公开。 必填项已用*标注