Some results of the relocation problems with processing times and deadlines

Abstract

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, 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 inO(h^∗log h)time and the other in O(h^2∗log h)time, to solve some further restricted problems.

Keywords:

• relocation problem
• scheduling
• processing time
• deadline
• algorithm
• NP-complete

C.R. Categories:

• F.2.2 [Nonnumerical Algorithms and Problems]
• K.6.1 [Project and People Management]