English

运筹学学报

• 运筹学 • 上一篇    下一篇

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

闻振卫   

  1. 苏州大学数学科学院
  • 收稿日期:2011-02-28 修回日期:2011-03-26 出版日期:2011-12-15 发布日期:2011-12-19
  • 通讯作者: 闻振卫 E-mail:zwwen@suda.edu.cn

Two-machine open shop scheduling with machine-dependent processing times

Zhen-Wei WEN   

  • Received:2011-02-28 Revised:2011-03-26 Online:2011-12-15 Published:2011-12-19
  • Contact: Zhen-Wei WEN E-mail:zwwen@suda.edu.cn

PDF

1097

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

关键词:  排序, 自由作业, 运输问题, 指派问题, 最优解

Abstract: 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.

Key words: scheduling, open shop, transportation problem, assignment problem, optimal solution