Resource-requirement minimization in relocation problems with precedence constraints

Bertrand M.T. Lin, Shian Shyong Tseng

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

The relocation problem is a generalized resourceconstrained job scheduling problem in the aspect that the amount of resources returned at the completion of a job is not necessarily equal to that demanded. In this paper, we propose fundamental properties of the basic relocation problem. Also, we consider a variant RPPC into which precedence constraints are introduced. We show that RPPC is NP-complete, even if the precedence graphs are bi-partite. Furthermore, efficient algorithms are presented to solve some polynomially solvable subproblems.

Original languageEnglish
Title of host publicationProceedings - ICCI 1992
Subtitle of host publication4th International Conference on Computing and Information
EditorsPeter E. Lauer, Anestis A. Toptsis, Waldemar W. Koczkodaj
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages26-29
Number of pages4
ISBN (Electronic)081862812X, 9780818628122
DOIs
StatePublished - 1 Jan 1992
Event4th International Conference on Computing and Information, ICCI 1992 - Toronto, Canada
Duration: 28 May 199230 May 1992

Publication series

NameProceedings - ICCI 1992: 4th International Conference on Computing and Information

Conference

Conference4th International Conference on Computing and Information, ICCI 1992
CountryCanada
CityToronto
Period28/05/9230/05/92

Fingerprint Dive into the research topics of 'Resource-requirement minimization in relocation problems with precedence constraints'. Together they form a unique fingerprint.

Cite this