Template-type: ReDif-Paper 1.0
Author-Name: Schuurman Petra
Author-Name: Vredeveld Tjark
Author-workplace-name: METEOR
Title: Performance Guarantees of Local Search for Multiprocessor Scheduling
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; 
Series: Research Memoranda
Creation-Date: 2005
Number: 054
File-URL: http://digitalarchive.maastrichtuniversity.nl/fedora/objects/guid:6c320e7c-e9f9-4b38-83a5-7ac0061c2785/datastreams/ASSET1/content
File-Format: application/pdf
File-Size: 265172
Handle: RePEc:unm:umamet:2005054