论文部分内容阅读
讨论使两台和三台平行机的最小完工时间为最大的线性算法——对偶阈值算法DAm（ε），其中ε是参数。对于问题P2‖Cmin，证明对偶阈值算法DA2（1／7）的最坏情况界为6／7，并证明此界为紧界：对于问题P2‖Cmin，进而提出层次对偶阈值算法TDA3（ε），并证明当ε取2／11时，算法的最坏情况界为9／11。这些都是线性时间算法中使最坏情况界值为最小的算法。