Minimising variance of job completion times in a single machine

G. Srinivasan and B. Srirangacharyulu

International Journal of Operational Research, 2012, vol. 13, issue 1, 110-127

Abstract: In this paper, we consider a deterministic n-job, single-machine sequencing problem with the objective of minimising the variance of job completion times. Completion time variance (CTV) is relevant in situations where uniformity in service is needed. CTV is a non-regular performance measure that can decrease when one or more completion times increases. It penalises jobs that are completed early as well as late. Minimising CTV in a single machine is a ‘hard’ problem. The objective of this paper is to provide an exact algorithm to solve the single-machine CTV minimisation problem based on implicit enumeration. We develop a lower bound for a given partial sequence and present a branch and bound algorithm to solve the problem. Computational results show that optimal solutions for problems up to 80 jobs can be obtained with less computational time when compared to an existing pseudo-polynomial algorithm.

Keywords: single machine scheduling; completion time variance; branch and bound; job completion times. (search for similar items in EconPapers)
Date: 2012
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.inderscience.com/link.php?id=44030 (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:ijores:v:13:y:2012:i:1:p:110-127

Access Statistics for this article

More articles in International Journal of Operational Research from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().