A dominance-based heuristic to minimise completion time variance in a single machine system
H.M. Soroush and
European Journal of Industrial Engineering, 2019, vol. 13, issue 5, 589-626
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. (search for similar items in EconPapers)
References: Add references at CitEc
Citations: Track citations by RSS feed
Downloads: (external link)
Access to full text is restricted to subscribers.
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
Persistent link: https://EconPapers.repec.org/RePEc:ids:eujine:v:13:y:2019:i:5:p:589-626
Access Statistics for this article
More articles in European Journal of Industrial Engineering from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().