Relocation problems of maximizing new capacities under a common due date

Miao-Tsong Lin, Shian Shyong Tseng

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


Given a set of h buildings to be torn down and rebuilt, each building Bi demands ni units of temporary vacancies for reconstruction (i.e. the reconstruction of Bi can be started only if there are at least ni temporary vacancies available) and returns ai 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.

Original languageEnglish
Pages (from-to)1433-1448
Number of pages16
JournalInternational Journal of Systems Science
Issue number9
StatePublished - 1 Jan 1992

Fingerprint Dive into the research topics of 'Relocation problems of maximizing new capacities under a common due date'. Together they form a unique fingerprint.

Cite this