| 効率よく解けた ⇔ （まだ）解けない |
| n製品の最適工程順序問題の場合 |
| 2機械 |
| 機械数 |
| 多機械 |
| 主な解法 |
| ジョンソン法 |
| 分枝限定法など |
| O(nlog2n) |
| O(n!) |
| 最悪計算量 |
|
|
| n=1万，1億演 |
|
| 算/秒の時 |
|
| 0.002秒 |
| 6×1035634宇宙年 |
|
|
|
|
|
| • | 効率の良い方法は |
|||
| 見つかっていない |
||||
| • | いつかは見つかる？ |
|||
|
|
|
| 他の問題の |
||
| 場合はどう？ |
||