A polynomial algorithm to optimally schedule tasks on a virtual distributed system under tree-like precedence constraints
type: Item
instance of: scholarly article
title: A polynomial algorithm to optimally schedule tasks on a virtual distributed system under tree-like precedence constraints
zbMATH Open document ID: 0689.90045
DOI: 10.1016/0377-2217(89)90216-6
author: Philippe Chrétienne
published in: European Journal of Operational Research
publication date: 1989-01-01T00:00:00Z
review text: Considered is a computer system with an unbounded number of independent interchangeable processors with independent memory. The paper deals with a job scheduling problem in which the jobs are depending from each other through a tree-like structure. This means that any ``root'' job cannot be performed before all ``branch'' jobs have been performed. In this situation the jobs running on different processors must communicate with each other because of the independent memory. We assume that the maximum communication time is less than the minimum task processing time. In this case the paper gives a polynomial algorithm for the optimal job scheduling problem.
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68N25
Mathematics Subject Classification ID: 68M20
Mathematics Subject Classification ID: 90C90
zbMATH DE Number: 4130179
zbMATH Keywords: tree-like precedence constraints
zbMATH Keywords: graph
zbMATH Keywords: distributed system
zbMATH Keywords: independent interchangeable processors
zbMATH Keywords: independent memory
zbMATH Keywords: polynomial algorithm
zbMATH Keywords: optimal job scheduling
MaRDI profile type: Publication
full work available at URL: 0377-2217(89)90216-6
OpenAlex ID: W2057461902
cites work: Q4131987
cites work: Q4068433
cites work: Q4198056
description: scientific article; zbMATH DE number 4130179