×

An improved monotone algorithm for scheduling related machines with precedence constraints. (English) Zbl 1235.90070

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

Citations:

Zbl 1144.90384
PDFBibTeX XMLCite
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.