The complexity of short schedules for uet bipartite graphs

Authors
Bampis, E
Citation
E. Bampis, The complexity of short schedules for uet bipartite graphs, RAIRO RE OP, 33(3), 1999, pp. 367-370
Citations number
9
Categorie Soggetti
Engineering Mathematics
Journal title
RAIRO-RECHERCHE OPERATIONNELLE-OPERATIONS RESEARCH
ISSN journal
03990559 → ACNP
Volume
33
Issue
3
Year of publication
1999
Pages
367 - 370
Database
ISI
SICI code
0399-0559(1999)33:3<367:TCOSSF>2.0.ZU;2-8
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 e xecution lime tasks in NP-complete even for bipartite graphs, i.e. for prec edence graphs of depth one. This complexity result extends a classical resu lt of Lenstra and Rinnoy Kan [5].