平成27年度　経営工学部門　Ⅲ-27PR含む

• Facebook
• X(旧:Twitter)
• はてブ
• LINE
• Pocket

問題

Ⅲ－27 以下のa～eの条件の下で3つのジョブ J₁, J₂, J₃ に関するジョブショップ・スケジューリング問題を考える。最大メイクスパンが最も小さい実行可能スケジュールのガントチャートとして、最も適切なのは次のうちどれか。

条件

a. 各ジョブはそれぞれ3つの処理からなる。
b. ジョブは3つの機械 M₁, M₂, M₃ で処理され、その処理順序（カッコ内は処理時間）は下表で示される。
c. どのジョブも処理順序に従い、ある機械で処理した後、次の機械の処理を行う。
d. 1つの機械で同時に2つの処理を行うことができない。
e. どのジョブも時刻0で開始可能である。

①　

②　

③　

④　

⑤　

解答

正解は　2　になります。

ジョブショップ・スケジューリング問題を徹底解説：正しい順序で最適なスケジュールを選ぶ

ジョブショップ・スケジューリング問題は、生産管理やプロジェクト管理において重要な課題です。
本記事では、3つのジョブ（J1, J2, J3）と3つの機械（M1, M2, M3）を用いたスケジュール問題を題材に、最大メイクスパンが最も小さい実行可能なスケジュールを選ぶ方法を解説します。

メイクスパンとは？

メイクスパンとは、全てのジョブが完了するまでに必要な最長時間を指します。
例えば、複数の作業が異なるリソース（ここでは機械M1, M2, M3）で処理される場合、それぞれの処理が完了する時刻の中で最も遅い時刻がメイクスパンとなります。
この値を最小化することは、プロジェクト全体の効率化や生産性向上に直結します。

各選択肢のガントチャートとメイクスパン

以下では、画像から読み取れる各選択肢のガントチャートを基にメイクスパンを計算し、それぞれの特徴と問題点を解説します。

選択肢①

• ガントチャート：
  • 機械M1：J1 (0～3)、J3 (3～5)、J2 (5～6)
  • 機械M2：J3 (0～3)、J1 (3～6)、J2 (6～9)
  • 機械M3：J2 (0～5)、J3 (5～8)、J1 (8～10)
• 最大メイクスパン：10
  • 全てのジョブが完了する時刻は10（機械M3でJ1が終了）。
• 評価：
  • 不適切。ジョブJ2が指定された順序（M1→M3→M2）を守っていません。具体的には、最初にM3で処理されていますが、本来はM1から始まるべきです。

選択肢②（正解）

• ガントチャート：
  • 機械M1：J2 (0～1)、J1 (1～4)、J3 (4～6)
  • 機械M2：J3 (0～3)、J1 (4～7)、J2 (7～10)
  • 機械M3：J2 (1～6)、J3 (6～9)、J1 (9～11)
• 最大メイクスパン：11
  • 全てのジョブが完了する時刻は11（機械M3でJ1が終了）。
• 評価：
  • 全てのジョブが指定された順序通りに処理されています。
  • 各機械の空き時間が少なく、効率的な並べ方です。
  • 最大メイクスパンは①より長いものの、全体的なバランスが良いため最適とされます。

選択肢③

• ガントチャート：
  • 機械M1：J2 (0～1)、J3 (3～5)、J1 (8～11)
  • 機械M2：J3 (0～3)、J1 (3～6)、J2 (6～9)
  • 機械M3：J2 (1～6)、J1 (6～8)、J3 (8～11)
• 最大メイクスパン：11
  • 全てのジョブが完了する時刻は11（機械M3で最後に終了）。
• 評価：
  • 全てのジョブが指定された順序通りに処理されています。
  • 選択肢②と同じ最大メイクスパンですが、待機時間が多く非効率です。

選択肢④

• ガントチャート：
  • 機械M1：J1 (0～3)、J2 (3～4)、J3 (4～6)
  • 機械M2：J3 (0～3)、J1 (5～8)、J2 (10～13)
  • 機械M3：J1 (3～5)、J2 (5～10)、J3 (10～13)
• 最大メイクスパン：13
  • 全てのジョブが完了する時刻は13（機械M2で最後に終了）。
• 評価：
  • 最大メイクスパンが長く非効率です。

選択肢⑤

• ガントチャート：
  • 機械M1：J2 (0～1)、J3 (1～3)、J1 (3～6)
  • 機械M2：J2 (1～4)、J3 (4～7)、J1 (7～10)
  • 機械M3：J2 (4～9)、J3 (9～12)、J1 (12～14)
• 最大メイクスパン：14
  • 全てのジョブが完了する時刻は14（機械M3で最後に終了）。
• 評価：
  • 最大メイクスパンが最も長く非効率です。

比較表

以下に各選択肢を比較した表を示します：

結論

本問題における正解は選択肢②です。このガントチャートでは以下を実現しています：

1. 全ての条件を満たしています（処理順序・機械利用制約）。
2. 最大メイクスパン（11）がバランス良く最適化されています。

一方、選択肢①は、ジョブ順序違反によって不適切と判断されます。全ての条件を満たすことが重要です。

感想

毎回ジョブショップ・スケジューリングでは頭を抱えます。

関連記事

平成25年度　経営工学部門　Ⅲ-27問題III-273つのジョブJ₁,J₂,J₃に関するジョブショップ・スケジューリング問題において、次のa～……

今回の問題でもなんで①じゃダメなのか、最初わからなかった・・・。

ああ、そうか。順番無視してるのね！って気づいたのが記事解説着手から30分後。

こりゃ鬼門かも・・・。

しかしこれ、しっかり書いていくとわかってくるものですね！！

ちょっと面白いかも。

• Facebook
• X(旧:Twitter)
• はてブ
• LINE
• Pocket