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

H.M. Soroush and Fatmah Almathkour

European Journal of Industrial Engineering, 2019, vol. 13, issue 5, 589-626

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. (search for similar items in EconPapers)
Date: 2019
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.inderscience.com/link.php?id=102157 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

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 ().