期限付きジョブシーケンス問題 ― 貪欲法で最大利益の実行順序を求める

問題の概要

この問題では、複数のジョブ（仕事）からなるリストが与えられます。各ジョブには「締め切り（デッドライン）」と「利益」が設定されており、すべてのジョブは1単位時間で完了するため、締め切りの最小値は1です。ある時刻に実行できるジョブは1つだけという制約のもとで、合計利益を最大化するジョブの実行順序を求めるのが目的です。

この問題は貪欲法（グリーディ法）によって効率的に解けます。まず、すべてのジョブを利益の降順にソートします。次に、利益の高いジョブから順に、「そのジョブの締め切り以前にある空きスロットのうち最も遅いもの」へ割り当てていきます。価値の高いジョブを優先的に配置しつつ、締め切り直前のスロットを後続のジョブのために残せるため、結果として全体の利益が最大化されます。

このアルゴリズムの計算量は O(n²) です。

入力と出力

入力:
ジョブID・締め切り・利益を持つジョブのリストと、ジョブ数 n
{('a', 2, 100), ('b', 1, 19), ('c', 2, 27), ('d', 1, 25), ('e', 3, 15)}
n = 5
出力:
最大利益となるジョブシーケンス: c a e

アルゴリズム

jobSequence(jobList, n)

入力 − ジョブのリストと、リスト内のジョブ数。

出力 − 実際に採用されるジョブの順序（シーケンス）。

Begin
    jobList を利益の降順にソートする
    結果を格納するジョブシーケンスのリストと、空き時間枠を管理する slot を用意する
    最初はすべてのスロットを「空き」に初期化する
    与えられたすべてのジョブ i に対して
        リストの末尾側から前方へ向かって走査する
            slot[j] が空きであれば
                jobSequence[j] := i
                slot[j] := 「使用中」にする
                内側のループを抜ける
    ここまでを全ジョブについて繰り返す

    空きではないすべてのスロット j に対して
        jobList[jobSequence[j]] を参照してジョブの ID を表示する
End

アルゴリズムのポイント

• 利益の降順ソート： 利益の大きいジョブから先に確保することで、機会損失を最小限に抑えます。
• 後ろのスロットから割り当て： 各ジョブを「締め切り以内のできるだけ遅い時刻」に置くことで、他のジョブのための選択肢を最大限残せます。
• 計算量： ソートは O(n log n)、スロット探索の二重ループが O(n²) となり、全体の計算量は O(n²) です。

サンプルコード（C++）

#include<iostream>
#include<algorithm>
using namespace std;

struct Job {
    char id;
    int deadLine;
    int profit;
};

bool comp(Job j1, Job j2) {
    return (j1.profit > j2.profit);     //compare jobs based on profit
}

int min(int a, int b) {
    return (a<b)?a:b;
}

void jobSequence(Job jobList[], int n) {
    sort(jobList, jobList+n, comp);     //sort jobList on profit

    int jobSeq[n];      // To store result (Sequence of jobs)
    bool slot[n];       // To keep track of free time slots

    for (int i=0; i<n; i++)
        slot[i] = false; //initially all slots are free

    for (int i=0; i<n; i++) {     //for all given jobs
        for (int j=min(n, jobList[i].deadLine)-1; j>=0; j--) {   //search from last free slot
            if (slot[j]==false) {
                jobSeq[j] = i;   // Add this job to job sequence
                slot[j] = true;  // mark this slot as occupied
                break;
            }
        }
    }

    for (int i=0; i<n; i++)
        if (slot[i])
            cout << jobList[jobSeq[i]].id << " ";     //display the sequence
}

int main() {
    Job jobList[] = {{'a',2,100}, {'b',1,19}, {'c',2,27},{'d',1,25},{'e',3,15}};
    int n = 5;
    cout << "Following is maximum profit sequence of job sequence: ";
    jobSequence(jobList, n);
}

実行結果

Following is maximum profit sequence of job sequence: c a e

動作の解説

サンプル入力を利益の降順に並べ替えると、a(100) → c(27) → d(25) → b(19) → e(15) の順になります。

• ジョブ a（締め切り2）→ 時刻2のスロットが空いているため、そこに配置。
• ジョブ c（締め切り2）→ 時刻2は使用済みのため、時刻1のスロットに配置。
• ジョブ d（締め切り1）→ 時刻1が埋まっているため配置できず、スキップ。
• ジョブ b（締め切り1）→ 同様に配置できず、スキップ。
• ジョブ e（締め切り3）→ 時刻3のスロットが空いているため、そこに配置。

その結果、時刻1に c、時刻2に a、時刻3に e を実行する順序「c a e」が得られ、合計利益は 27 + 100 + 15 = 142 となります。