AN EFFICIENT ALGORITHM FOR SCHEDULING INDEPENDENT TASKS.

Abstract

An algorithm is developed for sequencing an independent task set, characterized by deterministic processing times and due dates, on a single processor so that total tardiness is minimized. The tasks are assumed to have a loss function of the form max (O, ((c sub i) - (d sub i))) where c sub i is the calender completion time of task i and d sub i is its due date. The method is in general suboptimal, but conditions are given for which an optimal schedule is always obtained. In addition, a technique is presented for improving suboptimal solutions by interchanging certain non-adjacent pairs of tasks. Finally, this scheduling technique is applied to the multiple processor case. (Author)

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1970
Accession Number
AD0711543

Entities

People

  • J. D. Irwin
  • L. J. Wilkerson

Organizations

  • Auburn University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Engineering
  • Information Processing
  • Mathematics
  • Scheduling (Production)

Readers

  • Operations Research
  • Parallel and Distributed Computing.

Technology Areas

  • AI & ML
  • AI & ML - Bayesian Inference
  • AI & ML - Machine Learning Algorithms