This paper investigates the complexity of scheduling biprocessor tasks on dedicated processors to minimize mean flow time.
Since the general problem is strongly NP-hard, we assume some restrictions on task lengths and the structure of associated
scheduling graphs. Of particular interest are acyclic graphs. In this way we identify a borderline between NP-hard and polynomially
solvable special cases.