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

ジョブショップ・スケジューリング問題（JSP）

ジョブショップ・スケジューリング問題（JSP）は、生産管理やオペレーションズリサーチの分野における重要な課題です。この問題は、複数の作業があり、それぞれが特定の順序で複数の機械で処理されるときに、一定の評価指標を基に最適なスケジュールを作成することを目的としています。JSPでは、納期遅れの最小化や機械全体の稼働時間を最小化することが主な目標です。

概要

JSPでは、いくつかの作業と複数の機械があります。各作業は、あらかじめ定められた順序で各機械によって処理され、最終的な完成に至るプロセスを持ちます。この順序と機械ごとの処理時間は、事前に決められた条件として与えられます。重要な点は、各機械が同時に複数の作業を処理することができないことです。このような制約の下で、全ての作業を完了させるまでの所要時間を最小限に抑えるため、各機械にはどの作業をどの順序で処理するかを決定する必要があります。所要時間は「メイクスパン」と呼ばれ、このメイクスパンを最小化することがJSPの核心です。

JSPは、仕事の数や機械の数が増えるにつれて、その最適解を求めることが難しくなります。特に、機械の数が3つ以上になると、問題はNP完全であることが知られています。これは、解法を導くために必要な計算資源が急激に増大することを意味しており、多くのケースで効率的な解法が見いだせないことを示しています。

ガントチャート

JSPのスケジュールを視覚的に表現する方法の一つがガントチャートです。これは、横軸に時間、縦軸に機械を配置し、作業の進捗を時間経過とともに示すグラフです。ガントチャートを使用することで、作業の流れや機械ごとの稼働状況を一目で把握することが可能となり、スケジュール管理や最適化のための分析が容易になります。

デッドロック

スケジューリングにおいて、特定の順序を決定した場合に、その順序で作業が進行できなくなる現象を「デッドロック」と呼びます。このような状態に陥ると、作業の進行が妨げられ、計画通りに全ての作業を完了させることが困難になります。

難問の識別

JSPには特に難しい問題がいくつか存在し、その中で「10 Tough Problems」として知られる例題が有名です。これらはベンチマークテストとして広く利用されており、特にabz7、abz8、abz9、la21、la24、la25、la27、la29、la38、la40などが積極的に研究されています。これらの問題は、スケジューリングの性能を測るための指標として位置付けられています。

関連問題

JSPに関連する問題として、フローショップ・スケジューリング問題とオープンショップ・スケジューリング問題があります。フローショップでは、全ての作業が同様の順序で進行することが求められ、オープンショップでは作業の順序に制約がない場合を扱います。これらの問題もスケジューリングの一環として重要であり、JSPとの関連性が深いです。

参考文献

本問題やその解法に関しては、以下の参考文献が挙げられます。B. MacCarthyとJ. Liuによる1993年の文献は、スケジューリング研究のギャップに言及し、最適化およびヒューリスティック手法のレビューを提供しています。

もう一度検索