In this article we study the problem of scheduling independent tasks, each of which requires the simultaneous availability of a set of prespecified processors, with the objective of minimizing the maximum completion time. We propose a graph-theoretical approach and identify a class of polynomial instances, corresponding to comparability graphs. We show that the scheduling problem is polynomially equivalent to the problem of extending a graph to a comparability graph whose maximum weighted clique has minimum weight. Using this formulation we show that in some cases it is possible to decompose the problem according to the canonical decomposition of the graph. Finally, a general solution procedure is given that includes a branch-and-bound algorithm for the solution of subproblems which can be neither decomposed nor solved in polynomial time. Some examples and computational results are presented.

Nonpreemptive Scheduling of Independent Tasks with Prespecified Processor Allocations / Bianco, L.; Dell'Olmo, Paolo; Speranza, M. G.. - In: NAVAL RESEARCH LOGISTICS. - ISSN 0894-069X. - STAMPA. - 41:(1994), pp. 959-971.

Nonpreemptive Scheduling of Independent Tasks with Prespecified Processor Allocations

DELL'OLMO, Paolo;
1994

Abstract

In this article we study the problem of scheduling independent tasks, each of which requires the simultaneous availability of a set of prespecified processors, with the objective of minimizing the maximum completion time. We propose a graph-theoretical approach and identify a class of polynomial instances, corresponding to comparability graphs. We show that the scheduling problem is polynomially equivalent to the problem of extending a graph to a comparability graph whose maximum weighted clique has minimum weight. Using this formulation we show that in some cases it is possible to decompose the problem according to the canonical decomposition of the graph. Finally, a general solution procedure is given that includes a branch-and-bound algorithm for the solution of subproblems which can be neither decomposed nor solved in polynomial time. Some examples and computational results are presented.
1994
PARALLEL PROCESSING SYSTEMS; ALGORITMI; COMPUTATIONAL COMPLEXITY
01 Pubblicazione su rivista::01a Articolo in rivista
Nonpreemptive Scheduling of Independent Tasks with Prespecified Processor Allocations / Bianco, L.; Dell'Olmo, Paolo; Speranza, M. G.. - In: NAVAL RESEARCH LOGISTICS. - ISSN 0894-069X. - STAMPA. - 41:(1994), pp. 959-971.
File 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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/47554
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 24
  • ???jsp.display-item.citation.isi??? 22
social impact