製造業のA社では、NC工作機械を用いて、四つの仕事a〜dを行っている。
各仕事間の段取り時間は表のとおりである。
合計の段取り時間が最小になるように仕事を行った場合の合計段取り時間は何時間か。
ここで、仕事はどの順序で行ってもよいものとし、FROMからTOへの段取り時間で検討する。
単位 時間
|
| ア | 4 | イ | 5 | ウ | 6 | エ | 7 |
答え ア
【解説】
各仕事からの段取り時間の最短のものを選びながら作業を進める。
仕事aから始めると、次の仕事は最短を選択し仕事c、仕事cから仕事bと仕事dの段取り時間が同じなので、双方について調べると
- 仕事a→仕事c→仕事b→仕事d=1+2+2=5時間
- 仕事a→仕事c→仕事d→仕事b=1+2+3=6時間
仕事bから始めると、仕事aと仕事dの段取り時間が同じなので、双方について調べると
- 仕事b→仕事a→仕事c→仕事d=1+1+2=4時間
- 仕事b→仕事c→仕事d→仕事a=1+2+4=7時間
仕事cから始めると、仕事bと仕事dの段取り時間が同じなので、双方について調べると
- 仕事c→仕事b→仕事a→仕事d=2+1+2=5時間
- 仕事c→仕事d→仕事b→仕事a=2+3+1=6時間
仕事dから始めると、次の仕事は最短を選択し仕事c、仕事cの次の仕事b、仕事bの次は仕事aになり
- 仕事d→仕事c→仕事b→仕事a=2+2+1=5時間
したがって、段取り時間の合計が最短になるのは、仕事b→仕事a→仕事c→仕事dのときの4時間(ア)である。
【キーワード】
・経路探索
- 経路探索
出発地から目的地まで、複数の経路や中継地点がある場合は、どの経路を通れば最も運賃(輸送費)を少なくすることができるかが問題になります。(最近は、駅すぱあとのようなソフトのおかげで自分で計算することは少ないですが…)
この問題の解き方は、中継地点ごとに最も安い運賃を求めながら、出発地から目的地の運賃を求めます。
似たような問題に線形計画法がありますが、線形計画法のように連立方程式は用いません。
もっと、「経路探索」について調べてみよう。
戻る
一覧へ
次へ