Brucker et al. (Math Methods Oper Res 56: 407-412, 2003) have given an O(n 2)-time algorithm for the problems P | pj = 1, r j , outtree |∑ Cj and P | pmtn, pj = 1, rj, outtree | ∑ Cj . In this note, we show that their algorithm admits an O(n log n)-time implementation.
All Science Journal Classification (ASJC) codes
- Management Science and Operations Research
- Nonpreemptive scheduling
- Parallel and identical machines
- Preemptive scheduling
- Total completion time