Browse Prior Art Database

Algorithms for Scheduling Independent Tasks

IP.com Disclosure Number: IPCOM000128514D
Original Publication Date: 1974-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 18 page(s) / 46K

Publishing Venue

Software Patent Institute

Related People

Sartaj K. Sahni: AUTHOR [+3]

Abstract

We study the following job sequencing problems: i) single processor job sequencing with deadlines ii) job sequencing on nr-identical processors to minimize finish time and related problems iii) job sequencing on 2-identical processors to minimize weighted mean flow time. Dynamic programming type algorithms are presented to obtain optimal solutions to these problems. We present a general technique to obtain approximate solutions for optimization problems solvable in this way. This technique is then applied to the problems above to obtain polynomial time algorithms that generate "good" approximate solutions. * ywords & phrases: job scheduling, mean flow time, weighted mean flow time, finish time, sequencing with deadlines, approximate solution, polynomial time complexity. *This research was supported by the University of Minnesota under Research Grant # 4$1-0906--4125-02.

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

Page 1 of 18

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Algorithms for Scheduling Independent Tasks

by Sartaj K. Sahni

Computer, Information, and Control Sciences Department Institute of Technology University of Minnesota Minneapolis, Minnesota _ 5455 Technical Report 74-16 July, 1974 Cover design courtesy of Ruth and Jay Leavitt Algorithms for Scheduling Independent Tasks*

by Sartaj K. Sahni Department of Computer Science University of Minnesota

Abstract

We study the following job sequencing problems: i) single processor job sequencing with deadlines ii) job sequencing on nr-identical processors to minimize finish time and related problems iii) job sequencing on 2-identical processors to minimize weighted mean flow time. Dynamic programming type algorithms are presented to obtain optimal solutions to these problems. We present a general technique to obtain approximate solutions for optimization problems solvable in this way. This technique is then applied to the problems above to obtain polynomial time algorithms that generate "good" approximate solutions.

* ywords & phrases: job scheduling, mean flow time, weighted mean flow time, finish time, sequencing with deadlines, approximate solution, polynomial time complexity. *This research was supported by the University of Minnesota under Research Grant # 4$1-0906--4125-02.

I. Introduction

Several scheduling problems have been shown to be NP-Complete -(see ,L11, (Z j, [3j, [9J, [111-and I13J). Informally a problem PI is sand to be plete if it is the case,that Pl can be solved in polynomial time iff the class of languages, NP, accepted by polynomial time bounded mondeterminiatic Turing machines is the same as that accepted by polynomial time bounded deterministic Turing machines (P).. The class of NP-Complete problems 3s an equivalence class which .includes such classical problems as the traveliiag salesman and knapsack problems. Job scheduling problems such as (:L) ,fob seq uencing with deadlines, (ii) Job seluencing.on m_,w 2 .processors to minimize fin4sh- time, (iii) Finding from among the class of schedules minimizing mean flow time the schedule with the smal2est finish time and (iv) minimizing the weighted mean flow time for m.>, 2, processors are known to be NP-Complete (see [9) -[1], [2) and [I] respectively). ,This, then,, means that obtaining an.algorithm of polynomial complexity to solve any of. these problems is as hard.as finding a polynomial algorithm for the traveling salesman or the max clique or any of the other NP-Complete problems(if indeed such an algorithm exists). Fisher ([4J and [5J) presents a solution iaetho:I for 'r.ize above problem based on LagrangidA mvltigliers. We present a dynamic programming type approach to obtain optimal, acrlutions..Tbe a7 gorithms:An Why wor'st ease; require an exponential arriounic- of time. As a result of the relationship between the various-IR-Complete problems and the implications of,this relationship to the complexity...