Minimizing the total weighted completion time in the relocation problem
| dc.citation.epage | 129 | en_US |
| dc.citation.issue | 2 | en_US |
| dc.citation.spage | 123 | en_US |
| dc.citation.volume | 13 | en_US |
| dc.citation.woscount | 2 | |
| dc.contributor.author | Kononov, Alexander V. | en_US |
| dc.contributor.author | Lin, Bertrand M. T. | en_US |
| dc.contributor.department | 資訊管理與財務金融系 註：原資管所+財金所 | zh_TW |
| dc.contributor.department | Department of Information Management and Finance | en_US |
| dc.date.accessioned | 2014-12-08T15:07:08Z | |
| dc.date.available | 2014-12-08T15:07:08Z | |
| dc.date.issued | 2010-04-01 | en_US |
| dc.description.abstract | 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. | en_US |
| dc.identifier.doi | 10.1007/s10951-009-0151-7 | en_US |
| dc.identifier.issn | 1094-6136 | en_US |
| dc.identifier.journal | JOURNAL OF SCHEDULING | en_US |
| dc.identifier.uri | http://dx.doi.org/10.1007/s10951-009-0151-7 | en_US |
| dc.identifier.uri | https://ir.lib.nycu.edu.tw/handle/11536/5590 | |
| dc.identifier.wosnumber | WOS:000274959700002 | |
| dc.language.iso | en_US | en_US |
| dc.subject | Relocation problem | en_US |
| dc.subject | Resource-constrained scheduling | en_US |
| dc.subject | NP-hardness | en_US |
| dc.subject | Approximation algorithm | en_US |
| dc.title | Minimizing the total weighted completion time in the relocation problem | en_US |
| dc.type | Article | en_US |