A Note on the Value of Interchange Methods in Scheduling Problems.

Abstract

Consider a multi-machine scheduling problem in which the jobs (of unit duration) may have non-zero release times, monotonic increasing deferral costs, and general precedence relationships between them. In general, efficient optimal solution techniques do not exist for problems of this type, and, typically realistically sized problems must be solved using heuristics. An efficient mehtod for implementing job interchange techniques is presented for improving heuristically derived schedules. The method is tested on over 200 randomly generated (NP-complete) problems. 98.5% of the problems are solved optimally. Finally, it is noted that the quality of the solution technique does not appear to be limited by computation costs, but rather by the (one time) developmental cost of the interchange computer code.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1978
Accession Number
ADA059719

Entities

People

  • C. Stafford Loveland
  • Thom J. Hodgson

Organizations

  • University of Florida

Tags

DTIC Thesaurus Topics

  • Computations
  • Computer Programming
  • Computers
  • Engineering
  • Errors
  • Florida
  • Industrial Engineering
  • Military Research
  • North Carolina
  • Operations Research
  • Parallel Processors
  • Scheduling (Production)
  • Security
  • Standards
  • Systems Engineering
  • Universities

Readers

  • Computational Modeling and Simulation
  • Graph Algorithms and Convex Optimization.
  • Instructional Design and Training Evaluation.