On relocation problems with multiple identical working crews

A. V. Kononov, Miao-Tsong Lin*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


The relocation problem was formulated from a public housing project. In its basic form, a set of buildings needed to be torn down and erected by a single working crew. Given a fixed budget, the relocation problem seeks to determine a feasible reconstruction sequence of the old buildings. This problem has been shown to be mathematically equivalent to the classical two-machine flowshop of makespan minimization. In this paper, we consider a variant where multiple working crews are available for the redevelopment project. Most of our results center on the situations where all buildings require the same redevelopment time. We first present a strong NP-hardness proof for the case with two working crews. Then, we give a negative result about the approximability of the studied problem. Approximation algorithms and associated performance-ratio analysis are designed for the cases with unbounded as well as bounded numbers of machines.

Original languageEnglish
Pages (from-to)366-381
Number of pages16
JournalDiscrete Optimization
Issue number4
StatePublished - 1 Dec 2006


  • Approximation
  • Job scheduling
  • NP-hardness
  • Parallel machines
  • Public housing project
  • Resource constraints


Dive into the research topics of 'On relocation problems with multiple identical working crews'. Together they form a unique fingerprint.

Cite this