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

摘要

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