On the worst-case ratio of a compound multiprocessor scheduling algorithm
type: Item
instance of: scholarly article
title: On the worst-case ratio of a compound multiprocessor scheduling algorithm
zbMATH Open document ID: 0634.68024
DOI: 10.1016/0020-0190(87)90217-1
author: Manfred Kunde
author: Horst Steppat
published in: Information Processing Letters
publication date: 1987-01-01T00:00:00Z
review text: Approximation algorithms for nonpreemptive scheduling of independent tasks on m identical processors are studied. For a heuristic MIX which chooses the best solution of the two well-known heuristics LPT and MULTIFIT the following results are derived: \[ (i)\quad 10/9\leq R_ 2(MIX)\leq 10/9 +2^{-k},\quad (ii)\quad 8/7\leq R_ 3(MIX)\leq 8/7 +2^{-k}, \] \[ (iii)\quad 15/13\leq R_ m(MIX)\text{ for all } m\geq 5. \] Here \(R_ m(MIX)\) denotes the worst-case ratio and k is the number of iterations in which MULTIFIT calls the subroutine FIRST-FIT DECREASING.
reviewed by: Peter Brucker
Mathematics Subject Classification ID: 68M20
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 90B35
zbMATH DE Number: 4033063
zbMATH Keywords: processor scheduling
zbMATH Keywords: bin packing
zbMATH Keywords: Approximation algorithms
zbMATH Keywords: worst-case ratio
MaRDI profile type: Publication
full work available at URL: 0020-0190(87)90217-1
OpenAlex ID: W2079915495
cites work: Q4131987
cites work: An Application of Bin-Packing to Multiprocessor Scheduling
cites work: Q3347319
cites work: Tighter Bounds for the Multifit Processor Scheduling Algorithm
cites work: Bounds on Multiprocessing Timing Anomalies
cites work: Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
cites work: NP-complete scheduling problems
Recommended article: Q3677169
Recommended article: A composite algorithm for multiprocessor scheduling
Recommended article: On the complexity of multiprocessor task scheduling
Recommended article: The worst-case analysis of the MULTIFIT algorithm for scheduling nonsimultaneous parallel machines
Recommended article: Q4813035
Recommended article: Q4427861
Recommended article: Worst-case analysis of scheduling heuristics of parallel systems
Recommended article: Q5167620
Recommended article: Computational complexity of some scheduling problems with multiprocessor tasks
Recommended article: WORST-CASE PERFORMANCE EVALUATION ON MULTIPROCESSOR TASK SCHEDULING WITH RESOURCE AUGMENTATION
description: scientific article; zbMATH DE number 4033063