First fit decreasing scheduling on uniform multiprocessors
type: Item
instance of: scholarly article
title: First fit decreasing scheduling on uniform multiprocessors
zbMATH Open document ID: 0571.90037
DOI: 10.1016/0166-218X(85)90010-1
author: Manfred Kunde
author: Horst Steppat
published in: Discrete Applied Mathematics
publication date: 1985-01-01T00:00:00Z
review text: Independent tasks are nonpreemptively scheduled on \(m\geq 2\) processors which are assumed to have different speeds. The purpose of this paper is to show that the worst case ratio of the multifit algorithm MF, which is based on the bin-packing method FFD (first fit decreasing), depends on the order of the processors and that the MF has a better worst case behaviour than the well-known LPT algorithm for certain processor configurations.
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 68M20
zbMATH DE Number: 3912082
zbMATH Keywords: uniform multiprocessor systems
zbMATH Keywords: nonpreemptive scheduling
zbMATH Keywords: Independent tasks
zbMATH Keywords: worst case ratio
MaRDI profile type: Publication
cites work: Q4131987
cites work: An Application of Bin-Packing to Multiprocessor Scheduling
cites work: Bounds for Multifit Scheduling on Uniform Processors
cites work: Bounds for LPT Schedules on Uniform Processors
cites work: Bounds on Multiprocessing Timing Anomalies
cites work: Q3959419
cites work: Q3929047
cites work: Q4051611
cites work: NP-complete scheduling problems
full work available at URL: 0166-218x(85)90010-1
OpenAlex ID: W2093017196
description: scientific article; zbMATH DE number 3912082