Browse Prior Art Database

Heuristic Algorithms for Scheduling Independent Tasks on Non-Identical Processors

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

Publishing Venue

Software Patent Institute

Related People

Oscar H. Ibarra: AUTHOR [+4]

Abstract

We study the finish time properties of several heuristic algorithms for scheduling n independent tasks on m non-identical processors. In particular, for m=2, we have an nTogn time-bounded algorithm that generates a schedule whose finish time is at most /5 2 1 of the optimal finish time. A simplified scheduling problem involving identical processors and restricted task sets is shown to be NP-complete. However, the LPT algorithm applied to this problem yields schedules which are near optimal for large n.

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

Page 1 of 20

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Heuristic Algorithms for Scheduling Independent Tasks on Non-Identical Processors

by Oscar H. Ibarra and Chul E. Kim

Department of Computer Science Institute of Technology University of Minnesota Minneapolis, Minnesota 55455,_Technical Report 75-7

1975 Cover courtesy of Ruth and Jay Leavitt

Heuristic Algorithms for Scheduling Independent

Tasks on Non-Identical Processors

by

Oscar H. Ibarra and C,hul E. Kim

Department of Computer Science University of Minnesota Minneapolis, Minnesota 55455 This research was supported by the National Science Foundation Grant DCR72-03728-A01 and the University of Minnesota Research Grant 435-0806-8520-02.

Abstract

We study the finish time properties of several heuristic algorithms for scheduling n independent tasks on m non-identical processors. In particular, for m=2, we have an nTogn time-bounded algorithm that generates a schedule whose finish time is at most /5 2 1 of the optimal finish time. A simplified scheduling problem involving identical processors and restricted task sets is shown to be NP-complete. However, the LPT algorithm applied to this problem yields schedules which are near optimal for large n.

Keywords and Phrases: finish time, heuristic algorithms, scheduling independent tasks, non- identical processors, identical processors, time-bounded algorithm, LPT schedules, SPT schedules, NP-complete problem, time complexity.

CR Categories: 4.32, 5.39

1. Introduction

We are given m > 2 processors,

(Equation Omitted)

independent tasks, Jl,...,Jn.l The processors are non--identical in the sense that process time functions ul, ....,um are defined on T so that a task Ji requires p j(Ji) time to process on processor

University of Minnesota Page 1 Dec 31, 1975

Page 2 of 20

Heuristic Algorithms for Scheduling Independent Tasks on Non-Identical Processors

(Equation Omitted)

This model of .a multiprocessor system was introduced in [1,2] where it was shown that an

(Equation Omitted)

time-bounded algorithm exists to obtain a schedule (of T on the m processors) having the least mean flow time. In this paper, we are concerned with the problem of finding a schedule whose finish time is as small as possible (such a schedule will be called optimal). This problem is known to be NP-complete [5,6,7]. Hence, it seems unlikely that a polynomial time-bounded algorithm exists for this problem. In [5], a dynamic programming type algorithm of exponential time complexity was given to find an optimal schedule. It was also shown in [5] that a polynomial time-bounded algorithm exists to obtain a schedule with a finish time arbitrary close to the optimal finish time. However, the complexity of the algorithm was

(Equation Omitted)

where e' is the relative error. We should mention that a special case of our problem u. when

(Equation Omitted)

(i.e., the processors have uniform speeds)was studied in [5,8]. 1 In Section 2, we look at several simple heuristic al...