標題: 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
公開日期: 1-Apr-2010
摘要: 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.
URI: http://dx.doi.org/10.1007/s10951-009-0151-7
http://hdl.handle.net/11536/5590
ISSN: 1094-6136
DOI: 10.1007/s10951-009-0151-7
期刊: JOURNAL OF SCHEDULING
Volume: 13
Issue: 2
起始頁: 123
結束頁: 129
Appears in Collections:Articles


Files in This Item:

  1. 000274959700002.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.