Minimizing the total weighted completion time in the relocation problem

檔案

日期

2010-04-01

期刊名稱

JOURNAL OF SCHEDULING

摘要

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.

所屬典藏

期刊論文
顯示完整詮釋資料 統計資料