Minimizing mean flow time with parallel processors and resource constraints
type: Item
instance of: scholarly article
title: Minimizing mean flow time with parallel processors and resource constraints
zbMATH Open document ID: 0606.68030
DOI: 10.1007/BF00263292
author: H. Rock
author: Jacek Blazewicz
author: Wieslaw Kubiak
author: Jayme L. Szwarcfiter
published in: Acta Informatica
publication date: 1987-01-01T00:00:00Z
review text: The problem considered is one of scheduling nonpreemptable tasks in multiprocessor systems when tasks need for their processing processors and other limited resources, and when mean flow time is the system performance measure. For each task the time required for its processing and the amount of each resource which it requires, are given. Special attention is paid to the computational complexity of algorithms for determining the optimal schedules for different assumptions concerning the environment. For the case of scheduling independent, arbitrary length tasks when each task may require a unit of an additional resource of one type, an \(O(n^ 3)\) algorithm is given. For more complicated resource requirements, however, it is proved that the problem under consideration is NP-hard in the strong sense, even for the case of two processors.
Mathematics Subject Classification ID: 68M20
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3980475
zbMATH Keywords: multiprocessor systems
zbMATH Keywords: NP-hard
zbMATH Keywords: parallel processors
zbMATH Keywords: additional resources
zbMATH Keywords: nonpreemptive scheduling
zbMATH Keywords: polynomial-time algorithms
MaRDI profile type: Publication
Wikidata QID: Q57387919
cites work: Deadline scheduling of tasks with ready times and resource constraints
cites work: Scheduling tasks on two processors with deadlines and additional resources
cites work: Scheduling Multiprocessor Tasks to Minimize Schedule Length
cites work: A linear time algorithm for restricted bin packing and scheduling problems
cites work: Scheduling subject to resource constraints: Classification and complexity
cites work: Scheduling independent tasks to reduce mean finishing time
cites work: Complexity Results for Multiprocessor Scheduling under Resource Constraints
cites work: Q4198056
cites work: Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
cites work: The NP-completeness column: An ongoing guide
cites work: Scheduling with deadlines and loss functions
cites work: Q4181597
cites work: Scheduling of project networks
cites work: Some new results in flow shop scheduling
cites work: Preemptive Scheduling, Linear Programming and Network Flows
full work available at URL: https://doi.org/10.1007/bf00263292
OpenAlex ID: W2049024694
description: scientific article; zbMATH DE number 3980475