Myopic Heuristics for the Single Machine Weighted Tardiness Problem.

Abstract

It is well known that the single machine weighted tardiness problem is NP-complete. Hence, it is unlikely that there exist polynomially bounded algorithms to solve this problem. Further, the problem is of great practical significance. We develop myopic heuristics for this problem; these heuristics have been tested against competing heuristics, against a tight lower bound, and where practical, against the optimum, with uniformly good results. Also, these heuristics can be used as dispatching rules in practical situations. In our efforts to seek optimum solutions we develop a hybrid dynamic programming procedure (a modified version of Baker's procedure) which provides lower and upper bounds when it becomes impractical to find the optimum solution. Further, stopping rules are developed for identifying optimal first job/jobs. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 28, 1982
Accession Number
ADA134880

Entities

People

  • R. M. V. Rachamadugu
  • T. E. Morton

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Autonomy

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • Coefficients
  • Computer Programming
  • Computing-Related Activities
  • Dynamic Programming
  • Military Research
  • Normal Distribution
  • Pilot Studies
  • Robotics
  • Scientific Research
  • Security
  • Sequences
  • Software Development
  • Two Dimensional
  • Universities

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Operations Research