In this note we consider the chain precedence relation in scheduling and distinguish between strong chains and weak chains. We prove that for two identical parallel processors the mean flow time problem with strong chains can be solved in polynomial time whereas for weak chains the same problem is NP-hard in the strong sense
Scheduling Chains to Minimize Mean Flow Time / Dror, M.; Kubiak, W.; Dell'Olmo, Paolo. - In: INFORMATION PROCESSING LETTERS. - ISSN 0020-0190. - STAMPA. - 61:(1997), pp. 297-301.
Scheduling Chains to Minimize Mean Flow Time
DELL'OLMO, Paolo
1997
Abstract
In this note we consider the chain precedence relation in scheduling and distinguish between strong chains and weak chains. We prove that for two identical parallel processors the mean flow time problem with strong chains can be solved in polynomial time whereas for weak chains the same problem is NP-hard in the strong senseFile allegati a questo prodotto
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
