Настройка проблемы

В этом примере 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. Продолжительность выполнения больше или равна каждому вычислительному времени.

makespanbound = makespan >= computetime;

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

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 - 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.