並列マシンスケジューリング

複数の並列マシンにジョブを割り当てます. ディスパッチングルール（SPT、LPT、EDD、FCFS、CR、WSPT）を使用して同一の並列マシンにジョブを割り当てます。ガントチャートでスケジュールを可視化し、マシン稼働率を比較します。

ディスパッチングルール（SPT、LPT、EDD、FCFS、CR、WSPT）を使用して同一の並列マシンにジョブを割り当てます。ガントチャートでスケジュールを可視化し、マシン稼働率を比較します。

並列機械スケジューリングとは？

並列機械スケジューリングは、複数の同一機械に一連のジョブを割り当て、makespan（メイクスパン、全体の完了時間）や総納期遅れの最小化といった目的を最適化する問題である。製造・計算処理・物流で一般的な複数機械の環境へ、単一機械のスケジューリングを拡張したものである。

LPT（Longest Processing Time、最長処理時間優先）規則は、並列機械上で makespan を最小化するためのよく知られたヒューリスティックである。ジョブを処理時間の降順に並べ、各ジョブを最も早く空く機械へ割り当てる。同一機械の場合、LPT は最適値の 4/3 以内の makespan を保証する。他の規則（SPT、EDD、WSPT）は、それぞれ異なる目的を最適化する。

機械稼働率、すなわち各機械が稼働している時間の割合は、負荷平準化の良否を示す。各機械の稼働率が均等であれば、負荷バランスが良好であることを意味する。ガントチャートによる可視化は各機械のスケジュールを時間軸上に示し、遊休時間や負荷の偏りを一目で分かるようにする。

Formula: Makespan = max(Completion Time of all machines) Utilization = Σ Processing Time / (Makespan x m) Tardiness = max(0, Completion - Due Date) LPT: Assign longest job to earliest available machine SPT: Assign shortest job to earliest available machine

計算例

4 つのジョブ（p=8,6,5,3）を 2 台の機械に LPT で割り当てる。Job1(8)→M1、Job2(6)→M2、Job3(5)→M2（負荷 6→11）、Job4(3)→M1（負荷 8→11）となる。makespan = 11。稼働率は M1=11/11=100%、M2=11/11=100% で、完全に平準化されている。LPT を用いない場合（FCFS）、makespan=14 となり負荷バランスも悪くなりうる。

この計算機を使用する場面

複数の同一機械にジョブバッチをスケジューリングしメイクスパンまたは総遅延を最小化する必要がある場合
機械追加が現在のワークロードのメイクスパンを意味ある程度に削減するか評価する生産能力計画時
特定のジョブミックスに対するディスパッチングルールを比較する際 — 異なるルールが異なる目的を最適化し最良の選択は優先事項に依存
機械故障後に残りのジョブを利用可能な機械に迅速に再スケジューリングし納期への影響を評価する際
すべての機械が生産スケジュールに均等に貢献するよう機械間の負荷をバランスさせアイドル時間を最小化する際

よくある間違い

メイクスパン最小化にSPTを使用 — SPTは平均フロータイムを最小化するのでありメイクスパンではない；並列機械のメイクスパンには最長ジョブを最初に割り当てるLPTを使用
機械追加が常にメイクスパンを比例的に削減すると仮定 — 改善は収穫逓減の法則に従う；ジョブサイズが非常に不均等な場合、機械追加がメイクスパンをほとんど削減しない可能性
ジョブが異なる時間に到着する場合にリリース時間を考慮しない — 静的ディスパッチングルールは全ジョブが時間0に利用可能と仮定；到着時間が異なる場合は動的ディスパッチングを使用
機械稼働率バランスの無視 — 最小メイクスパンスケジュールが一部の機械を長時間アイドル状態にする可能性；公平性と摩耗バランスのためにすべての機械の稼働率を確認

結果の解釈方法

すべての機械で均等な稼働率（各90%超） — 負荷がよくバランスされている；ディスパッチングルールが効率的に機能
1台の機械が100%稼働で他が大幅に低い — その機械がボトルネック；最長ジョブがメイクスパンを決定する可能性
総遅延 = 0 — すべてのジョブが納期前に完了；スケジュールがすべての納期コミットメントを達成
多くの遅延ジョブと高い総遅延 — ワークロードが納期期間内の能力を超過；残業、追加機械、延長納期の交渉を検討
LPTとSPTが非常に類似したメイクスパン — ジョブの処理時間が相対的に均一；ジョブのサイズが類似している場合ルールの選択はあまり重要でない

よくある質問

並列機械で makespan を最小化するディスパッチング規則はどれですか？

makespan の最小化には LPT（最長処理時間優先）が最良のヒューリスティックです。長いジョブから先に割り当てることで、大きなジョブが終盤にボトルネックを作るのを防ぎます。LPT は最適値の 4/3 - 1/(3m) 以内の解を保証します（m は機械台数）。機械 2 台の場合、これは最適値の 7/6（≈17%）以内となります。

投入可能時刻や納期がジョブごとに異なる場合は、どう扱えばよいですか？

投入可能時刻がある場合、ジョブはその時刻以降にしか開始できません。各機械が空くたびに優先度を再評価する動的なディスパッチングを使ってください。納期がある場合は、EDD や CR 規則が納期遅れの最小化に役立ちます。両方の制約がある複雑な問題では、複数の規則をシミュレーションして性能指標を比較します。最良の規則は、具体的なジョブ構成と目的によって変わります。