Some results of the relocation problems with processing times and deadlines

The relocation problem originates from the public housing project so as to minimize the budgets. Given a set of jobs each demands n i units of resources for processing and returns aiunits 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, an O(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 in O(h* log h) time and the other in O(h2* log h) time, to solve some further restricted problems.