Abstract
This paper deals with the worst-case performance of local search algorithms for makespan minimization on parallel machines. We analyze the quality of the local optima obtained by iterative improvements over the jump, the swap, and the newly defined push neighborhood.
Supported by the project “High performance methods for mathematical optimization” of the Netherlands Organization for Scientific Research (NWO)
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
P. Brucker, J. Hurink, and F. Werner. Improving local search heuristics for some scheduling problems I. Discrete Applied Mathematics, 65:97–122, 1996.
P. Brucker, J. Hurink, and F. Werner. Improving local search heuristics for some scheduling problems II. Discrete Applied Mathematics, 72:47–69, 1997.
Y. Cho and S. Sahni. Bounds for list schedules on uniform processors. SIAM Journal on Computing, 9:511–522, 1980.
U. Feige, M. Karpinski, and M. Langberg. Improved approximation of MAX-CUT on graphs of bounded degree. Technical Report 85215 CS, Institut för Informatik, Universität Bonn, 2000.
M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco, 1979.
M.X. Goemans and D.P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM, 42:1115–1145, 1995.
R.L. Graham, E.L. Lawler, J.K. Lenstra, and A.H.G. Rinnooy Kan. Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics, 5:287–326, 1979.
D.S. Hochbaum and D.B. Shmoys. Using dual approximation algorithms for scheduling problems: theoretical and practical results. Journal of the ACM, 34:144–162, 1987.
D.S. Hochbaum and D.B. Shmoys. A polynomial approximation scheme for machine scheduling on uniform processors: using the dual approximation approach. SIAM Journal on Computing, 17:539–551, 1988.
B.W. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. The Bell System Technical Journal, 49:291–307, 1970.
M.R. Korupolu, C.G. Plaxton, and R. Rajaraman. Analysis of a local search heuristic for facility location problems. Technical Report 98-30, DIMACS, 1998.
J.K. Lenstra, D.B. Shmoys, and É. Tardos. Approximation algorithms for scheduling unrelated parallel machines. Mathematical Programming, 46:259–271, 1990.
S. Lin and B.W. Kernighan. An effective heuristic for the traveling salesman problem. Operations Research, 21:489–516, 1973.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Schuurman, P., Vredeveld, T. (2001). Performance Guarantees of Local Search for Multiprocessor Scheduling. In: Aardal, K., Gerards, B. (eds) Integer Programming and Combinatorial Optimization. IPCO 2001. Lecture Notes in Computer Science, vol 2081. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45535-3_29
Download citation
DOI: https://doi.org/10.1007/3-540-45535-3_29
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42225-9
Online ISBN: 978-3-540-45535-6
eBook Packages: Springer Book Archive