Minimizing the total weighted completion time in relocation scheduling

Yi Chen Su, Bertrand M.T. Lin*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


This study investigates a resource-constrained scheduling problem to minimize the total weighted completion time. A set of jobs is to be processed on a single machine subject to the limited availability of a single-type resource. An initial level of the resource is provided to support the processing of the jobs. Each job requires an amount of the resource to commence its processing, and returns an amount of the resource back to the resource pool when its processing is finished. The amount of the resource consumed and that returned by each job may not be identical. Minimizing the total weighted completion time under this resource-constraint setting is known to be strongly NP-hard. In this study, we propose several optimality dominance properties, a lower bound and two approximate bounds for developments of branch-and-bound-based approximation algorithms. Heuristic algorithms and subsequent improvement procedures are deployed to produce initial upper bounds for the branch-and-bound-based approximation algorithms. We conduct computational experiments to appraise the performance of the proposed properties and algorithms.

Original languageEnglish
Article number108662
JournalComputers and Industrial Engineering
StatePublished - Nov 2022


  • Heuristic algorithm
  • Relocation problem
  • Resource-constrained scheduling
  • Total weighted completion time


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

Cite this