nach oben

Erschienen in:

2021 | OriginalPaper | Buchkapitel

Two Deadline Reduction Algorithms for Scheduling Dependent Tasks on Parallel Processors

verfasst von : Claire Hanen, Alix Munier Kordon, Theo Pedersen

Erschienen in: Integration of Constraint Programming, Artificial Intelligence, and Operations Research

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

This paper proposes two deadline adjustment techniques for scheduling non preemptive tasks subject to precedence relations, release dates and deadlines on a limited number of processors. This decision problem is denoted by \(P\vert prec, r_i, d_i\vert \star \) in standard notations. The first technique is an extension of the Garey and Johnson algorithm that integrates precedence relations in energetic reasoning. The second one is an extension of the Leung, Palem and Pnueli algorithm that builds iteratively relaxed preemptive schedules to adjust deadlines.

The implementation of the two classes of algorithms is discussed and compared on randomly generated instances. We show that the adjustments obtained are slightly different but equivalent using several metrics. However, the time performance of the extended Leung, Palem and Pnueli algorithm is much better than that of the extended Garey and Johnson ones.

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 MDDs Boost Equation Solving on Discrete Dynamical Systems

Nächstes Kapitel Improving the Filtering of Branch-and-Bound MDD Solver

Baptiste, P., Le Pape, C., Nuijten, W.: Satisfiability tests and time-bound adjustments for cumulative scheduling problems. Ann. Oper. Res. 92, 305–333 (1999)MathSciNetCrossRef

Bellenguez-Morineau, O.: Methods to solve multi-skill project scheduling problem. 4OR 6(1), 85–88 (2008)

Bonifas, N.: A \(\cal{O}(n^2 \log (n))\) propagation for the energy reasoning. In: Congrès ROADEF, February 2016

Carlier, A., Hanen, C., Kordon, A.M.: The equivalence of two classical list scheduling algorithms for dependent typed tasks with release dates, due dates and precedence delays. J. Sched. 20(3), 303–311 (2017). https://doi.org/10.1007/s10951-016-0507-8MathSciNetCrossRefMATH

Carlier, J., Latapie, B.: Une méthode arborescente pour résoudre les problèmes cumulatifs. RAIRO - Oper. Res. Rech. Opérationnelle 25(3), 311–340 (1991)CrossRef

Carlier, J., Pinson, E., Sahli, A., Jouglet, A.: An \(\cal{O}(n^2)\) algorithm for time-bound adjustments for the cumulative scheduling problem. Eur. J. Oper. Res. 286(2), 468–476 (2020)

Carlier, J., Pinson, E., Sahli, A., Jouglet, A.: Comparison of three classical lower bounds for the cumulative scheduling problem. (submitted) (2021)

Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, Third Edition. The MIT Press, 3rd edn., Cambridge (2009)

Derrien, A., Petit, T.: A new characterization of relevant intervals for energetic reasoning. In: O’Sullivan, B. (ed.) CP 2014. LNCS, vol. 8656, pp. 289–297. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-10428-7_22CrossRef

10.

Edmonds, J., Karp, R.M.: Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM (JACM) 19(2), 248–264 (1972)CrossRef

11.

Garey, M.R., Johnson, D.S.: Two-processor scheduling with start-time and deadlines. SIAM J. Comput. 6, 416–426 (1977)MathSciNetCrossRef

12.

Goldberg, A.V., Tarjan, R.E.: A new approach to the maximum-flow problem. J. ACM (JACM) 35(4), 921–940 (1988)MathSciNetCrossRef

13.

Goldberg, A.V., Tarjan, R.E.: Efficient maximum flow algorithms. Commun. ACM 57(8), 82–89 (2014)CrossRef

14.

Graham, R., Lawler, E., Lenstra, J., Kan, A.: Optimization and approximation in deterministic sequencing and scheduling: a survey. In: Hammer, P., Johnson, E., Korte, B. (eds.) Discrete Optimization II, Annals of Discrete Mathematics, vol. 5, pp. 287–326. Elsevier (1979)

15.

Hanen, C., Munier Kordon, A.: Two deadline reduction algorithms for scheduling dependent typed-tasks systems. In: ROADEF conference (2020)

16.

Hanen, C., Munier Kordon, A., Pedersen, T.: Two deadline reduction algorithm for scheduling dependent tasks on parallel processors (extended version) (2021). https://hal.archives-ouvertes.fr/hal-03200297

17.

Hanen, C., Zinder, Y.: The worst-case analysis of the Garey-Johnson algorithm. J. Sched. 12(4), 389–400 (2009)MathSciNetCrossRef

18.

Haouari, M., Kooli, A., Néron, E.: Enhanced energetic reasoning-based lower bounds for the resource constrained project scheduling problem. Comput. Oper. Res. 39(5), 1187–1194 (2012)MathSciNetCrossRef

19.

Haouari, M., Kooli, A., Néron, E., Carlier, J.: A preemptive bound for the resource constrained project scheduling problem. J. Sched. 17(3), 237–248 (2014)MathSciNetCrossRef

20.

Jackson, J.R.: Scheduling a production line to minimize maximum tardiness. management science research project (1955)

21.

Laborie, P.: Algorithms for propagating resource constraints in AI planning and scheduling: Existing approaches and new results. Artif. Intell. 143(2), 151–188 (2003)MathSciNetCrossRef

22.

Laborie, P., Nuijten, W.: Constraint Programming Formulations and propagation Algorithms, chap. 4, pp. 63–72. Wiley, Hoboken (2008)

23.

Leung, A., Palem, K.V., Pnueli, A.: Scheduling time-constrained instructions on pipelined processors. ACM Trans. Program. Lang. Syst. 23, 73–103 (2001)CrossRef

24.

Lombardi, M., Milano, M.: Optimal methods for resource allocation and scheduling: a cross-disciplinary survey. Constr. An Int. J. 17(1), 51–85 (2012)MathSciNetCrossRef

25.

Martel, C.: Preemptive scheduling with release times, deadlines, and due times. J. Assoc. Comput. Mach. 29(3), 812–829 (1982)MathSciNetCrossRef

26.

Munier Kordon, A.: A fixed-parameter algorithm for scheduling unit dependent tasks on parallel machines with time windows. Discret. Appl. Math. 290, 1–6 (2021)MathSciNetCrossRef

27.

Ouellet, Y., Quimper, C.-G.: A \(O(n \log ^2 n)\) checker and \(O(n^2 \log n)\) filtering algorithm for the energetic reasoning. In: van Hoeve, W.-J. (ed.) CPAIOR 2018. LNCS, vol. 10848, pp. 477–494. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-93031-2_34CrossRefMATH

28.

Tesch, A.: Improving energetic propagations for cumulative scheduling. In: Hooker, J. (ed.) CP 2018. LNCS, vol. 11008, pp. 629–645. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-98334-9_41CrossRef

29.

Ullman, J.: NP-complete scheduling problems. J. Comput. Syst. Sci. 10, 384–393 (1975)MathSciNetCrossRef

Titel: Two Deadline Reduction Algorithms for Scheduling Dependent Tasks on Parallel Processors
verfasst von: Claire Hanen
Alix Munier Kordon
Theo Pedersen
Verlag: Springer International Publishing
Buch: Integration of Constraint Programming, Artificial Intelligence, and Operations Research
Print ISBN: 978-3-030-78229-0

Electronic ISBN: 978-3-030-78230-6

Copyright-Jahr: 2021
DOI: https://doi.org/10.1007/978-3-030-78230-6_14

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"

Premium Partner