インターバルスケジューリングのアルゴリズムと計算複雑性

コンピューターサイエンスのアルゴリズム設計において、インターバルスケジューリングは非常に重要な問題群です。これは、特定の時間枠（インターバル）を持つタスク群を、限られたリソース（マシンなど）にどのように割り当てるかを決定する問題です。例えば、タスクAが2時から5時、タスクBが4時から10時という時間設定である場合、これらは時間が重複しているため、同一のリソースで同時に実行することはできません。このように、互いに重複しないタスクの集合を「互換性がある」と定義します。

この問題の核心は、限られた時間の中でいかに効率的にタスクを詰め込み、スループット（処理量）を最大化させるかにあります。これはグラフ理論における「インターバルグラフの最大独立集合」を求める問題と同義です。

Key Facts

• ISMP（最大化問題）：重複しないタスク数を最大化することを目的とし、貪欲法で最適解が得られる。
• 重み付きスケジューリング：各タスクに価値（重み）がある場合、多項式時間で最適解を算出可能。
• グループスケジューリング：タスクがグループ化され、各グループから1つだけ選択する場合、問題の難易度が急増する。
• 計算複雑性：グループ内の選択肢が3つ以上（k ≥ 3）になると、決定問題はNP完全となる。
• 近似解：複雑なグループスケジューリング問題でも、貪欲法により最適解の1/2以上の精度を持つ近似解が得られる。

単一リソースにおけるスケジューリング最適化

非重み付きタスクの最適化

単純に「最も早く始まるタスク」や「最も短いタスク」を選んでも、必ずしも最適解には至りません。なぜなら、非常に長いタスクを先に選んでしまうと、その間に実行できたはずの多くの短いタスクを排除してしまうからです。

ここで有効なのがEarliest Deadline First (EDF) と呼ばれる貪欲アルゴリズムです。この手法では、「最も早く終了するタスク」を優先的に選択し、それと重複する他の候補をすべて除外します。このプロセスを繰り返すことで、数学的に証明された最適解を得ることができます。計算量は、終了時間でソートする前処理を含め O(n log n) となります。

重み付きタスクの最適化

各タスクに「利益」などの重みが設定されている場合、単なる個数ではなく合計重量の最大化を目指します。この問題は動的計画法を用いて多項式時間で解決可能です。終了時間順にソートされたタスクに対し、あるタスクを採用した場合の利益と、採用しなかった場合の利益を比較しながら最適値を決定します。

インデックス (j)	判定式 (w[j] + M[p[j]] ≥ M[j-1])	採用結果	次のステップ
9	21 ≥ 20	採用 (True)	j = p[9] = 6
6	16 ≥ 11	採用 (True)	j = p[6] = 4
4	8 ≥ 11	不採用 (False)	j = 3
3	11 ≥ 5	採用 (True)	j = p[3] = 1
1	5 ≥ 0	採用 (True)	j = 0 (終了)

グループインターバルスケジューリングの複雑性

問題が高度になると、タスクが「グループ」に分かれます。各グループは一つのジョブを表し、その中の複数のインターバルは「実行可能な代替案」を意味します。この場合、「重複を避けつつ、できるだけ多くのグループから代表タスクを選ぶ」ことが目標となります。

決定問題 (GISDP) の難易度

すべてのグループから代表を選べるかを判定する問題（GISDP）の難易度は、グループ内の選択肢数 k に依存します。

• k = 2 の場合：2-SAT（2-充足可能性問題）に還元できるため、多項式時間で解くことが可能です。
• k ≥ 3 の場合：Boolean充足可能性問題からの還元により、NP完全であることが証明されています。つまり、効率的な解法が見つかっていない非常に困難な問題です。

最大化問題 (GISMP) と近似解

可能な限り多くのグループをスケジュールする最大化問題（GISMP）は、k ≥ 2 でNP完全であり、さらに MaxSNP-complete であるため、近似困難な性質を持ちます。

しかし、実用的なアプローチとして、終了時間が早い順に選択し、同一グループの他候補も同時に除外する貪欲法を用いることで、最適解の少なくとも 1/2 を確保する2-近似アルゴリズムが利用可能です。また、線形計画法（LP）の緩和を用いることで、k=2 の場合に 5/3 の近似比を達成するなど、より精度の高い近似手法も研究されています。

関連問題と拡張概念

インターバルスケジューリングは、より広範なスケジューリング問題の一種です。例えば、リソース数を最小化する「リソース割り当て問題」や、複数のプロセッサで並列処理を行う「同一マシンスケジューリング」などが挙げられます。また、時間軸以外の次元（2次元以上）に拡張した「最大不交集合問題」は、一般にNP完全となります。

Frequently Asked Questions

なぜ「最も短いタスク」を選ぶ方法では最適解にならないのですか？

短いタスクを選んだとしても、それが他の2つのタスクの境界にまたがっている場合、その1つの短いタスクを選ぶことで、結果的に2つのタスクを諦めることになり、全体のタスク数が減少する可能性があるためです。

NP完全とは具体的にどのような状態を指しますか？

簡単に言えば、正解を検証することは簡単ですが、正解を見つけるための効率的な（多項式時間で動作する）アルゴリズムが現在のところ見つかっていない、計算的に非常に困難な問題のクラスを指します。

重み付きスケジューリングではどのような手法が使われますか？

主に動的計画法が用いられます。タスクを終了時間順に並べ、各ステップで「現在のタスクを採用して以前の互換的な最適解を加算するか」か「現在のタスクを捨てて直前の最適解を維持するか」を比較して決定します。

グループスケジューリングにおいて k=2 が多項式時間で解ける理由は？

各グループから1つだけ選ぶという制約と、インターバルの重複禁止という制約を、2つのリテラルからなる論理式（2-SAT）として表現できるためです。2-SATは線形時間で判定可能です。

近似アルゴリズムの「近似比 2」とはどういう意味ですか？

どのような入力データに対しても、そのアルゴリズムが導き出す解が、理論上の最適解の半分（1/2）以上の価値を持つことが保証されていることを意味します。