Browse Prior Art Database

Flow Shop and Job Shop Schedules

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

Publishing Venue

Software Patent Institute

Related People

Teofilo Gonzalez: AUTHOR [+4]

Abstract

It is shown that finding minimum finish time preemptive and nonpreemptive schedules for flow shops and job shops is NP-Complete. Bounds on the performance of various heuristics to generate reasonably good schedules are also obtained. Key Words and Phrases: flow shop, job shop, preemptive and nonpreemptive schedules, mean flow time, finish time, NP-Complete, approximate solution, complexity. CR Categories: 5.23, 5.39 This research was supported in part by NSF grant DCR 74-10081 and University of Minnesota Graduate School Research Grant #468-0100-4909-06.

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

Page 1 of 12

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Flow Shop and Job Shop Schedules

by TE:ofilo Gonz#1,N ~~,~6taj Sahni 75-14

Department of Computer Science Institute of Technology University of Minnesota Minneapolis, Minnesota. 55455

1975 Cover courtesy of Ruth and Jay Leavitt

Flow Shop And Job Shop Schedules

Teofilo Gonzalez and Sartaj Sahni University of Minnesota

Abstract

It is shown that finding minimum finish time preemptive and nonpreemptive schedules for flow shops and job shops is NP-Complete. Bounds on the performance of various heuristics to generate reasonably good schedules are also obtained. Key Words and Phrases: flow shop, job shop, preemptive and nonpreemptive schedules, mean flow time, finish time, NP-Complete, approximate solution, complexity. CR Categories: 5.23, 5.39 This research was supported in part by NSF grant DCR 74-10081 and University of Minnesota Graduate School Research Grant #468-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 processor j is a sequence of tuples

(Equation Omitted)

The ki are job indexes, s~. is the start time of job lGii i and f~ is its finish i i time. Job !Li is processed continuously on processor j from s~ i to fk i The tuples in the schedule are ordered such that

(Equation Omitted)

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

(Equation Omitted)

University of Minnesota Page 1 Dec 31, 1975

Page 2 of 12

Flow Shop and Job Shop Schedules

It is also required that each job i spends exactly tj~i total time on processor j . A schedule for a m-shop is a set of m processor schedules. Qze for each processor in the shop. In addition these m processor schedules must be such that no job is to be processed simultaneously on 2 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-preemptive schedule is one in which individual processor schedules have at most one tuple (i, si,fi) for each job i to be scheduled. For any processor j, this allows for t j" = 0 and also requires that fi - si = tj'i. A schedule in which no restriction is placed on the number of tuples per job per processor is preemptive. Note that all non-preemptive schedules are also preemptive while the reverse is not true. For any schedule, S, we define the finish time, fi(S) of job i to be the.,earliest time at. which all tasks of job i have been completed. The mean flow time, mft(S,), is defined to be the quantity Efi(S). An optimal mean flou...