Minimizing the total weighted completion time in relocation scheduling. (November 2022)

• Record Type: Journal Article
• Authors: Su, Yi-Chen; Lin, Bertrand M.T.
• Is Part Of: Computers & industrial engineering. Volume 173(2022)
• Publication Date: 2022-11
• Subjects: Relocation problem -- Resource-constrained scheduling -- Total weighted completion time -- Heuristic algorithm; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2022.108662
• Languages: English
• ISSNs: 0360-8352

Abstract

Abstract: 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. Highlights: Resource-constrained scheduling to minimize the total weighted completion time is studied. Several optimality properties, a lower bound and two approximate bounds are developed. Heuristic algorithms and improvement procedures are deployed to produce approximate solutions. Computational experiments are designed and conducted.