Этот пример включает набор задач, которые будут обработаны параллельно. Каждая задача имеет известное время вычислений. makespan является количеством времени, чтобы обработать все задачи. Этот рисунок показывает два процессора; высота каждого цветного поля представляет отрезок времени, чтобы обработать задачу. Каждая задача может иметь различное время выполнения на каждом процессоре.
Ваша цель состоит в том, чтобы запланировать задачи на процессоры, чтобы минимизировать makespan.
Этот пример имеет 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.