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

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1984
Accession Number
ADA142392

Entities

People

  • D. J. Zawack
  • Gerald L. Thompson

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Applied Mathematics
  • Coefficients
  • Computations
  • Computer Programming
  • Efficiency
  • Evolutionary Algorithms
  • Heuristic Methods
  • Integer Programming
  • Job Shop Scheduling
  • Linear Programming
  • Mathematical Programming
  • Mathematics
  • Military Research
  • Parametric Programming
  • Scheduling (Production)
  • Simplex Method

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Occupational Health and Safety.
  • Systems Analysis and Design

Technology Areas

  • Space