Algoritm hibrid de planificare a unui set de activităţi

1. Introducere..............................................................................4
1.1 Contextul alegerii temei...........................................................4
1.2 Introducere în problematica planificării unui set de activităţi......4
1.2.1 Definiţie si relaţia cu alte teme..............................................4
1.2.2 Conceptul de configuraţie....................................................5
1.2.3 Planificarea văzută ca o problemă de satisfacere a constrângerilor (CSP)....5
1.2.4 Tehnici generale de rezolvare pentru CSP............................6
1.2.5 Definirea constrângerilor......................................................7
1.2.6 Un scurt istoric al tehnicilor de planificare şi stadiul actual al cunoaşterii..7
1.3 Algoritmul descris şi implementat în lucrare..............................9
1.3.1 Algoritmul CBSR................................................................9
1.3.2 Algoritmul propriu..............................................................10
1.4 Rezultatele obţinute ...............................................................10

2. Problema de planificare a unei set de activităţi..........................11
2.1 Formalizarea problemei de planificare....................................11
2.2 Evaluarea configuraţiilor........................................................11
2.3 Algoritmi de căutare locală....................................................12
2.3.1 Noţiunea de vecinătate......................................................12
2.3.2 Relieful mulţimii de configuraţii C.......................................14
2.3.3 Algoritmii de căutare locală şi problema de planificare.......15
2.3.4 Algoritmul gradient descent..............................................15
2.3.5 Algoritmul tabu search.....................................................16
2.3.6 Algoritmul simulated annealing.........................................17
2.3.7 Metaeuristica iterated local search...................................18
2.4 Punctul de plecare..............................................................20
2.4.1 Considerente generale.....................................................20
2.4.2 Metoda F-RACE............................................................20
2.4.3 Structurile de date folosite în cadrul algoritmului CBSR.....21
2.4.4 Descrierea detaliată a algoritmului CBSR..........................22
2.4.5 Motivarea alegerii şablonului propus în cadrul algoritmului CBSR...24
2.5 Abordarea proprie..............................................................25
2.5.1 Considerente generale......................................................25
2.5.2 Ideea...............................................................................25
2.5.3 Calculul paralel.................................................................26
2.5.4 Mecanismul de triere al thread-urilor.................................27
2.5.5 Pseudocodul algoritmului propus......................................27
2.5.6 Sfaturi utile în vederea implementării algoritmului...............32
3. Prezentarea aplicaţiei software...............................................33
3.1 Considerente generale.........................................................33
3.2 Tipurile de constrângeri suportate........................................33
3.3 Funcţionalităţile oferite şi modul de utilizare..........................34
3.4 Structura aplicaţiei software................................................35
3.4.1 Organizarea codului........................................................35
3.4.2 Structurile de date folosite...............................................36
3.4.3 Euristicile de construcţie folosite......................................37
3.4.4 Mecanismul de multi-threading ......................................37
3.4.5 Secţiuni de interes..........................................................38
4. Concluzii finale...................................................................40
4.1 Testarea aplicaţiei software şi rezultatele obţinute..............40
4.2 Planificarea rămâne o problemă deschisă..........................42
4.3 Direcţii viitoare de dezvoltare...........................................42
4.4 Exemple de orare obţinute folosind aplicaţia software creată....43 Bibliografie.............................................................................46