Browse Prior Art Database

Scheduling for Maximum profit

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

Publishing Venue

Software Patent Institute

Related People

Oscar H. Ibarra: AUTHOR [+4]

Abstract

A subset of a set of tasks J is to be scheduled on a single processor. Associated with each task J is its execution time '.:(J) and profit p(J). The tasks have precedence constraints in that a task cannot be scheduled until all of its predecessors have been scheduled. This paper considers the following problems:

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

Page 1 of 17

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Scheduling for Maximum profit

by Oscar H. Ibarra and Chul E. Kim

Technical Report 75-2 January, 1975

This research was supported by the National Science Foundation Grant DCR72-03728-AOI and the University of Minnesota Graduate School Research Grant 435-0806-8520-02,

Cover courtesy of Ruth and Jay Leavitt Scheduling for Maximum Profit* by Oscar H. Ibarra and Chul E. Kim Department of Computer. Science University of Minnesota Minneapolis, Minnesota 55455

Abstract

A subset of a set of tasks J is to be scheduled on a single processor. Associated with each task J is its execution time '.:(J) and profit p(J). The tasks have precedence constraints in that a task cannot be scheduled until all of its predecessors have been scheduled. This paper considers the following problems:

(1) MAXPROFIT Problem: Given T , the available processor time, find a subset L of -7 such that ~ u(,J) < T and L p(J) is maximal. JET, JeL (2) MINTIMEProblem: Given P , the minimum profit desired, find a subset L of J such that I p(J) ?_ P and I u(J) is minimal. JcL JCL

Keywords and Phrases: Schedule, TLA-XPROFIT problem, MffwTI"E problem, precedence graph, tree, forest, 0/1 knapsack problem, ~'P-complete problem, polynomial time algorithm, approximation algorithm.

CR Categories: 4.19, 5.25, 5.39, 5.42

This research was supported by the National Science Foundation Grant DCR72-03728-A01 and the University of Minnesota Graduate School Research Grant 435-0806-8520-02. 2

1. Introduction

Suppose we are given a set of tasks

(Equation Omitted)

a subset of which is to be scheduled on a single processor. The tasks in J have precedence constraints which can be represented by a directed acyclic graph (simply called precedence graph). Two functions a and p are defined on where u(J) is interpreted as the execution time of
.task J and p(,I) the profit returned if J is processed. A task may not be scheduled until all of its predecessors have been executed. following scheduling problems: (1) MAXPROFIT Problem: Given T , the available processor time, find a subset L of g '-(L will be referred to as a schedule) such that

University of Minnesota Page 1 Dec 31, 1975

Page 2 of 17

Scheduling for Maximum profit

(Equation Omitted)

is maximal . JeL In this paper, we look at the JeL (2) MINTIME Problem: Given P , the minimum profit desired, find a schedule L of J such that

(Equation Omitted)

is minimal. There are several obvious practical interpretations of the MAXPROFIT and MINTIME problems. The tasks might be interpreted as projects, t.:(J) as the time (or cost) required to complete project J , and p(J) as the profit returned.(or value) of completing project J . The precedence constraints would mean that certain projects cannot be started before the completion of other projects. The MAXPROFI7.' problem when the tasks are independent reduces to the well known 0/1 knapsack problem studied in [2,3,4,6,7,.9 ]. Another interpretat...