van Zuylen, Anke An improved monotone algorithm for scheduling related machines with precedence constraints. (English) Zbl 1235.90070 Oper. Res. Lett. 39, No. 6, 423-427 (2011). Summary: We answer an open question posed by S. O. Krumke et al. [Oper. Res. Lett. 36, No. 2, 247–249 (2008; Zbl 1144.90384)] by showing how to turn the algorithm of Chekuri and Bender for scheduling related machines with precedence constraints into an \(O(\log m)\)-approximation algorithm that is monotone in expectation. This significantly improves on the previously best known monotone approximation algorithms for this problem, from [loc.cit.] and Thielen and Krumke (2008), which have an approximation guarantee of \(O(m^{2/3})\). MSC: 90B35 Deterministic scheduling theory in operations research 90C59 Approximation methods and heuristics in mathematical programming 90C60 Abstract computational complexity for mathematical programming problems Keywords:scheduling; algorithmic mechanism design; precedence constraints; monotone algorithms Citations:Zbl 1144.90384 PDFBibTeX XMLCite \textit{A. van Zuylen}, Oper. Res. Lett. 39, No. 6, 423--427 (2011; Zbl 1235.90070) Full Text: DOI References: [1] Archer, A.; Tardos, E.´, Truthful mechanisms for one-parameter agents, (FOCS’01: 42nd IEEE Symposium on Foundations of Computer Science (2001), IEEE Computer Soc.: IEEE Computer Soc. Los Alamitos, CA), 482-491 [2] Chekuri, C.; Bender, M., An efficient approximation algorithm for minimizing makespan on uniformly related machines, J. Algorithms, 41, 2, 212-224 (2001), Preliminary version appeared in IPCO’98 · Zbl 1051.68150 [3] Chudak, F. A.; Shmoys, D. B., Approximation algorithms for precedence-constrained scheduling problems on parallel machines that run at different speeds, J. Algorithms, 30, 2, 323-343 (1999), Preliminary version appeared in SODA’97 · Zbl 0923.68012 [4] Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Optimization and approximation in deterministic sequencing and scheduling: a survey, Ann. Discrete Math., 5, 287-326 (1979), Discrete optimization (Proc. Adv. Res. Inst. Discrete Optimization and Systems Appl., Banff, Alta., 1977), II · Zbl 0411.90044 [5] Jaffe, J. M., Efficient scheduling of tasks without full use of processor resources, Theoret. Comput. Sci., 12, 1, 1-17 (1980) · Zbl 0446.68027 [6] Krumke, S. O.; Schwahn, A.; van Stee, R.; Westphal, S., A monotone approximation algorithm for scheduling with precedence constraints, Oper. Res. Lett., 36, 2, 247-249 (2008) · Zbl 1144.90384 [7] Shmoys, D. B.; Wein, J.; Williamson, D. P., Scheduling parallel machines on-line, SIAM J. Comput., 24, 6, 1313-1331 (1995), Preliminary version appeared in FOCS’91 · Zbl 0845.68042 [8] C. Thielen, S.O. Krumke, A general scheme for designing monotone algorithms for scheduling problems with precedence constraints, in: WAOA’08: 6th International Workshop on Approximation and Online Algorithms, 2008, pp. 105-118.; C. Thielen, S.O. Krumke, A general scheme for designing monotone algorithms for scheduling problems with precedence constraints, in: WAOA’08: 6th International Workshop on Approximation and Online Algorithms, 2008, pp. 105-118. · Zbl 1209.90187 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.