Scheduling independent 2-processor tasks to minimize schedule length
type: Item
instance of: scholarly article
title: Scheduling independent 2-processor tasks to minimize schedule length
zbMATH Open document ID: 0544.68032
DOI: 10.1016/0020-0190(84)90006-1
author: M. Drabowski
author: Jacek Blazewicz
author: Jan Węglarz
published in: Information Processing Letters
publication date: 1984-01-01T00:00:00Z
review text: The problem considered in this paper is the deterministic scheduling of tasks on a set of identical processors. However, the model presented differs from the classical one by the requirement that certain tasks need more than one processor at a time for their processing. In the paper an O(n log n) algorithm is given for scheduling n preemtable tasks on m processors to minimize schedule length, when tasks are divided into two subsets. Each task from the first subset requires one processor at a time, and each task from the second subset requires two processors at a time for its processing.
Mathematics Subject Classification ID: 68M20
Mathematics Subject Classification ID: 90B35
zbMATH DE Number: 3866579
zbMATH Keywords: multiprocessor tasks
zbMATH Keywords: polynomial-time algorithm
zbMATH Keywords: deterministic scheduling
zbMATH Keywords: identical processors
Wikidata QID: Q57387935
MaRDI profile type: Publication
full work available at URL: 0020-0190(84)90006-1
OpenAlex ID: W1981443073
cites work: Q4131987
cites work: Q4198056
cites work: Characterization of Connection Assignment of Diagnosable Systems
cites work: Q3929047
cites work: Optimization of Reduced Dependencies for Synchronous Sequential Machines
DBLP publication ID: journals/ipl/BlazewiczWD84
description: scientific article; zbMATH DE number 3866579