摘要
研究加工时间仅依赖于机器的两台机自由作业排序问题O_2|p_(ij)=p_i,p_2<p_1<2p_2,Non-Idle|ΣC_j.项思明和唐国春(1998)证明了可将该问题转化成指派问题.俞文(?)和应刚(1998)给出了这一问题的显式解,并用较长的篇幅证明其显式解的正确性;他们还举例说明所给出的显式最优排序并不排除其他形式的最优解的存在;但他们未说明所给出的显式解何时才是唯一最优解.将给出问题O_2|p_(ij)=p_i,p_2<p_1<2p_2,Non-Idle|∑C_j的显式解的直观的最优性证明,并讨论问题显式解何时是唯一的最优解.
A two-machine open shop scheduling problem with machine-dependent processing times O_2｜pij=pi,p2p12p2,Non-Idle ｜ΣC_j 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 discussed the uniqueness of the optimal solution.
出处
《运筹学学报》
CSCD
2011年第4期65-74,共10页
Operations Research Transactions
基金
国家自然科学基金(10871143)
关键词
排序
自由作业
运输问题
指派问题
最优解
scheduling
open shop
transportation problem
assignment problem
optimal solution
