momente şi schiţe de informatică şi matematică
anti point—and—click

Distribuţia orară a distribuţiei pe zile a orelor şcolii (III)

orar şcolar | R
2021 mar

Reveniri…

Programul mount_in_days.R prelua din tb1202x3.RDS, distribuţia pe zile a orelor şcolii şi adăuga coloana $ora pe liniile corespunzătoare unei aceleiaşi zile, alocând profesorii pe orele zilei, pentru fiecare clasă:

for(zi in Zile) {
    lTMT[[zi]] <- Dzl %>% filter(zl == zi) %>% 
          select(prof, cls) %>%
          arrange(prof) %>%   # arrange(desc(prof)) %>%
          split(.$cls) %>%
          mountHtoDay(.)
} 

Înainte de a aplica mountHtoDay() fiecărei clase, liniile corespunzătoare zilei respective au fost ordonate (prin arrange()) după $prof – adică descrescător după numărul de ore pe săptămână ale profesorilor (amintim că $prof este "factor ordonat", în care ordinea nivelelor reflectă descrescător numărul total de ore). Orarul rezultat (în tmt5.RDS) avea în total, 320 de ferestre (v.[1]).

Dacă repetăm programul mount_in_days.R, schimbând însă linia "arrange(prof) %>%" cu "arrange(desc(prof)) %>%" (ordonând liniile crescător după numărul total de ore) – obţinem un nou orar (în tmt6.RDS), cu un total de numai 233 de ferestre; iar timpul de execuţie în acest caz a fost aproape 1 minut (în primul caz, era aproape 5 minute).

Cei care au puţine ore, pot avea multe ferestre; de exemplu, 2 ore pot fi alocate primeia şi ultimeia din zi – rezultând 5 ferestre. Începând alocarea orelor cu cei care au puţine ore, se profită şi de faptul că aceştia au puţine clase comune – încât ei vor fi alocaţi cel mai adesea pe primele ore, aproape fără ferestre; profesorii cu măcar 5 ore în ziua respectivă pot avea maximum 2 ferestre şi lăsându-i la sfârşit, avem şansa ca numărul total de ferestre să crească mai puţin, decât în cazul când am începe alocarea orelor în sens invers.

În funcţie de proporţia celor cu multe ore, faţă de cei cu puţine ore pe săptămână – obţinem un orar cu multe sau cu mai puţine ferestre, după cum începem alocarea pe orele zilei cu unii (cei cu multe ore), respectiv cu ceilalţi.

Dar şi dacă sunt 320 şi dacă sunt 233 de ferestre – practic, timpul pentru reducerea interactivă a ferestrelor rezultate pe o zi este cam acelaşi (o oră, pentru a reduce de la 60-70 ferestre la numai 10-15 – deci pentru întregul orar, cam 4-5 ore de lucru).

Practica reducerii ferestrelor

Cu aplicaţia /dayRecast putem reduce (într-o anumită măsură) ferestrele din orarele zilnice rezultate; evidenţiem aici câteva principii de lucru.

Orarul zilei poate fi pastat direct în caseta <textarea” – dar cel mai bine este să-l înscriem în fişierul HTML, în locul orarului existent (preluând mai întâi fişierele aplicaţiei, eventual de la github). Pe orar, coloanele corespunzătoare orelor zilei trebuie să conţină fiecare clasă câte o singură dată; desigur, o clasă care în ziua respectivă are numai 4 ore (respectiv 5, sau 6 ore) figurează numai în primele 4 coloane (respectiv, în primele 5 sau 6 coloane).

După ce marcăm prin click o clasă K şi pe aceeaşi linie, un loc liber '-' – click pe SWAP va muta K pe locul liber respectiv; dar această „mutare” înseamnă de fapt o serie întreagă de mutări de clase între cele două coloane, trebuind respectată regula unicităţii clasei pe coloană (clasa K exista deja pe coloana „destinaţie” a operaţiei SWAP, deci trebuie mutată pe coloana „sursă”, de unde tocmai a dispărut – dar la această nouă „destinaţie” există o anumită clasă, care trebuie iarăşi mutată, ş.a.m.d. – până ce în sfârşit, „clasa” de mutat ajunge să fie '-').

În orice caz, SWAP angajează numai două coloane şi este posibilă această „strategie”: operăm de sus în jos mai întâi pe primele două coloane, apoi pe a doua şi a treia, apoi pe a treia şi a patra coloană, ş.a.m.d. – urmărind de fiecare dată să aliniem clasele de pe fiecare linie fie spre stânga, fie spre dreapta – astfel încât '-' să apară eventual înainte sau/şi după clase, dar nu între clase. Procedeul merge (şi repede) cam până la momentul când putem constata că profesorii din prima jumătate a orarului (presupunem că este cea mai aglomerată, adică am început cu profesorii care au multe ore) nu mai au ferestre; pentru cealaltă jumătate a orarului lucrurile se complică, trebuind folosit SWAP (şi Undo) între diverse coloane, urmărind de fiecare dată ce se întâmplă cu numărul curent de ferestre şi având grijă să nu stricăm prea mult, aranjamentele din prima jumătate.

O altă strategie de lucru posibilă (pe care am folosit-o cu precădere) constă în a evidenţia pe rând orarul fiecărei clase (folosind Mark) şi a folosi SWAP pentru a reduce pe cât se poate ferestrele existente la un anumit moment al lucrului, pe orarul clasei respective (ignorând într-o primă etapă, efectul lui SWAP pe celelalte linii ale orarului):

Orarul iniţial avea peste 60 de ferestre; cum-necum am reuşit să reduc numărul de ferestre la 46 şi trebuind să întrerup lucrul, am salvat prin Export starea curentă a orarului, împreună cu lista "History" a mutărilor efectuate prin SWAP (începând de la orarul iniţial); ulterior, am înlocuit în fişierul "dayRecast.html" conţinutul lui <textarea>, cu orarul din fişierul obţinut prin Export – încât reîncărcând în browser "dayRecast.html", avem imaginea de mai sus (după ce am folosit Mark pentru clasa 9B).

În ziua respectivă, profesorii clasei 9B au în total 5 ferestre (iar "P31" are două ferestre consecutive); nu-i chiar banal, de eliminat toate cele 5 ferestre – dar dacă reuşim şi dacă prin aceasta, numărul total de ferestre se reduce la exact 41 (= 46 - 5), sau se reduce la mai puţin de 41, atunci putem fi siguri că (deşi am operat numai la 9B) numărul de ferestre de la profesorii celorlalte clase nu are de suferit (fiind posibil totuşi ca o fereastră să dispară de la unul şi să apară în plus, la un altul).

Iată lista operaţiilor SWAP folosite, în termenii înregistraţi în lista "History" (indice_rând, indice_coloană_sursă, indice_coloană_destinaţie – cu precizarea că "indice" începe de la 0):

30  1  3   # la P31: 9B din coloana 1 se mută în coloana 3; mutare inversă la P05
30  3  2   # la P31: 9B din coloana 3 se mută în coloana 2; invers (9B cu 8D), la P49
 4  1  3   # la P05: 9B col.1 => col.3 şi invers: la P49, 9B col.3 <-> 6E col.1
13  6  3   # la P14: 9B col.6 => col.3 şi la P05: 10D col.6 <-> 9B col.3 
46  5  3   # la P47: 9B col.5 => col.3 şi la P14: 9B col.3 <-> 12B col.5
24  4  3
30  2  3
24  2  4

Aceste 8 operaţii SWAP elimină toate cele 5 ferestre, iar totalul ferestrelor se reduce la exact 41 (=46-5, deci profesorii de la celelalte clase nu sunt afectaţi):

Mai departe (în principiu) procedăm şi cu celelalte clase, pe rând, cam la fel cum am evidenţiat mai sus pentru 9B – urmărind mereu ca numărul total de ferestre să scadă de fiecare dată, pe cât se poate, cel puţin cu numărul de ferestre ale profesorilor clasei curente; desigur, procedeul nu este liniar: se poate de exemplu, ca pe parcurs să dispară o fereastră de la un profesor şi să apară în plus, la unul dintre profesorii uneia dintre clasele operate la un pas anterior.

O a treia strategie de lucru avută în vedere constă în a opera cu SWAP (analog operării de mai sus la clasa 9B) pe lista profesorilor care au clase comune; în acest scop, am prevăzut un handler de click pe coloana "prof" (click pe numele "P08" de exemplu, vizualizează numai liniile profesorilor care au clase în comun cu "P08").

Evidenţierea ferestrelor

Operând cam cum am arătat mai sus, am reuşit să reduc numărul ferestrelor de la 60-70, la 10-14 (şi toate, de câte o singură oră) – obţinând fişierele "RecastLu.csv" etc. (redenumite după zile); aceste fişiere nu conţin şi secţiunea "History", adăugată prin Export (fiindcă ideea adăugării acestei secţiuni şi a operaţiei applyHIST a apărut „între timp”); am completat cele 5 fişiere .csv cu antetul "prof,1,2,3,4,5,6,7" – încât le putem „citi” direct în R ca obiecte "tibble":

# csv2df.R
library(tidyverse)
Zile <- c("Lu", "Ma", "Mi", "Jo", "Vi")
lCSV <- c(paste0("Recast", Zile, ".csv"))  # fişierele "RecastLu.csv", etc.

DFO <- map_df(1:5, function(i) {
              read_csv(lCSV[i]) %>%
              mutate(., zl = factor(Zile, levels = Zile, ordered=TRUE)[i])
       })

> DFO   # inspectăm un fragment, din consolă
# A tibble: 346 x 9
   prof  `1`   `2`   `3`   `4`   `5`   `6`   `7`   zl  
 1 P01   10B   12D   8D    10A   12B   -     -     Lu   
 2 P02   -     7E    11C   6D    7A    12E   -     Lu   
 3 P03   5D    8B    -     8E    11C   6E    -     Lu

Primele 73 de linii din DFO reprezintă orarul zilei 'Lu', liniile 74:145 reprezintă orarul zilei 'Ma', ş.a.m.d. Pentru a evidenţia numai liniile care conţin ferestre, adăugăm o coloană $gps în care concatenăm valorile înscrise pe fiecare linie în coloanele `1`..`7`, eliminând însă (prin gsub()) valorile '-' iniţiale şi finale, dacă există; apoi, selectăm cu grep() numai liniile pe care în coloana $gps apare şi caracterul '-':

DFO$gps <- unlist(lapply(1:nrow(DFO), function(i) 
                                      paste0(DFO[i, 2:8], collapse="")))
DFO$gps <- gsub('^-*|-*$', "", DFO$gps, perl=TRUE)
WND <- DFO[grep('-', DFO$gps), ]

> WND  # inspectăm un fragment, din consolă (liniile zilei 'Lu')
# A tibble: 61 x 10
   prof  `1`   `2`   `3`   `4`   `5`   `6`   `7`   zl    gps
 1 P03   5D    8B    -     8E    11C   6E    -     Lu    5D8B-8E11C6E   
 2 P05   9C    10E   12A   -     11B   12D   -     Lu    9C10E12A-11B12D
 3 P06   12E   9A    -     5D    5E    -     -     Lu    12E9A-5D5E     
 4 P07   8A    9C    -     10E   5D    -     -     Lu    8A9C-10E5D     
 5 P11   5B    6C    5A    -     8F    -     -     Lu    5B6C5A-8F      
 6 P13   10E   -     10D   7D    8B    -     -     Lu    10E-10D7D8B    
 7 P24   7C    6A    -     6B    9D    -     -     Lu    7C6A-6B9D      
 8 P29   12C   8E    -     8A    10B   -     -     Lu    12C8E-8A10B    
 9 P33   9A    10A   -     9D    -     -     -     Lu    9A10A-9D       
10 P45   -     7A    -     7B    12C   7D    -     Lu    7A-7B12C7D     

Am redat numai cele 10 linii cu ferestre, din ziua 'Lu'; fiindcă WND conţine 61 de linii şi fiindcă avem numai ferestre de câte o singură oră, în oricare zi – deducem că numărul total de ferestre ale orarului s-a redus de la cele 320 de ore existente iniţial (sau 233, fiindcă pentru 'Jo' şi 'Vi' am lucrat pe orarele obţinute prin alocarea inversă, începând cu profesorii cu ore puţine), la exact 61 de ferestre.

Iniţial, orarul nostru avea pentru ziua 'Lu' un număr de 65 de ferestre (16 de câte o oră, 17 de câte două ore şi 5 ferestre de câte 3 ore – v. [1]) şi iată – am reuşit să-l reformulăm încât să aibă numai 10 ferestre, toate de câte o singură oră. Dar este vorba de orarul obţinut prin programele din [1], plecând de la o încadrare reală a profesorilor, extrasă din orarul existent al unei anumite şcoli; oare pe orarul original de pe care am extras încadrarea, care o fi situaţia ferestrelor?

N-avem decât să repetăm secvenţa de comenzi de mai sus, asupra orarului original (după aducerea acestuia la formatul CSV cuvenit) şi obţinem:

> WND
# A tibble: 97 x 10
   prof  zi    `1`     `2`    `3`   `4`   `5`      `6`    `7`   gps
 1 P01   Lu    -       -      10C   -     8B       6A     11E   10C-8B6A11E     
 2 P04   Lu    7A      11B    6C    -     6B       7C     -     7A11B6C-6B7C    
 3 P05   Lu    10C     -      12E   11E   9A       10D    -     10C-12E11E9A10D 
 4 P07   Lu    8A      -      5D    -     12A      10E    -     8A-5D-12A10E    
 5 P08   Lu    6D      -      10A   -     -        -      -     6D-10A          
 6 P09   Lu    -       -      11A   -     10E      11C    -     11A-10E11C      
 7 P10   Lu    7E      10D    10D   -     12B      12B    -     7E10D10D-12B12B 
 8 P15   Lu    8E      6A     8E    8D    -        8B     -     8E6A8E8D-8B     
 9 P17   Lu    11B     11A    -     10D   -        -      -     11B11A-10D      
10 P21   Lu    5D      10C    -     12D   5D       7A     7A    5D10C-12D5D7A7A 
11 P26   Lu    12D/12E -      5C    8C    11D/11E  11A/1… -     12D/12E-5C8C11D…
12 P28   Lu    12D/12E 5D     -     8B    11C/11D… 5E     7D    12D/12E5D-8B11C…
13 P31   Lu    11D     10E    8B    -     7D       -      -     11D10E8B-7D     
14 P35   Lu    5E      5A     5B    -     8F       6B     7B    5E5A5B-8F6B7B   
15 P37   Lu    5A      -      5E    -     12E      -      -     5A-5E-12E       
16 P42   Lu    10A     8C     -     9D    6E       8C     -     10A8C-9D6E8C    
17 P48   Lu    10B     -      7B    5B    -        -      -     10B-7B5B        
18 P52   Lu    8B      12D    -     7B    10C      -      -     8B12D-7B10C     
19 P54   Lu    -       -      12B   -     12C      -      -     12B-12C         
20 P55   Lu    9C      9A     6B    10E   -        9B     9B    9C9A6B10E-9B9B  
21 P56   Lu    -       -      -     5A    -        11D    -     5A-11D          
22 P57   Lu    -       -      -     9C    -        6D     -     9C-6D           
23 P58   Lu    8F      -      6E    -     -        -      -     8F-6E           
24 P67   Lu    9A      12A    -     12A   -        -      -     9A12A-12A  

Am redat iarăşi, numai liniile corespunzătoare zilei 'Lu'. Se vede că pentru această zi, orarul original conţine 26 de ferestre (22 de câte o singură oră şi – la 'P07' şi 'P37' – două ferestre de câte două ore neconsecutive); în plus, 4 profesori (liniile 19 şi 21:23) au numai câte două ore, dar şi câte o fereastră între ele (situaţie pe care am reuşit să o evităm pe orarul nostru: în orice zi, cei cu numai două ore nu au fereastre).

WND conţine 97 de linii, dar între acestea avem şi 10 linii cu câte două ferestre – deci numărul total de ferestre pe orarul original este 107. Programul din [1] prin care am generat orarul nu prevedea vreo condiţie – de aceea au rezultat de două sau de trei ori mai multe ferestre (320 într-o versiune, 233 în cealaltă), decât în orarul original (şi de aceea, execuţia programului respectiv a durat aşa de puţin - 5 minute, respectiv 1 minut); probabil că dacă am reuşi să integrăm o condiţie prin care să se urmărească şi să se limiteze numărul de ferestre curent, am putea genera şi prin programul din [1], orare cu cel mult 100 de ferestre (cu preţul creşterii duratei de execuţie). Deocamdată am compensat absenţa unei astfel de condiţionări, prin aplicaţia („externă” programului) de reducere a ferestrelor, descrisă mai sus (bineînţeles că această aplicaţie se poate folosi şi pentru orarul original, reducând cele 107 ferestre probabil tot pe la vreo 60).

Perspectiva problemelor

Sunt cam trei luni, de când ne ocupăm aici de „problema orarului şcolar” (termen de căutare: "school timetabling problem"), folosind R. Am plecat de la o încadrare a profesorilor pe clase (câte ore şi la care clase, are fiecare); sunt două variabile „de completat”: ziua şi ora din zi, în care fiecare profesor să-şi facă lecţia la fiecare dintre clasele pe care este încadrat (sub condiţia principală de a nu suprapune lecţiile). Prin urmare, apar două probleme: repartizarea lecţiilor pe zilele de lucru şi respectiv, alocarea pe orele zilei a lecţiilor repartizate într-o aceeaşi zi

Trebuie observat că tratările teoretice întâlnite (v. "school timetabling problem") nu disociază aceste două probleme şi abordează problema ca fiind din clasa „probleme dificile” (de optimizare). Dar având două „variabile libere” – este normal să considerăm două probleme şi tratându-le separat, putem constata că pentru rezolvarea acestora nu este neapărat necesar să apelăm la tehnici sofisticate (dar subliniem că avem în vedere variabile libere, neconstrânse de la bun început).

Am rezolvat ambele probleme printr-un acelaşi algoritm, foarte simplu, „de etichetare” (bazat pe ideea de "factor" din R). Orice „lecţie” angajează în principal două date: un profesor şi o clasă; am „normalizat” datele încadrării (folosind pachetul R tidyverse) şi enumerând toate lecţiile într-o anumită ordine, am etichetat liniile respective prin factorul "Zile", respectiv (dar acum nu chiar factor) "Ora"-din-zi.

Etichetarea prin "Zile" decurge pe clase, asigurând deja, în mod implicit, că fiecare profesor îşi face lecţiile la o aceeaşi clasă în zile diferite (exceptând numai cazul când numărul acestor lecţii depăşeşte numărul zilelor de lucru). La repartizarea pe zile am impus acest principiu: lecţiile unui aceluiaşi profesor, la toate clasele sale, să fie repartizate echilibrat, dacă numărul total al acestora este cel puţin 10 (şi „îngrămădit” în două-trei zile, pentru profesorii cu puţine ore pe săptămână). Pentru retuşarea interactivă a repartizării pe zile obţinute prin programul respectiv, am creat aplicaţia /recast.

Având lecţiile dintr-o aceeaşi zi, repartizarea pe orele zilei decurge iarăşi, pe clase; liniile respective (cel mult 7, după numărul de ore pe ziua respectivă ale clasei curente) sunt etichetate cu o permutare sau alta a orelor, urmărind ca orele alocate astfel profesorilor clasei curente să nu se suprapună cu orele deja alocate anterior; coloana etichetelor respective este analogă coloanei "Zile", dar nu mai este un "factor" (trebuind să aibă un număr variabil de „nivele”, după câte ore are clasa curentă în acea zi).

Câtă vreme nu impunem vreo altă condiţionare pentru etichetarea cu ore, orarul zilei rezultă într-un timp foarte scurt, dar conţine multe ferestre; prin aplicaţia externă /dayRecast se pot reduce interactiv ferestrele existente pe orarul unei zile.

Am experimentat cele două programe de repartizare (pe zile, respectiv pe orele zilei) pe o încadrare destul de voluminoasă – 76 de profesori la 41 de clase, totalizând 1202 ore (sau „lecţii”) pe săptămână; din cele evidenţiate mai sus se poate aprecia că rezultatele finale sunt onorabile (atât ca timp total de lucru necesar obţinerii orarului final, cât şi în privinţa calităţii intrinseci a orarului), cu atât mai mult cu cât programele respective sunt şi foarte scurte (fiecare având sub 50 de linii de program, în limbajul R).

Unele aspecte au rămas totuşi, netratate – conducând la diverse noi probleme (ultimele două din lista care urmează, fiind cel mai importante):
    — de văzut cum am putea reduce numărul de ferestre de pe orarul unei zile nu printr-o aplicaţie interactivă, ci automat, printr-un program independent;
    — de integrat în programul mount_in_days.R o condiţionare prin care alocarea orară curentă să ţină seama de numărul de ferestre curent (defavorizând alocările care produc o creştere prea mare a acestuia);
    — de creat (probabil în aplicaţia interactivă /dayRecast) posibilitatea de a muta o oră sau alta de pe orarul final al unei zile, pe orarul unei alte zile (reducând prin aceasta, numărul de ferestre şi pe o zi şi pe cealaltă);
     de văzut cum am putea completa programele din [1] (pentru generarea distribuţiei pe zile a orelor şcolii şi respectiv, pentru generarea distribuţiei pe orele zilei), încât să avem în vedere şi situaţia când o clasă trebuie partajată între doi profesori, sau când două clase trebuie combinate într-o aceeaşi oră a zilei;
     cum să adaptăm programele respective situaţiei în care clasele funcţionează în două schimburi (caz în care s-ar cuveni să fie cât mai puţine situaţii în care profesorul să aibă ore în ambele schimburi într-o aceeaşi zi).

Mai departe, dezvoltarea demarată prin [1] ar putea beneficia de colaborarea specifică proiectelor "open source"; rămâne de încercat cândva, „strângerea” lucrurile într-un "project" public de sine stătător…

vezi Cărţile mele (de programare)

docerpro | Prev | Next