Accession Number:

ADA059719

Title:

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

Descriptive Note:

Research rept.,

Corporate Author:

FLORIDA UNIV GAINESVILLE DEPT OF INDUSTRIAL AND SYSTEMS ENGINEERING

Report Date:

1978-09-01

Pagination or Media Count:

23.0

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.

Subject Categories:

  • Administration and Management
  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE