最小化并行处理中的最大完工时间
这个例子涉及一组要并行处理的任务。每个任务都有一个已知的处理时间。makespan是指处理所有任务所需的时间。该图显示了两个处理器;每个彩色方框的高度表示处理任务的时间长度。每个任务在每个处理器上可以有不同的运行时间。
您的目标是在处理器上调度任务，以便使最大完工时间最小化。
问题的设置
这个例子有11个处理器和40个任务。每个处理器处理每个任务的时间在数组中给出processingTime．对于本例，生成随机处理时间。
rng默认的再现率%numberOfProcessors = 11;numberOfTasks = 40;processingTime = [10;7;2;5;3;4;7;6;4;3;
processingTime (i, j)表示该处理器的时间量我需要处理任务j．
要使用二进制整数规划解决问题，请创建过程为二进制优化变量数组，其中Process (i,j) = 1意味着处理器我流程任务j．
Process = optimvar(“过程”、大小(processingTime),“类型”,“整数”,下界的0,“UpperBound”1);
每个任务必须精确地分配给一个处理器。
Assigneachtask = sum(process,1) == 1;
为了表示目标，定义一个名为的非负优化变量考．
Makespan = optimvar(“考”,下界的, 0);
计算每个处理器处理其任务所需的时间。
computetime = sum(process.*processingTime,2);
将计算时间与最大完工时间联系起来。最大完成时间大于或等于每个计算时间。
Makespanbound = makespan >= computetime;
创建一个优化问题，其目标是最小化最大完工时间，并包括问题的约束条件。
Scheduleproblem = optimproblem(“目标”考);scheduleproblem.Constraints.assigneachtask = assigneachtask;scheduleproblem.Constraints.makespanbound = makespanbound;
解决问题并查看解决方案
解决问题，抑制平时的显示。
选项= optimoptions(scheduleproblem，“显示”,“关闭”）;[sol,fval,exitflag] = solve(scheduleproblem，“选项”选项)
索尔=带字段的结构:Makespan: 1.3634进程:[11x40 double]
Fval = 1.3634
exitflag = OptimalSolution
返回的exitflag指示求解器找到了最优解，这意味着返回的解具有最小的最长时间。
返回的makespan为1.3634。这样的日程安排效率高吗?要找到答案，请将生成的时间表作为堆叠柱状图进行查看。首先，创建一个调度矩阵我表示处理器完成的任务我．然后，找出时间表中每个条目的处理时间。
Processval = round(sol.process);Maxlen = max(sum(processval,2));所需矩阵宽度的%现在计算调度矩阵optimalSchedule = 0 (numberOfProcessors,maxlen);ptime = optimalSchedule;为i = 1:numberOfProcessors schedi = find(processval(i，:));optimalSchedule(i,1:长度(调度))=调度;ptime(i,1:length(schedi)) = processingTime(i,schedi);结束optimalSchedule
optimalSchedule =11×1025 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 35 0 0 0 0 0 0 0 0 0 0 0 0 0 6 22 39 0 0 0 0 0 0 0 10 26日28日20 30 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 21日24日27日0 0 0 0 0 0 0 8 33 16 0 0 0 0 0 0 0 3 17 34 0 0 0 0 0 0 0⋮
以堆叠柱状图的形式显示时间表矩阵。在每个栏的顶部标上任务编号。
图酒吧(ptime,“堆叠”)包含(的处理器数量) ylabel (的处理时间)标题(“任务分配给处理器”）为i = 1:尺寸(optimalSchedule, 1)为j = 1:尺寸(optimalSchedule, 2)如果optimalSchedule(i,j) > 0 processText = num2str(optimalSchedule(i,j)，“% d”）;hText = text(i,sum(ptime(i,1:j)，2)，processText);集(hText,“VerticalAlignment”,“顶级”,“HorizontalAlignment”,“中心”,“字形大小”10“颜色”,“w”）;结束结束结束
找到堆叠条的最小高度，它表示处理器停止工作的最早时间。然后，找到最大高度对应的处理器。
Minlength = min(sum(ptime,2))
Minlength = 1.0652
[~，processormaxlength] = max(sum(ptime,2))
Processormaxlength = 7
所有处理器都忙到时间为止最小长度= 1.0652。从堆叠柱状图中，您可以看到处理器8在那个时候停止工作。处理器processormaxlength= 7是最后一个停止工作的处理器，它发生在时间考= 1.3634。
另请参阅
相关的话题
您也可以从以下列表中选择一个网站:
