Title: Minimising weighted completion time on a single machine under uncertain weights

Authors: Hui Wu; Bing Wang

Addresses: Science and Information College, Qingdao Agricultural University, Qingdao 266109, Shandong Province, China; School of Mechatronic Engineering and Automation, Shanghai University, Shanghai 200072, China ' School of Mechatronic Engineering and Automation, Shanghai University, Shanghai 200072, China

Abstract: This paper has investigated the single-machine scheduling problem regarding the minimisation of the total weighted completion time, with the known processing times, while weights are uncertain. Uncertainty in weights is modelled using a scenario set, which contains explicitly listed scenarios of weights (the discrete-scenario case) or the Cartesian product of the intervals that contain possible values of weights (the interval-data case). Two main criteria are investigated: minimising the maximum objective function (min-max version) and minimising the maximum regret (min-max regret version). The computational complexity of the min-max (regret) versions of the single-machine scheduling problem in the cases of the discrete scenario as well as interval data is discussed, respectively, and on this basis, the approximation of corresponding NP-hard problems is further analysed.

Keywords: single-machine scheduling; weighted completion time; min-max; min-max regret; complexity; approximation.

DOI: 10.1504/IJAAC.2022.119422

International Journal of Automation and Control, 2022 Vol.16 No.1, pp.108 - 124

Received: 30 Oct 2019
Accepted: 17 Apr 2020
Published online: 03 Dec 2021 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article