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 |
檔案
- 000274959700002.pdf (306.1 KB, Adobe PDF)
所屬典藏: 期刊論文