Browse Prior Art Database

On Line Scheduling of a Uniform Processor System With Release Times

IP.com Disclosure Number: IPCOM000128544D
Original Publication Date: 1977-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 19 page(s) / 42K

Publishing Venue

Software Patent Institute

Related People

Sartaj Sahni: AUTHOR [+4]

Abstract

[Equation ommitted] on line algorithm to preemptively schedule n independent tasks on m uniform processors is presented. It is assumed that there is a release time associated with each task. No task may be started before its release time. All tasks must be completed by a common due time (if possible). Our algorithm generates schedules having 0(nm) preemptions in the worst case.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 12% of the total text.

Page 1 of 19

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

On Line Scheduling of a Uniform Processor System With Release Times

by

Sartaj Sahni and Yookua Cho

Computer Science Department

114 Lind Hall Institute of Technology University of Minnesota Minneapolis, Minnesota 55455 Technical Report 77-17 September 1977 Cover design courtesy Ruth and Jay Leavitt On Line Scheduling of a Uniform Processor System With Release Times

Sartaj Sahni and Yoakun Cho University of Minnesota

Abstract:

(Equation Omitted)

on line algorithm to preemptively schedule n independent tasks on m uniform processors is presented. It is assumed that there is a release time associated with each task. No task may be started before its release time. All tasks must be completed by a common due time (if possible). Our algorithm generates schedules having 0(nm) preemptions in the worst case.

Key words and Phrases: independent tasks, uniform processors, preemptive schedule, release time, common due time, complexity. This research was supported in part by NSF grant MCS 76- 21024.

1. Introduction

A uniform processor system

(Equation Omitted)

is a set of m processors (machines). Associated with each processor,

(Equation Omitted)

is a speed

(Equation Omitted)

. Processor

(Equation Omitted)

can perform

University of Minnesota Page 1 Dec 31, 1977

Page 2 of 19

On Line Scheduling of a Uniform Processor System With Release Times

(Equation Omitted)

units of processing in one unit of time. When

(Equation Omitted)

is said to be a system of identical processors. Let T be a set of n independent tasks. Let

(Equation Omitted)

and

(Equation Omitted)

respectively be the processing requirement, release time and due time of task

(Equation Omitted)

A DD schedule for T is an assignment of tasks to processors such that (I) no processor is required to process more than one task at any time, (ii) no task is simultaneously processed on more than one processor, (iii) the processing of no task begins beforoe its release time and (iv) all tasks are completed by their due times. Note that not all task sets have DD schedule on a given processor system.

An on line algorithm to find a DD schedule (if one exists) is an algorithm which, for every distinct release time

(Equation Omitted)

, determines the schedule from 0 to

(Equation Omitted)

without knowledge of the jobs released on or after

(Equation Omitted)

.

Many researchers have studied the problem of obtaining DD schedules (when they exist). Kan
[6] shows that the problem of determining the existence of nonpreemptive DD schedules is Np Complete. McNaughton's algorithm [8] can be used to obtain preemptive DD schedules for systems of identical processors when the task set T has only one distinct release time and one distinct due time. Gonzalez and Sahni [3] present an

(Equation Omitted)

algorithm that works for uniform processor systems when T has only one distinct release time and one distinct due time. For the case when all tasks have the sa...