Approaches to the N-Job M-Machine Scheduling Problem.

Abstract

The thesis presents two methods of solving the n-job m-machine job shop scheduling problem. The criterion for optimality is the minimization of the total time to process all jobs on all machines. The technological ordering of machines for each job is fixed, known, and nonrandom. The first method presented, a graphical method, indicates a lower bound and an upper bound on the optimal time to process all jobs on all machines. The second method is a branch and bound algorithm. In principle an optimal solution can always be determined by this method. Only limited computational experience is presented for the algorithm but some methods for efficient computation are suggested. (Author)

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1971
Accession Number
AD0721544

Entities

People

  • Norman John Shackelton Jr

Organizations

  • Naval Postgraduate School

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Computational Complexity
  • Computations
  • Engineering
  • Job Shop Scheduling
  • Mathematical Analysis
  • Mathematics
  • Scheduling (Production)

Readers

  • Graph Algorithms and Convex Optimization.
  • Manufacturing Engineering.
  • Regression Analysis.