Minimizing the total weighted completion time in the relocation problem

Alexander V. Kononov, Miao-Tsong Lin

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

This paper studies the minimization of total weighted completion time in the relocation problem on a single machine. The relocation problem, formulated from an area redevelopment project, can be treated as a resource constrained scheduling problem. In this paper, we show four special cases to be NP-hard in the strong sense. Problem equivalence between the unit-weighted case and the UET (unit-execution-time) case is established. For two further restricted special cases, we present a polynomial time approximation algorithm and show its performance ratio to be 2.

Original languageEnglish
Pages (from-to)123-129
Number of pages7
JournalJournal of Scheduling
Volume13
Issue number2
DOIs
StatePublished - 1 Apr 2010

Keywords

  • Approximation algorithm
  • NP-hardness
  • Relocation problem
  • Resource-constrained scheduling

Fingerprint Dive into the research topics of 'Minimizing the total weighted completion time in the relocation problem'. Together they form a unique fingerprint.

Cite this