Focused simulated annealing search: An application to job shop scheduling |
| |
Authors: | Norman M Sadeh Yoichiro Nakakuki |
| |
Institution: | (1) The Robotics Institute, Carnegie Mellon University, 15213 Pittsburgh, PA, USA;(2) NEC C & C Research Laboratories, 4-1-1 Miyazaki, Miyamae-ku, 216 Kawasaki, Japan |
| |
Abstract: | This paper presents a simulated annealing search procedure developed to solve job shop scheduling problems simultaneously
subject to tardiness and inventory costs. The procedure is shown to significantly increase schedule quality compared to multiple
combinations of dispatch rules and release policies, though at the expense of intense computational efforts. A meta-heuristic
procedure is developed that aims at increasing the efficiency of simulated annealing by dynamically inflating the costs associated
with major inefficiencies in the current solution. Three different variations of this procedure are considered. One of these
variations is shown to yield significant reductions in computation time, especially on problems where search is more likely
to get trapped in local minima. We analyze why this variation of the meta-heuristic is more effective than the others. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|