Title: A dominance-based heuristic to minimise completion time variance in a single machine system

Authors: H.M. Soroush; Fatmah Almathkour

Addresses: Department of Statistics and Operations Research, Kuwait University, P.O. Box 5969, Safat 13060, Kuwait ' Department of Statistics and Operations Research, Kuwait University, P.O. Box 5969, Safat 13060, Kuwait

Abstract: This paper addresses the problem of minimising the variance of job completion times in a deterministic single-machine scheduling system. Minimising completion time variance is an appropriate objective in scheduling environments where service uniformity is essential. Due to the NP-hard nature of the problem, various heuristics have been presented to obtain a near-optimal solution. In this paper, we introduce a new heuristic based on some powerful precedence (dominance) relation structures, including the concepts of permanent and temporary precedence (dominance) relationships, to determine the positions of adjacent and non-adjacent jobs in a sequence. Our computational experiments demonstrate that the proposed heuristic significantly outperforms the existing ones in deriving the optimal or near-optimal solutions for three well-known sets of benchmark problems and some large randomly generated instances. [Received: 5 August 2018; Revised: 24 December 2018; Accepted: 23 January 2019]

Keywords: scheduling; single machine; completion time variance; heuristic; precedence; dominance.

DOI: 10.1504/EJIE.2019.102157

European Journal of Industrial Engineering, 2019 Vol.13 No.5, pp.589 - 626

Published online: 09 Sep 2019 *

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