Browse Prior Art Database

Scheduling Independent Tasks With Due Times on A Uniform Processor System

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

Publishing Venue

Software Patent Institute

Related People

Sartaj Sahni: AUTHOR [+4]

Abstract

An algorithm to preemptively schedule n tasks on m uniform processors is presented. It is assumed that each task is available at time 0. Associated with each task is a due time by which it is to be completed. Our algorithm schedules all tasks to complete by their due times whenever this is possible. The asymptotic time complexity of our algorithm is 0(n logn+mn). It generates 0(mn) preemptions in the worst case. An example of n tasks requiring 0(mn) preemptions is also presented. Our algorithm can also be used when all tasks have the same due time but have different release times.

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

Page 1 of 23

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Scheduling Independent Tasks With Due Times on A Uniform Processor System

by

Sartaj Sahni and Yookun Cho

040.0307

Computer Science Department

114 Lind Hall Institute of Technology. University of Minnesota Minneapolis, Minnesota 55455

Technical Report 77-7 May 1977

cover design courtesy of Ruth and Jay Leavitt Scheduling Independent Tasks With Due Times On A Uniform Processor 9ystem

Sartaj Sahni and Yookun Cho University of Minnesota

Abstract:

An algorithm to preemptively schedule n tasks on m uniform processors is presented. It is assumed that each task is available at time 0. Associated with each task is a due time by which it is to be completed. Our algorithm schedules all tasks to complete by their due times whenever this is possible. The asymptotic time complexity of our algorithm is 0(n logn+mn). It generates 0(mn) preemptions in the worst case. An example of n tasks requiring 0(mn) preemptions is also presented. Our algorithm can also be used when all tasks have the same due time but have different release times.

Keywords_and Phrases: independent tasks, preemptive schedule, due time, uniform processors, complexity.

*This research was supported in part by NSF grant MCS 76-21024.

1. Introduction

Let

(Equation Omitted)

be a set of m processors. Let

(Equation Omitted)

respectively be the task times, release times and due times of n independent tasks. Associated with each processor P i is a speed sis s i >O. Processor P i has an effective processing

University of Minnesota Page 1 Dec 31, 1977

Page 2 of 23

Scheduling Independent Tasks With Due Times on A Uniform Processor System

capability of s units of processing per time unit. Task j can be processed on P in t /S units. The processors

(Equation Omitted)

are said to be uniform as they operate at a constant speed independent of time. When

(Equation Omitted)

, the processors are said to be identical. In this paper we shall be concerned only with preemptive schedules. A schedule S for the n tasks is a DD-schedule iff the processing of each task commences no earlier than its release time and completes no later than its due time.

For the case of identical processors, Horn [3] presents an 0(n 3 ) algo-rithm to obtain a DD- schedule for any set of n independent tasks for which such a schedule exists. Sahni [5] presents a fast algorithm that obtains DD-schedules (whenever they exist) when either all tasks have the same release time or all tasks have the same due time. For the case of two uniform processors, Bruno and Gonzalez [11, present an O(n 3 algorithm that obtains a DD-Schedule (whenever one exists). Gonzalez and Sahni [2] have developed an 0(n +mlogm) algorithm that can be used when all tasks have the same release time and also the same due time.

In this paper we study the case when all tasks have the same release time. Different tasks may however have different due times. Our algorithm to construct a DD-Schedule for...