平成25年度 経営工学部門 Ⅲ-27PR含む
問題
III-27 3つのジョブJ₁, J₂, J₃に関するジョブショップ・スケジューリング問題において、次のa～eの条件の下で作成された現状のスケジュールが下図に示されている。
この問題のスケジュールに関する以下の記述のうち、最も不適切なものはどれか。
条件:
a. 各ジョブはそれぞれ3つの作業からなる。
b. ジョブは3つの機械M₁, M₂, M₃で加工され、その加工手順（カッコ内は作業時間）と納期は下表で示される。
| ジョブ | ジョブの加工手順（カッコ内は作業時間） | 納期 |
|---|---|---|
| J₁ | M₁(5) → M₂(3) → M₃(2) | 13 |
| J₂ | M₁(2) → M₃(6) → M₂(4) | 12 |
| J₃ | M₂(4) → M₁(3) → M₃(4) | 17 |
c. どのジョブも加工手順に従い、ある機械で加工した後、次の機械の加工を行う。
d. 1つの機械では同時に2つの加工を行うことができない。
e. どのジョブも時刻0で開始可能である。
① 現状のスケジュールの総納期遅れは5分である。
② 現状のスケジュールのM₂において、J₁とJ₂の順序を交換したときのメイクスパンは16分である。
③ 現状のスケジュールのM₂において、J₁とJ₂の順序を交換したときの総納期遅れは4分である。
④ 現状のスケジュールのM₂において、J₁とJ₂の順序を交換したときの納期遅れジョブ数は1である。
⑤ 現状のスケジュールのM₂において、J₁とJ₂の順序を交換したときのスケジュールでは、J₂の待ち時間は減少する。
解答
正解は 2 になります。
ジョブショップ・スケジューリング問題の解説
生産管理における重要な課題であるジョブショップ・スケジューリング問題について、具体的に解説していきます。
ジョブショップ・スケジューリングとは
ジョブショップ・スケジューリングは、生産工程での作業の順番を決定するための問題です。ここでは、複数のジョブ（作業）が複数の機械を使って加工されます。目標は、全体のスケジュールを最適化し、納期や作業時間を管理することです。
現状のスケジュール分析
現状のスケジュールでは、3つのジョブ（J₁、J₂、J₃）が3台の機械（M₁、M₂、M₃）で処理されています。各ジョブの完了時刻を確認すると：
- J₁: 16分（納期13分）→ 3分遅れ
- J₂: 14分（納期12分）→ 2分遅れ
- J₃: 17分（納期17分）→ 遅れなし
したがって、総納期遅れは5分（3分＋2分）となります。
選択肢の詳細解説
選択肢①「現状のスケジュールの総納期遅れは5分である」
- J₁の完了時刻：16分（納期13分）→ 3分遅れ
- J₂の完了時刻：14分（納期12分）→ 2分遅れ
- J₃の完了時刻：17分（納期17分）→ 遅れなし
したがって、総納期遅れは5分（3分＋2分）となり、この記述は正しい。
選択肢②「現状のスケジュールのM₂において、J₁とJ₂の順序を交換したときのメイクスパンは16分である」
- 現状のスケジュールでM₂の作業順序をJ₁→J₂からJ₂→J₁に変更すると
- J₂はM₂でM₃での作業が終わる8分から作業開始
- その後12分後よりJ₁での作業開始
- J₁はM₂で3分であり、全体の完了時間（メイクスパン）は15分となる
したがって、この記述は不適切。
選択肢③「現状のスケジュールのM₂において、J₁とJ₂の順序を交換したときの総納期遅れは4分である」
順序交換後：
- J₁の完了時刻：17分（納期13分）→ 4分遅れ
- J₂の完了時刻：12分（納期12分）→ 遅れなし
- J₃の完了時刻：17分（納期17分）→ 遅れなし
したがって、総納期遅れは4分となり、この記述は正しい。
選択肢④「現状のスケジュールのM₂において、J₁とJ₂の順序を交換したときの納期遅れジョブ数は1である」
順序交換により：
- J₁は納期遅れとなる
- J₂は12分で作業完了し納期に間に合う
- J₃は元々納期遅れなし
したがって、この記述は正しい。
選択肢⑤「現状のスケジュールのM₂において、J₁とJ₂の順序を交換したときのスケジュールでは、J₂の待ち時間は減少する」
- J₂はM₃での作業完了後にM₂での作業が可能
- その後もJ₁で待ち時間無く加工可能。
したがって、この記述は正しい。
結論
選択肢②が最も不適切です。メイクスパンの計算が明らかに誤っており、ジョブショップ・スケジューリングの基本原則に反する結果となっているためです。
感想
過去にスケジューリングの問題は出ていましたね。
ジョブショップ・スケジューリングのタグを追加しておこう。
この過去問ではかなり苦労しましたが、今回の問題はすんなり解けた気がします。
いちおう、正解でしたよ！
関連記事Related articles
