A solvable case of the variance minimization problem

DOI10.1016/0893-9659(93)90086-3MaRDI QIDQ1324501zbMATH OpenOpenAlexFDO

Authors V. Pereyra

Publication date 24 May 1994

Published in Applied Mathematics Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0893-9659(93)90086-3

zbMATH Keywords

arbitrary weightscompletion time varianceequal processing times

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Deterministic scheduling theory in operations research (90B35)

Review text

The completion time variance (CTV) problem was first proposed by \textit{A. G. Merten} and \textit{M. E. Muller} [Management Sci., Theory 18, 518-528 (1972; Zbl 0254.90040)]. It is a scheduling problem. The general CTV problem involves arbitrary processing times and weights. The equal weight case has already been studied extensively and shown to be NP-complete (references are given). The case where processing times are equal but weights are arbitrary is investigated in this paper. It is shown that this case is well solvable and an algorithm is derived which can yield an optimal solution in \(O(n\log n)\) time. The algorithm may be extended as a heuristic to the general CTV problem.

Recommendations

• Completion time variance minimization on a single machine is difficult
• A branch and bound algorithm to minimize completion time variance on a single processor.
• Minimizing completion time variance with compressible processing times
• New results on the completion time variance minimization

Cites work

• Deterministic and Random Single Machine Sequencing with Variance Minimization
• Minimising Waiting Time Variance in the Single Machine Problem
• Minimizing the Time-in-System Variance for a Finite Jobset
• Simultaneous Minimization of Mean and Variation of Flow Time and Waiting Time in Single Machine Systems
• Variance Minimization in Single Machine Sequencing Problems

Cited in

(9)

• A minimax job completion-time problem revisited
• Mimimization of agreeably weighted variance in single machine systems
• Completion time variance minimization on a single machine is difficult
• Pseudopolynomial algorithms for CTV minimization in single machine scheduling
• Completion time variance minimisation on two identical parallel processors
• Minimizing completion time variance with compressible processing times
• Permutation polyhedra and minimisation of the variance of completion times on a single machine
• scientific article; zbMATH DE number 764420 (Why is no real title available?)
• Variance Minimization – Relationship between Completion-Time Variance and Waiting-Time Variance

This page was built for publication: A solvable case of the variance minimization problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1324501)