令和2年度　経営工学部門　Ⅲ-24

2026年8月5日

当ページのリンクには広告が含まれています。

問題

Ⅲ－24　ジョブショップ及びそのスケジューリングに関する次の記述のうち、最も不適切なものはどれか。

① ジョブショップの典型は、注文に応じてさまざまな種類の工作機械を生産している機械工場に見られる。

② ルールベーススケジューリングは、生産システムの構成要素に関する条件を制約としたモデルを基礎として、ジョブの加工、移動、滞留などの工程状態をシミュレートすることによって、スケジュールを作成する方法である。

③ 2機械のジョブショップでメイクスパン最小化を目的とするスケジューリング問題に対してJ．R．Jacksonの最適化アルゴリズムがある。

④ 3台以上のジョブショップスケジューリング問題は、NP困難な問題であり、最適なスケジュールを求めるのは容易でない。

⑤ スケジューリング問題において、ジョブショップの場合は、フローショップの場合よりジョブの流れが複雑で、錯綜したものとなるから、最適なスケジュールを求めることが困難になる。

解答

正解は　2　になります。

問題の概要

本問は、生産管理におけるスケジューリング理論、特に「ジョブショップ・スケジューリング（Job-Shop Scheduling）」の学術的定義、流動特性、および計算複雑性（モデルの解きやすさ・難易度）に関する正確な知識を問う問題です。

生産システムにおけるスケジューリング問題（設備への作業割り当て計画）は、工場のレイアウトや対象となるジョブ（仕事）の流動パターン（機械を訪れる順序）によって、主に以下の2つに大別されます。

フローショップ（Flow-Shop）
すべてのジョブが、同一の機械順序（例：機械A $\rightarrow$ 機械B $\rightarrow$ 機械C）に沿って一方向に流れる生産環境。大量生産やライン生産方式に多く見られます。
ジョブショップ（Job-Shop）
ジョブごとに加工経路（機械を訪れる順序や回数）が完全に独立しており、あるジョブは「A $\rightarrow$ B $\rightarrow$ C」と進み、別のジョブは「B $\rightarrow$ C $\rightarrow$ A」や「C $\rightarrow$ B」のように進む生産環境。多品種少量生産や個別受注生産の機械加工職場で一般的に見られます。

本問を解くにあたっては、JIS Z 8141（生産管理用語）における定義をベースとし、「ルールベース（ディスパッチング・ルール）」と「シミュレーションベース」の境界線、2機械環境における古典的最適化アルゴリズム（Jacksonのアルゴリズム）、および3台以上の設備における計算複雑性理論（NP困難性）を厳密に区別・理解しているかどうかが厳しく問われています。

各選択肢の詳細解説

① ジョブショップの典型は、注文に応じてさまざまな種類の工作機械を生産している機械工場に見られる。

【詳細解説と論理的根拠】
ジョブショップ生産（Job-shop production）は、汎用的な機能を持つ工作機械を機能別（旋盤エリア、フライス盤エリア、マシニングセンタエリア、熱処理エリアなど）に配置し、多種多様なジョブを個別・少量ずつ処理する形態です。
注文に応じて、旋盤加工の後にすぐ組み立てる製品もあれば、旋盤 $\rightarrow$ 熱処理 $\rightarrow$ 研削工程と複雑に設備間を往復する製品もあります。
注文ごとに製品仕様が異なり、加工経路が不規則に入り乱れる「工作機械を生産している機械工場」は、まさにジョブショップ生産形態の教科書的な典型例（JIS Z 8141の定義通り）です。
したがって、この記述は適切です。

② ルールベーススケジューリングは、生産システムの構成要素に関する条件を制約としたモデルを基礎として、ジョブの加工、移動、滞留などの工程状態をシミュレートすることによって、スケジュールを作成する方法である。

【詳細解説と論理的根拠】
本肢の記述は明白に不適切であり、本問の正解（不適切な選択肢）となります。
記述されている「生産システムの構成要素に関する条件を制約としたモデルを基礎として〜工程状態をシミュレートする」というアプローチは、ルールベーススケジューリングの定義ではなく、「シミュレーションベーススケジューリング（Simulation-based Scheduling）」、あるいはAPS（先進的スケジューリングシステム）などで用いられる「有限能力スケジューリング（Finite Capacity Scheduling：FCS）」の定義です。

「ルールベース（ディスパッチング・ルール：Dispatching Rule）スケジューリング」の正確な定義は以下の通りです。

各機械（設備）の前に加工待ちのジョブ（仕掛品）が複数並んだ際、あらかじめ定めた「1つの単純な優先権ルール（ルール）」に従って、その場で動的に次に加工するジョブを決定（ディスパッチ）していく手法。

代表的な優先ルール（ルールベース）には、以下のようなものがあります。

SPTルール（Shortest Processing Time）：加工時間が最も短いジョブを優先する（平均滞留時間を最小化する）。
EDDルール（Earliest Due Date）：納期が最も早いジョブを優先する（最大納期遅れを最小化する傾向がある）。
CRルール（Critical Ratio）：納期までの残裕度（臨界比）が最も小さいジョブを優先する。

ルールベースは、工場全体の大掛かりな制約モデルを構築して未来の全挙動を緻密にシミュレートするものではなく、あくまで「その場その場の局所的な判断ルール」に過ぎません。
したがって、手法の定義を混同させているこの記述は最も不適切です。

③ 2機械のジョブショップでメイクスパン最小化を目的とするスケジューリング問題に対してJ．R．Jacksonの最適化アルゴリズムがある。

【詳細解説と論理的根拠】
2台の機械（$M_1, M_2$）があり、すべてのジョブが $M_1 \rightarrow M_2$ の順に流れる「2機械フローショップ問題」の総加工時間（メイクスパン）を最小化するアルゴリズムとしては、「ジョンソン法（Johnson’s Rule）」が広く知られています。
しかし、本問の対象である「ジョブショップ」は、経路が一定ではありません。
ジョブによっては $M_2 \rightarrow M_1$ の順で動くものや、$M_1$ だけ、あるいは $M_2$ だけで加工を終えるものも混在します。
1956年、J. R. Jacksonはこの複雑な「2機械ジョブショップ問題」に対し、ジョンソン法を美しく拡張した「ジャクソン法（Jackson’s Algorithm / Rule）」と呼ばれる最適化アルゴリズムを提唱しました。

ジャクソン法では、全ジョブを以下の4つの集合（グループ）に分類します。

$A$ ： $M_1$ のみで加工するジョブの集合
$B$ ： $M_2$ のみで加工するジョブの集合
$AB$： $M_1 \rightarrow M_2$ の順で加工するジョブの集合
$BA$： $M_2 \rightarrow M_1$ の順で加工するジョブの集合

そして、集合 $AB$ と集合 $BA$ に対してそれぞれ独立してジョンソン法を適用し、最終的に「$M_1$ では $AB \rightarrow A \rightarrow BA$ の順」「$M_2$ では $BA \rightarrow B \rightarrow AB$ の順」で処理を割り当てることで、メイクスパンを確実に最小化できる厳密解（最適解）を導き出します。
このように、2機械ジョブショップに対する確固たる最適化アルゴリズムが存在するため、この記述は適切です。

④ 3台以上のジョブショップスケジューリング問題は、NP困難な問題であり、最適なスケジュールを求めるのは容易でない。

【詳細解説と論理的根拠】
計算複雑性理論（コンピュテーショナル・コンプレキシティ）において、割り当てる機械の台数が3台以上になったジョブショップ・スケジューリング問題（JSP）は、数学的に「NP困難（NP-hard）」な問題であることが証明されています。
NP困難とは、大まかに言えば「問題の規模（ジョブの数や機械の数）が大きくなると、厳密な最適解を計算するために必要な手間が、指数関数的に爆発してしまう問題」のことです。
ジョブ数が数十個、機械数が数台を超えただけで、宇宙的な組み合わせの数（総当たりパターン）になってしまうため、動的計画法や整数計画法などの厳密解法を用いて「100点満点の絶対的な最適スケジュール」を現実的な時間内（数分・数時間以内）に算出することはスーパーコンピュータを使っても容易ではありません。
実務ではメタヒューリスティクス（遺伝的アルゴリズム、タブーサーチなど）を用いて「実用上十分な合格点（近似解）」を狙うのが一般的です。
したがって、この記述は適切です。

⑤ スケジューリング問題において、ジョブショップの場合は、フローショップの場合よりジョブの流れが複雑で、錯綜したものとなるから、最適なスケジュールを求めることが困難になる。

【詳細解説と論理的根拠】
フローショップ環境では、すべてのジョブが同じ方向（単一のベクトル）へ向かって順序よく流れるため、機械ごとの待ち行列の予測やボトルネックの特定が比較的容易です（ただし、3台以上になればフローショップもNP困難にはなります）。
それに対して「ジョブショップ」環境では、あるジョブの次工程が別のジョブの前工程と衝突するなど、工場内の物理的な物流・経路が多方向に入り乱れ、文字通り「錯綜（さくそう）」します。
これにより、ある機械でのスケジューリング判断が、別の遠く離れた機械の待ち行列に予期せぬ多大な影響を及ぼすため、探索すべき解の空間（選択肢の組み合わせ構造）がフローショップよりも格段に複雑化し、実務的・相対的な意味において「最適なスケジュールを求めることの困難さ」が大幅に跳ね上がります。
したがって、この記述は適切です。

追加解説（試験対策の視点）

経営工学の試験問題において、スケジューリングの難易度や手法の対応関係は非常に美しい「対称性」を持っています。
以下の対比マップを頭に入れておくことで、どのような角度から出題されても瞬時に正誤を判定できるようになります。

2機械の場合（最適解が数理的に出せる限界）
- フローショップ（同経路） $\rightarrow$ ジョンソン法で最速解決
- ジョブショップ（別経路） $\rightarrow$ ジョンソン法を4グループに拡張したジャクソン法で最速解決
3機械以上の場合（人間の手にも計算機にも負えない限界）
- フローショップ $\rightarrow$ NP困難（一部の特殊条件を除き、厳密解の算出は困難）
- ジョブショップ $\rightarrow$ NP困難（モノの流れが錯綜するため、フローショップ以上に実務上の計画立案が困難）

実務の生産管理では、この3台以上の壁（NP困難）を回避するため、選択肢②で否定された「単純なルールベース（SPTやEDD）」を機械ごとに現場の判断で適用するか、システム全体でシミュレーション（FCS）を回して高速に予定を組み立てています。

まとめ

選択肢②の誤り: 「構成要素の条件を制約としたモデルをベースに工程をシミュレートする方法」は、ルールベースではなくシミュレーションベース（有限能力スケジューリング）の定義であるため不適切。
本来のルールベースは、機械の前でEDDやSPTといった簡易ルールで動的に順序を決める手法を指す。
ジャクソン法（選択肢③）: 2機械ジョブショップ問題のメイクスパンを最小化するための由緒正き最適化手法である。
NP困難と錯綜性（選択肢④・⑤）: 3台以上のジョブショップは計算量が爆発するNP困難であり、流動経路が四方八方に錯綜するため、フローショップよりも最適解の導出が構造的に困難である。