Minimizing total completion time for UET tasks with release time and outtree precedence constraints

Brucker et al. (Math Methods Oper Res 56: 407–412, 2003) have given an O(n <Superscript>2</Superscript>)-time algorithm for the problems <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$$P \mid p_{j}=1, r_{j}$$</EquationSource> </InlineEquation>, outtree <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$$\mid \sum C_{j}$$</EquationSource> </InlineEquation> and <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$$P \mid pmtn, p_{j}=1, r_{j}$$</EquationSource> </InlineEquation>, outtree <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$$\mid \sum C_{j}$$</EquationSource> </InlineEquation>. In this note, we show that their algorithm admits an O(n log n)-time implementation. Copyright Springer-Verlag 2005