Shortest path to nonpreemptive schedules of unit-time jobs on two identical parallel machines with minimum total completion time (Q706379)

In this paper two-machine scheduling problems with unit processing times, release dates, precedence constraints and minimum total completion time are studied. More specifically, it is shown that problems \(P2| prec,r_j,p_j=1| \sum C_j\) and \(F2| prec,r_j,p_j=1| \sum C_j\) are polynomially solvable by reducing them to shortest path problems. Furthermore, the concept of ideal schedules (minimizing the makespan and total completion time simultaneously) is discusssed.