Performance Guarantees of Local Search for Multiprocessor Scheduling
AbstractIncreasing interest has recently been shown in analyzing the worst-case behavior of local search algorithms. In particular, the quality of local optima and the time needed to find the local optima by the simplest form of local search has been studied. This paper deals with worst-case performance of local search algorithms for makespan minimization on parallel machines. We analyze the quality of the local optima obtained by iterative improvement over the jump, swap, multi-exchange, and the newly defined push neighborhoods. Finally, for the jump neighborhood we provide bounds on the number of local search steps required to find a local optimum.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by Maastricht : METEOR, Maastricht Research School of Economics of Technology and Organization in its series Research Memoranda with number 054.
Date of creation: 2005
Date of revision:
Contact details of provider:
Web page: http://www.maastrichtuniversity.nl/web/UMPublications.htm
operations research and management science;
This paper has been announced in the following NEP Reports:
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Vredeveld, Tjark & Lenstra, Jan Karel, 2003. "On local search for the generalized graph coloring problem," Open Access publications from Maastricht University urn:nbn:nl:ui:27-17096, Maastricht University.
- Hurkens, C.A.J. & Vredeveld, T., 2003. "Local search for multiprocessor scheduling: how many moves doet it take to a local optimum?," Open Access publications from Maastricht University urn:nbn:nl:ui:27-17095, Maastricht University.
- Peters, Hans & Vermeulen, Dries, 2006. "WPO, COV and IIA bargaining solutions," Research Memoranda 021, Maastricht : METEOR, Maastricht Research School of Economics of Technology and Organization.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Charles Bollen).
If references are entirely missing, you can add them using this form.