Preemptive Scheduling of Uniform Processors with Memory.

Abstract

We consider the problem of preemptively scheduling n jobs on a system of m uniform processors. Each job has a release time, a due time, and a memory requirement associated with it. Each processor has a speed and a memory capacity associated with it. Linear programming formulations are obtained for the following optimization criteria: (1) minimize the schedule length and (2) minimize the maximum lateness. We also consider three special cases with the former optimization criteria. For each of these cases, low order polynomial time algorithms are obtained. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 01, 1982
Accession Number
ADA113124

Entities

People

  • Sartaj Sahni
  • Ten-hwang Lai

Organizations

  • University of Minnesota

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Algorithms
  • Computer Programming
  • Computer Science
  • Engineering
  • Heuristic Methods
  • Inequalities
  • Interdisciplinary Science
  • Intervals
  • Linear Programming
  • Linear Systems
  • Minnesota
  • Polynomials
  • Scheduling (Production)
  • Simplex Method
  • Systems Science
  • Universities

Readers

  • Operations Research
  • Parallel and Distributed Computing.