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 12DAdmitem ș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 11EDe 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 07C 09D - 11E 11E - -
#> Fr1 - 06C 10B - - - -
#> Ds1 - - - 06B 09E 10E 07A
#> Fr2 - 09A 11C - 10C - -
#> Mz1 - - 07D 05C 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…