[1] De capul meu prin problema orarului şcolar (pe Google Play)
Din repartizarea pe zile rezultată în [2] putem obţine prin mount_hours() – foarte rapid, dacă acceptăm unele suprapuneri – câte un „orar” pentru fiecare zi; ar urma apoi să folosim celelalte programe din [1], pentru a elimina suprapunerile induse de cuplaje şi pentru a reduce numărul de ferestre… În final, ajungem la un orar principial (nu ştim, dacă şi acceptabil) pentru şcoala respectivă.
Caracterul „principial” rezultă din proprietăţile urmărite în cursul repartizării pe zile, a lecţiilor; pe scurt, am vrut o repartizare omogenă pe fiecare dintre factorii implicaţi (zile, clase, profesori şi discipline).
O repartizare neprincipială, ar fi aceea în care profesorii îşi fac orele, fiecare sau în cuplaje, în cât mai puţine zile – fiind interesaţi să aibă zile libere şi eventual, să nu aibă vreo oră-fereastră; iar repartizarea cea mai bună ar fi aceea în care nu prea mai vorbim de „repartizare”: toate orele din anul şcolar – de "Matematică" de exemplu – se fac de dimineaţă până seara în câteva zile consecutive (lucrătoare sau nu)…
N.B. Poate că omogenitatea să nu fie decât un moft; de ce să căutăm omogenizare şi să clamăm „principii”, când situaţia reală este neuniformă cam din toate punctele de vedere? Avem şi clase cu 28 şi clase cu 32 de ore (ba chiar şi „grupe” de clasă) şi profesori cu 16-30 şi profesori cu 1-4 ore; avem şi discipline foarte importante (Religie, la oricare clasă din ţară) şi obiecte foarte neimportante ("Educatie muzicala", cu juma' de oră şi numai la unele clase), iar în practica obişnuită în şcoli, un obiect nu prea are de-a face cu altul…
Este firesc să verificăm totuşi, dacă distribuţia pe zile re_distr.csv obţinută în [2] satisface într-adevăr, proprietăţile dorite – având în vedere că am retuşat interactiv (din consolă şi din aplicaţia "Recast.html") rezultatul din mount_days(); dar verificarea a devenit chiar necesară, fiindcă am sesizat cum-necum că pe re_distr.csv redat în [2], N01 are 7 ore (singur sau în cuplaje) în ziua Ma, dar tot nu şi le poate face fără derogări – cum urmăream în [2] – fiindcă niciuna dintre clasele respective nu are 7 ore (iar clasele încep programul de la prima oră a zilei, fără excepţii).
Această notă păstrată pe hârtie: "Is2: 10I Jo ⇄ Ma 10G" îmi aminteşte că după ce am exportat din "Recast.html" în acel "re_distr.csv" reprodus deja (şi uitat) în [2], am mai făcut o ultimă ajustare, la Is2:
Is2,10H 12I 6A,10D 10G 11E,10B 10E 10F 5A,10C 10I 5A,10A 12A 6B # uitat în "re_distr.csv", v. [2] Is2,10H 12I 6A,10D 10I 11E,10B 10E 10F 5A,10C 10G 5A,10A 12A 6B # după ultima modificare
După această interschimbare de clase, 10I capătă 7 ore pe Ma şi problema lui N01 dispare; dar probabil că am uitat (!) să export din nou, sau să actualizez "re_distr.csv" şi în [2]. Cum-necum, trebuie să acceptăm fără nazuri, că putem uita şi putem greşi – încât verificarea finală a rezultatelor este chiar necesară.
După ce am corectat direct în "re_distr.csv" linia indicată mai sus, am reconstituit „dicţionarul” dict_days.RDS (v. [2]) al lecţiilor prof | cls corespunzătoare fiecărei zile.
Să înfiinţăm un program "test.R" în care mai întâi încărcăm funcţiile de investigare necesare, precum şi dicţionarele în care am modelat cuplajele existente; apoi, instituim ca obiecte de memorie DS şi lDS (diferind doar ca formă, sau structură), distribuţia pe zile ale cărei proprietăţi urmează să le investigăm:
# test.R proprietăţile distribuţiei pe zile "re_distr.csv" source("stmt_utils.R") # Zile, dis_indiv(), total_conn(), etc. (v. [1]) load("Messing.Rda") # listele Tw1, Tw2, Twx, şi setul TwCl DS <- read_csv("re_distr.csv", col_types="cccccc") %>% fromRecast() # 'data.frame': 1260 obs. of 3 variables: # $ prof: chr "Lg3Lg1" "Lg3Lg1" "Lg3Lg1" "Lg3Lg1" ... # $ zl : Ord.factor w/ 5 levels "Lu"<"Ma"<"Mi"<..: 1 2 3 4 5 5 3 ... # $ cls : chr "10A" "10A" "10A" "10A" ... lDS <- readRDS("dict_days.RDS") # zi => tabelul lecţiilor zilei # List of 5 # $ Lu:'data.frame': 252 obs. of 2 variables: # ..$ prof: chr [1:252] "Lg3Lg1" "Le1" "Le1" "Le1" ... # ..$ cls : chr [1:252] "10A" "10A" "10C" "12E" ... # $ Ma:'data.frame': 252 obs. of 2 variables: # ..$ prof: chr [1:252] "Lg3Lg1" "M06" "M06" "M06" ... # ..$ cls : chr [1:252] "10A" "10A" "10C" "12A" ... # etc.
Seturile 'data.frame' din lista lDS conţin câte 252 de linii – deci cele 1260 de lecţii prof | cls sunt distribuite uniform pe zile.
Orele fiecărei clase sunt distribuite uniform pe zile (câte 6 la clasele cu 30 de ore, câte 6 sau 7 la cele cu peste 30 şi câte 6 sau 5, la cele cu mai puţin de 30 de ore):
table(DS[c('cls', 'zl')]) %>% print() cls Lu Ma Mi Jo Vi cls Lu Ma Mi Jo Vi cls Lu Ma Mi Jo Vi 10A 6 7 6 7 6 11F 6 6 6 6 5 6A 6 6 6 6 5 10B 6 6 6 6 6 11G 5 6 6 6 6 6B 6 6 6 6 6 10C 6 5 6 5 6 11H 5 6 6 6 6 7A 6 7 7 6 6 10D 6 6 6 7 6 11I 6 5 6 6 6 8A 6 6 6 7 7 10E 6 6 6 6 7 12A 6 6 6 5 6 8B 6 6 7 7 6 10F 6 7 6 6 6 12B 6 5 6 6 5 9A 7 7 6 6 6 10G 6 6 6 7 6 12C 5 6 6 6 6 9B 7 6 6 6 6 10H 6 6 7 6 6 12D 6 6 5 6 6 9C 7 6 6 6 6 10I 6 7 6 6 6 12E 6 5 6 6 6 9D 6 6 6 7 6 11A 6 5 6 6 6 12F 6 6 6 5 6 9E 6 6 6 6 7 11B 6 6 5 6 6 12G 6 6 5 6 6 9F 6 6 6 6 7 11C 6 6 6 5 6 12H 6 6 6 5 6 9G 6 7 6 6 6 11D 6 6 6 6 5 12I 6 6 6 5 6 9H 6 6 7 6 6 11E 6 5 6 6 6 5A 6 6 5 5 6 9I 6 6 6 7 6
N-am vrut să exagerăm, dar poate că ar fi meritat de luat în consideraţie şi acest aspect: în fiecare zi să avem cam acelaşi număr de clase cu câte 6 ore, respectiv cu câte 5 şi cu câte 7 ore… Ar fi de notat totuşi, această observaţie târzie: pentru reducerea ferestrelor este important să existe şi un anumit număr de clase (cu cât mai mare, cu atât mai bine) care în ziua respectivă au câte 7 ore.
Pentru profesori, ne uităm întâi la cei care nu sunt angajaţi în cuplaje:
DSi <- dis_indiv(DS) DSi %>% filter(! prof %in% union(names(Tw1), names(Tw2))) %>% print(n=Inf) prof Lu Ma Mi Jo Vi + prof Lu Ma Mi Jo Vi + prof Lu Ma Mi Jo Vi + 2 Ge1 5 5 5 5 5 25 24 Lf2 4 4 3 4 3 18 46 Ch4 3 3 3 2 2 13 3 Ef1 5 5 4 5 5 24 25 M03 4 4 4 3 3 18 47 Fz6 3 2 2 3 2 12 4 Le1 5 4 5 5 5 24 26 M04 4 3 4 4 3 18 48 Lf4 2 3 3 2 2 12 5 R01 5 5 5 4 5 24 27 M05 3 3 4 4 4 18 49 Bi4 3 2 0 3 2 10 6 Re1 5 5 4 5 5 24 28 M06 4 3 4 4 3 18 50 M11 2 2 2 2 2 10 7 Bi1 4 4 5 4 4 21 29 M07 3 4 3 4 4 18 51 Is3 3 2 2 0 2 9 8 Fz1 4 4 4 4 5 21 30 R04 3 3 4 4 4 18 52 Lf5 3 0 3 3 0 9 9 Fz2 4 5 4 4 4 21 31 R05 3 4 4 3 4 18 53 Ps1 0 2 3 2 2 9 10 Ge2 4 4 4 4 4 20 32 Re2 3 4 3 4 4 18 54 R07 2 2 0 2 3 9 11 Is1 4 4 4 4 4 20 33 Fz5 3 3 3 4 4 17 55 R08 0 3 0 3 3 9 12 Lf1 4 4 4 4 4 20 34 R06 3 4 3 4 3 17 56 Ef3 2 2 2 0 2 8 13 M01 4 4 4 4 4 20 35 Bi2 4 3 3 3 3 16 57 Ef4 3 0 2 0 2 7 14 R02 4 4 4 4 4 20 36 Bi3 3 3 4 3 3 16 58 R09 0 2 2 1 2 7 15 R03 4 4 4 4 4 20 37 Ch1 3 4 3 3 3 16 59 Et1 2 2 0 2 0 6 16 M02 4 3 4 4 4 19 38 Ch2 3 3 3 4 3 16 60 Fz7 2 0 0 2 2 6 17 Ec1 4 3 3 4 4 18 39 Is2 3 3 4 3 3 16 61 Le5 2 2 2 0 0 6 18 Ef2 4 3 4 3 4 18 40 Lf3 3 3 4 3 3 16 62 Ti1 0 3 3 0 0 6 19 Em1 3 4 3 4 4 18 41 M08 3 3 3 4 3 16 63 Es1 2 2 0 1 0 5 20 Fs1 3 3 4 4 4 18 42 M09 4 3 3 3 3 16 64 Fz8 1 0 2 2 0 5 21 Fz3 4 3 4 3 4 18 43 M10 3 4 3 3 3 16 65 R10 1 0 1 1 1 4 22 Fz4 4 4 3 3 4 18 44 Ch3 3 3 3 4 2 15 23 Le3 3 4 4 3 4 18 45 Ev1 3 3 3 3 3 15
Cei neangajaţi în cuplaje cu măcar 16 ore – până la linia 43 – au distribuţii individuale uniforme (diferenţa dintre numărul de ore pe o zi şi alta este de cel mult o singură oră); dintre cei 7 care urmează (cu numărul de ore între 15 şi 10), unii au deasemenea, distribuţii uniforme (liniile 45..48 şi 50); pentru cei cu mai puţin de 10 ore, distribuţiile au fost „concentrate” pe cât s-a putut, în mai puţine zile – dar nu mai puţine decât numărul de ore la o aceeaşi clasă; de exemplu, R10 are numai 4 ore, dar toate la o aceeaşi clasă (cum putem verifica imediat prin DS %>% filter(prof=="R10")) – încât acestea au fost alocate (în mount_days()) câte una pe zi şi nu în două zile.
Analog putem verifica faptul că profesorii care au ore proprii dar sunt angajaţi şi în cuplaje, au deasemenea distribuţii uniforme; prin joint_dis() din [2] putem verifica şi faptul că N01 – singurul care, incluzând şi lecţiile cuplate, are mai mult de 30 de ore – va putea face orele respective fără vreo derogare a programului obişnuit al vreunei clase (fiindcă în zilele când are 7 ore, măcar una dintre clasele respective are 7 ore).
mount_hours() montează o coloană $ora pe lecţiile prof | cls ale zilei curente, în care pentru fiecare clasă alocă valori 1..k (k fiind numărul de ore în acea zi pentru clasa curentă) – astfel încât lecţiile fiecărui profesor neangajat în cuplaje să fie alocate în ore distincte, cu cel mult două ferestre, iar numărul total de ferestre să nu depăşească o cotă prestabilită (12% de exemplu) din totalul orelor din ziua respectivă.
Subliniem că nu se încearcă evitarea suprapunerilor şi pentru profesorii angajaţi în cuplaje şi nici nu se caută un „orar” cu cât mai puţine ferestre – lăsând eliminarea suprapunerilor şi reducerea numărului de ferestre în seama unor programe separate.
mount_hours(), aşa cum este formulat în [1], decurge atunci foarte rapid. De exemplu, pentru ziua Lu din dict_days.RDS ne-a rezultat cam în 25 secunde, acest „orar” (reprodus aici pentru a demonstra încurcăturile cauzate de cuplaje, evitate în mount_hours() din [1]):
Lu
cls 1 2 3 4 5 6 7
10A Ef3 Lg3Lg1 Ev1 Ec1 N04 Le1 -
10B Le4Le2 Bi4 Ch3 Fz2 Ec1 Ge1 -
10C N09 Fz4 R02 Le1 Bi2 Ef1 -
10D M10 N09N01 Ec1 Fz1 R02 Bi1 -
10E Fz5 N07N13 Ef1 M02 Ch4 R01 -
10F N10N06 Ef3 Lf3 Bi4 M09 Ev1 -
10G Fz7 Le5 M04 Lf1 R05 N11ex3 -
10H Lf5 M08 Ch2 Bi2 Ge2 Is2 -
10I R05 Lf5 Re2 Ch1 M01 Le3 -
11A N07 Fz7 R07 Le4 Lg2Lg1 M03 -
11B Bi3 Is3 Ge2 M09 R01 N04 -
11C Is3 N02N12 Le4 Fz4 M03 Ec1 -
11D N07N01 N01 Bi4 Fz3 M04 Is1 -
11E R01 Re1 Fz6 M06 Le3 N11 -
11F Ch2 N02 M09 Lf5 R04 Ef4 -
11G N07N08 Fz3 Lf2 Re1 M05 - -
11H N02 Ch2 Fz4 M04 Lf3 - -
11I Fz8 N03ex1 Lf4 R02 Ef4 N03 -
12A ex4Lg1 Bi2 Ge1 Lg1 M06 Ch3 -
12B N10 Le4Le2 M06 M03 Ge1 Bi2 -
12C ex2N01 Fz5 R04 Ef2 M02 - -
12D M08 Ch4 N02N12 Le3 N01 Ef2 -
12E N08 Lf1 M03 Is1 Le1 Re1 -
12F N09N14 N09 Le1 R04 Fz3 M09 -
12G N11N05 M05 Bi1 Ge1 Ef2 Fz3 -
12H Ge1 Le1 M01 N06 N06ex2 R07 -
12I Fz6 M10 Is2 R03 Le2 N01 -
5A M07 Es1 Re1 Le2 R03 Lf1 -
6A N13 R06 M02 Ev1 Is2 Lf2 -
6B Es1 Et1 Bi3 M07 Ef1 R02 -
7A Lf4 Bi3 Fz1 Ch3 Re1 M02 -
8A Et1 M11 Ch4 R06 Fz1 Le2 -
8B M11 Le4 Is3 Ef1 Em1 R03 -
9A N05 M07 Ch1 Em1 Re2 Lg2Lg1 R03
9B Le5 Fz6 R05 N04 Lf1 M06 Is1
9C Le2 R01 M10 Bi1 Fz5 Ge2 N04
9D N02N12 Ef2 M08 R01 Lf2 Fz1 -
9E Fs1 Ef1 Fz2 M05 N03 Lf3 -
9F N06 N10N06 R06 Lf2 Fz2 Em1 -
9G N05ex2 Ch1 Ef4 Ge2 Fz4 M04 -
9H N03ex1 Fs1 N03 Re2 Bi1 M01 -
9I R10 N14 Fs1 M01 Is1 Fz2 -
Avem mai puţine clase (42) decât profesori (108, numărând şi pe cei „fictivi” care reprezintă cuplajele) – încât am preferat să redăm orarul pe clase (şi nu pe profesori).
Am marcat mai sus câteva ore, pentru a observa existenţa unor suprapuneri la profesorii angajaţi în cuplaje: N01 ar trebui să intre în ora 1 la clasa 11D, împreună cu N07, dar şi la clasa 12C, împreună cu ex2; iar lui N07 i s-a alocat ora 1 şi la clasa 11A şi deasemenea, lui ex2 i s-a alocat tot ora 1 şi la clasa 9G, împreună cu N05.
Exemplul redat evidenţiază faptul că existenţa cuplajelor încurcă foarte mult, producerea unui orar – motiv pentru care le-am şi ignorat iniţial, în mount_hours() din [1], amânând pentru un program separat (destul de complicat, v. [1]) eliminarea suprapunerilor induse de cuplaje.
În realitate, am ignorat pe cât am putut cuplajele, din două motive: mai întâi este vorba de o anumită predispoziţie incorigibilă de a ignora aspecte derivate din raţiuni funcţionăreşti sau interese mărunte (cică n-avem destule laboratoare, încât împărţim clasa în grupe, la doi profesori; nu putem forma o clasă cu 15 elevi, trebuie să aibă măcar 30 – ori 15 sunt pentru "Limba germana" şi 15 pentru "Limba engleza", deci împărţim iarăşi pe grupe, la doi profesori; nu găsim destui profesori competenţi de "Educatie muzicala" şi de "Educatie vizuala", deci fixăm câte doar o juma' de oră pentru aceste discipline – că oricum mai trebuie să introducem şi disciplina "Educatie XXX", şi disciplina cutare şi cutare…).
În plus, dacă sunt puţine cuplaje (ca în [1]) atunci pare firesc să nu ne pese dacă iniţial, ar rezulta şi vreo două suprapuneri – nu poate fi greu de corectat ulterior…
Al doilea motiv este unul foarte obişnuit: n-am fost în stare până acum, să formulez o procedură simplă, pe care s-o integrez în mount-hours(), pentru a preveni apariţia de suprapuneri şi în cazul celor angajaţi în cuplaje. Bineînţeles că această situaţie are totuşi un caracter temporar şi insistând asupra ei, am reuşit să o remediez, în timpul destul de lung de când am formulat mount_hours() în [1] (unde chiar am datat-o, "ian.2022" – simţind că va veni un moment în care să o putem îmbunătăţi).
Ideea este în fond foarte simplă: după ce am alocat ore 1..k profesorilor clasei curente şi ne-am asigurat că nu apare vreo suprapunere cu ore alocate anterior la alte clase (ignorând însă cuplajele) – vizăm şi profesorii clasei care sunt angajaţi eventual în vreun cuplaj, verificând şi pentru aceştia, dacă nu apar suprapuneri „ascunse”, cu ore alocate anterior oricăruia dintre cei conexaţi prin cuplare cu profesorul curent.
Nu credem că se poate da o „explicaţie” mai simplă decât am formulat mai sus – dar să imaginăm totuşi un exemplu. Să zicem că procesul de alocare pe orele zilei a lecţiilor a ajuns la clasa Q şi aceasta are 6 ore, cu profesorii P1..P6; să zicem că prima alocare încercată (1, 2, 3, 4, 5, 6) a eşuat fiindcă de exemplu, s-a găsit că profesorului P3 i s-a alocat anterior, la o clasă precedentă celeia la care am ajuns, ora 3 (încât nu-i mai putem aloca ora 3 şi la clasa Q); să zicem că eşuează încă un anumit număr de alocări (în fond, permutări de 1..6) şi apoi, găsim că alocarea (1, 3, 5, 2, 6, 4) nu mai produce vreo suprapunere (ignorând cuplajele) cu ore alocate anterior, profesorilor P1..P6. În această situaţie, mountHtoCls() – din [1] – care modelează alocarea lecţiilor clasei curente, se cam încheie (reţinând alocarea găsită) şi mount_hours() trece la clasa care urmează după Q.
Ei, acum intervine îmbunătăţirea la care ne-am referit mai sus; încă nu încheiem mountHtoCls(), ci vizăm în plus, acei profesori dintre P1..P6 care sunt angajaţi în unul sau mai multe cuplaje, pe ziua respectivă. Să zicem că P3 – căruia mai sus i-am alocat ora 5 la clasa Q şi am verificat deja că nu mai are ora 5 la vreo altă clasă – este "N01", despre care ştim că intră în multe cuplaje. Să presupunem că ne-am formulat de la începutul lucrurilor un dicţionar Tz1 al cuplajelor în care este angajat în ziua respectivă, fiecare profesor; ne uităm atunci la orele alocate înainte de a ajunge la clasa Q, tuturor cuplajelor înscrise în Tz1[["N01"]] şi verificăm dacă ora 5 alocată acum la clasa Q pentru N01, nu se suprapune cumva cu ora (tot 5) alocată anterior vreunuia dintre aceste cuplaje – dacă există vreo suprapunere, refuzăm alocarea şi încercăm o nouă permutare; altfel, încheiem ca şi în [1] mountHtoCls().
Reformulăm deci mountHtoCls() – funcţie internă lui mount_hours() – astfel (adăugând faţă de [1], secvenţa dintre liniile marcate cu '###'):
Twinz <- union(names(Tz1), names(Tz2)) # cuplajele din ziua curentă mountHtoCls <- function(Q) { # alocă pe 1..7, lecţiile unei clase (iul.2022) mpr <- PRMh[[nrow(Q)-3]] # matricea de permutări corespunzătoare clasei bhp <- bith[Q$prof] # biţii alocaţi anterior, profesorilor clasei for(i in 1:ncol(mpr)) { po <- mpr[, i] bis <- bitwShiftL(1, po - 1) if(any(bitwAnd(bhp, bis) > 0)) next # caută o permutare care să evite biţi '1' alocaţi deja knd <- TRUE ### for(k in 1:nrow(Q)) { # vizează profesorii clasei angajaţi în cuplaje P <- as.character(Q$prof[k]) if(P %in% Twinz) { bt <- if(nchar(P) > 3) Tz2[[P]] else Tz1[[P]] BC <- bitwAnd(bith[bt], bis[k]) if(any(BC > 0)) { # există o suprapunere de cuplaje knd <- FALSE break } } } if(!knd) next # exclude suprapunea de cuplaje ### if(anyDuplicated(names(bhp)) > 0) # profesor cu 2 ore for(jn in 1:(nrow(Q)-1)) # cumulează biţii asociaţi orelor sale if(names(bhp)[jn] == names(bhp)[jn+1]) bis[jn] <- bis[jn+1] <- bis[jn] + bis[jn+1] blks <- bitwOr(bhp, bis) # cumulează biţii vechilor şi noii alocări Cond1 <- unlist(lapply(blks, cnt_holes)) if(any(Cond1 > 2)) next # controlează numărul de ferestre bith[Q$prof] <<- blks # actualizează vectorul alocărilor (global) return(Q %>% mutate(ora = po)) # înscrie orarul clasei curente } return(NULL) # pentru clasa curentă NU s-a reuşit un orar "bun" }
Acum mount_hours() va produce un orar corect – fără „suprapuneri ascunse induse de cuplaje” cum aveam în [1]; ca urmare, nu mai este nevoie de programul "correct.R", prin care eliminam în [1], suprapunerile apărute.
Timpul de lucru pentru mount_hours() va fi desigur, mai mare ca în [1] – dar se compensează cu faptul că nu mai este necesar să rulăm şi "correct.R".
Să reformulăm şi programul "test3.R" din [1], prin care putem aplica mount_hours() unei distribuţii pe zile date:
# test3.R (iul.2022) source("stmt_utils.R") load("BTW.rda") # BTW_prof, BTW_cls (coeficienţii "betweenness" - v. [1]) PRMh <- readRDS("lstPerm47.RDS") # matricele de permutări de 4..7 ore load("Messing.Rda") # Tw1, Tw2, etc. (modelarea cuplajelor) source("mount_hours.R") LSS <- readRDS("dict_days.RDS") # dicţionar zi ==> lecţiile prof|cls ale zilei orar <- vector("list", 5) # vom salva aici orarul constituit zilei curente names(orar) <- Zile twin_day <- function(ltw) { # lista Tw1, respectiv Tw2 {{ltw}}[intersect(names({{ltw}}), prof_day)] %>% map(., function(D) intersect(D, prof_day)) %>% compact() } # păstrează numai cuplajele existente în ziua curentă p_max <- 0.2 # pentru calculul maximului admis, de ferestre pe zi prnTime() # afişează timpul curent for(zi in Zile) { lssn <- LSS[[zi]] # lecţiile zilei curente, prof|cls prof_day <- unique(lssn$prof) Tz1 <- twin_day(Tw1) # cei cu ore proprii, angajaţi şi în cuplaje Tz2 <- twin_day(Tw2) # cuplajele din ziua curentă (profesorii "fictivi") btw_prof <- BTW_prof[[zi]] # "betweenness"-profesori pentru ziua curentă btw_cls <- BTW_cls[[zi]] # "betweenness"-clase pentru ziua curentă nGaps <- round(nrow(lssn) * p_max) # maximum admis, de ferestre cat(zi, "- max.gaps =", nGaps, "\n") orar[[zi]] <- mount_hours(lssn) # produce un orar prof|cls|ora al zilei prnTime() } saveRDS(orar, file="orar_9.RDS")
Redăm din consola R, cum decurge o execuţie a programului (anume, tocmai aceea care ne-a dat "orar_9.RDS"):
> source("test3.R") 18:46:17 Lu - max.gaps = 50 [1] 47 18:46:19 Ma - max.gaps = 50 [1] 49 # orarul pe Ma are în jur de 49 ferestre 18:47:33 Mi - max.gaps = 50 [1] 38 18:47:34 Jo - max.gaps = 50 [1] 44 18:47:38 Vi - max.gaps = 50 [1] 46 18:47:50
Timpul de execuţie (şi orarele produse) variază de la o execuţie la alta, fiindcă profesorii sunt abordaţi într-o anumită ordine aleatorie (ţinând cont totuşi, de coeficienţii "betweenness" dintr-un anumit graf asociat profesorilor, v. [1]) şi la fel, clasele.
Cum se vede din datele redate mai sus, am obţinut "orar_9.RDS" în mai puţin de două minute, iar într-o serie de mai multe execuţii succesive am obţinut câte un orar în cel mai mult 4-5 minute.
Desigur, timpul de execuţie se măreşte şi dincolo de o oră, dacă pretindem procente mai mici pentru ferestre; însă nu trebuie să ne cramponăm de numărul de ferestre – avem în [1] un program destul de bun, pentru a reduce ferestrele; iar pe de altă parte, n-am modificat şi calculul numărului de ferestre angajat în mount_hours() (care în [1] ignora cuplajele), astfel că acest calcul a rămas doar estimativ (de exemplu, pe datele redate mai sus, Ma sunt nu 49, ci sunt în jur de 49 ferestre).
Redăm orarul pentru Ma – pe profesori (grupând cumva cuplajele şi formatând pe două coloane de text, prin programul utilitar pr), pentru a evidenţia şi ferestrele apărute:
> readRDS("orar_9.RDS")[["Ma"]] %>% prof_matrix() %>% print.table() prof 1 2 3 4 5 6 7 prof 1 2 3 4 5 6 7 N02 - 11H - 7A 5A 11F - Et1 - - - 8B - 7A - N02N12 12D - - - - - - Ev1 - - - 10B 8A 10G - N12 - 11C - - - - - Fs1 12I - - 9B 9C - - N03N12 - - - - 10H - - Fz1 - - - 10H 11B 8A 7A N03 - - - 11I - 10H - Fz2 9H 9I 10F 9E 9F - - N03ex1 9E 9H - - - - - Fz3 11G 12G 11F - - - - N10N03 - - 11H - - - - Fz4 - - 10C 12B 11C 12A - N10 9F 12B - - - - - Fz5 - 6A - 12E - 10A - N06 10F 12H - - - - - Fz6 9A 11E - - - - - N06ex2 - - 12E 12H - - - Ge1 - - 8A 11F 12D 6A 10F N05 - - - 12G - 9G - Ge2 - - - 11G 10C 10I 9A N11N05 12G - - - - - - Is1 11H - - 12D 9G 9A - N09 - 10D - - - - - Is2 10D - 11E - 10I - - N09N14 9I - 12F - - - - Is3 8B 8A - - - - - N01 - - - 12C 11D 12I - Le1 - 9E 12C 9F - 12H - ex3N01 - - - - - - 10I Le3 - - - 11E 10D 11D 9G N07N01 - - 11D - - - - Le5 - 9A 10G - - - - ex2N01 12C - - - - - - Lf1 - - 12D 11B 12C 10E - N11N01 - 12I - - - - - Lf2 - - 11G 9C 9D 10B - N07 - 9B - - - - - Lf3 - - 9H 12I 12F - - N07N13 10E - - - - - - Lf4 - - 10D 10C 12H - - N07N04 - - - - - 9C - M01 12H 11I 9I 9H - - - N04 12A - 11B - - - - M02 6A 12C 7A - - - - N13N04 - 11B - - 9B - - M03 - 12E - 11A 12B 11C - Le4 - 12A - - 10E 9D - M04 - 11D 9G - - 11H - Le4Le2 10B - - - - - - M05 - 10B - - 12G 11G - Le2 - 5A 6B 6A 9I 10F - M06 - 10C 12A 10A - - - Lg1 11A - - - - - - M07 5A 6B 9F 9A - - - Lg3Lg1 - - - - 10A - - M08 11E 9D 10H - - - - Lg2Lg1 - 11A 9A - - - - M09 12F - 12I - 11F - - ex4Lg1 - - - 12A - - - M10 - - 9C 10D 12I 11B - N11ex3 - - - - 10G - - M11 8A 8B - - - - - ex2ex3 - 11F - - - - - N08 12E 11G - - - - - Bi1 - - 11I - 9E 9F 10A Ps1 11D 10H - - - - - Bi2 9G 12D - - 11H - - R01 9D - 10E 11C 11E 12D - Bi3 6B 7A - 10E - - - R02 11I - - 10F 10B 6B - Bi4 11C 10I - - - - - R03 7A - 5A - 9A 8B - Ch1 - - 11C 9I 11I 9H - R04 - - 10A 12F - 12G - Ch2 10C 10A 12G - - - - R05 - 10G - 10I 9H 9E - Ch3 - - 10B - 8B 9B - R06 - 9F 6A 8A 12E - - Ch4 11B 10E 9D - - - - R07 - - 12H 11H - - - Ec1 11F - 10I - 11G - - R08 10H - - 11D 12A - - Ef1 9B - 8B 5A 6A 10D - R09 12B 9G - - - - - Ef2 - - 11A - 7A 12F - Re1 - 12F 12B 6B 11A 12C - Ef3 10A - - 10G - - - Re2 9C - 9E - 10F 9I - Em1 - - 9B 9G 6B 5A - Ti1 10I 9C - 9D - - - Es1 10G 10F - - - - -
La profesorii care au ferestre ('-' între ore la două clase), acestea sunt în număr de cel mult două (cum prevedeam în mountHtoCls()); dacă le numărăm pe toate care se văd, găsim 49 de ferestre (cum ne anunţase "test3.R") – dar din cauza cuplajelor, există probabil şi ferestre „ascunse” (după cum pot fi şi unele ferestre false).
De exemplu, N12 are două ferestre „ascunse”: intră în ora 1 împreună cu N02 la clasa 12D, apoi în ora 2 intră singur la 11C şi apoi tocmai în ora 5, intră împreună cu N03 la 10H (deci am socoti nu 49, ci 51 de ferestre).
Pe linia lui N03 apare fereastră între orele la 11I şi 10H – dar este o falsă fereastră, fiindcă ea se acoperă cu ora la 10H a cuplajului N03N12 în care este angajat.
Pentru a vedea câte ferestre avem de fapt şi pentru a le reduce sub o limită maximală fixată, folosim funcţiile din programul "recast.R":
> source("test_recast.R") # programul din [1] care angajează "recast.R" 07:38:21 # timpul iniţial Lu 58 14 # numărul iniţial şi limita dorită (25% din cel iniţial), de ferestre 57 56 55 54 52 51 49 48 46 41 40 36 35 ... 17 15 14 [1] 14 07:44:31 Ma 58 14 57 55 53 52 49 48 46 45 44 43 41 39 ... 15 14 13 12 11 10 [1] 10 07:51:18 Mi 40 10 39 38 37 36 35 33 32 31 29 28 27 26 25 21 ... 12 11 10 [1] 10 08:04:39 Jo 52 13 51 50 49 48 45 44 43 42 38 37 36 ... 15 14 13 [1] 13 08:17:36 Vi 47 11 46 45 44 43 42 41 40 39 38 37 36 34 33 ... 13 12 10 9 8 [1] 8 08:29:14 # timpul final
Orarul rezultat (de data aceasta, în mai puţin de o oră) are (de data aceasta) 14, 10, 10, 13 şi respectiv 8 ferestre. Printr-o nouă execuţie, obţinem un orar diferit de precedentul, atât ca timp şi număr de ferestre, cât şi în privinţa profesorilor cărora le rămân fie una, fie două ferestre.
Executând de mai multe ori (de dragul experimentului, să zicem) şi alegând din orarele rezultate pe acelea cu cel mai mic număr de ferestre – am putut îmbina în final un orar care are în total 40 de ferestre – cu repartiţia 9, 7, 8, 8, 8 – adică 3.17% din totalul 1260 al lecţiilor (ceea ce pare onorabil). Redăm aici orarul pe Ma, pe care ne-au rămas 7 ferestre (şi urmărim „manual” pe fiecare):
prof 1 2 3 4 5 6 7 M11 8A 8B - - - - - Is3 - - - - 8A 8B - N09 - 10D - - - - - Lg1 11A - - - - - - Le4Le2 - 10B - - - - - Et1 - - - - 8B 7A - N12 - - - 11C - - - N07 9B - - - - - - N11N05 - - 12G - - - - N06 - - - - 10F 12H - Ps1 10H 11D - - - - - N02N12 - - 12D - - - - Fz6 9A 11E - - - - - Ch4 - - - 9D 10E 11B - N07N13 - 10E - - - - - Lg3Lg1 - - - - 10A - - N08 12E 11G - - - - - ex2ex3 - - - - - 11F - R09 - - - - 12B 9G - Es1 10G 10F - - - - - N10 9F 12B - - - - - ex4Lg1 - - - - - 12A - Bi4 10I 11C - - - - - N03N12 - - - - 10H - - N07N04 - - - 9C - - - N10N03 - - 11H - - - - N13N04 11B - 9B - - - - # fereastră falsă (N07N13 ocupă ora 2) R07 12H 11H - - - - - N09N14 12F - 9I - - - - # fereastră falsă (N09) N03ex1 9H 9E - - - - - Bi2 - - - 11H 9G 12D - ex2N01 - - - - 12C - - Le5 - - - - - 10G 9A N11N01 - - - - - 12I - N11ex3 - - - - 10G - - N06ex2 - - 12E 12H - - - Fz2 - 9I 9F 10F 9H 9E - N04 - 11B - - 12A - - # ferestre false (N07N04, N13N04) Ef3 10A 10G - - - - - Ec1 11G 10I 11F - - - - ex3N01 - - - - - - 10I M01 11I 12H 9H 9I - - - M04 - - - - 11D 11H 9G Fz3 - - - 11F 12G 11G - Ch2 10C 12G 10A - - - - M02 6A 7A 12C - - - - N03 - - - 11I - 10H - # fereastră falsă (N03N12, etc.) M08 11E 10H 9D - - - - N05 12G 9G - - - - - N07N01 - - 11D - - - - M05 - - - 12G 11G 10B - Lg2Lg1 - 11A - 9A - - - # 1 (Lg1 are fereastră ora 3) Ti1 9C 9D 10I - - - - Ch3 8B 9B 10B - - - - Fs1 - - - 12I 9C 9B - M09 11F 12F 12I - - - - Lf3 12I 9H 12F - - - - Bi3 10E 6B 7A - - - - Le4 - - 12A 10E 9D - - M06 12A 10A 10C - - - - Ef2 - - - 11A 7A 12F - Fz5 - - - - 12E 6A 10A M07 6B 9F 9A 5A - - - Is2 - - - 10D 11E 10I - Ch1 9I 11I 11C 9H - - - R03 7A 9A 5A 8B - - - R08 11D 12A 10H - - - - R06 - - 8A 12E 6A 9F - N01 12C 12I - 11D - - - # fereastră falsă (N07N01, etc.) Ev1 10B 8A 10G - - - - R04 - - - 10A 12F 12G - Lf4 - - - 10C 12H 10D - Le1 9E 12C 12H 9F - - - M03 11C 12E 11A 12B - - - Le2 5A - 6A 6B 9I 10F - # fereastră falsă: Le4Le2 ocupă ora 2 Re2 10F 9C - - 9E 9I - # 2 Bi1 - - 11I 9E 9F 10A - Em1 9G 5A - 9B 6B - - # 1 Fz4 - - 12B 12A 10C 11C - Lf1 - - 11B 12C 12D 10E - R02 - - - 10B 11I 6B 10F Is1 - - 9G 12D 11H 9A - R05 - - 9E 10G 10I 9H - Le3 - - 11E 9G 10D 11D - Lf2 - - 9C 11G 10B 9D - M10 - - 10D 11B 12I 9C - Ge2 - 10C 11G 10I 9A - - N02 11H 11F - 7A 5A - - # fereastră falsă (N02N12 ocupă ora 3) Ef1 10D - 8B 6A 9B 5A - # 1 R01 9D 12D 10E 11E 11C - - Re1 12B - 6B 12F 11A 12C - # 1 Fz1 - - - 10H 11B 8A 7A Ge1 12D 6A 10F 8A 11F - -
Să observăm că procedând „manual” am găsit numai 6 ferestre; unde-i a 7-a? Fereastra „invizibilă” se află totdeauna la unul dintre profesorii pe care-i numisem ”externi” zilei (aceia care apar în cuplaje, dar în ziua respectivă nu au ore proprii); consultând dicţionarul acestora pentru "Ma" (v. [1]) – găsim că N11 este cel la care apare a 7-a fereastră: intră cu N05 la 12G în ora 3, apoi cu ex3 la 10G în ora 5 şi cu N01 la 12I în ora 6 (deci are fereastră în ora 4).
A mai rămas de îndeplinit o condiţie: Em1 şi Ev1 ar trebui să intre simultan la o clasă de-a 9-a şi la cea omonimă de-a 10-a (v. [2]); nu-i greu de rezolvat „interactiv”, dar s-ar cuveni ca "recast.R" să aibă în vedere şi unele rezervări prealabile de alocare…
Oricum însă, orarul obţinut nu este „acceptabil”: aici am considerat – contrar realităţii – că toate cele 42 de clase ar funcţiona într-un singur schimb; dar măcar este clar acum, că putem încă îmbunătăţi programele din [1]: mai sus am reuşit să eliminăm programul complicat "correct.R", amplificând puţin funcţia mount_hours() (da… cea mai bună ”îmbunătăţire” este eliminarea).
vezi Cărţile mele (de programare)