Hero Image
- Mihai Surdeanu

Algoritm pentru planificarea optimă a unor pași dintr-un workflow

Să spunem că vrei să implementezi un algoritm de planificare automată a unui set de pași, parte a unui workflow, în care fiecare pas poate depinde de unul sau mai mulți pași din acesta. Bineînțeles că algoritmul pe care dorim să îl implementăm, se dorește a fi cât mai optim, în așa fel încât să genereze cea mai bună variantă de planificare a tuturor pașilor (unii pași pot fi în paralel executați), în așa fel încât să se minimizeze timpul de rulare al întreg workflow-ului.

O să dau și un exemplu pentru a face lucrurile și mai clare. Să zicem că ai un workflow alcătuit din 5 pași: p1, p2, p3, p4, p5 și următoarea listă de dependințe între aceștia:

  • p3 -> p1 și p2 (Înterpretare: p3 depinde de p1 și p2)
  • p4 -> p3 (Înterpretare: p4 depinde de p3)
  • p5 -> p1 (Înterpretare: p5 depinde de p1)

simple

Nice. Ce ar însemna în realitatea de zi cu zi ca un pas să depinde de altul? Păi foarte simplu. Ar însemna că pentru a executa un pas din workflow, vei avea nevoie de outputul altuia.

Având în vedere aceste constrângeri, algoritmul de planificare ar trebui să scoată următorul output pentru executarea cât mai optimă a workflow-ului:

  • [(p1, p2), (p3, p5), p4], unde (*) înseamnă un set de pași executați în paralel iar [*] înseamnă un set de pași executați secvențial.

Se cere să se implementeze un algoritm prin care să se obțină cel mai bun mod de planificare posibil.

O posibilă implementare

Putem construi un graf, nodurile fiind pașii, iar arcele dependințele dintre acestea. Graful îl putem reprezenta ca și o matrice, în care atât pe linii cât și pe coloane avem pașii. Mai departe, în matrice putem pune 1 dacă există o dependință sau 0 dacă nu există. Având în vedere toate aceste observații, vom avea următoarea matrice:

p1 p2 p3 p4 p5
p1 0 0 0 0 0
p2 0 0 0 0 0
p3 1 1 0 0 0
p4 0 0 1 0 0
p5 1 0 0 0 0

Ce înseamnă să am pe o linie 0, în matricea de mai sus? Simplu. Înseamnă că pasul respectiv (dat de linia asociată) nu depinde de niciun alt pas. Asta este ideal pentru noi, pentru că înseamnă că putem extrage pasul respectiv și îl putem planifica spre execuție. Cu alte cuvinte, putem extrage pașii p1 și p2. O dată ce am extras toți pașii în care există 0 pe linii, pot să merg mai departe și să marchez aceste linii cu -1 și totadată să pun 0 pe toate coloanele de unde am extras diverși pași.

Matricea după prima rundă de extrageri:

p1 p2 p3 p4 p5
p1 -1 -1 -1 -1 -1
p2 -1 -1 -1 -1 -1
p3 0 0 0 0 0
p4 0 0 1 0 0
p5 0 0 0 0 0

Continuăm cu runda 2, prin a extrage alți pași care au pe linie numai 0. În acest caz, vorbim de pașii p3 și p5. Acești pași pot fi executați în paralel. Cu aceste modificări, matricea devine:

p1 p2 p3 p4 p5
p1 -1 -1 -1 -1 -1
p2 -1 -1 -1 -1 -1
p3 -1 -1 -1 -1 -1
p4 0 0 0 0 0
p5 -1 -1 -1 -1 -1

Ultimul pas este să extragem p4. Algoritmul se oprește când toate matricea conține numai -1.

Planul cel mai optim de execuție este: [(p1, p2), (p3, p5), p4]

Ce facem cu dependințele ciclice?

Să spunem că avem doar 3 pași în workflow, pași care depind unul de altul în modul următor:

  • p2 -> p1
  • p3 -> p2
  • p1 -> p3

cyclic

Aici avem o dependință ciclică indirectă. Cum ar arăta matricea noastră:

p1 p2 p3
p1 0 0 1
p2 1 0 0
p3 0 1 0

După cum se poate observa, în cazul în care nu se poate extrage nicio linie completă cu 0, atunci algoritmul se va opri pentru că vom avea cu siguranță o dependință ciclică directă sau indirectă.

Acestea fiind spuse, vă urez un călduros: spor la implementat! 🙂

Related Posts:

Algoritm pentru determinarea celui mai sigur loc pentru a viziona un film pe timp de Covid

Algoritm pentru determinarea celui mai sigur loc pentru a viziona un film pe timp de Covid

Dragilor,

Revin astăzi cu o nouă problemă, de actualitate pentru vremurile în care trăim noi acum. Să zicem să vreau să mă duc la cinematograf, în vreme de pandemie, pentru a viziona un film și am bilet pe un anumit rând. Nu aș vrea totuși să stau pe locul care mi s-a oferit, ci aș vrea să îmi determin singur locul pe rând unde aș vrea să stau în așa fel încât să fie cât mai safe pentru mine. Ce înseamnă cât mai safe pentru mine, înseamnă să stau cât mai departe de cineva atât în partea stangă cât și în partea dreaptă.

17th Jan 2022 - Mihai Surdeanu

Comments:

Blog Comments powered by Disqus.