The relocation problem originates from the public housing project so as to minimize the budgets. Given a set of jobs each demands nt units of resources for processing and returns a, units of resources. The relocation problem is to determine the minimum resource requirements demanded by the successful completion of this set of jobs. In the literature, anO(h*log h)algorithm has been proposed by Kaplan and Amir, where h is the number of jobs. In this paper, we consider the relocation problem with processing times and deadlines in which each job is additionally associated with a processing length and an individual deadline. Studies of NP-completeness of some versions of this problem are included. Also, we propose two polynomial algorithms, one runs inO(h*log h)time and the other inO(h2*log h)time, to solve some further restricted problems.
展开▼
