Local search is widely used for optimization problems such as scheduling problems to improve the quality of solutions. In some cases, however, neighborhood operations at an early stage prevent a solution from being improved in a later stage. In this report, we present a heuristic method that executes neighborhood operations considering the later stages by using a function that estimates the objective value at the end of the search. Using this method, we can avoid neighborhood operations that make the objective value a lot better at that point, but which have adverse effects on the later stages. As a result, we can get better schedules. Experimental results show that our method makes better schedules for about half of the instances in a real-world scheduling problem.
By: Takayuki Yoshizumi; Toshiyuki Hama
Published in: RT0718 in 2007
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .