加工のために使用する機械の順番は製品ごとに定まっている．加工順と加工に必要な時間をまとめたのが以下の表である．
| 製品名 | 加工順 | 機械M1での加工時間(時間) | 機械M2での加工時間(時間) |
|---|---|---|---|
| A | M1→M2 | 2 | 4 |
| B | M1→M2 | 6 | 7 |
| C | M1→M2 | 8 | 3 |
| D | M1のみ | 2 | - |
| E | M1のみ | 6 | - |
| F | M2のみ | - | 7 |
| G | M2のみ | - | 3 |
| H | M2→M1 | 6 | 5 |
| I | M2→M1 | 2 | 8 |
| J | M2→M1 | 5 | 3 |
| K | M2→M1 | 9 | 4 |
さて，11個の製品の加工をなるべく早く終了するにはどのような順序により各機械での加工を行えば良いか．加工順序を機械毎に提案せよ．また，ガントチャートを作成することによって，提案した加工順序での総経過時間を求めよ．
コメント： 問題の構造がどのようになっているか良く考えて，最適な加工順序を導こう．素朴な方法やがむしゃらな方法では途方も無い時間がかかってしまうよ．