Dedicated scheduling of biprocessor tasks to minimize mean flow times

Abstract. This paper investigates the complexity of scheduling bipro-cessor 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 par-ticular interest are acyclic graphs. In this way we identify a borderline between NP-hard and polynomially solvable special cases.