ジョブショップスケジューリング (GA)

ジョブショップスケジューリングと遺伝的アルゴリズム

ジョブショップスケジューリングは複数ジョブの工程を機械に割り当て、メイクスパンや納期遅延を最小化する順序を決定します。各ジョブは特定機械での順序付き工程で構成され、2工程が同時に1機械を共有できません。

JSSPはNP困難です。GAは候補スケジュールの個体群を進化させて解決します。POX交叉はジョブ順序を保存しつつ親を結合、スワップ突然変異は工程位置を交換し新解を探索します。

JSSPは機械加工、半導体製造、印刷等の製造環境で重要です。メイクスパンの10-15%削減は設備投資なしで処理量を直接増加させます。

Formula: メイクスパン = max(全工程の完了時間) 納期遅延 = Σ max(0, 完了_j − 納期_j) GA: 個体群初期化 → 適合度評価 → 親選択 → POX交叉 → スワップ突然変異 → 反復

計算例

3ジョブ、3機械。ジョブ1: M1(3)→M2(2)→M3(4)。ジョブ2: M2(4)→M1(3)→M3(2)。ジョブ3: M3(2)→M2(3)→M1(1)。最適メイクスパン = 12。GA（個体数100、世代200）で通常この値または5%以内を発見。

この計算機を使用すべき場面

• 生産計画者が完了時間を最小化するために共有設備を使用するマシンショップで複数ジョブをスケジューリングする場合
• 製造エンジニアが新しい機械の追加や作業順序の変更が全体スループットに与える影響を評価する場合
• 印刷所や半導体ファブのスケジューラーが最小遅延で顧客納期を満たすためにジョブの優先順位を決定する場合
• オペレーションズリサーチャーがGAベースのスケジューリングを現在の手動またはプライオリティルールスケジューリング手法とベンチマークする場合

避けるべき一般的な間違い

• 複雑な問題に対して集団サイズが小さすぎる — 10以上のジョブと5以上の機械では、遺伝的多様性を維持し早期収束を防ぐために少なくとも100-200個体を使用してください
• 世代数が少なすぎて次善解を受け入れる — 適合度がまだ改善しているか監視してください；停滞すれば収束、まだ改善中なら世代を増やしてください
• リリース時間と納期が存在する時にそれらを無視 — これらの制約なしでGAはメイクスパンのみを最適化し、実際のタイミング要件に違反するスケジュールを生成する可能性があります
• 異なるランダムシードでGAを複数回実行しない — GAは確率的です；単一回の実行は局所最適に陥る可能性があります；3-5回実行して最良の結果を採用してください

結果の解釈方法

• 総遅延がゼロであれば全ジョブが納期前に完了 — スケジュールは実行可能であり、焦点をメイクスパンのさらなる短縮に移すべきです
• メイクスパンがボトルネック機械の処理時間合計に近い場合、スケジュールはほぼ最適 — さらなる改善の余地はほとんどありません
• ガントチャートは機械のアイドル時間を明らかにします：大きなギャップはスケジューリングの非効率または避けられないシーケンス制約を示します

関連規格・参考資料

• Garey, Johnson & Sethi (1976) — ジョブショップのメイクスパン最小化のNP困難性を確立
• メイクスパン(C_max)と総遅延 — 生産スケジューリングの標準的な目的関数
• 遺伝的アルゴリズム(Holland, 1975) — 本ツールでスケジュール空間の探索に適用したメタヒューリスティックの一群

よくある質問

GAパラメータをどう設定すれば良い結果が得られますか？

個体数50-200、突然変異率0.05-0.15、200-500世代で開始。大きな個体群はより多く探索しますが遅い。10+ジョブでは個体数≥100、世代≥300を使用してください。

メイクスパン最適化と納期遅延最適化の違いは？

メイクスパン最小化は全ジョブをできるだけ早く完了しスループット最大化に最適。納期遅延最小化は納期遵守を優先。これらは競合し得るため多目的最適化でバランスを取れます。