Title :
Resource-requirement minimization in relocation problems with precedence constraints
Author :
Lin, Bertrand M T ; Tseng, Shian-Shyong
Author_Institution :
Dept. of Comput. Sci. & Inf. Eng., Nat. Chiao-Tung Univ., Hsinchu, Taiwan
Abstract :
The relocation problem is a generalized resource-constrained 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. The authors propose fundamental properties of the basic relocation problem. Also, they consider a variant RPPC into which precedence constraints are introduced. They 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
Keywords :
computability; computational complexity; minimisation; scheduling; NP-complete; bi-partite; polynomially solvable subproblems; precedence constraints; precedence graphs; relocation problem; resource-constrained job scheduling; Computer science; Information science; Job design; Law; Legal factors; Optimal scheduling; Partitioning algorithms; Processor scheduling; Virtual colonoscopy;
Conference_Titel :
Computing and Information, 1992. Proceedings. ICCI '92., Fourth International Conference on
Conference_Location :
Toronto, Ont.
Print_ISBN :
0-8186-2812-X
DOI :
10.1109/ICCI.1992.227713