Hostname: page-component-848d4c4894-tn8tq Total loading time: 0 Render date: 2024-07-07T23:23:21.784Z Has data issue: false hasContentIssue false
  • English
  • Français

The complexity of short schedulesfor uet bipartite graphs

Published online by Cambridge University Press:  15 August 2002

Evripidis Bampis
Evripidis Bampis*
Affiliation:
LaMI, Université d'Evry Val d'Essonne, 91025 Evry Cedex, France E-mail: [email protected]
Get access

Abstract

We show that the problem of deciding if there is a schedule of length three for the multiprocessor scheduling problem on identical machines and unit execution time tasks in -complete even for bipartite graphs, i.e. for precedence graphs of depth one. This complexity result extends a classical result of Lenstra and Rinnoy Kan [5].

Keywords

Schedulemultiprocessorbipartite graphcomplexity.
Type
Research Article
Information
RAIRO - Operations Research , Volume 33 , Issue 3 , July 1999 , pp. 367 - 370
Copyright
© EDP Sciences, 1999

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)