Setup задач

Этот пример имеет 11 процессоров и 40 задач. Время для каждого процессора, чтобы обработать каждую задачу дано в массиве processingTime. В данном примере сгенерируйте случайные времена вычислений.

rng default % for reproducibility
numberOfProcessors = 11;
numberOfTasks = 40;
processingTime = [10;7;2;5;3;4;7;6;4;3;1] .* rand(numberOfProcessors,numberOfTasks);

processingTime(i,j) представляет количество времени тот процессор i берет, чтобы обработать задачу j.

Чтобы решить задачу с помощью бинарного целочисленного программирования, создайте process как бинарный массив переменной оптимизации, где process(i,j) = 1 средний процессор i задача процессов j.

process = optimvar('process',size(processingTime),'Type','integer','LowerBound',0,'UpperBound',1);

Каждая задача должна быть присвоена точно одному процессору.

assigneachtask = sum(process,1) == 1;

Чтобы представлять цель, задайте неотрицательную переменную оптимизации под названием makespan.

makespan = optimvar('makespan','LowerBound',0);

Вычислите время, когда каждый процессор требует, чтобы обработать его задачи.

computetime = sum(process.*processingTime,2);

Свяжите вычислить времена с makespan. makespan больше или равен каждому, вычисляют время.

makespanbound = makespan >= computetime;

Создайте задачу оптимизации, цель которой состоит в том, чтобы минимизировать makespan, и включать ограничения задач.

scheduleproblem = optimproblem('Objective',makespan);
scheduleproblem.Constraints.assigneachtask = assigneachtask;
scheduleproblem.Constraints.makespanbound = makespanbound;

Решите задачу и просмотрите решение

Решите задачу, подавив обычное отображение.

options = optimoptions(scheduleproblem,'Display',"off");
[sol,fval,exitflag] = solve(scheduleproblem,'Options',options)

sol = struct with fields:
    makespan: 1.3634
     process: [11x40 double]

fval = 1.3634

exitflag = 
    OptimalSolution

Возвращенный exitflag указывает, что решатель нашел оптимальное решение, означая, что возвращенное решение имеет минимальный makespan.

Возвращенный makespan 1.3634. Действительно ли это - эффективное расписание? Чтобы узнать, просмотрите получившееся расписание как сложенную столбчатую диаграмму. Во-первых, создайте матрицу расписания где строка i представляет задачи, сделанные процессором i. Затем найдите время вычислений для каждой записи в расписании.

processval = round(sol.process);
maxlen = max(sum(processval,2)); % Required width of the matrix
% Now calculate the schedule matrix
optimalSchedule = zeros(numberOfProcessors,maxlen);
ptime = optimalSchedule;
for i = 1:numberOfProcessors
    schedi = find(processval(i,:));
    optimalSchedule(i,1:length(schedi)) = schedi;
    ptime(i,1:length(schedi)) = processingTime(i,schedi);
end
optimalSchedule

optimalSchedule = 11×10

    25    38     0     0     0     0     0     0     0     0
     4    12    23    32     0     0     0     0     0     0
     7    13    14    18    31    37     0     0     0     0
    35     0     0     0     0     0     0     0     0     0
     6    22    39     0     0     0     0     0     0     0
    10    26    28    30     0     0     0     0     0     0
    20     0     0     0     0     0     0     0     0     0
    21    24    27     0     0     0     0     0     0     0
     8    16    33     0     0     0     0     0     0     0
     3    17    34     0     0     0     0     0     0     0
      ⋮

Отобразите матрицу расписания как сложенную столбчатую диаграмму. Пометьте верхнюю часть каждой панели с номером задачи.

figure
bar(ptime,'stacked')
xlabel('Processor Number')
ylabel('Processing Time')
title('Task Assignments to Processors')
for i=1:size(optimalSchedule,1)
    for j=1:size(optimalSchedule,2)
        if optimalSchedule(i,j) > 0
            processText = num2str(optimalSchedule(i,j),"%d");
            hText = text(i,sum(ptime(i,1:j),2),processText);
            set(hText,"VerticalAlignment","top","HorizontalAlignment","center","FontSize",10,"Color","w");
        end
    end
end

Найдите минимальную высоту сложенных панелей, которая представляет самое раннее время, процессор прекращает работать. Затем найдите процессор, соответствующий максимальной высоте.

minlength = min(sum(ptime,2))

minlength = 1.0652

[~,processormaxlength] = max(sum(ptime,2))

processormaxlength = 7

Все процессоры заняты до времени minlength = 1.0652. Из сложенной столбчатой диаграммы вы видите, что процессор 8 прекращает работать в то время. Процессор processormaxlength = 7 последний процессор, который прекратит работать, который происходит во время makespan = 1.3634.