Bounds and asymptotic results for the uniform parallel processor weighted flow time problem
type: Item
instance of: scholarly article
title: Bounds and asymptotic results for the uniform parallel processor weighted flow time problem
zbMATH Open document ID: 0804.90078
DOI: 10.1016/0167-6377(93)90100-U
author: S. T. Webster
published in: Operations Research Letters
publication date: 1995-01-19T00:00:00Z
review text: Scheduling \(n\) jobs with known process times and weights on \(m\) parallel processors of different speed with the objective to minimize weighted flow time is known to be an NP-complete optimization problem. The author derives lower and upper bounds for the uniform processor problem which generalize well-known bounds for the identical processor problem. These bounds are used to show asymptotic properties of the uniform processor problem. Based on this it is shown that the heuristic of scheduling jobs on the first available processor in order of nondecreasing process time to weight ratio is asymptotically relatively optimal for a growing number of jobs. Also, the lower bound is asymptotically relatively optimal.
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 68M20
zbMATH DE Number: 527398
zbMATH Keywords: parallel processors
zbMATH Keywords: weighted flow time
zbMATH Keywords: asymptotic properties
zbMATH Keywords: uniform processor problem
reviewed by: Martin Middendorf
MaRDI profile type: Publication
cites work: Scheduling independent tasks to reduce mean finishing time
cites work: Analysis of Heuristics for Stochastic Programming: Results for Hierarchical Scheduling Problems
cites work: The Asymptotic Optimality of the LPT Rule
cites work: Q3824091
cites work: Tight Bounds and Probabilistic Analysis of Two Heuristics for Parallel Processor Scheduling
cites work: Probabilistic analysis of the minimum weighted flowtime scheduling problem
cites work: New Bounds for the Identical Parallel Processor Weighted Flow Time Problem
cites work: Approximation results in parallel machines stochastic scheduling
cites work: Turnpike Optimality of Smith's Rule in Parallel Machines Stochastic Scheduling
description: scientific article; zbMATH DE number 527398