企業活動
基本情報技術者試験 科目A免除 修了試験 20151220 実施分 問72
製造業の A 社では，NC 工作機械を用いて，四つの仕事 a～d を行っている。各仕事間の段取り時間は表のとおりである。合計の段取り時間が最小になるように仕事を行った場合の合計段取り時間は何時間か。ここで，仕事はどの順序で行ってもよく，a～d を一度ずつ行うものとし，FROM から TO への段取り時間で検討する。
表（単位 時間，行=FROM，列=TO）:
（／は斜線で値なし）
| FROM＼TO | 仕事a | 仕事b | 仕事c | 仕事d |
|---|---|---|---|---|
| 仕事a | ／ | 2 | 1 | 2 |
| 仕事b | 1 | ／ | 1 | 2 |
| 仕事c | 3 | 2 | ／ | 2 |
| 仕事d | 4 | 3 | 2 | ／ |
答えを選ぶ
出典：基本情報技術者試験 科目A免除 修了試験 20151220 実施分 問72（問題文は IPA の公開問題。解説は当サイト作成）
解説に誤りを見つけたら、解説の誤りを報告してください。
答えと解説を見る
正解：ア
覚える知識
段取り時間最小の作業順序(巡回問題)
作業順序の最適化は、遷移コスト表から合計が最小となる経路を探す。
この問題で必要なこと
全順列から最小の段取り合計を探す。b→a(1)→c(1)→d(2)で4時間が最小。
ひっかけ
各行の最小値を貪欲に選び、全作業を一度ずつという制約を満たさない経路を選ぶ。
この知識の出題：本試験系 0 回・免除試験 8 回（公開問題での観測値）。頻出知識ランキング833位（全1,254件中）。