Bounds for nonpreemptive scheduling of jobs with similar processing times on multiprocessor systems using the LPT-algorithm
type: Item
instance of: scholarly article
title: Bounds for nonpreemptive scheduling of jobs with similar processing times on multiprocessor systems using the LPT-algorithm
zbMATH Open document ID: 0729.90053
DOI: 10.1007/BF02238297
published in: Computing
publication date: 1991-01-01T00:00:00Z
review text: The well-known, NP-complete problem of scheduling a set of n independent jobs nonpreemptively on m identical parallel processors to minimize the maximum finish time is considered. Let \(\omega_ 0\) be the finish time of an optimal schedule and \(\omega\) the finish time of a schedule found by the Longest Processing Time (LPT-)heuristic. We will improve the Graham-bound for the LPT-heuristic \((\omega /\omega_ 0\leq 4/3-1/3m)\), which is tight in general, by considering only jobs with similar processing times.
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 68M20
zbMATH DE Number: 4207213
zbMATH Keywords: nonpreemptive scheduling
zbMATH Keywords: worst case analysis
zbMATH Keywords: identical parallel processors
zbMATH Keywords: similar processing times
author: Hans Kellerer
MaRDI profile type: Publication
cites work: Bounds on Schedules for Independent Tasks with Similar Execution Times
cites work: Q4131987
cites work: An Application of Bin-Packing to Multiprocessor Scheduling
cites work: Bounds on Multiprocessing Timing Anomalies
full work available at URL: https://doi.org/10.1007/bf02238297
OpenAlex ID: W1546966627
description: scientific article; zbMATH DE number 4207213