Browsing by Author "LIN, MT"

Now showing 1 - 2 of 2

RELOCATION PROBLEMS OF MAXIMIZING NEW CAPACITIES UNDER A COMMON DUE DATE
(1992-09-01)
LIN, MT
;
TSENG, SS
;
資訊工程學系
;
Department of Computer Science
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.
SOME RESULTS OF THE RELOCATION PROBLEMS WITH PROCESSING TIMES AND DEADLINES
(1991)
LIN, MT
;
TSENG, SS
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering