RELOCATION PROBLEMS OF MAXIMIZING NEW CAPACITIES UNDER A COMMON DUE DATE

Abstract

Given a set of h buildings to be torn down and rebuilt, each building B(i) demands n(i) units of temporary vacancies for reconstruction (i.e. the reconstruction of B(i) can be started only if there are at least n(i) temporary vacancies available) and returns a(i) units of vacancies when it is rebuilt. The reconstruction time of each building is assumed to be unitary. Under the initial provision of V0 units of vacancies and a specified due date d, SIGMA(Bi is-an-element-of S)a(i), where S is a feasible sequence such that absolute value of S less-than-or-equal-to d, is the objective function to be maximized. We show that the problem is NP-complete. Based on a dominance heuristics, we further propose a branch-and-bound algorithm. Experimental results are included to elucidate the effectiveness of our algorithm. Two further restricted versions are also polynomially solvable.