Main Content

並列処理におけるメイクスパンの最小化

ライブ スクリプトを開く

この例では、並列で処理される一連のタスクを扱います。各タスクの処理時間はわかっています。メイクスパンは、すべてのタスクを処理するのにかかる時間です。以下の図は 2 つのプロセッサを表しています。色付きの各ボックスの高さは、タスクを処理する時間の長さを表します。各タスクの実行時間はプロセッサごとに異なる場合があります。

ゴールは、メイクスパンが最小になるよう、プロセッサのタスクをスケジュールすることです。

問題の設定

この例では、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 を処理するのにかかる時間を表します。

0-1 整数計画法を使用して問題を解くために、バイナリ最適化変数配列として process を作成します。ここで、process(i,j) = 1 は、プロセッサ i がタスク j を処理することを意味します。

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

各タスクは 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 の時点です。

参考

関連するトピック