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

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1994
Accession Number
ADA289188

Entities

People

  • Norman M. Sadeh
  • Yoichiro Nakakuki

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Advanced Electronics
  • Autonomy

DTIC Thesaurus Topics

  • Algorithms
  • Annealing
  • Computations
  • Cost Reductions
  • Costs
  • Decomposition
  • Degradation
  • Genetic Algorithms
  • High Temperature
  • Inventory
  • Job Shop Scheduling
  • Linear Programming
  • Low Temperature
  • Materials
  • Optimization
  • Probability
  • Scheduling (Production)

Readers

  • Operations Research