Skip to content
検索結果に戻る

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

提唱者
Pinedo, M. L.
年
2016
種類
Combinatorial scheduling problem
系統
Optimization

この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む

文字サイズ

何をする手法か?

ジョブショップスケジューリングとは、一連のジョブ(タスク)を、順序制約および能力制約に従って、時間とともに一連の機械(リソース)に割り当てる問題であり、メイクスパン(総完了時間)、遅延、またはコストなどのパフォーマンス指標を最適化することを目的とします。ジョブショップ問題は、オペレーションズ・リサーチにおける古典的な組み合わせ最適化問題であり、ヒューリスティクス(貪欲法によるディスパッチングルール、焼きなまし法、遺伝的アルゴリズム)および厳密解法(分枝限定法、制約プログラミング)によって対処されます。製造業、プロジェクト管理、および計算スケジューリングの基本となります。

手法の背後にある直感

10台の機械を持つ小さな機械加工工場を想像してください。顧客の注文(ジョブ)は5つの部品からなり、各部品は異なる機械での一連の加工工程を必要とします。部品1は機械Aでの加工、次に機械Cでの穴あけが必要です。部品2は機械Bでの穴あけ、次に機械Dでの溶接が必要です。すべての部品は最終組み立てのために集められます。課題は、機械能力を超えず、各部品の加工順序を尊重しながら、総完了時間を最小化するようにすべての加工工程をスケジュールすることです。部品1を機械Aに割り当てるのが遅すぎると、機械Cはアイドル状態になります。機械Cに負荷をかけすぎると、すべてが遅延します。ジョブショップ問題は、この複雑さを捉えています。100件のジョブと20台の機械がある場合、可能なスケジュールの数は天文学的な数になり、厳密な解法は非現実的です。代わりに、ヒューリスティクスを使用して、迅速に良好な(必ずしも最適ではない)スケジュールを見つけます。

歴史学

ジョブショップスケジューリング問題は、1950年代にオペレーションズ・リサーチの研究問題として登場しました。Johnson (1954) による画期的な研究は2機械問題を最適に解決し、Fisher and Thompson (1963) は今日でも使用されているベンチマーク問題を作成しました。この問題はNP困難であることが1970年代に証明され、ヒューリスティクスとメタヒューリスティクスの開発を促進しました。現代的なアプローチには、制約プログラミング(1990年代~2000年代)、遺伝的アルゴリズム、およびハイブリッド手法が含まれます。ジョブショップスケジューリングは現在、製造業を超えてクラウドコンピューティング、通信、輸送にまで応用が広がる成熟した分野となっています。

使うべき場面

ジョブショップスケジューリングは、複数の機械/リソースと明確な加工工程順序を持つジョブが存在するあらゆる製造業またはサービス業の環境に適用されます。典型的な応用例としては、機械加工工場、印刷工場、半導体ウェハー製造、病院(手術室スケジューリング)、およびプロジェクトスケジューリングが挙げられます。ジョブの複雑性が高い(ジョブあたりの加工工程数が多い)、機械の稼働率が重要である、または納期が厳しい場合にこれを使用します。組立ライン環境(直線的な流れ)や単純な単一機械の加工では重要性は低くなります。

限界と注意点

  • 組み合わせの複雑性:最適解の発見はNP困難であり、実用的な解にはヒューリスティクスが必要ですが、これは必ずしも全体最適解であるとは限りません
  • ヒューリスティクス解は文脈依存的です。ある工場でうまく機能するルールが、別の工場ではうまく機能しない可能性があり、調整と検証が必要です
  • 静的な入力(固定されたジョブと機械)を想定していますが、実際の工場では動的な到着、キャンセル、および設備の故障が発生するため、頻繁な再スケジューリングが必要です
  • スケジュールの安定性:新しいジョブや中断によるスケジュールの頻繁な変更は、コストを増加させ、作業員や顧客との調整を複雑にする可能性があります

出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。

強み

  • 単純なスケジューリングルールでは対応できない、複雑で現実的な制約(順序、機械能力、納期)に対応します
  • 場当たり的なルールではなく、関連するビジネス指標(メイクスパン、遅延、機械稼働率)を最適化します
  • 中断への迅速な対応を可能にします。機械の故障や緊急ジョブの到着時に、再スケジューリングアルゴリズムが改訂された計画を生成できます
  • 数学的定式化により、感度分析とトレードオフの検討(例:遅延対メイクスパン)が可能になります
  • 効率的なソフトウェアツールと成熟したメタヒューリスティクスアルゴリズムによってサポートされます

応用

  • 精密機械加工工場が、15台のCNC機械で200以上のカスタム部品をスケジュールするために焼きなまし法を用いたジョブショップスケジューリングを採用し、メイクスパンを15%削減し、納期遵守率を85%から95%に向上させました
  • 半導体製造工場が、50台のツールにわたる500以上のプロセスステップを管理するために制約ベースのスケジューリングを適用し、ウェハーサイクルタイムを最小化し、仕掛品在庫を20%削減しました
  • 印刷会社が、異なる能力を持つ8台の印刷機に印刷ジョブを割り当てるために動的なジョブショップスケジューリングを使用し、ジョブミックス(大量生産対特殊品)を最適化し、段取り時間を最小化しました
  • 病院のスケジューリングチームが、手術室のスケジューリングにジョブショップアルゴリズムを実装し、外科医、手術チーム、および設備を調整し、手術室の稼働率を65%から82%に向上させました

使い方

使い方

1

ジョブ(注文、タスク)を、加工工程の順序、必要な機械、加工時間、および納期とともに定義します。利用可能な機械とその利用可能時間を指定します。

2

制約を指定します。加工工程の順序(部品1は加工Bを開始する前に加工Aを完了する必要がある)、能力(各機械は一度に1つのジョブしか処理できない)、およびオプションで、リリース時間と納期です。

3

各機械でジョブを順序付けるためにディスパッチングルール(例:最短加工時間、最短納期、クリティカルレシオ)を適用し、初期スケジュールを生成します。

4

メタヒューリスティクス(焼きなまし法、タブーサーチ、遺伝的アルゴリズム、アリコロニー最適化)を使用して、局所探索または集団ベースの方法を通じてスケジュールを改善します。

5

スケジュールの品質(メイクスパン、遅延、アイドル時間、バッファ時間)を評価します。許容できる場合は実装します。そうでない場合は、パラメータを調整して再最適化します。

よくある落とし穴

  • 誤った指標の最適化:機械稼働率の最大化はジョブの遅延を増加させる可能性があり、すべての納期を満たすにはかなりのアイドル時間が必要になる場合があります
  • 段取り時間と切り替えを無視すること:アイドル時間を最小化するが頻繁で時間のかかる段取りを必要とするスケジュールは、実際には最適ではない可能性があります
  • 検証なしにヒューリスティクススケジュールを過信すること。実際の工場での挙動に対して検証せずに使用すると、モデルが捉えるよりも制約が複雑であることが判明する場合があります

よくある質問

メイクスパンとは何ですか、そしてなぜ重要ですか?

メイクスパンとは、最初の加工工程の開始から最後の加工工程の完了までの総時間です。これは、設備稼働率、キャッシュフロー(完了が早いほど支払いも早い)、および顧客満足度に直接相関します。メイクスパンの最小化は、ジョブショップスケジューリングにおける一般的な主要目標です。

静的ジョブショップスケジューリングと動的ジョブショップスケジューリングの違いは何ですか?

静的スケジューリングは、すべてのジョブが事前にわかっていると仮定します。固定されたセットを最適化します。動的スケジューリングは、時間とともに到着するジョブを処理します。新しいジョブが到着したり、中断が発生したりすると、スケジュールは改訂されます。ほとんどの実際の工場は動的であり、高速な再最適化アルゴリズムが必要です。

どのディスパッチングルールを使用すべきですか?

単一のルールが支配的になることはありません。最短加工時間(SPT)はメイクスパンを最小化します。最短納期(EDD)は遅延を最小化します。クリティカルレシオは両方をバランスさせます。工場の優先順位と制約に最適なルールを見つけるために、過去のデータまたはシミュレーションでルールをテストしてください。

ジョブショップスケジューリングは、作業員のスキルやクロス・トレーニングを扱えますか?

はい、リソースモデルを拡張することによって可能です。「機械A」だけでなく、「作業員1がいる機械A」または「作業員2がいる機械A」のように指定します。ただし、これにより問題の複雑さが増します。スケジューリングソフトウェアがマルチリソース制約をサポートしていることを確認してください。

関連する手法

参考文献

  1. Pinedo, M. L. (2016). Scheduling: Theory, algorithms, and systems (5th ed.). Cham: Springer.

    DOI 文献を開く
    コピーしました。
  2. Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2), 278-285.

    DOI 文献を開く
    コピーしました。