Single machine scheduling with coefficient of variation minimization
type: Item
instance of: scholarly article
title: Single machine scheduling with coefficient of variation minimization
zbMATH Open document ID: 0763.90054
DOI: 10.1016/0377-2217(92)90120-X
author: M. Raghavachari
author: M. Zammouri
published in: European Journal of Operational Research
publication date: 1993-04-01T00:00:00Z
review text: The problem of scheduling \(n\) non-preemptive and simultaneously available jobs on a single machine is considered. The aim is to minimize \(\sum^ n_{i=1} C^ 2_ i\left/\left(\sum^ n_{i=1} C_ i\right)^ 2\right.\), where \(C_ i\) is the completion time of job \(i\). Two properties of optimal schedules are established: (1) The job with the largest processing time is always scheduled first in an optimal schedule. (2) Any optimal schedule is \(V\)-shaped (a schedule is \(V\)-shaped if all jobs preceding the job with shortest processing time are sequenced in non-increasing order of their processing times and jobs following the shortest time job are sequenced in non-decreasing order of their processing times). For \(n=3,4,5\) simple procedures for finding optimal schedules are obtained. A heuristic method is proposed for the general case.
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 90-08
zbMATH DE Number: 148009
zbMATH Keywords: \(V\)-shape schedule
zbMATH Keywords: single machine
zbMATH Keywords: heuristic
reviewed by: Ya. M. Shafransky
MaRDI profile type: Publication
cites work: Minimizing absolute and squared deviations of completion times with different earliness and tardiness penalties and a common due date
cites work: Minimizing mean absolute deviation of completion times about a common due date
cites work: V-shape property of optimal sequence of jobs about a common due date on a single machine
cites work: Minimising Waiting Time Variance in the Single Machine Problem
cites work: Minimizing the Flow-time Variance in Single-machine Systems
cites work: Minimizing Variation of Flow Time in Single Machine Systems
cites work: V-shape property for optimal schedules with monotone penalty functions
cites work: Variance Minimization in Single Machine Sequencing Problems
cites work: Stochastic Single Machine Scheduling with Quadratic Early-Tardy Penalties
cites work: A V-shape property of optimal schedule of jobs about a common due date
cites work: Minimizing the Time-in-System Variance for a Finite Jobset
cites work: Deterministic and Random Single Machine Sequencing with Variance Minimization
description: scientific article; zbMATH DE number 148009