复合并行机排序问题启发式算法性能比的紧界研究

A Study of Tight Bound of Heuristic Algorithm Performance Ratio for AFS Scheduling Problem

已证明装配式流水作业排序问题是NP完全问题,没有好算法。提出了该问题的启发式算法———归并算法,并证明了该算法在最坏情况下的性能比。用一个典型实例证明:此上界是可达的。

Because scheduling problem of assembly flow shop is proved NP - complete and hence there exists no ＂good＂ algorithm. The other heuristic algorithm is presented to find suboptimal solution and provid the upper bounds of the performance ratio in the worst case for the heuristic algorithms, it is showed that the upper bounds are achievable for the algorithm.