分装式流水作业加工模型的性质及启发式算法研究

Study on the property and the Heuristic algorithms of TMF process model

分装式流水作业(简记为TMF)加工模型是从生产实践中提炼出的新型的排序模型。由于文献[1][2]中已经证明该问题在一般情况下是NP-完全问题,没有多项式时间算法。在这篇论文中进一步讨论了该加工模型的性质,并提出了它的启发式算法以及启发式算法在最坏情况下的性能比的上界。

A type of new process model is studied. Because it is shown to be NP - complete Ill,no good polynomial algorithm can he found, in this paper the property and the heuristic algorithms of the process model is presented to find suboptimal solution, and provided that the upper bounds of the performance ratio in the worst case for the heuristic algorithms.