SCHEDULING CHAINS TO MINIMIZE MEAN FLOW TIME

Authors
DROR M KUBIAK W DELLOLMO P
Citation
M. Dror et al., SCHEDULING CHAINS TO MINIMIZE MEAN FLOW TIME, Information processing letters, 61(6), 1997, pp. 297-301
Citations number
7
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
61
Issue
6
Year of publication
1997
Pages
297 - 301
Database
ISI
SICI code
0020-0190(1997)61:6<297:SCTMMF>2.0.ZU;2-N
Abstract
In this note we consider the chain precedence relation in scheduling a nd distinguish between strong chains and weak chains. We prove that fo r two identical parallel processors the mean flow time problem with st rong chains can be solved in polynomial time whereas for weak chains t he same problem is NP-hard in the strong sense. (C) 1997 Elsevier Scie nce B.V.