Abstract
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 method is used in the proof of main results, which greatly simplifies the proof and decreases case by case analysis.
Supported by NSFC (10301028, 10271110, 60021201) and TRAPOYT of China.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Burkard, R.E., He, Y., Kellerer, H.: A linear compound algorithm for uniform machine scheduling. Computing 61, 1–9 (1998)
Coffman, E.G., Garey, M.R., Johnson, D.S.: An application of bin-packing to multiprocessor scheduling. SIAM Journal on Computing 7, 1–17 (1978)
Graham, R.L.: Bounds for certain multiprocessor anomalies. Bell Systems Technical Journal 45, 1563–1581 (1966)
Graham, R.L.: Bounds on multiprocessing timing anomalies. SIAM Journal on Applied Mathematics 17, 416–429 (1969)
He, Y., Kellerer, H., Kotov, V.: Linear compound algorithms for the partitioning problem. Naval Research Logistics 47, 593–601 (2000)
He, Y., Yang, Q.F., Tan, Z.Y., Yao, E.Y.: Algorithms for semi on-line multiprocessor scheduling. Journal of Zhejiang University Science 3, 60–64 (2002)
He, Y., Zhang, G.C.: Semi on-line scheduling on two identical machines. Computing 62, 179–187 (1999)
Hochbaum, D.S., Shmoys, E.L.: Using dual approximation algorithms for scheduling problems: Theoretical and practical results. Journal of the ACM 34, 144–162 (1987)
Hochbaum, D.S., Shmoys, E.L.: A polynomial approximation scheme for scheduling on uniform processors: Using the dual approximation approach. SIAM J. on Computing 17, 539–551 (1988)
Kellerer, H., Kotov, V., Speranza, M.G., Tuza, Z.: Semi on-line algorithms for the partition problem. Operations Research Letters 21, 235–242 (1997)
Tan, Z.Y., He, Y.: Semi-on-line problems on two identical machines with combined partial information. Operations Research Letters 30, 408–414 (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Tan, Z., He, Y. (2005). Linear Time Algorithms for Parallel Machine Scheduling. In: Megiddo, N., Xu, Y., Zhu, B. (eds) Algorithmic Applications in Management. AAIM 2005. Lecture Notes in Computer Science, vol 3521. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11496199_20
Download citation
DOI: https://doi.org/10.1007/11496199_20
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-26224-4
Online ISBN: 978-3-540-32440-9
eBook Packages: Computer ScienceComputer Science (R0)