Three notes on scheduling unit-length jobs with precedence constraints to minimize the total completion time

In this paper, we provide three notes on scheduling unit-length jobs with precedence constraints to minimize the total completion time. First, we propose an exact algorithm for in-trees, of which the complexity depends mainly on the graph height, i.e., the length of the longest chain of the precedence graph. We show that this work improves the algorithm in the literature both theoretically and experimentally. Second, we close the open problem for level-orders by showing how it is polynomially solvable. Third, we prove that preemptive scheduling in-trees is strongly NP-hard with arbitrary number of machines, of which the complexity was also open.