Linear time algorithms for parallel machine scheduling

作者：Tan, Zhi Yi^*; He, Yong

来源：Acta Mathematica Sinica-English Series, 2007, 23(1): 137-146.

DOI：10.1007/s10114-005-0838-4

• scheduling
• design and analysis of algorithm
• worst-case ratio
• computer-aided proof

This paper addresses linear time algorithms for parallel machine scheduling problems. We introduce a kind of threshold algorithms and discuss their main features. Three linear time threshold algorithm classes DT, PT and DTm are studied thoroughly. For all classes, we study their best possible algorithms among each class. We also present their application to several scheduling problems. The new algorithms are better than classical algorithms in time complexity and/or worst-case ratio. Computer-aided proof technique is used in the proof of main results, which greatly simplifies the proof and decreases case by case analysis.

• 出版日期2007-1
• 单位浙江大学