Maximizing the reward in the relocation problem with generalized due dates

The relocation problem, based on a public housing project in Boston, USA, is a generalized resource-constrained scheduling problem in which the amount of resources (new housing units) returned by a completed job (building) is not necessarily the same as the amount of resources (original housing units) it started out with for processing. In this paper we consider a variant where several generalized due dates are specified to define the number of new housing units that should be built in the entire duration of the project. Generalized due dates are different from conventional due dates in that they are job independent and common to all jobs. In the present study each generalized due date is given to specify an expected percentage of completion of the project. Given an initial number of temporary housing units, the goal is to find a feasible reconstruction sequence that maximizes the total reward over all generalized due dates. This paper investigates the time complexity of the problem. Two upper bounds and a dominance property are proposed for the design of branch-and-bound algorithms. Computational experiments are carried out to assess the efficiency of the proposed properties. The results show that the proposed properties can significantly reduce the time required for producing an optimal schedule.