排序问题Fm‖Cmax的几种启发式算法在最坏情况下性能比上界的可达性研究

摘要

Ｇｏｎｚａｌｅｚ和Ｓａｈｎｉ已证明：当ｍ≥３时，排序问题ＦｍＣｍａｘ是ＮＰ困难问题，没有好算法。因此，很多学者提出了多种简单易行的启发式方法求这类问题的次优解，且对其中的ＧＳ算法和ＲＳ算法证明了在最坏情况下性能比Ｃ＊ｍａｘ（Ａ）／Ｃ＊ｍａｘ的上界不超过｛ｍ／２｝＊。本文用同一例子证明，对这两种算法，这一上界是可达的。