nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

Precedence-Constrained Scheduling and Min-Sum Set Cover

(Extended Abstract)

verfasst von : Felix Happach, Andreas S. Schulz

Erschienen in: Approximation and Online Algorithms

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We consider a single-machine scheduling problem with bipartite AND/OR-constraints that is a natural generalization of (precedence-constrained) min-sum set cover. For min-sum set cover, Feige, Lovàsz and Tetali [15] showed that the greedy algorithm has an approximation guarantee of 4, and obtaining a better approximation ratio is NP-hard. For precedence-constrained min-sum set cover, McClintock, Mestre and Wirth [30] proposed an \(O(\sqrt{m})\)-approximation algorithm, where m is the number of sets. They also showed that obtaining an algorithm with performance \(O(m^{1/12-\varepsilon })\) is impossible, assuming the hardness of the planted dense subgraph problem.

The more general problem examined here is itself a special case of scheduling AND/OR-networks on a single machine, which was studied by Erlebach, Kääb and Möhring [13]. Erlebach et al. proposed an approximation algorithm whose performance guarantee grows linearly with the number of jobs, which is close to best possible, unless P = NP.

For the problem considered here, we give a new LP-based approximation algorithm. Its performance ratio depends only on the maximum number of OR-predecessors of any one job. In particular, in many relevant instances, it has a better worst-case guarantee than the algorithm by McClintock et al., and it also improves upon the algorithm by Erlebach et al. (for the special case considered here).

Yet another important generalization of min-sum set cover is generalized min-sum set cover, for which a 12.4-approximation was derived by Im, Sviridenko and Zwaan [23]. Im et al. conjecture that generalized min-sum set cover admits a 4-approximation, as does min-sum set cover. In support of this conjecture, we present a 4-approximation algorithm for another interesting special case, namely when each job requires that no less than all but one of its predecessors are completed before it can be processed.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Approximate Strong Edge-Colouring of Unit Disk Graphs

Nächstes Kapitel Fault Tolerant Clustering with Outliers

A random graph drawn from (m, p) contains m vertices and the probability of the existence of an edge between any two vertices is equal to p.

One can also show that \(mc(\cdot ,k)\) and \(f_k(\cdot )\) are supermodular for any k.

Ambühl, C., Mastrolilli, M.: Single machine precedence constrained scheduling is a vertex cover problem. Algorithmica 53(4), 488–503 (2009). https://doi.org/10.1007/s00453-008-9251-6MathSciNetCrossRefMATH

Ambühl, C., Mastrolilli, M., Mutsanas, N., Svensson, O.: On the approximability of single-machine scheduling with precedence constraints. Math. Oper. Res. 36(4), 653–669 (2011). https://doi.org/10.1287/moor.1110.0512MathSciNetCrossRefMATH

Azar, Y., Gamzu, I., Yin, X.: Multiple intents re-ranking. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, pp. 669–678. ACM (2009). https://doi.org/10.1145/1536414.1536505

Bansal, N., Gupta, A., Krishnaswamy, R.: A constant factor approximation algorithm for generalized min-sum set cover. In: Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1539–1545. SIAM (2010). https://doi.org/10.1137/1.9781611973075.125

Bansal, N., Khot, S.: Optimal long code test with one free bit. In: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, pp. 453–462. IEEE (2009). https://doi.org/10.1109/FOCS.2009.23

Bar-Noy, A., Bellare, M., Halldórsson, M.M., Shachnai, H., Tamir, T.: On chromatic sums and distributed resource allocation. Inf. Comput. 140(2), 183–202 (1998). https://doi.org/10.1006/inco.1997.2677MathSciNetCrossRefMATH

Charikar, M., Naamad, Y., Wirth, A.: On approximating target set selection. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Leibniz International Proceedings in Informatics (LIPIcs), vol. 60, pp. 4:1–4:16 (2016). https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2016.4

Chekuri, C., Motwani, R.: Precedence constrained scheduling to minimize sum of weighted completion times on a single machine. Discrete Appl. Math. 98(1–2), 29–38 (1999). https://doi.org/10.1016/S0166-218X(98)00143-7MathSciNetCrossRefMATH

Chekuri, C., Motwani, R., Natarajan, B., Stein, C.: Approximation techniques for average completion time scheduling. SIAM J. Comput. 31(1), 146–166 (2001). https://doi.org/10.1137/S0097539797327180MathSciNetCrossRefMATH

10.

Chudak, F.A., Hochbaum, D.S.: A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine. Oper. Res. Lett. 25(5), 199–204 (1999). https://doi.org/10.1016/S0167-6377(99)00056-5MathSciNetCrossRefMATH

11.

Correa, J.R., Schulz, A.S.: Single-machine scheduling with precedence constraints. Math. Oper. Res. 30(4), 1005–1021 (2005). https://doi.org/10.1287/moor.1050.0158MathSciNetCrossRefMATH

12.

Dinur, I., Steurer, D.: Analytical approach to parallel repetition. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pp. 624–633. ACM (2014). https://doi.org/10.1145/2591796.2591884

13.

Erlebach, T., Kääb, V., Möhring, R.H.: Scheduling AND/OR-networks on identical parallel machines. In: Solis-Oba, R., Jansen, K. (eds.) WAOA 2003. LNCS, vol. 2909, pp. 123–136. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24592-6_10CrossRefMATH

14.

Feige, U., Lovász, L., Tetali, P.: Approximating min-sum set cover. In: Jansen, K., Leonardi, S., Vazirani, V. (eds.) APPROX 2002. LNCS, vol. 2462, pp. 94–107. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45753-4_10CrossRef

15.

Feige, U., Lovász, L., Tetali, P.: Approximating min sum set cover. Algorithmica 40(4), 219–234 (2004). https://doi.org/10.1007/s00453-004-1110-5MathSciNetCrossRefMATH

16.

Goemans, M.X.: Cited as personal communication in [35] (1996)

17.

Goemans, M.X., Queyranne, M., Schulz, A.S., Skutella, M., Wang, Y.: Single machine scheduling with release dates. SIAM J. Discrete Math. 15(2), 165–192 (2002). https://doi.org/10.1137/S089548019936223XMathSciNetCrossRefMATH

18.

Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Optimization and approximation in deterministic sequencing and scheduling: a survey. In: Annals of Discrete Mathematics, vol. 5, pp. 287–326. Elsevier (1979). https://doi.org/10.1016/S0167-5060(08)70356-X

19.

Hall, L.A., Schulz, A.S., Shmoys, D.B., Wein, J.: Scheduling to minimize average completion time: off-line and on-line approximation algorithms. Math. Oper. Res. 22(3), 513–544 (1997). https://doi.org/10.1287/moor.22.3.513MathSciNetCrossRefMATH

20.

Hall, L.A., Shmoys, D.B., Wein, J.: Scheduling to minimize average completion time: off-line and on-line algorithms. In: Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 142–151. SIAM (1996)

21.

Happach, F.: Makespan minimization with OR-precedence constraints. arXiv preprint arXiv:1907.08111 (2019)

22.

Hochbaum, D.S.: Approximation algorithms for the set covering and vertex cover problems. SIAM J. Comput. 11(3), 555–556 (1982). https://doi.org/10.1137/0211045MathSciNetCrossRefMATH

23.

Im, S., Sviridenko, M., van der Zwaan, R.: Preemptive and non-preemptive generalized min sum set cover. Math. Program. 145(1–2), 377–401 (2014). https://doi.org/10.1007/s10107-013-0651-2MathSciNetCrossRefMATH

24.

Johannes, B.: On the complexity of scheduling unit-time jobs with OR-precedence constraints. Oper. Res. Lett. 33(6), 587–596 (2005). https://doi.org/10.1016/j.orl.2004.11.009MathSciNetCrossRefMATH

25.

Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9(3), 256–278 (1974). https://doi.org/10.1016/S0022-0000(74)80044-9MathSciNetCrossRefMATH

26.

Khot, S.: On the power of unique 2-prover 1-round games. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing, pp. 767–775. ACM (2002). https://doi.org/10.1145/509907.510017

27.

Lenstra, J.K., Rinnooy Kan, A.H.G.: Complexity of scheduling under precedence constraints. Oper. Res. 26(1), 22–35 (1978). https://doi.org/10.1287/opre.26.1.22MathSciNetCrossRef

28.

Lovász, L.: On the ratio of optimal integral and fractional covers. Discrete Math. 13(4), 383–390 (1975). https://doi.org/10.1016/0012-365X(75)90058-8MathSciNetCrossRefMATH

29.

Margot, F., Queyranne, M., Wang, Y.: Decompositions, network flows, and a precedence constrained single-machine scheduling problem. Oper. Res. 51(6), 981–992 (2003). https://doi.org/10.1287/opre.51.6.981.24912MathSciNetCrossRefMATH

30.

McClintock, J., Mestre, J., Wirth, A.: Precedence-constrained min sum set cover. In: 28th International Symposium on Algorithms and Computation. Leibniz International Proceedings in Informatics (LIPIcs), vol. 92, pp. 55:1–55:12 (2017). https://doi.org/10.4230/LIPIcs.ISAAC.2017.55

31.

Munagala, K., Babu, S., Motwani, R., Widom, J.: The pipelined set cover problem. In: Eiter, T., Libkin, L. (eds.) ICDT 2005. LNCS, vol. 3363, pp. 83–98. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-30570-5_6CrossRef

32.

Potts, C.N.: An algorithm for the single machine sequencing problem with precedence constraints. Math. Program. Study 13, 78–87 (1980)MathSciNetCrossRef

33.

Queyranne, M.: Structure of a simple scheduling polyhedron. Math. Program. 58(1–3), 263–285 (1993). https://doi.org/10.1007/BF01581271MathSciNetCrossRefMATH

34.

Schulz, A.S.: Scheduling to minimize total weighted completion time: performance guarantees of LP-based heuristics and lower bounds. In: Cunningham, W.H., McCormick, S.T., Queyranne, M. (eds.) IPCO 1996. LNCS, vol. 1084, pp. 301–315. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-61310-2_23CrossRef

35.

Schulz, A.S., Skutella, M.: Random-based scheduling new approximations and LP lower bounds. In: Rolim, J. (ed.) RANDOM 1997. LNCS, vol. 1269, pp. 119–133. Springer, Heidelberg (1997). https://doi.org/10.1007/3-540-63248-4_11CrossRef

36.

Sidney, J.B.: Decomposition algorithms for single-machine sequencing with precedence relations and deferral costs. Oper. Res. 23(2), 283–298 (1975). https://doi.org/10.1287/opre.23.2.283MathSciNetCrossRefMATH

37.

Skutella, M., Williamson, D.P.: A note on the generalized min-sum set cover problem. Oper. Res. Lett. 39(6), 433–436 (2011). https://doi.org/10.1016/j.orl.2011.08.002MathSciNetCrossRefMATH

38.

Smith, W.E.: Various optimizers for single-stage production. Nav. Res. Logist. Q. 3(1–2), 59–66 (1956). https://doi.org/10.1002/nav.3800030106MathSciNetCrossRef

39.

Sousa, J.P., Wolsey, L.A.: A time indexed formulation of non-preemptive single machine scheduling problems. Math. Program. 54(1–3), 353–367 (1992). https://doi.org/10.1007/BF01586059CrossRefMATH

40.

Woeginger, G.J.: On the approximability of average completion time scheduling under precedence constraints. Discrete Appl. Math. 131(1), 237–252 (2003). https://doi.org/10.1016/S0166-218X(02)00427-4MathSciNetCrossRefMATH

41.

Wolsey, L.A.: Mixed integer programming formulations for production planning and scheduling problems. Invited Talk at the 12th International Symposium on Mathematical Programming (1985)

Titel: Precedence-Constrained Scheduling and Min-Sum Set Cover
verfasst von: Felix Happach
Andreas S. Schulz
Verlag: Springer International Publishing
Buch: Approximation and Online Algorithms
Print ISBN: 978-3-030-39478-3

Electronic ISBN: 978-3-030-39479-0

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-39479-0_12

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"