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)

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:

Planificare propusă: [(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.

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:

p1p2p3p4p5
p100000
p200000
p311000
p400100
p510000
Matricea inițială

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 totată să pun 0 pe toate coloanele de unde am extras diverși pași.

p1p2p3p4p5
p1-1-1-1-1-1
p2-1-1-1-1-1
p300000
p400100
p500000
Matricea după prima rundă de extrageri

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:

p1p2p3p4p5
p1-1-1-1-1-1
p2-1-1-1-1-1
p3-1-1-1-1-1
p400000
p5-1-1-1-1-1
Matricea după a doua rundă de extrageri

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

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

Excepții – dependințe 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

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

p1p2p3
p1001
p2100
p3010

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! 🙂

Mihai

Pasionat de IT. Pasionat de viață. Pasionat de tot ceea ce înseamnă a face o viață mai bună, plină de înțelegere, ajutor reciproc și iubire de aproape.

Adaugă comentariu

Arhive

Arhiva personală