On the relocation problem with a second working crew for resource recycling

Miao-Tsong Lin*, H. L. Huang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


In this paper, we introduce a variant of the relocation problem, which was formulated from a public house redevelopment project in Boston. In the problem of interest, given some initial resources in a common pool there is a set of jobs to be processed on a two-machine flowshop. Each job acquires a specific number of resources to start its processing and will return a number of resources to the pool at its completion. The resource consumption and resource recycle processes are performed on machine one and machine two, respectively, in a two-machine flowshop style. Abiding by the resource constraints, the problem seeks to find a feasible schedule whose makespan is minimized. In this paper, we first present NP-hardness proofs for some special cases. Three heuristic algorithms are designed to compose approximate schedules. Two lower bounds are developed and then used to test the performance of our proposed heuristics. Numerical results from computational experiments suggest that the proposed heuristics can produce quality solutions in a reasonable time.

Original languageEnglish
Pages (from-to)27-34
Number of pages8
JournalInternational Journal of Systems Science
Issue number1
StatePublished - 15 Jan 2006


  • Flowshop
  • Heuristic algorithms
  • Lower bound
  • Makespan
  • NP-hard
  • Relocation problem

Fingerprint Dive into the research topics of 'On the relocation problem with a second working crew for resource recycling'. Together they form a unique fingerprint.

Cite this