|標題:||Minimizing the total weighted completion time in the relocation problem|
|作者:||Kononov, Alexander V.|
Lin, Bertrand M. T.
Department of Information Management and Finance
|關鍵字:||Relocation problem;Resource-constrained scheduling;NP-hardness;Approximation algorithm|
|摘要:||This paper studies the minimization of total weighted completion time in the relocation problem on a single machine. The relocation problem, formulated from an area redevelopment project, can be treated as a resource-constrained scheduling problem. In this paper, we show four special cases to be NP-hard in the strong sense. Problem equivalence between the unit-weighted case and the UET (unit-execution-time) case is established. For two further restricted special cases, we present a polynomial time approximation algorithm and show its performance ratio to be 2.|
|期刊:||JOURNAL OF SCHEDULING|