| Article ID: | iaor20052551 |
| Country: | France |
| Volume: | 33 |
| Issue: | 3 |
| Start Page Number: | 367 |
| End Page Number: | 370 |
| Publication Date: | Jul 1999 |
| Journal: | RAIRO Operations Research |
| Authors: | Bampis Evripidis |
| Keywords: | graphs |
We show that the problem of deciding is there is a schedule of length three for the multiprocessor scheduling problem on identical machines and unit execution time tasks in NP-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.