Минимизируйте Makespan в параллельной обработке

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

Ваша цель состоит в том, чтобы запланировать задачи на процессоры, чтобы минимизировать makespan.

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

Figure contains an axes. The axes with title Task Assignments to Processors contains 50 objects of type bar, text.

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

minlength = min(sum(ptime,2))
minlength = 1.0652
[~,processormaxlength] = max(sum(ptime,2))
processormaxlength = 7

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

Смотрите также

Похожие темы

Для просмотра документации необходимо авторизоваться на сайте