[1] Problema orarului școlar echilibrat și limbajul R
[2] V. Bazon - Orare școlare echilibrate și limbajul R https://books.google.ro/books?id=aWrDEAAAQBAJ
Un tuplaj implică doi sau trei profesori și două sau trei clase (sau „grupe” ori „noi clase”, care partiționează ansamblul elevilor claselor inițiale), astfel încât lecțiile prof|cls respective decurg în paralel, într-o aceeași oră 1:7 a zilei curente.
Înainte ziceam „pereche sau triplet de clase cuplate” – subînțelegând doar, profesorii implicați; astfel, 10EF este o pereche de clase cuplate, chiar pe două discipline ("Desen/Muzică" și "Germană") – dar de fapt, avem de-a face cu două tuplaje distincte.
Amintim că prin cuplaj înțelegem două lecții în care doi profesori intră într-o aceeași oră a zilei, la o aceeași clasă – lucrând independent pe câte o grupă de elevi ai acelei clase.
Anterior, pentru a repartiza pe zile cele 928 de lecții prof|cls existente aici, am specificat separat tuplajele, sub forma unui „orar prealabil” – alegând manual ziua care să-l conțină pe fiecare (de exemplu tuplajului "Ds1Mz1 /10B 10D/" i-am repartizat ziua Mi, iar tuplajului "LG3LG1LG4 /11A 11B 11D/" i-am repartizat zilele Lu și Vi); prin programul "by_days.R" am obținut o repartizare pe zile a lecțiilor rămase în afara tuplajelor, pe care apoi am întregit-o cu „orarul” pe zile prealabil constituit, al tuplajelor.
În schimb, pentru repartizarea pe ore 1:7 a lecțiilor zilei curente (prin funcția mount_hours()), am ignorat complet tuplajele (încât de exemplu, în ziua Mi clasele 10B și 10D au apărut în ore diferite la profesorii Ds1 și Mz1); apoi, pentru a aranja tuplajele în câte o aceeași oră a zilei au fost necesare unele intervenții interactive (prin funcția move_cls() din programul "reduce_gaps.R", ușor modificată). Dar nu-i cazul de a amâna pe cine știe când, ideea firească de a modifica mount_hours() pentru a ține seama din capul locului, și de tuplajele zilei respective…
Să ne amintim (iarăși) cum procedează mount_hours()…
Pentru fiecare clasă – într-o ordine aleatorie „preferențială” (urmărind cumva ordinea crescătoare a coeficienților „betweenness”) – se apelează funcția internă mountHtoCls(); aceasta etichetează lecțiile clasei cu o permutare de 1:N (N≥4 fiind numărul de ore/zi la clasa respectivă) cu proprietatea principală că nu are valori comune cu etichetări făcute anterior altor clase, pe profesorii comuni cu cei din clasa curentă (altfel, un profesor ar trebui să intre în aceeași oră la două clase); se verifică deasemenea ca prin etichetarea cu ore aplicată pe clasa curentă, niciunul dintre profesori să nu capete (coroborând cu alocările anterioare) mai mult de două ferestre (dar fără a socoti pe cele induse eventual de cuplaje) – facilitând astfel, reducerea ulterioară a totalului de ferestre din orarul rezultat în final.
Acum, separăm tuplajele pe zile și adăugăm câte un câmp "ora", ale cărui valori urmează să fie determinate – rămâne de văzut cum – în mount_hours():
P23 <- readRDS("cls23_days.RDS") %>% rename(zl = zi) %>% mutate(prof = as.character(prof), ora = 0L) %>% split(.$zl) %>% map(function(S) S %>% select(prof, cls, ora)) %>% setNames(Zile) saveRDS(P23, "P23i.RDS") # Pr1Pr2 | Cl1 Cl2 [Cl3] | ora=0
De exemplu, pentru o zi mai complicată – cu aceleași clase în două tuplaje:
> P23[["Vi"]] prof cls ora 5 LG2LG1 10A 10B 0 # LG2/10A și LG1/10B, într-o aceeași oră 10 LG2LG1 12E 12F 0 15 LG2LG3 11E 11F 0 20 LG3LG1LG4 11A 11B 11D 0 24 LG3LG4 10E 10F 0 27 Ds1Mz1 10E 10F 0
Să presupunem că, pentru Vi, s-a ajuns la alocarea lecțiilor clasei 10E și nu s-a întâlnit anterior clasa 10F – atunci, pentru cele două tuplaje /10E 10F/ câmpul $ora din P23[["Vi"]] are valoarea 0; în acest caz, odată cu etichetarea în curs a lecțiilor clasei 10E, se înscriu celor două tuplaje, în câmpul $ora, valorile cu care au fost etichetate lecțiile la profesorii LG3 și respectiv, Ds1 – să zicem pentru exemplu, 2 și 5.
Când se va ajunge ulterior la alocarea lecțiilor celeilalte clase din tuplaj, 10F – va trebui ca lui LG4 să i se aloce aceeași oră (=2) ca anterior lui LG3 la 10E, citind-o din câmpul $ora al tuplajului respectiv; la fel, lui Mz1 va trebui să i se aloce ora 5, înregistrată anterior în tuplajul cu Ds1 pe clasele /10E 10F/.
Dacă etichetarea lecțiilor clasei curente nu reușește, pentru nicio permutare de ore, atunci se anulează toate alocările făcute (inclusiv câmpul $ora din tuplaje), se reordonează aleatoriu clasele și se relansează procesul, în noua ordine a claselor.
Pentru a instrumenta procedeul descris mai sus, constituim întâi o listă în care specificăm pe fiecare zi, clasele care fac parte din tuplaje în acea zi:
zTC <- map(Zile, function(z) { P23[[z]] %>% pull(cls) %>% lapply(function(tk) strsplit(tk, " ")[[1]]) %>% unlist() %>% as.vector() %>% unique() }) %>% setNames(Zile) saveRDS(zTC, "zTC.rds") # clasele din tuplaje, pe fiecare zi > zTC[["Vi"]] [1] "10A" "10B" "12E" "12F" "11E" "11F" "11A" "11B" "11D" "10E" "10F"
Mai avem nevoie de două funcții, pentru lucrul intern; în vederea modificării, copiem definiția funcției mount_hours() într-un alt fișier, "mount_h1.R" și înainte de funcția internă mountHtoCls() specificăm:
P23 <- P23i[[zi]] ztc <- zTC[[zi]] ph_in_tuplaj <- function(Q) { # Q fiind o clasă din tuplaje p23 <- z23 %>% filter(grepl(Q, cls)) # unde z23 = P23[[zi]] curent map_dfr(1:nrow(p23), function(n) { i <- match(Q, strsplit(p23[n, 2], " ")[[1]]) vpr <- strsplit(p23[n, 1], "(?<=.{3})", perl=TRUE)[[1]] data.frame(prof = vpr[i], ora = p23[n, 3]) }) } set_h_tuplaj <- function(Q, P, h) { if(h %in% z23[which(grepl(Q, z23[,2])), 3]) return(FALSE) z23[which(grepl(Q, z23[,2]) & grepl(P, z23[,1])), 3] <<- h TRUE }
Prin ph_in_tuplaj() (…nu avem încă, denumiri mai potrivite) se va obține un „tabel” conținând profesorii de la clasa indicată și valoarea curentă a câmpului $ora, din tuplajele în care apare acea clasă; astfel, reluând exemplul de mai sus – după ce la clasa 10E am fixat valorile 2 și 5 pentru LG3 și Ds1, când se va ajunge la clasa 10F vom avea:
> ph_in_tuplaj("10F") prof ora 1 LG4 2 # la 10F, LG4 trebuie alocat în aceeași oră cu LG3 de la 10E 2 Mz1 5 # iar Mz1 în aceeași oră cu Ds1 de la 10E
Înainte de a apela mountHtoCls() pentru clasa următoare, mount_hours() va verifica dacă aceasta este implicată în setul claselor din tuplaje ztc – caz în care va stoca în pth rezultatul returnat de ph_in_tuplaj():
z23 <- P23 # (re)inițializează setul tuplajelor ($ora devine 0) for(K in lstCls) { if(K %in% ztc) pth <- ph_in_tuplaj(K) # pentru clasa curentă (dintr-un tuplaj) else {pth <- NULL} W <- mountHtoCls(Z[[K]]) # încearcă un orar pentru clasa curentă
Cealaltă funcție, set_h_tuplaj() actualizează câmpul $ora din tuplajul care conține clasa curentă și profesorul căruia tocmai i s-a alocat o anumită oră; dar dacă sunt mai multe tuplaje care conțin clasa curentă și la unul dintre acestea câmpul $ora conține chiar valoarea cu care se intenționa actualizarea acestuia – atunci doar se returnează FALSE (evitând ca două tuplaje distincte să se suprapună într-o aceeași oră).
De observat că a trebuit să folosim "<<-" (operatorul de „atribuire globală”), dat fiind că setul tuplajelor z23 este extern funcției.
În funcția mountHtoCls(), înainte de a căuta permutarea de ore cu care să eticheteze lecțiile clasei curente, se extrage din pth vectorul profesorilor clasei implicați în tuplaje:
dP <- "" if(!is.null(pth)) dP <- pth$prof # profesorii din tuplaje, ai clasei curente
O permutare de ore este de fapt un octet în care poziția fiecărui bit 1 indică a câta oră se alocă lecției, în ordinea dată de câmpul $prof din setul lecțiilor clasei pe ziua respectivă. Când mountHtoCls() găsește o permutare bis convenabilă (nu se suprapune cu alocările făcute anterior altor clase, pe profesorii clasei curente), se verifică valorile curente din câmpul $ora al tuplajelor în care apar eventual, profesori ai clasei curente (procedând cum am ilustrat mai sus pentru tuplajele pe /10E 10F/ din ziua de Vi):
if(P %in% dP) { h <- pth[pth[, 1] == P, 2] # $ora este câmpul 2 if(h > 0) { # de la o clasă întâlnită anterioar bs <- h2bin[h] if(bitwAnd(bis[k], bs) == 0L) { knd <- FALSE # suprapunere cu alocarea anterioară break # trebuie căutată o altă permutare } } else { # înscrie $ora, dacă nu coincide cu # a altui tuplaj pe clasa curentă if(! set_h_tuplaj(Q$cls[1], P, which(h2bin == bis[k]))) { knd <- FALSE break } } } if(! knd) next # trece la o altă permutare de ore
Anterior, după ce reușea alocarea lecțiilor pentru toate clasele, mount_hours() verifica în final dacă totalul ferestrelor „pe orizontale” este mai mic decât un anumit procent din totalul lecțiilor zilei curente (căutând un alt orar, în caz contrar).
Dar acum, în "mount_h1.R", ne interesează mai mult ca participanții la tuplaje să nu aibă ferestre (fiindcă în procedura de reducere a numărului de ferestre pe care o intenționăm, orarul stabilit pentru tuplaje nu va suferi modificări); însă verificăm numai pentru tuplajele cu profesori LG* (fiindcă Ds1 și Mz1 sunt în tuplaj doar câte o singură dată pe zi):
if(succ) { # dacă s-au alocat pe ore toate lecțiile if(sum(unlist(lapply(bith[grepl("LG", names(bith))], cnt_holes))) < 1) break # încheie dacă cei din tuplaje nu au ferestre }
Formulăm acum un program care să folosescă funcția mount_hours() (modificată cum am evidențiat mai sus):
# to_hours.R rm(list = ls()) # elimină obiectele din sesiunea precedentă library(tidyverse) Zile <- c("Lu", "Ma", "Mi", "Jo", "Vi") load("Tw12.Rda") # [1] "Tw1" "Tw2" load("BTW.rda") # "BTW_prof", "BTW_cls" ("betweenness", pe zile) load("lPrTz.Rda") # "lTz1", "lTz2" (dependențele cuplajelor, pe zile) PRMh <- readRDS("lstPerm47.RDS") # matricele de permutări cu 4:7 elemente P23i <- readRDS("P23i.RDS") # tuplaje, pe fiecare zi zTC <- readRDS("zTC.rds") # clasele angajate în tuplaje, pe fiecare zi h2bin <- as.integer(c(1, 2, 4, 8, 16, 32, 64)) # măștile binare ale orelor 1:7 # funcții pe care le-am formulat anterior pe aici: # cnt_holes(), hourly_matrix(), prnTime() source("mount_h1.R") # încarcă funcția mount_hours() (modificată) LSS <- readRDS("R12_ldz.RDS") # dicționar zi ==> lecțiile prof|cls ale zilei ORR <- vector("list", 5) # vom salva aici orarul constituit zilei curente names(ORR) <- Zile prnTime('\n') # afișează timpul inițial for(zi in Zile) { ORR[[zi]] <- mount_hours(LSS[[zi]], zi) # orar prof|cls|ora al zilei cat(zi, " "); prnTime('\n') # timpul curent } saveRDS(ORR, file = "ORR_3n.RDS")
Pentru a verifica eventual lucrurile, putem adăuga următoarea secvență, prin care constituim un fișier-text cu matricele orare (ordonate după profesori) și tuplajele zilelor:
sink(file="ORR_3n.txt", append=TRUE) for(zi in Zile) { orz <- ORR[[zi]] %>% hourly_matrix() # matricea orară a zilei orz <- orz[order(rownames(orz)), ] # ordonăm liniile după profesori print(P23i[[zi]]) # tuplajele zilei curente print.table(orz) } sink()
Subliniem că duratele, orarele furnizate, numărul de ferestre și distribuția acestora – depind de momentul lansării programului, de calitatea coeficienților "betweenness" (…n-am mai considerat și conenexiunile care apar între profesorii și între clasele din câte un același tuplaj) și desigur (dar mai puțin important) de calculatorul și sistemul de operare folosit.
Redăm un caz fericit (execuția a luat nu 30-60 minute, ci doar câteva minute):
vb@Home:~/23nov$ R -q > source("to_hours.R") 06:03:45 33 Lu 06:04:13 34 Ma 06:04:54 33 Mi 06:05:08 35 Jo 06:08:02 36 Vi 06:11:06 # saveRDS(ORR, "ORR_3n.RDS")
Redăm (reorganizând și marcând după caz) datele rezultate în "ORR_3n.txt" pentru ziua Vi:
prof cls ora 5 LG2LG1 10A 10B 0 # tuplaj alocat în ora 3 10 LG2LG1 12E 12F 0 # 6 15 LG2LG3 11E 11F 0 # 5 20 LG3LG1LG4 11A 11B 11D 0 # 4 24 LG3LG4 10E 10F 0 # 6 27 Ds1Mz1 10E 10F 0 # 4 1 2 3 4 5 6 1 2 3 4 5 6 Bl1 - - 11F 12F 11C 10A LI2LI3 - 9A - - - - Bl2 - - 9B 11E 7B 8B LI3 11B - 11A - - - Bl3 11D 6A 10D - - - LR1 9A 12B - - 11B 11A CC1 11E 11E - 5B - 11F LR2 - 9B 5A - 5B 6B Ch1 9C 10C - 10D 10B - LR3 - 11F - 9F 10C 10D Ch2 9D - 7A - 8B 9B LR4 7A 8B - 8A - 7B Ch4 - - - - 12C - LR5 - - 12C 9D 10F 6A Ds1 - 9F 6B 10E - - LR6 12F - - 12E 9E 11E ET1 5B 5A - - - - LR7 11C 12D - 9C - - Fl1 - 9D - 12B 12E 9E LR8 10F 12E - - - - Fz1 10D 9E 10F 11C 9D 10B Lt1 7B - - 11F - - Fz2 - - 12D 12C 9A - Mt1 - - 5B 7A 6A 5A Fz3 9F 12A - - - - Mt2 11A - 9A 12A 10A 9D Fz4 8B 7B - - - - Mt3 10B 11B 12B 9B - - Gg1 - - 9E 12D 10E 7A Mt4 12D - 12A - 11D 12C Gg2 - - 11C 8B 9F 11D Mt5 10E 10D 11E 10C - - Is1 10C 10F - - 5A 8A Mt6 6B 8A 9C - - - Is2 9E - 11B - 9B - Mz1 - - 8B 10F 12F - Is3 - 5B 11D - 12D - Ps1 10A 10E 10C - - - LE1 6A 11D 8A - 9C - Ps2 12E 12F - - - - LE2 12B - 9F 10B 11A - Rl1 - 9C 9D - 8A 9A LE3 - 6B 12E 10A - - Rl2 - 11C 6A 6B - - LE4 12A 12C - - - - Sp1 - 11A - 7B 12B 9C LG1 - - 10B 11B 6B 12F Sp2 8A 7A - 6A - 11B LG2 - - 10A 5A 11E 12E Sp3 11F - - - - - LG3 - - 7B 11A 11F 10E Tc1 12C - - 9E 10D 11C LG4 - - 10E 11D 7A 10F Tc2 - 10A 12F 9A - - LI1 9B 10B - - - - Tc2LI1 - - - - 12A - LI2 5A - - - - -
Am marcat aici, tuplajele și se verifică ușor că ele au fost corect repartizate (10E și 10F cad în aceeași oră la Ds1 și Mz1; apoi 11ABD sunt într-o aceeași oră la LG3, LG1 și LG4 ș.a.m.d.) – și încă, fără ferestre. Dar au rezultat în total, peste 30 de ferestre…
Pentru a reduce numărul de ferestre folosim programul anterior reduce_gaps_1.R, dar fără funcțiile (un)taboo_hours() – acestea trebuiau formulate „manual” pentru fiecare matrice orară în parte, notând coloanele orare corespunzătoare tuplajelor.
Generalitatea necesară se obține totuși ușor.
Mai întâi (cam la fel ca în funcția anterioară decompose23()) separăm profesorii și clasele aferente lor din setul tuplajelor pe fiecare zi P23i.RDS:
PCt <- map(P23i, function(TP) { map_dfr(1:nrow(TP), function(i) { vpr <- strsplit(TP[i, 1], "(?<=.{3})", perl=TRUE)[[1]] vcl <- strsplit(TP[i, 2], " ")[[1]] data.frame(prof = vpr, cls = vcl) }) }) %>% setNames(Zile) > PCt[["Lu"]] prof cls 1 Ds1 9A 2 Mz1 9B 3 LG2 10A 4 LG1 10B 5 LG2 12E 6 LG1 12F 7 LG2 11E 8 LG3 11F 9 LG3 11A 10 LG1 11B 11 LG4 11D
Valorile unice din coloanele tabelului PCt[[zi]] reprezintă profesorii și respectiv clasele, care intră în tuplaje (clasele din tuplaje, pe fiecare zi, le obținusem pe altă cale mai sus, în zTC.rds – de care acum ne putem lipsi).
Să întregim PCt[[zi]], adăugând pe fiecare linie ora alocată în orarul ORR[[zi]] lecției respective:
ORR <- readRDS("ORR_3n.RDS") PCth <- map(Zile, function(zi) { pt <- PCt[[zi]]$prof %>% unique() # profesorii din tuplajele zilei ct <- PCt[[zi]]$cls %>% unique() # clasele din tuplajele zilei ORR[[zi]] %>% filter(prof %in% pt & cls %in% ct) %>% arrange(ora, cls) %>% inner_join(PCt[[zi]]) # exclude liniile "false" }) %>% setNames(Zile) saveRDS(PCth, "PCH_tup.RDS") # zi --> prof|cls|ora (la tuplaje) > PCth[["Lu"]] prof cls ora 1 LG2 11E 3 2 LG3 11F 3 3 Ds1 9A 3 4 Mz1 9B 3 5 LG2 10A 4 6 LG1 10B 4 7 LG2 12E 5 8 LG1 12F 5 9 LG3 11A 6 10 LG1 11B 6 11 LG4 11D 6
Am reținut din orarul zilei ORR[[zi]], numai liniile aferente profesorilor și claselor din tuplajele acelei zile; dar între acestea există eventual și linii „false” – de exemplu, linia Mz1 12F 5 trebuie exclusă, fiindcă ea nu corespunde vreunui tuplaj (chit că și Mz1 și 12F intră fiecare în câte un tuplaj); inner_join() ne-a asigurat comod eliminarea acelor linii care nu se află (pe primele două câmpuri) în setul tuplajelor zilei.
Acum, orarele cu număr redus de ferestre se obțin adăugând în reduce_gaps_1.R cu modificările notate mai sus, următorul „program principal”:
ORR <- readRDS("ORR_3n.RDS") PCH <- readRDS("PCH_tup.RDS") # orarele tuplajelor, pe fiecare zi W <- list() # pentru orarele cu număr redus de ferestre for(zi in Zile) { set_globals(zi) OZ <- ORR[[zi]] %>% hourly_matrix() # matricea orară a zilei NG1 <- count_gaps(OZ) # numărul inițial de ferestre Good <- 6 # numărul sperat de ferestre PCh <- PCH[[zi]] # orele tuplajelor, pe ziua curentă for(i in 1:nrow(PCh)) # maschează tuplajele ('X'), în matricea orară OZ[PCh$prof[i], PCh$ora[i]] <- "X" Cmb <- combn(ncol(OZ), 2) # combinările de 7 (6 sau 5) luate câte două prnTime(paste0(" (", NG1, " ferestre)\n")) orr <- search_better(OZ) # declanșează procesul de reducere a ferestrelor for(i in 1:nrow(PCh)) # demaschează tuplajele orr[PCh$prof[i], PCh$ora[i]] <- PCh$cls[i] W[[zi]] <- orr[order(rownames(orr)), ] prnTime("\n") }
Redăm cursul uneia dintre execuțiile programului:
11:54:39 (31 ferestre)
28 26 24 22 21 19 18 17 16 15 14 13 12 11 10 9 8 * 8 * 8 7 * 7 * 7 12:08:00
12:08:00 (43 ferestre)
41 39 37 36 35 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 * 9 * 9 * 9 * 9 12:22:58
12:22:58 (35 ferestre)
34 33 32 31 30 29 28 27 26 25 24 23 22 21 19 18 17 16 15 14 13 12 11 10 * 10 * 10 * 10 * 10 12:36:30
12:36:31 (39 ferestre)
38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 * 10 * 10 * 10 * 10 12:50:45
12:50:46 (35 ferestre)
34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 13 12 * 12 * 12 * 12 * 12 13:10:42
> saveRDS(W, "W3.RDS")
Extrăgând din mai multe (trei) execuții, orarul câte unei zile – am obținut un orar care are în total 47 de ferestre (5.06% față de totalul 928 al lecțiilor):
W <- list(Lu = W3[["Lu"]], Ma = W1[["Ma"]], Mi = W1[["Mi"]], Jo = W2[["Jo"]], Vi = W3[["Vi"]]) sapply(Zile, function(zi) {set_globals(zi); count_gaps(W[[zi]])}) Lu Ma Mi Jo Vi 7 9 9 9 12 # total, 47 ferestre
Redăm orarul pe Vi, marcând iarăși tuplajele (dar și ferestrele rămase, față de orarul inițial pe care l-am redat mai sus):
1 2 3 4 5 6 1 2 3 4 5 6
Bl1 11F 12F - - 11C 10A LI2LI3 - 9A - - - -
Bl2 11E 9B - 8B 7B - LI3 11A - 11B - - -
Bl3 11D 6A 10D - - - LR1 - 11B 11A 9A 12B -
CC1 5B 11E 11F 11E - - LR2 6B 5B - - 5A 9B
Ch1 - - 9C 10C 10D 10B LR3 10D 9F - 11F 10C -
Ch2 7A 8B 9D 9B - - LR4 8B 7A 8A 7B - -
Ch4 12C - - - - - LR5 10F 9D - 6A 12C -
Ds1 - - - 10E 9F 6B LR6 - - 12F 9E 12E 11E
ET1 - - - - 5B 5A LR7 11C 9C 12D - - -
Fl1 9D 12B 9E 12E - - LR8 12E 10F - - - -
Fz1 10B 10D 10F 11C 9D 9E Lt1 7B 11F - - - -
Fz2 - - - 12D 9A 12C Mt1 - - 5B 5A 6A 7A
Fz3 9F 12A - - - - Mt2 9A 11A - 10A 12A 9D
Fz4 - - - - 8B 7B Mt3 - - 12B 10B 9B 11B
Gg1 9E 12D 7A - 10E - Mt4 12D 11D 12C 12A - -
Gg2 - - 8B 9F 11D 11C Mt5 10C 10E 11E 10D - -
Is1 8A 10C 5A - 10F - Mt6 - - - 6B 8A 9C
Is2 11B 9E 9B - - - Mz1 - - - 10F 12F 8B
Is3 - - - 5B 12D 11D Ps1 10E 10A 10C - - -
LE1 - - 11D 8A 9C 6A Ps2 12F 12E - - - -
LE2 - - 9F 12B 10B 11A Rl1 9C 8A 9A 9D - -
LE3 10A 6B 12E - - - Rl2 6A 11C 6B - - -
LE4 12A 12C - - - - Sp1 12B 7B - 9C 11A -
LG1 - - 10B 11B 6B 12F Sp2 - - 6A 7A 11B 8A
LG2 - 5A 10A - 11E 12E Sp3 - - - - - 11F
LG3 - - 7B 11A 11F 10E Tc1 - - 11C 12C 9E 10D
LG4 - - 10E 11D 7A 10F Tc2 - - - 12F 10A 9A
LI1 9B 10B - - - - Tc2LI1 - - 12A - - -
LI2 5A - - - - -
Bineînțeles că tuplajele au rămas în pozițiile inițiale, fiindcă move_cls() le-a găsit marcate cu "X" și a refuzat mutarea claselor respective într-o altă coloană orară; inițial, pe tuplaje nu existau ferestre – dar clasa 5A de la LG2 nu intră în tuplaje, deci a putut fi mutată (pentru a mai reduce din ferestre), astfel că LG2 a căpătat totuși o fereastră.
Cele 12 ferestre n-au mai putut fi reduse; din păcate, la doi profesori (Bl1 și LR2) au rezultat câte două ferestre (legate; la alți 8 profesori avem câte o singură fereastră).
Să mai observăm că profesorii care intră în cuplaje obișnuite (LI* și Tc2) nu au ferestre: ora 2 la LI3 este acoperită de LI2LI3 (și continuă ora 1 de la LI2), iar cuplajul Tc2LI1 are oră la 12A între orele lui LI1 și cele ale lui Tc2.
Probabil că este avantajos ca orarul final să conțină multe ferestre (ne amintim că orarul original de la care am plecat, conținea 121 de ferestre): s-ar evita reproșurile obișnuite (păi… mai toți au ferestre!). Dar dacă orarul conține un număr rezonabil (mic) de ferestre, atunci devine importantă repartiția acestora – fiind de dorit ca un același profesor să nu aibă una sau două ferestre pe zi, de prea multe ori.
Având lista W a matricelor orare pe fiecare zi, putem formula într-o manieră generală tabelarea liniilor corespunzătoare profesorilor neangajați în cuplaje, care au una sau două ferestre într-o zi sau alta (pentru a investiga apoi, tabelul respectiv):
ntp <- union(names(Tw1), names(Tw2)) lgp <- map(Zile, function(zi) { moz <- W[[zi]] %>% as.data.frame() %>% mutate(prof = rownames(.)) %>% relocate(prof, .before = 1) %>% `rownames<-`(NULL) if(ncol(moz) < 8) # rbind() cere un același număr de coloane moz <- moz %>% mutate('7' = '-') map_dfr(1:nrow(moz), function(i) { np <- rownames(moz)[i] if(! moz[i, 1] %in% ntp) { rc <- paste0(moz[i, 2:ncol(moz)], collapse="") if(grepl("\\w+-{1,2}\\w+", rc)) # liniile cu ferestre return(moz[i, ]) } }) }) %>% setNames(Zile) GPS <- Reduce(rbind, lgp)
Repartiția pe zile a profesorilor (neangajați în cuplaje) cu una sau două ferestre pe zi:
> (tg <- table(GPS$prof)) Bl1 Bl2 Bl3 CC1 Ch1 Ch2 Ds1 Fz1 Gg1 Is1 Is3 LE3 LG1 LG2 LG4 LR1 LR2 LR3 LR5 Mt1 3 1 1 1 1 1 2 2 3 1 1 2 1 3 1 1 2 3 1 1 Mt2 Mt4 Rl1 Sp1 Sp2 Tc1 2 1 1 2 1 1
Să verificăm ferestrele pentru profesorii care au 3 zile cu ferestre:
> GPS %>% filter(prof %in% names(tg[tg == 3])) %>% arrange(prof) prof 1 2 3 4 5 6 7 1 Bl1 12A 12C 11F - 12B - - 2 Bl1 9A 12C 11C - 10A - - 3 Bl1 11F 12F - - 11C 10A - 4 Gg1 11E 5B - 5A 9D - - 5 Gg1 10A 9B - - 9A 9E - 6 Gg1 9E 12D 7A - 10E - - 7 LG2 8B 9E - 10C 8A 9A - 8 LG2 5B 9E - 9A 10C - - 9 LG2 - 5A 10A - 11E 12E - 10 LR3 9F 11F - 10E 10C - - 11 LR3 10E 9F - - 10D 10C - 12 LR3 10D 9F - 11F 10C - -
Constatăm că trei profesori (Bl1, Gg1 și LR3) au câte 4 ferestre (o zi cu două ferestre și două zile cu câte una); reproșurile din partea acestora sunt iminente…
Dar pentru fiecare, numărul de ferestre trebuie raportat cumva, la numărul de ore:
> LSS <- readRDS("R12i.RDS") # cele 928 lecții prof|cls|zl > table(LSS$prof)[names(tg)] Bl1 Bl2 Bl3 CC1 Ch1 Ch2 Ds1 Fz1 Gg1 Is1 Is3 LE3 LG1 LG2 LG4 LR1 LR2 LR3 LR5 Mt1 19 20 18 20 18 18 19 28 20 20 16 19 21 23 21 20 19 18 18 23 Mt2 Mt4 Rl1 Sp1 Sp2 Tc1 21 18 21 21 21 21
Cum era de așteptat (având în vedere procedurile pe care le-am folosit pentru repartizarea lecțiilor pe zile și pe orele zilei), profesorii care au puține ore nu au ferestre; media numărului de ore mean(table(LSS$prof)) este de 14 ore și cum vedem mai sus, au ferestre numai unii cu măcar 4 ore mai mult ca media (exceptând un caz: Is3 are numai 2 ore peste medie).
Este de așteptat ca pe majoritatea orarelor care pot rezulta prin procedurile noastre (cu sub 50 de ferestre pe orarul final), să avem cam aceleași proprietăți ale distribuției ferestrelor, evidențiate mai sus (dar eventual, cu alți doi-trei profesori îndreptățiți să fie nemulțumiți).
În orice caz – este improbabil să putem obține un orar fără ferestre, care să fie echilibrat pe zile, pe clase și pe profesori și în care toate clasele să aibă program normal (de la prima oră a zilei) și să nu aibă într-o aceeași zi două ore cu un același profesor (exceptând situația când pe disciplina respectivă, clasa are mai mult de 5 ore pe săptămână).
Este drept pe de altă parte, că procedura folosită pentru reducerea numărului de ferestre este susceptibilă de îmbunătățiri și poate fi încă optimizată…
vezi Cărţile mele (de programare)