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.