Main Content

最小化并行处理中的完成时间

打开实时脚本

此示例涉及一组需要并行处理的任务。每个任务都有已知的处理时间。完成时间是处理所有任务所需的时间。该图显示了两个处理器；每个彩色框的高度代表处理任务所需的时间长度。每个任务在每个处理器上可以有不同的运行时间。

您的目标是在处理器上安排任务，以尽量减少完成时间。

问题设置

此示例有 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);

将计算时间与完成时间关联起来。完成时间大于或等于每次计算时间。

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 表示求解器找到了最佳解，这意味着返回的解具有最短的完成时间。

返回的完成时间是 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。

另请参阅

相关主题