Premium
Mean flow scheduling and optimal construction of a treelike communication network
Author(s) -
Perl Yehoshua,
Yesha Yaacov
Publication year - 1981
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230110111
Subject(s) - scheduling (production processes) , computer science , mathematical optimization , algorithm , french horn , mathematics , psychology , pedagogy
Horn's algorithm for weighted mean flow scheduling with treelike precedence constraints is reexamined. A new analysis of an efficient implementation of Horn's algorithm shows an O(n log n) complexity. This is an improvement on the known O(n 2 ) complexity of this algorithm. An application of Horn's algorithm to a problem of optimal scheduling of a treelike communication network is presented.