Minimising variance of job completion times in a single machine

Minimising variance of job completion times in a single machine

0.00 Avg rating0 Votes
Article ID: iaor201113419
Volume: 13
Issue: 1
Start Page Number: 110
End Page Number: 127
Publication Date: Dec 2012
Journal: International Journal of Operational Research
Authors: ,
Keywords: scheduling, combinatorial optimization
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.

Reviews

Required fields are marked *. Your email address will not be published.