TY - JOUR

T1 - Tight complexity analysis of the relocation problem with arbitrary release dates

AU - Sevastyanov, Sergey V.

AU - Lin, Miao-Tsong

AU - Huang, Hsiao Lan

PY - 2011/8/12

Y1 - 2011/8/12

N2 - 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.

AB - 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.

KW - Makespan

KW - Multi-parametric dynamic programming

KW - NP-hardness

KW - Release dates

KW - Relocation problem

KW - Resource constraints

UR - http://www.scopus.com/inward/record.url?scp=79960559166&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2011.04.034

DO - 10.1016/j.tcs.2011.04.034

M3 - Article

AN - SCOPUS:79960559166

VL - 412

SP - 4536

EP - 4544

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 35

ER -