Maximizing the reward in the relocation problem with generalized due dates

Miao-Tsong Lin*, S. T. Liu

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


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.

Original languageEnglish
Pages (from-to)55-63
Number of pages9
JournalInternational Journal of Production Economics
Issue number1
StatePublished - Sep 2008


  • Branch-and-bound algorithm
  • Generalized due dates
  • NP-hardness
  • Relocation problem
  • Resource-constrained scheduling

Fingerprint Dive into the research topics of 'Maximizing the reward in the relocation problem with generalized due dates'. Together they form a unique fingerprint.

Cite this