流水线调度问题探究

流水线作业是现代生产线最常用的技术,流水线调度问题是具有很强工程背景的典型NP完全问题。文中介绍了特殊情况下流水线调度的有效算法:Johnson算法;对于一般情况,介绍了两种启发式算法:CDS算法和Palmer算法。对这两种启发式算法的分析表明,在时间复杂度上,CDS算法比Palmer算法复杂。但大量实验测试表明,CDS算法的结果比Palmer算法更佳。所以,当需要快速获得一个近似解的时候,可以采用Palmer算法;当对解的结果要求比较高的时候,可以采用CDS算法。

The Research of Pipeline Problem

The technology of pipeline is the most frequently used in modern product line. Pipeline problem is a typical NP-complexity problem with a solid background of the project.Introduces Johnson algorithm:an effective algorithm under special circumstance for pipeline problem. For ordinary situations, introduces two effective heuristic algorithms: CDS and Palmer. By analyzing these two heuristic algorithms,can know that the time complexity of CDS is smaller than that of Palmer. But experiment studies show that CDS algorithm performs better on the accuracy than Palmer algorithm. So if need to get an approximate solution quickly, the algorithm of Palmer should be selected; if need a good solution, the algorithm of CDS should be selected.