Performance Guarantees of Local Search for Multiprocessor Scheduling

Petra Schuurman and Tjark Vredeveld
Additional contact information
Tjark Vredeveld: METEOR

No 54, Research Memoranda from Maastricht : METEOR, Maastricht Research School of Economics of Technology and Organization

Abstract: Increasing 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.

Keywords: operations research and management science (search for similar items in EconPapers)
New Economics Papers: this item is included in nep-cmp
Date: 2005
View list of references

Downloads: (external link)
http://edocs.ub.unimaas.nl/loader/file.asp?id=1132 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: http://EconPapers.repec.org/RePEc:dgr:umamet:2005054

Access Statistics for this paper

More papers in Research Memoranda from Maastricht : METEOR, Maastricht Research School of Economics of Technology and Organization
Series data maintained by Willy Villevoye ().