摘要
对文献[2]中提出的求AFS问题的次优解的两个简单易行的启发式算法及其品性进行了进一步的研究。由于已证明了其在最坏情况下性能比Cmax(H)/Cmax的上界不去超过2,本文用两个典型的例子证明:对这两种算法,这一上界是可达的。
The heuristic algorithms and their performance ratios introduced in the references [2] arefurther studied here. It is proved that the upper bounds of the performance ratio in the worst case forheuristic algorithms are not greater than 2. In this paper the authors show in two examples that upperbounds are achievable for these types of algorithm.
关键词
排序
启发式算法
性能比
AFS问题
scheduling
assembly flow shop
heuristic algorithm
performance ratio