標題: Tight complexity analysis of the relocation problem with arbitrary release dates
作者: Sevastyanov, Sergey V.
Lin, Bertrand M. T.
Huang, Hsiao-Lan
資訊管理與財務金融系 註:原資管所+財金所
Department of Information Management and Finance
關鍵字: Relocation problem;Resource constraints;Release dates;Makespan;NP-hardness;Multi-parametric dynamic programming
公開日期: 12-八月-2011
摘要: The paper considers makespan minimization on a single machine subject to release dates in the relocation problem, originated from a resource-constrained redevelopment project in Boston. Any job consumes a certain amount of resource from a common pool at the start of its processing and returns to the pool another amount of resource at its completion. In this sense, the type of our resource constraints extends the well-known constraints on resumable resources, where the above two amounts of resource are equal for each job. In this paper, we undertake the first complexity analysis of this problem in the case of arbitrary release dates. We develop an algorithm, based on a multi-parametric dynamic programming technique (when the number of parameters that undergo enumeration of their values in the DP-procedure can be arbitrarily large). It is shown that the algorithm runs in pseudo-polynomial time when the number m of distinct release dates is bounded by a constant. This result is shown to be tight: (1) it cannot be extended to the case when m is part of the input, since in this case the problem becomes strongly NP-hard, and (2) it cannot be strengthened up to designing a polynomial time algorithm for any constant m > 1, since the problem remains NP-hard for m = 2. A polynomial-time algorithm is designed for the special case where the overall contribution of each job to the resource pool is nonnegative. As a counterpart of this result, the case where the contributions of all jobs are negative is shown to be strongly NP-hard. (C) 2011 Elsevier B.V. All rights reserved.
URI: http://dx.doi.org/10.1016/j.tcs.2011.04.034
http://hdl.handle.net/11536/20353
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2011.04.034
期刊: THEORETICAL COMPUTER SCIENCE
Volume: 412
Issue: 35
起始頁: 4536
結束頁: 4544
顯示於類別:期刊論文


文件中的檔案:

  1. 000294031200008.pdf