In this paper we consider the problem of minimizing the completion time variance of n jobs on a single machine with deterministic processing times. We propose a new heuristic and compare the results with existing popular heuristics for the problem. We also propose a method based on genetic algorithms to solve the problem. We present the worst case performance analysis of the proposed heuristic. We also consider the problem of minimizing the completion time variance of n jobs on m identical parallel machines in both restricted and unrestricted versions. A heuristic method and a method based on genetic algorithms are presented for both the cases and results of computational testing are provided. It is concluded that the proposed methods provide better results compared to existing methods for the single machine case as well as for the multi-machine case. © 2009 Elsevier Ltd. All rights reserved.

G Srinivasan

Department of Management Studies

COMPLETION TIME VARIANCE

COMPUTATIONAL TESTING

EXISTING METHOD

Heuristic

IDENTICAL PARALLEL MACHINES

MULTI-MACHINE SCHEDULING

Multimachine systems

Processing time

SINGLE MACHINE SCHEDULING

SINGLE MACHINES

WORST-CASE PERFORMANCE ANALYSIS

BUSINESS MACHINES

Genetic algorithms

Heuristic algorithms

Optimization

Problem solving

Scheduling algorithms

Heuristic methods

IIT Madras is a public technical and research university located in Chennai, Tamil Nadu. Founded in 1959, it is recognised as an Institute of National Importance.

IIT Madras has been ranked as the top engineering institute in India for four years in a row by the National Institutional Ranking Framework of the MHRD

It currently offers undergraduate, postgraduate and research degrees across 16 disciplines in Engineering, Sciences, Humanities and Management. About 596 faculty belonging to science and engineering departments and centres of the Institute are engaged in teaching, research and industrial consultancy.

IIT Madras

Computers and Operations Research

In this paper, the permutation flowshop scheduling problem with the objective of minimising the completion time variance (CTV) of jobs is considered, and a simulated annealing algorithm (SA) and two modified SAs (MSA1 and MSA2) are proposed. In the first phase, the proposed algorithms are used to minimise CTV of jobs without any right shifting of completion times of jobs on the last machine (RSCT). As followed in the literature some times, the RSCT (except that of the last job) is attempted in the second phase, and in the third phase, we convert sequences so as to follow the V-shaped property with respect to processing time of jobs on the last machine, followed by RSCT except that of the last job, so that the makespan and the machine utilisation in the shop floor remain the same. We present an extensive computational evaluation of the existing and the proposed heuristic algorithms. © The Author(s) 2019.

International Journal of Industrial and Systems Engineering

Simulated annealing algorithms to minimise the completion time variance of jobs in permutation flowshops

This paper addresses the problem of scheduling n jobs on a single machine and on m identical parallel machines to minimize the completion time variance of jobs. This problem of scheduling jobs on parallel machines is motivated by a case study in an automobile ancillary unit. First, a heuristic to solve the single-machine scheduling problem is proposed. The parallel-machine scheduling problem is solved in two phases: job-allocation phase and job-sequencing phase. Two heuristics are proposed in the job-allocation phase, whereas in the job-scheduling phase, the single-machine scheduling approach is used. In this paper, both versions of parallel-machine scheduling problem (restricted and unrestricted) are considered. A good upper bound is obtained using a genetic algorithm, to evaluate the performance of the proposed heuristics for the parallel-machine scheduling problem. An extensive computation evaluation of the proposed heuristics is presented for both single-machine scheduling problem and the parallel-machine scheduling problem (especially considering the case study), along with the comparison of performances with the existing heuristics in the literature. © 2016, Springer-Verlag London.

International Journal of Advanced Manufacturing Technology

Heuristics to minimize the completion time variance of jobs on a single machine and on identical parallel machines

We consider a deterministic n-job, single machine scheduling problem with the objective of minimizing the Mean Squared Deviation (MSD) of job completion times about a common due date (d). The MSD measure is non-regular and its value can decrease when one or more completion times increases. MSD problem is connected with the Completion Time Variance (CTV) problem and has been proved to be NP-hard. This problem finds application in situations where uniformity of service is important. We present an exact algorithm of pseudo-polynomial complexity, using ideas from branch and bound and dynamic programming. We propose a dominance rule and also develop a lower bound on MSD. The dominance rule and lower bound are effectively combined and used in the development of the proposed algorithm. The search space is explored using the breadth first branching strategy. The asymptotic space complexity of the algorithm is O(nd). Irrespective of the version of the problem - tightly constrained, constrained or unconstrained - the proposed algorithm provides optimal solutions for problem instances up to 1000 jobs size under different due date settings. © 2013 Elsevier B.V. All rights reserved.

European Journal of Operational Research

An exact algorithm to minimize mean squared deviation of job completion times about a common due date

In this work, the flowshop scheduling problem is considered with the objective of minimising the completion-time variance (CTV) of jobs, and an Ant Colony Optimisation (ACO) algorithm is presented. Two implementations of the Modified Ant Colony Optimisation algorithm (MACO-I and MACO-II) are proposed to solve the permutation flowshop scheduling problem. The proposed ant-colony-algorithm implementations have been tested on 90 benchmark flowshop scheduling problems. The solutions yielded by the proposed MACO implementations are compared with various algorithms and with the best CTV of jobs reported in the literature. The proposed MACO implementations are found to perform very well in minimising the chosen performance measure. © 2012 Copyright Taylor and Francis Group, LLC.

International Journal of Production Research

A modified ant-colony optimisation algorithm to minimise the completion time variance of jobs in flowshops

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. Copyright © 2012 Inderscience Enterprises Ltd.

International Journal of Operational Research

Minimising variance of job completion times in a single machine

The problem of scheduling in permutation flowshops with the objective of minimizing the completion-time variance of jobs is considered and solved by making use of ant-colony optimization (ACO) algorithms. ACO is an algorithmic approach, inspired by the foraging behavior of real ants, which can be applied to solve combinatorial optimization problems. A new ant-colony algorithm (NACO) has been developed in this paper to solve the flowshop scheduling problem. The objective is to minimize the completion-time variance of jobs. Two existing ant-colony algorithms and the proposed ant-colony algorithm have been compared with an existing heuristic for scheduling with the objective of minimizing the completion-time variance of jobs. It is found that the proposed ant-colony algorithm gives promising and better results, on an average, as compared to those solutions given by the existing ant-colony algorithms and the existing heuristic for the permutation flowshop scheduling problem under study. © 2005 Elsevier B.V. All rights reserved.

International Journal of Production Economics

An ant-colony optimization algorithm for minimizing the completion-time variance of jobs in flowshops

In this paper we discuss a single machine scheduling problem with the objective of minimizing the variance of job completion times. The CTV problem has been proved to be NP hard (Oper. Res. Lett. 14 (1993) 49) and no polynomial time algorithm exists to find an optimal solution for CTV minimization on single machine. Hence enumerative techniques and heuristics are used to get optimal and near optimal solutions, respectively. We present a branch and bound algorithm and extend the same algorithm to generate epsilon optimal solutions for large sized problems (i.e., number of jobs > 30). The algorithm has been computationally tested, with randomly generated problems involving up to 100 jobs, using a personal computer (PC) with a 64 MB RAM capacity. The computational time required for generating optimal solutions are in few seconds for problems with jobs between 25 and 30. The performance of the branch and bound algorithm is compared with the pseudo-polynomial algorithm (Oper. Res. 40 (1992) 1148) for small sized problems. For problems with greater number of jobs, the epsilon optimal solutions obtained using branch and bound algorithm are compared with results of simulated annealing (Single machine scheduling with some non-regular objectives, M.S. Thesis, IIT Madras, 1997), tabu search (Proceedings of Operations Management Conference, IIT Madras, 2000) and heuristic proposed by Manna and Prasad (Eur. J. Oper. Res. 114 (1999) 411). Scheduling jobs in manufacturing systems considering non-regular measures of performance have gained importance in recent years. The objectives of minimizing completion time variance (CTV problem) and minimizing squares of deviations of job completion times from a given common due-date (MSD problem) are the two problems that use non-regular measures, and have attracted attention in single machine scheduling and flowshop scheduling when jobs require uniform treatment i.e., each entity spends approximately sametime in the system or waits for service as every other entity. This problem is very much relevant when a manufacturing/service system places emphasis on Just-in-Time philosophy. The purpose of this paper is to present an algorithm for minimizing completion time variance for a set of jobs to be processed on a single machine. The proposed algorithm is computationally evaluated with randomly generated problems involving up to 100 jobs and results are reported. © 2002 Elsevier Science Ltd. All rights reserved.

A branch and bound algorithm to minimize completion time variance on a single processor

Journal of Combinatorial Optimization

Analytic evaluation of the expectation and variance of different performance measures of a schedule on a single machine under processing time variability

The International Journal of Advanced Manufacturing Technology

Minimizing flow-time variance in a single-machine system using genetic algorithms

A new approach to solving the multiple traveling salesperson problem using genetic algorithms

Completion time variance minimization in single machine and multi-machine systems

Journal	Computers and Operations Research
ISSN	03050548
Open Access	No