使两台和三台平行机的最小完工时间为最大的线性算法

Linear Algorithms for Maximizing the Minimum Machine Completion Time on Two and Three Parallel Machines

讨论使两台和三台平行机的最小完工时间为最大的线性算法——对偶阈值算法DA m(ε),其中ε是参数。对于问题P2||Cmin,证明对偶阈值算法DA2(1/7)的最坏情况界为6/7,并证明此界为紧界;对于问题P3||Cmin,进而提出层次对偶阈值算法TDA3(ε),并证明当ε取2/11时,算法的最坏情况界为9/11。这些都是线性时间算法中使最坏情况界值为最小的算法。

Linear time algorithms for maximizing the minimum machine completion time on two and three parallel machines have been researched. For P2‖Cmin, the worst-case ratio of Dual-Threshold Algorithm DA2（1/7） 6/7, which is the tight one, is proved. Moreover, for P2‖Cmin, Two-lay-Dual-Threshold Algorithms TDA3（ E ）, where ε is a optional parameter, is obtained, and modify the worst-case ratio to 9/11 if ε is equal to 2/11. Up to now, these algorithms are the best algorithms with the least worst-case ratio among linear time algorithms.