library(hours2lessons)
Asumăm existența unui set de date (data.frame) cu câte o linie pentru fiecare dintre lecțiile prof|cls ale unei zile de lucru, cu următoarele proprietăți principale (caracteristice unui orar școlar): fiecare profesor apare de cel mult 7 ori (și la o aceeași clasă, de cel mult două ori); fiecare clasă apare de cel puțin 4 ori și cel mult 7 ori (altfel spus, profesorii au câte cel mult 7 ore/zi; clasele au între 4 și 7 ore/zi). Ca exemplu este furnizat setul de lecții LSS.
În coloana prof avem coduri (în loc de “numele profesorilor”) de lungime 3 sau 6, semnificând disciplina principală a profesorului (abreviată pe două litere) și un număr de ordine între cei (cel mult 9) încadrați pe o aceeași disciplină principală; un cod de lungime 6, dacă există, reprezintă un cuplaj (sau “profesor fictiv”), alipind două coduri de lungime 3: cei doi profesori au de făcut lecția respectivă (într-o aceeași oră) cu câte o grupă de elevi ai clasei cls.
str(LSS) # un exemplu de set de lecții
#> tibble [204 × 2] (S3: tbl_df/tbl/data.frame)
#> $ prof: chr [1:204] "Mt1" "Is3" "Ro9" "En4" ...
#> $ cls : chr [1:204] "05A" "05A" "05A" "05A" ...
LSS %>% dplyr::filter(nchar(prof)==6) # listează cuplajele existente
#> # A tibble: 2 × 2
#> prof cls
#> <chr> <chr>
#> 1 Ds1Mz1 12E
#> 2 Fr1Gr1 12D
Admitem și existența unor tuplaje, într-un set suplimentar de date: profesorii din acest set au de intrat în câte o aceeași oră a zilei, la câte o grupă constituită din elevi de la două, trei sau chiar patru clase (sau eventual, la câte una dintre clasele respective); formal, un tuplaj este reprezentat inițial înscriind în prof vectorul profesorilor și în cls vectorul claselor “tuplate” acestora. Ca exemplu este furnizat setul de lecții tuplate Tuplaje.
Tuplaje
#> prof cls
#> 1 Ds1 Mz1 10E 11E
#> 2 Fr2 Fr3 Gr1 09A 09C 09D
#> 3 Fr1 Fr2 Fr3 Gr2 10B 10C 10E
#> 4 Fr1 Fr2 Gr1 11C 11E
De observat că dacă numărul de profesori este (cu 1) mai mare ca al claselor, atunci… avem de înființat noi cuplaje (de exemplu, Fr1Fr2 la clasele 10B și 11C, corespunzător tuplajelor din liniile 3 și 4).
Sarcina pachetului: avem de adăugat pe setul tuturor lecțiilor o coloană ora, astfel încât profesorii (inclusiv cei fictivi) să nu-și suprapună lecțiile (în câte o aceeași oră) și pe de altă parte, profesorii implicați într-un tuplaj să intre într-o aceeași oră, la clasele din tuplajul respectiv (fără suprapunere cu lecțiile vreunui alt tuplaj și nici cu lecțiile proprii ale membrilor tuplajului respectiv).
Parafrazăm aici, algoritmul folosit în funcția mount_hours() pentru a constitui un orar al lecțiilor.
Mai întâi, se investighează setul de tuplaje (dacă există) și dacă este cazul se înființează noi cuplaje (egalând în fiecare tuplaj numărul de clase cu cel de profesori); se completează setul principal de lecții (care conține lecțiile profesorilor și cuplajelor inițiale, din afara tuplajelor) cu lecțiile din setul suplimentar al celor tuplate (dacă există un profesor care cumulează mai mult de 7 ore, atunci… STOP).
Se împart lecțiile după clasă (constituind o listă care asociază fiecărei clase, setul lecțiilor acesteia).
Se parcurge lista claselor, într-o ordine aleatorie dar ponderată de coeficienții betweenness (în ordine crescătoare) rezultați printr-o funcție internă (în care utilizăm două funcții din pachetul igraph) pe graful claselor după numărul de profesori comuni la câte două clase.
Se înființeză un vector care asociază fiecărui profesor câte un octet (inițializat cu 0L) în care urmează să se înregistreze alocările făcute până la momentul curent, lecțiilor profesorului respectiv (un bit 1 în poziția i=0:6 arată că i s-a alocat deja ora (i+1)).
Se etichetează lecțiile clasei curente cu o permutare de ore (după numărul de ore/zi ale clasei); dacă astfel, la vreunul dintre profesorii clasei, se constată o suprapunere cu vreo lecție alocată anterior (la o clasă întâlnită înaintea celei curente), atunci se încearcă o altă permutare de ore (pentru lecțiile clasei curente). Dacă pentru niciuna dintre permutările încercate, nu se poate evita conflictul cu alocările anterioare, atunci… se abandonează parcurgerea mai departe a listei claselor, se reinițializează vectorul octeților de alocare asociați profesorilor și se reia parcurgerea listei claselor, dar într-o altă ordine (aleatoriu, cu “preferințe” date de coeficienții asociați claselor).
Dacă pentru clasa curentă se nimerește o etichetare cu ore convenabilă (fără suprapuneri cu octeții de alocare ai profesorilor clasei, constituiți până la momentul curent), atunci se înregistrează pe biți (în octeții de alocare ai profesorilor clasei) alocarea respectivă și se trece la următoarea clasă.
Corelațiile induse de normele de încadrare a profesorilor (care limitează numărul de ore pe profesor și pe clasă) asigură că la un moment dat (după un număr mai mare sau mai mic de reluări) se va nimeri totuși o ordine de parcurgere a claselor prin care lecțiile fiecărei clase sunt etichetate cu ore, fără conflicte; reunind în final orarele claselor, rezultă orarul prof|cls|ora (în format lung) pe ziua respectivă.
Fiind implicate elemente aleatorii, la fiecare nouă execuție a funcției mount_hours() se va obține de regulă câte un alt orar. Subliniem că nu se are în vedere, numărul de ferestre rezultate pe orarele individuale ale profesorilor (fiind sarcina unui alt pachet, să ajusteze orarul încât numărul total de ferestre să fie cât se poate de mic).
Funcția long2matrix() transformă orarul din “formatul lung” într-o matrice în care fiecare linie indică pentru câte un profesor, clasele la care va intra acesta în fiecare oră (iar “-” marchează o fereastră sau o oră liberă, din afara orarului individual respectiv).
De exemplu, pentru seturile LSS și Tuplaje găsim orarul profesorilor angajați în cuplaje sau în tuplaje (cu sublinierea că la o nouă execuție, vom obține un alt orar, poate în mai puține încercări, poate mai bun sau poate, mai rău):
mount_hours(LSS, Tuplaje) %>% as.data.frame() %>%
dplyr::filter(grepl("Fr|Gr|Ds|Mz", .$prof)) %>%
long2matrix() %>% as.data.frame()
#> 1 2 3 4 5 6 7
#> Ds1Mz1 - - 12E - - - -
#> Fr1Gr1 - - - 12D - - -
#> Gr2 - 10E - - 05A - -
#> Fr1Fr2 - 10B 11C - - - -
#> Fr3 - 10C - - 09C - -
#> Gr1 11E 07C 11E - 09D - -
#> Fr1 06C - - - 10B - -
#> Ds1 07A 06B - 09E - 10E -
#> Fr2 - - - - 09A 10C 11C
#> Mz1 05C - - 07D 08B 11E -
În ora în care profesorul fictiv Ds1Mz1 intră la clasa 12E, profesorii Ds1 și Mz1 nu au ore proprii (încât pot intra împreună, pe grupe, la 12E); observăm la fel, pentru cuplajul Fr1Gr1.
Profesorii Fr1, Fr2 și Gr1 formau un tuplaj pe clasele 11C și 11E și observăm că s-a înființat profesorul fictiv Fr1Fr2 care intră la 11C într-o aceeași oră în care Gr1 intră la 11E (oră în care Fr1 și Fr2 sunt liberi).
Fr1Fr2 intră încă într-un tuplaj, cu Fr3 și Gr2, pe clasele 10B, 10C și 10E și se vede pe coloanele orare de mai sus că lecțiile acestui tuplaj cad într-o aceeași oră și nu există suprapuneri de lecții ale membrilor tuplajului.
Iar lecțiile tuplajului (Fr2 Fr3 Gr1 / 09A 09C 09D) cad și ele într-o aceeași oră, fără suprapuneri cu alte lecții ale profesorilor respectivi.
Algoritmul de etichetare cu ore descris mai sus se poate adapta și pentru repartizarea echilibrată pe zilele de lucru, a lecțiilor prof|cls specificate în încadrarea săptămânală inițială, a profesorilor (în loc de permutări de ore, folosim permutări de zile); dar desigur, aceasta ar fi sarcina unui alt pachet…