Minimize Makespan in Parallel Processing

Problem Setup

This example has 11 processors and 40 tasks. The time for each processor to process each task is given in the arrayprocessingTime. For this example, generate random processing times.

rngdefault% for reproducibilitynumberOfProcessors = 11; numberOfTasks = 40; processingTime = [10;7;2;5;3;4;7;6;4;3;1] .* rand(numberOfProcessors,numberOfTasks);

processingTime(i,j)represents the amount of time that processoritakes to process taskj.

To solve the problem using binary integer programming, createprocessas a binary optimization variable array, whereprocess(i,j) = 1means processoriprocesses taskj.

process = optimvar('process',size(processingTime),'Type','integer','LowerBound',0,'UpperBound',1);

Each task must be assigned to exactly one processor.

assigneachtask = sum(process,1) == 1;

To represent the objective, define a nonnegative optimization variable namedmakespan.

makespan = optimvar('makespan','LowerBound',0);

Compute the time that each processor requires to process its tasks.

computetime = sum(process.*processingTime,2);

考与计算时间。的makespan is greater than or equal to each compute time.

makespanbound = makespan >= computetime;

Create an optimization problem whose objective is to minimize the makespan, and include the problem constraints.

scheduleproblem = optimproblem('Objective',makespan); scheduleproblem.Constraints.assigneachtask = assigneachtask; scheduleproblem.Constraints.makespanbound = makespanbound;

Solve Problem and View Solution

Solve the problem, suppressing the usual display.

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

的returnedexitflagindicates that the solver found an optimal solution, meaning the returned solution has minimal makespan.

的returned makespan is 1.3634. Is this an efficient schedule? To find out, view the resulting schedule as a stacked bar chart. First, create a schedule matrix where rowirepresents the tasks done by processori. Then, find the processing time for each entry in the schedule.

processval = round(sol.process); maxlen = max(sum(processval,2));% Required width of the matrix% Now calculate the schedule matrixoptimalSchedule = zeros(numberOfProcessors,maxlen); ptime = optimalSchedule;fori = 1:numberOfProcessors schedi = find(processval(i,:)); optimalSchedule(i,1:length(schedi)) = schedi; ptime(i,1:length(schedi)) = processingTime(i,schedi);endoptimalSchedule

optimalSchedule =11×1025 38 0 0 0 0 0 0 0 0 4 12 23 32 0 0 0 0 0 0 7 1314 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 ⋮

Display the schedule matrix as a stacked bar chart. Label the top of each bar with the task number.

figure bar(ptime,'stacked') xlabel('Processor Number') ylabel('Processing Time') title('Task Assignments to Processors')fori=1:size(optimalSchedule,1)forj=1:size(optimalSchedule,2)ifoptimalSchedule(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");endendend

Find the minimum height of the stacked bars, which represents the earliest time a processor stops working. Then, find the processor corresponding to the maximum height.

minlength = min(sum(ptime,2))

minlength = 1.0652

[~,processormaxlength] = max(sum(ptime,2))

processormaxlength = 7

All processors are busy until timeminlength= 1.0652. From the stacked bar chart, you can see that processor 8 stops working at that time. Processorprocessormaxlength= 7 is the last processor to stop working, which occurs at timemakespan= 1.3634.