Browse Prior Art Database

Single Machine Flow-Time Scheduling With a Single Breakdown

IP.com Disclosure Number: IPCOM000128369D
Original Publication Date: 1987-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 13 page(s) / 34K

Publishing Venue

Software Patent Institute

Related People

John Bruno: AUTHOR [+3]

Abstract

We consider the problem of scheduling tasks on a single machine to minimize the flow time. The machine is subject to a single breakdown during the processing of the jobs. The breakdown occurs at a time tbrk and the machine is unavaliable until time tf ix ? tbrk. A task which is preemted due to the breakdown must be restarted and other-wise preemptions are not allowed. We assume that tbrk and tf ix are fixed and known before scheduling begins and the processing times of the tasks are also known. We show that the problem of deciding whether there is a schedule with flow time less than or equal to a given value is NP-complete.

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

Page 1 of 13

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Single Machine Flow-Time Scheduling With a Single Breakdown

John Bruno

Department of Computer Science

January, Single Machine Flow-Time Scheduling With a Single Breakdown

John Brunot

Department of Computer Science University of California Santa Barbara, CA 93106

ABSTRACT

We consider the problem of scheduling tasks on a single machine to minimize the flow time. The machine is subject to a single breakdown during the processing of the jobs. The breakdown occurs at a time tbrk and the machine is unavaliable until time tf ix ? tbrk. A task which is preemted due to the breakdown must be restarted and other-wise preemptions are not allowed. We assume that tbrk and tf ix are fixed and known before scheduling begins and the processing times of the tasks are also known. We show that the problem of deciding whether there is a schedule with flow time less than or equal to a given value is NP-complete.

1. Introduction

An instance of the single machine flow-time problem with a single breakdown is specified by: GIVEN: n + 3 positive numbers

(Equation Omitted)

, where the cis are the processing times of n tasks and

(Equation Omitted)

. Scheduling begins at time 0 and the machine is unavailable in the interval (tbrk ,tf ix ). No preemptions are allowed. QUESTION: Does there exist a schedule n such that Cue, the flow time(sum of finishing times) of the schedule n, satisfies C,,S C?

An instance of the 2 Partition problem is given by: GIVEN: n positive numbers

(Equation Omitted)

QUESTION: Does there exist a subset

(Equation Omitted)

that ~xl = b , where

University of California at Santa Barbara Page 1 Dec 31, 1987

Page 2 of 13

Single Machine Flow-Time Scheduling With a Single Breakdown

(Equation Omitted)

2. Reduction

Assume we are given an instance, say I, of the 2-partition problem, i.e., we are

given n positive numbers

(Equation Omitted)

Define

(Equation Omitted)

.

t The work of this author was partially supported by The Lady Davis Fellowship Trust through a Lady Davis Visiting Professorship at the Technion, Haifa, Israel. Define

(Equation Omitted)

Note that

(Equation Omitted)

for

(Equation Omitted)

Let A be some constant such that

(Equation Omitted)

. Then define

(Equation Omitted)

for

(Equation Omitted)

Note that

(Equation Omitted)

University of California at Santa Barbara Page 2 Dec 31, 1987

Page 3 of 13

Single Machine Flow-Time Scheduling With a Single Breakdown

. Given 1, we define an instance Q (I) of the single machine flow time problem with a single breakdown as: GIVEN: There are 2n + 2 tasks. For each i ---- O,l,...,n there are two tasks each with pro- cessing time

(Equation Omitted)

and

(Equation Omitted)

QUESTION: Does there exist a schedule 7r such that

(Equation Omitted)

Theorem 1: Let I be an instance of the 2-Partition problem and Q (I) the corresponding instance of the single machine flow-time problem with a single breakdown. Then there exists a subset P of (1,2,...,n...