Title: Minimising variance of job completion times in a single machine

Authors: G. Srinivasan; B. Srirangacharyulu

Addresses: Department of Management Studies, Indian Institute of Technology Madras, Chennai 600036, Tamil Nadu, India ' Department of Management Studies, Indian Institute of Technology Madras, Chennai 600036, Tamil Nadu, India

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.

DOI: 10.1504/IJOR.2012.044030

International Journal of Operational Research, 2012 Vol.13 No.1, pp.110 - 127

Published online: 11 Jan 2015 *

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