| Article ID: | iaor20127625 |
| Volume: | 33 |
| Issue: | 3 |
| Start Page Number: | 367 |
| End Page Number: | 370 |
| Publication Date: | Jul 1999 |
| Journal: | RAIRO - Operations Research |
| Authors: | Bampis Evripidis |
| Keywords: | combinatorial optimization |
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].