关于二台机器自由作业的总流程问题

On the Total Flow-Time Problem of Two Machine Open-Shop

二台机器自由作业的总流程问题是NP困难问题．当加工时间仅依赖于机器时，该问题尚未被解决．本文对于机器均不允许空闲的约束条件下的上述问题，给出了显式解，即最优时间表的构造形式，从而改进了文献中的结果．此外，本文还对允许空闲的上述问题，作了一些讨论，指出了Vakharia和Catay一文（1997）中算法的错误．

It's known that the total flow-time problem of two machine open-shop is NP-hard. The restriction problem with machine dependent processing times has not been solved yet. In this paper, for the above problem under the non-idle machine constraints, an explicit solution, i.e., a construction form of an optimal schedule, is designed and proved. This conclusion improves the existing result about the restricted problem. Furthermore in this paper, for the above problem without constraints, some discussions are made, and a mistake of the algorithm in Vakharia &Catay (1997) is pointed.