Accession Number : ADA113124

Title :   Preemptive Scheduling of Uniform Processors with Memory.

Descriptive Note : Technical rept.,

Corporate Author : MINNESOTA UNIV MINNEAPOLIS DEPT OF COMPUTER SCIENCE

Personal Author(s) : Lai,Ten-Hwang ; Sahni,Sartaj

PDF Url : ADA113124

Report Date : Feb 1982

Pagination or Media Count : 37

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)

Descriptors :   *Data processing, *Memory devices, Scheduling, Linear programming, Formulations, Optimization, Polynomials, Algorithms, Release, Requirements, Capacity(Quantity), Length

Subject Categories : Theoretical Mathematics
      Computer Hardware

Distribution Statement : APPROVED FOR PUBLIC RELEASE