Accession Number : ADA289188

Title :   Focused Simulated Annealing Search: An Application to Job-Shop Scheduling.

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA ROBOTICS INST

Personal Author(s) : Sadeh, Norman M. ; Nakakuki, Yoichiro

PDF Url : ADA289188

Report Date : SEP 1994

Pagination or Media Count : 36

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.

Descriptors :   *ANNEALING, *STOCHASTIC PROCESSES, *TIMELINESS, *JOB SHOP SCHEDULING, SIMULATION, COMPUTATIONS, POLICIES, COST EFFECTIVENESS, PROBLEM SOLVING, TIME, SOLUTIONS(GENERAL), QUALITY, SEARCHING, INVENTORY.

Subject Categories : Statistics and Probability
      Operations Research
      Administration and Management

Distribution Statement : APPROVED FOR PUBLIC RELEASE