一类装配式流水作业排序问题的启发式算法及其性能比研究

根据Ｆ′２｜ｍ１≥２，ｍ２＝１｜Ｃｍａｘ排序问题是ＮＰ完全问题的论断，提出了ＡＦＳ问题的两个启发式算法，分别给出了应用启发式算法的实例。

复合并行机F′2|m_1≥2,m_2=1|C_(max)排序问题的归并算法研究

在文献[1]中,已经证明了排序问题F′2|m1≥2,m2=1|Cmax是NP完全问题,没有好算法.本文提出了复合并行机F′2|m1≥2,m2=1|Cmax排序问题的一个启发式算法归并算法,并证明了该算法在最坏情况下的性能比(PerformanceRatio)是2m-1m,且优于文献[2]中算法.

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

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