论文部分内容阅读
大多数排序方面的文章主要考虑机器加工工件的过程是连续的，不会出现机器停止的情形．然而在实际生活中，机器加工工件的过程有时是可以停止的，例如机器定期维护，员工定期休假等等，这种状况在排序中称之为机器定期维护限制．
本文中考虑的情形即为一组同型机在加工过程中不是连续不停的，机器在某一个特定的时间段内将停止运行，对于这种情形下平行机排序的一些相关问题，文中先确定目标函数最优值的上下界，然后通过折半查找算法来搜索目标函数的最优解，其中采用的折半查找算法中关于基本问题的可行性检验是采用网络最大流算法．整个算法的关键步骤在于如何构造与排序问题相对应的网络图，从而将排序问题表示成为一组最大流问题．根据一些不同的限制条件以及所求问题的目标函数的不同，构造不同的网络图，这在很大程度上也决定了算法的时间复杂性．