对于一个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);endfprintf('最优染色体: %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);
MATLAB
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);
endendend
MATLAB
计算目标函数值程序:
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));endend
MATLAB
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);endend
MATLAB