×

Minimizing total completion time for UET tasks with release time and outtree precedence constraints. (English) Zbl 1109.90040

Summary: P. Brucker, J. Hurink and S. Knust [Math. Methods Oper. Res. 56, No. 3, 407–412 (2002; Zbl 1064.90016)] have given an \(O (n^{2})\)-time algorithm for the problems \(P \mid p_{j} = 1,\;r_{j}\), outtree \(\mid \sum C_{j}\) and \(P \mid pmtn,\;p_{j} = 1,\;r_{j}\), outtree \(\mid \sum C_{j}\). In this note, we show that their algorithm admits an \(O (n \log n)\)-time implementation.

MSC:

90B35 Deterministic scheduling theory in operations research
90C60 Abstract computational complexity for mathematical programming problems

Citations:

Zbl 1064.90016
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aho AV, Hopcroft JE, Ullman JD (1974) The design and analysis of computer algorithms. Addison Wesley, Reading
[2] Brucker P, Hurink J, Knust S. (2003). A polynomial algorithm for \(P \mid p_{j} = 1, r_{j}\) , outtree \(\mid \sum C_{j}\) and \(P \mid pmtn, p_{j} = 1, r_{j}\) , outtree \(\mid \sum C_{j}\) . Math Methods Oper Res 56:407–412 · Zbl 1064.90016 · doi:10.1007/s001860200228
[3] Coffman EG Jr, Graham RL (1972) Optimal scheduling for two-processor systems. Acta Inform 1:200–213 · Zbl 0248.68023 · doi:10.1007/BF00288685
[4] Coffman EG Jr, Sethuraman J, Timkovsky VG (2003) Ideal preemptive schedules on two processors. Acta Inform 39:597–612 · Zbl 1060.68014 · doi:10.1007/s00236-003-0119-6
[5] Graham RL, Lawler EL, Lenstra JK, Rinnooy Kan AHG (1979) Optimization and approximation in deterministic scheduling: a survey. Ann Discrete Math 5:287–326 · Zbl 0411.90044 · doi:10.1016/S0167-5060(08)70356-X
[6] Huo Y, Leung JY-T (2005) Minimizing mean flow time for UET tasks, ”web.njit.edu/eung/mft-uet/paper.ps” · Zbl 1109.90040
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.