Browse Prior Art Database

Open Shop Scheduling to Minimize Finish Time

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

Publishing Venue

Software Patent Institute

Related People

Teofilo Gonzalez: AUTHOR [+4]

Abstract

A linear time algorithm to obtain a minimum finish time schedule for the two processor open shop together with a polynomial tame algorithm to obtain a minimum finish time preemptive schedule for open shops with more than two processors are obtained. It is also shown that the problem of obtaining minimum finish time nonpreemptive schedules when the open shop has more than two processors is NP-Complete.

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

Page 1 of 17

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Open Shop Scheduling to Minimize Finish Time

Teofilo Gonzalez and Sartaj Sahni

Computer, Information, and Control Sciences Department Institute of Technology University of Minnesota Minneapolis, Minnesota

55455 75-11 This research was supported in part by NSF grant DCR 74-10081 and University of Minnesota Graduate School Research Grant #468-0100-4909-06.

Cover courtesy Ruth and ,Tay Leavitt.

Open Shop Scheduling to Minimize Finish Time

Teofilo Gonzalez and Sartaj Sahn,i University of Minnesota

Abstract

A linear time algorithm to obtain a minimum finish time schedule for the two processor open shop together with a polynomial tame algorithm to obtain a minimum finish time preemptive schedule for open shops with more than two processors are obtained. It is also shown that the problem of obtaining minimum finish time nonpreemptive schedules when the open shop has more than two processors is NP-Complete.

Key Words and Phrases: open shop, preemptive and nonpreemptive schedules, finish time, polynomial complexity, NP-Complete.

CR Categories: 4.32, 5.39 This research was supported in part by NSF grant DCR 74-10081 and University of Minnesota Graduate School Research Grant 4468-0100-4909-06.

1. Introduction

A shop consists of m > 1 processors (or machines). Each of these processors performs a different task. There are n > 1 jobs. Each job i has m tasks. The processing time for task j of job i is tj~i. Task j of job i is to be processed on processor

(Equation Omitted)

A schedule for a processor j is a sequence of tuples

(Equation Omitted)

The are job indexes, s~. is the start time of job Qi and fR is its finish i i time. Job 2i is processed continuously on processor j from s Q. to i ft,. The tuples in the schedule are ordered such that

(Equation Omitted)

University of Minnesota Page 1 Dec 31, 1975

Page 2 of 17

Open Shop Scheduling to Minimize Finish Time

There may be more than one tuple per job and it is assumed that

(Equation Omitted)

It is also required that..each.job, i spends-exactly t,., total time on processor j . A schedule for a m-shop is a set of m J sl processor schedules. One for each processor in the shop. In addition, these m processor schedules must be such that no job is to be processed simultan- eously on two or more processors. A shop schedule will be abbreviated to schedule in future references. The finish time of a schedule is the latest completion time of the individual processor schedules and represents the time at which all tasks have been completed. An optimal finish time (OFT) schedule is one which has the least finish time amongst all schedules. Anon -prees3t.iye schedule is one in which the individual processor schedules has at most one tuple (i, si,fi) for each job i to be scheduled. For any processor, j, this allows for ti1i = 0 and also requires that

(Equation Omitted)

. A schedule in which no restriction is placed on the number of tuples per job p...