Relocation problems of maximizing new capacities under a common due date

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 V _o units of vacancies and a specified due date d, Σ_BiεSa _i where S is a feasible sequence such that S ≤ 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.