关于一类自由作业机器排序问题

On a Class of Openshop Scheduling Problem

文章研究文［１］中提出的加工时间依赖于机器的自由作业排序问题。Ｍ．Ｄｏｒｏｒ在［１］中提出了一个算法（算法３．４）。最近，Ａ．Ｊ．Ｖａｋｈａｒｉａ、Ｂ．Ｃａｔａｙ［２］及项思明、唐国春［３］均指出Ｍ．Ｄｏｒｏｒ的算法不是最优的。项思明和唐国春提出对这类问题在机器连续加工情形下的一种求解方法，即将排序问题化成指派问题。本文对这种解法作了简化，并回答文［３］中提出的几个问题。

We examine a class of openshop machine scheduling with machine dependent processing times in . In , M.Doror presents an algorithm to solve the problem O2|P ij =P i,P 2<P 1<2P 2| ∑ C j. A.J.Vakharia and B.Catay and S.M.Xiang and G.C.Tang give some counter examples to show that Doror's algorithm is not optimal. S.M.Xiang and G.C.Tang apply an assignment problem to solve such a problem. We simplify their method and answer some problems in in this paper.