文献类型：期刊文献

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

英文题名：On the Total Flow-Time Problem of Two Machine Open-Shop

作者：应刚[1];

机构：[1]上海华东理工大学应用数学研究所;

年份：1998

卷号：2

期号：2

起止页码：84

中文期刊名：运筹学学报

外文期刊名：OR Transactions

收录：CSTPCD;;CSCD:【CSCD2011_2012】；

基金：国家自然科学基金

语种：中文

中文关键词：时间表问题;自由作业;总流程;算法;排序

外文关键词：Scheduling Problems, Open-Shop, Total Flow-Time, Algorithms, Explicit Solution

摘要：二台机器自由作业的总流程问题是ＮＰ困难问题，当加工时间仅依赖于机器时，该问题尚示被解决，本文对于机器均空闲的约束条件下的上述问题，给业式解，即最优时间表的构造形式，从而改进了文献中的结果。此外，本文还对允许空闲的上述问题，作了一些讨论，指出了Ｖａｋｈａｒｉａ和Ｃａｔａｙ一文中算法的错误。
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.