Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Bounds for LPT Schedules on Uniform Processors

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

Publishing Venue

Software Patent Institute

Related People

Teofilo Gonzalez: AUTHOR [+5]

Abstract

We study the performance of LPT (largest processing time) schedules with respect to optimal schedules in a non-preemptive multiprocessor environment. The processors are assumed to have different speeds and the tasks being scheduled are independent. Keywords and Phrases: LPT schedules, uniform processors, non-preemptive scheduling, independent tasks. CR Categories: 4.32, 5.39 This research was supported in part by NSF grants DCR72-03728-A01 and DCR 74-10081.

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

Page 1 of 19

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Bounds for LPT Schedules on Uniform Processors*

by

Teofilo Gonzalez,, Oscar H. Ibarra and Sartaj Sahni

Computer, Information, and Control Sciences Department

114 Main Engineering Institute of Technology University of Minnesota Minneapolis, Minnesota 55455

Technical Report 75-1 January 75 DEPARD N or C041PutfR SCIfN

,*This research was supported in part by NSF grants DCR72-03728-A01 and DCR 74-10081.

Cover design courtesy of Ruth and Jay Leavitt

Bounds for LPT Schedules on Uniform Processors by Teofilo Gonzalez, Oscar H. Ibarra and Sartaj Sahni University of Minnesota

Abstract

We study the performance of LPT (largest processing time) schedules with respect to optimal schedules in a non-preemptive multiprocessor environment. The processors are assumed to have different speeds and the tasks being scheduled are independent.

Keywords and Phrases: LPT schedules, uniform processors, non-preemptive scheduling, independent tasks.

CR Categories: 4.32, 5.39 This research was supported in part by NSF grants DCR72-03728- A01 and DCR 74-10081.

1. Introduction

A uniform processor system [4] is one in which the processors P1,...,Pm have relative speeds sl,...,sm respectively. It is assumed that the speeds have been normalized such that

(Equation Omitted)

. The problem of scheduling n independent tasks (Jl,...,Jn) with execution times (tl,...,tn) on m uniform processors to obtain a schedule with the optimal (least) finish time is known to be NP- Complete [1,4]. Hence, it appears unlikely that there is any polynomial time bounded algorithm to generate such schedules. For preemptive scheduling, however, optimal finish time algorithms can be obtained in polynomial time [6,7]. Horowitz and Sahni [4] showed that for any m , polynomial time algorithms exist to obtain schedules with a finish time arbitrarily, close to the optimal finish time. The complexity of these algorithms was, however, -exponential in m. The

University of Minnesota Page 1 Dec 31, 1975

Page 2 of 19

Bounds for LPT Schedules on Uniform Processors

purpose of this paper is to study the finish time properties of LPT schedules with.respect to the optimal finish time. An LPT (Largest-processing-time) schedule [2, p.100] is a schedule obtained as the result of an algorithm which, whenever a processor becomes free, assigns the task whose execution time is the largest of those tasks not yet assigned. We assume that ties are broken by assigning the task to the processor with least index. Graham [3] studied LPT schedules for the special case of identical processors, i.e.,

(Equation Omitted)

If f is the finish time of the LPT schedule and f* the optimal,.finish time, then Graham's result is that f/f* < 3 - 3m and tha-r=his bound is the best.possible bound. In section 2 we extend his work to the general case of uniform processors. While the bound we obtain is best possible for m=2 , it appears that it is not so for m > 2 . In view of...