Browse Prior Art Database

Preemptive Scheduling of Independent Jobs With Release and Due Times on Open, Flaw and Job Shops

IP.com Disclosure Number: IPCOM000128550D
Original Publication Date: 1978-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 22 page(s) / 50K

Publishing Venue

Software Patent Institute

Related People

Yookun Cho: AUTHOR [+4]

Abstract

We study the problem of obtaining feasible preemptive schedules for independent jobs. It is assumed that each job has associated with it a release and due time. No job can begin before its release time. All jobs must be completed by their respective due tames. It is shown that determining the existence of feasible preemptive schedules for a two processor flow or job shop is NP-Hard even when all jobs have the same due time and there are only two distinct release times. The two processor case with many release times and one due time is NP-Hard in the strong sense. A linear programming formulation for the open shop problem is obtained. Also, fast polynomial time algorithms are obtained for open shops under certain restrictions. Keywords and Phrases: preemptive schedule, independent jobs, open shop, flow shop, job shop, release time, due time, NP-Hard, complexity. This research was.supported in part by NSF grant MCS 76-21024.

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

Page 1 of 22

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Preemptive Scheduling of Independent Jobs With Release and Due Times on Open, Flaw and Job Shops.

by Yookun Cho and Sartaj Sahni Computer Science Department

114 Lind Hall Institute of Technology University of Minnesota Minneapolis, Minnesota 55455 Technical Report 78-5 March 1978 Cover design courtesy of Ruth and Jay Leavitt Preemptive Scheduling of Independent Jobs With Release and Due Times on Open, Flow and Job Shop s

Yookun Cho and Sartaj Sahni University of Minnesota

Abstract:

We study the problem of obtaining feasible preemptive schedules for independent jobs. It is assumed that each job has associated with it a release and due time. No job can begin before its release time. All jobs must be completed by their respective due tames. It is shown that determining the existence of feasible preemptive schedules for a two processor flow or job shop is NP-Hard even when all jobs have the same due time and there are only two distinct release times. The two processor case with many release times and one due time is NP-Hard in the strong sense. A linear programming formulation for the open shop problem is obtained. Also, fast polynomial time algorithms are obtained for open shops under certain restrictions. Keywords and Phrases: preemptive schedule, independent jobs, open shop, flow shop, job shop, release time, due time, NP-Hard, complexity. This research was.supported in part by NSF grant MCS 76-21024.

1. Introduction

A shop is an ordered set {P1,PZ,...,Pm,f of m>1 processors (or machines), n, n>1 jobs are to be scheduled on these processors. In the case of flow shops and open shops, each job has m tasks associated with it. The task time for task j of job i is denoted by ti,j. Task j is to be processed on processor P j, 1<j< m. In the case of an open shop, tasks may be processed in any order.In the case of a flow shop, task j of job i cannot start until task j-1 of that job has completed. In the case of a job shop there is a processor P(i,j) associated with each task and job. The j'th task of job i is to be processed on PP(i,j)~ Task j must finish before task j+1 can commence. A job may have any number of tasks. In addition to task times, job i also has associated with it a release time R(i) and a due time D(i). The processing of no task of job i can be-gin before time R(i). A11 tasks of job i must finish by D(i). ADD-schedule is an assignment of tasks to processors such that the processing of every job finishes by its due time and no job begins processing before its due time. In addition, no job can be simultaneously processed on more than one processor. In a non-preemptive DD-schedule every task, once started, continues to process until it finishes. In a preemptive DD-schedule the processing of some tasks may be interrupted and later continued. We shall use

(Equation Omitted)

to respectively denote the distinct release and due times present in the sets

University of...