Accession Number:

ADA142392

Title:

A Problem Expanding Parametric Programming Method for Solving the Job Shop Scheduling Problem.

Descriptive Note:

Technical rept.,

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

Personal Author(s):

Report Date:

1984-04-01

Pagination or Media Count:

24.0

Abstract:

A new zero one integer programming model for the job shop scheduling problem with minimum makespan criterion is presented. The algorithm consists of two parts a a branch and bound parametric linear programming code for solving the job shop problem with fixed completion time b a problem expanding algorithm for finding the optimal completion time. Computational experience for problems having up to 36 operations is presented. The largest problem solved was limited by memory space, not computation time. Efforts are under way to improve the efficiency of the algorithm and to reduce its memory requirements.

Subject Categories:

  • Administration and Management

Distribution Statement:

APPROVED FOR PUBLIC RELEASE