Nonpreemptive scheduling of independent tasks with prespecified processor allocations

L. Bianco, P. Dell'Olmo and M. Grazia Speranza

Naval Research Logistics (NRL), 1994, vol. 41, issue 7, 959-971

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 John Wiley & Sons, Inc.

Date: 1994
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1002/1520-6750(199412)41:73.0.CO;2-K

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:41:y:1994:i:7:p:959-971

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().