標題: On relocation problems with multiple identical working crews
作者: Kononov, A. V.
Lin, B. M. T.
資訊管理與財務金融系 註:原資管所+財金所
Department of Information Management and Finance
關鍵字: public housing project;job scheduling;resource constraints;parallel machines;NP-hardness;approximation
公開日期: 1-Dec-2006
摘要: The relocation problem was formulated from a public housing project. In its basic form, a set of buildings needed to be torn down and erected by a single working crew. Given a fixed budget, the relocation problem seeks to determine a feasible reconstruction sequence of the old buildings. This problem has been shown to be mathematically equivalent to the classical two-machine flowshop of makespan minimization. In this paper, we consider a variant where multiple working crews are available for the redevelopment project. Most of our results center on the situations where all buildings require the same redevelopment time. We first present a strong NP-hardness proof for the case with two working crews. Then, we give a negative result about the approximability of the studied problem. Approximation algorithms and associated performance-ratio analysis are designed for the cases with unbounded as well as bounded numbers of machines. (c) 2006 Elsevier B.V. All rights reserved.
URI: http://dx.doi.org/10.1016/j.disopt.2006.06.003
http://hdl.handle.net/11536/11508
ISSN: 1572-5286
DOI: 10.1016/j.disopt.2006.06.003
期刊: DISCRETE OPTIMIZATION
Volume: 3
Issue: 4
起始頁: 366
結束頁: 379
Appears in Collections:Articles


Files in This Item:

  1. 000242965400008.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.