A Hybrid Algorithm for the One Machine Sequencing Problem to Minimize Total Tardiness.

Abstract

In a recent paper, Hamilton Emmons has established theorems relating to the order in which pairs of jobs are to be processed in an optimal schedule to minimize the total tardiness of performing jobs on one machine. Using these theorems, the algorithm of this paper determines the precedence relationships among pairs of jobs (whenever possible) and eliminates the first and the last few jobs in an optimal sequence. The remaining jobs are then ordered by incorporating the precedence relationships in a dynamic programming framework. Propositions are proved which considerably reduce the total computation involved in the dynamic programming phase. Computational results indicate that the solution time goes up only linearly with the size (n) of the problem. The median solution time for solving 50 job problems was 0.36 seconds on UNIVAC 1108 computer. (Author)

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1970
Accession Number
AD0722822

Entities

People

  • V. Srinivasan

Organizations

  • Carnegie Mellon University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computational Complexity
  • Computations
  • Computer Programming
  • Computers
  • Dynamic Programming
  • Evolutionary Algorithms
  • Heuristic Methods
  • Mathematical Analysis
  • Mathematics
  • Sequences

Readers

  • Computer Science/Computer Engineering/Data Science/Digital Signal Processing.
  • Graph Algorithms and Convex Optimization.
  • Organizational Psychology.