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

摘要

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