An almost exact solution to the min completion time variance in a single machine

Stefano Nasini and Rabia Nessah

European Journal of Operational Research, 2021, vol. 294, issue 2, 427-441

Abstract: We consider a single machine scheduling problem to minimize the completion time variance of n jobs. This problem is known to be NP-hard and our contribution is to establish a novel bounding condition for a characterization of an optimal sequence. Specifically, we prove a necessary and sufficient condition (which can be verified in O(nlogn)) for the characterization of five scheduling positions in the optimal sequence. Applying this characterization, we propose a new approach to derive the highest lower bound for the minimal completion time variance, outperforming the existing bounds for this problem. The numerical tests indicate that the novel lower bound is, on average, less than 0.01% far away from the optimal solution, outperforming all the existing lower bounds on the minimum completion time variance.

Keywords: Scheduling; Single machine; Completion time variance; Optimal sequence characterization; Lower bound (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221721000680
Full text for ScienceDirect subscribers only

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:eee:ejores:v:294:y:2021:i:2:p:427-441

DOI: 10.1016/j.ejor.2021.01.038

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().