有多重最优解的流水型两工序排序问题研究

The Study of Flow-line Two-stage Production Schedules with Infinite Optimal Solutions

本文指出了著名的约翰逊 (Johnson)定理只能找到两工序排序问题的一个最优解 ,不能求出有多重最优解的两工序排序问题的所有最优解。本文给出了一种寻找两工序排序问题多重最优解的计算方法 ,并举例对该方法进行了验证。

In this paper we show that the well-known Johnson theorem only can find only one optimal solution of flowline two-stage production schedules. In fact some flow-line two-stage production shcedules have infinite optimal solutions. A new method of finding all optimal solutions of the flowline two-stage production schedules is given. The validity of the method is tested and verified by an example finally.