Two Deadline Reduction Algorithms for Scheduling Dependent Tasks on Parallel Processors
| Autor: | Claire Hanen, Alix Munier Kordon, Theo Pedersen |
|---|---|
| Přispěvatelé: | Recherche Opérationnelle (RO), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Architecture et Logiciels pour Systèmes Embarqués sur Puce (ALSOC), Université Paris Nanterre (UPN) |
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
Scheduling problems
Job shop scheduling Computer science Extension (predicate logic) Star (graph theory) Decision problem Notation Nonpreemptive multitasking Scheduling (computing) Reduction (complexity) Preemptive relaxation Precedence constraints [INFO]Computer Science [cs] Algorithm Energetic reasoning |
| Zdroj: | Integration of Constraint Programming, Artificial Intelligence, and Operations Research CPAIOR 2021: Integration of Constraint Programming, Artificial Intelligence, and Operations Research CPAIOR 2021: Integration of Constraint Programming, Artificial Intelligence, and Operations Research, Jul 2021, Vienne, Austria. pp.214-230, ⟨10.1007/978-3-030-78230-6_14⟩ Integration of Constraint Programming, Artificial Intelligence, and Operations Research ISBN: 9783030782290 CPAIOR |
| Popis: | International audience; 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|prec,ri,di|⋆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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|