依赖机器的两台机自由作业排序问题

文章研究加工时间仅依赖于机器的两台机自由作业排序问题 O2 | pij = pi, p2 < p1 < 2p2, Non-Idle | ΣCj。项思明和唐国春(1998)证明了可将该问题转化成指派问题。俞文ci 和应刚(1998)给出了这一问题的显式解，并用较长的篇幅证明其显式解的正确性；他们还举例说明所给出的显式最优排序并不排除其他形式的最优解的存在；但他们未说明所给出的显式解何时才是唯一最优解。本文将给出问题 O2 | pij = pi, p2 < p1 < 2p2, Non-Idle | ΣCj的显式解的直观的最优性证明，并讨论问题显式解何时是唯一的最优解。

Two-Machine Open Shop Scheduling with Machine-Dependent Processing Times

Abstract　A two-machine open shop scheduling problem with machine-dependent processing times O2 | pij = pi, p2< p1< 2p2, Non-Idle | ΣCj is examined. Xiang & Tang prove that this problem can be transformed to an assignment problem which is polynomially solvable. Yu & Ying give an explicit solution of this problem, and proves its optimality. In addition they present that the explicit solution is not exclusive and other optimal solutions are possible exist. We give a simple proof of the optimality of the explicit solution Yu & Ying proposed and discuss the uniqueness of the optimal solution.