[1] Asupra unui orar școlar (I-IV)
Problema esențială este repartizarea pe zilele de lucru a lecțiilor prof|cls extrase din "planul de încadrare" al școlii, astfel încât să fie respectate echilibrele firești, evocate anterior, asupra numărului de ore/zi — iar cu o anumită strădanie, putem obține (v. [1], partea a II-a) chiar o repartizare perfectă; dar o repartizare "cvasi-perfectă" (v. partea a IV-a) este ușor de obținut și este acceptabilă.
Lecțiile ajunse într-o aceeași zi pot fi așezate ușor într-un orar al zilei, dacă nu ne pasă încă de ferestre; indiferent ce matrice-orar am constitui, prin refitgaps putem reduce apoi numărul ferestrelor apărute, la o valoare "constantă", dependentă (în general) nu de orarul propriu-zis, ci de fapt numai de setul lecțiilor din acea zi. Problema este acum că uneori, această "constantă" pare totuși mare și repetând refitgaps::recast() pe matricea-orar respectivă (sau pe o nouă matrice-orar, asociată repartiției zilnice existente), nu mai reușim să coborâm numărul de ferestre.
Pentru exemplu, dacă pe matricea-orar dată repetăm de 4 ori recast(), obținând orare cu (15 14 15 16) ferestre, atunci "constanta" referită mai sus ar fi 14 (cea mai mică din seria de valori găsită), în sensul că sunt foarte mici șanse ca repetând încă o dată (sau reluând seria de repetări) să obținem vreun orar cu mai puțin de 14 ferestre (se poate întâmpla, mărind eventual valoarea implicită a parametrului Niter; dar timpul de execuție se va mări sensibil și de obicei, diminuarea nu va fi mai mare decât 1).
Pentru a continua coborârea numărului de ferestre, trebuie să modificăm repartizarea pe zile existentă, mutând lecții dintr-o zi în alta — dar în așa fel încât să nu stricăm echilibrele ("perfecte", sau "cvasi-perfecte") din repartizarea inițială.
În cadrul unei distribuții perfecte (sau cvasi-perfecte) date, dacă vrem să păstrăm caracterul "perfect" al repartizării pe zile respective, lecția P1/K/Z1 se poate schimba cu lecția P2/K/Z2 dacă:
Subliniem că trecerea lecției P1/K din ziua Z1 în ziua Z2 este echivalentă cu trecerea lecției P2/K din ziua Z2 în ziua Z1 (deci avem de considerat unul singur dintre cele două sensuri, pentru a găsi toate interschimbările posibile de lecții).
Următoarea funcție listează (ca data.frame) toate lecțiile care pot fi interschimbate între două zile date (am ales sensul de la Z1 la Z2; lDZ este lista seturilor de lecții prof|cls repartizate în câte o aceeași zi):
get_intersch <- function(lDZ, Z1, Z2) { # Profesorii cu mai multe ore în prima, față de a doua zi profs_to_move <- function(z1, z2) { Ds1 <- table(lDZ[[z1]]$prof) Ds2 <- table(lDZ[[z2]]$prof) n12 <- intersect(names(Ds1), names(Ds2)) names(which(Ds1[n12] > Ds2[n12])) } # Clasele unde profesorul are ore în prima, dar nu și în a doua zi clss_to_move <- function(Prof, z1, z2) { K1 <- lDZ[[z1]] %>% filter(prof == Prof) %>% pull(cls) %>% unique() K2 <- lDZ[[z2]] %>% filter(prof == Prof) %>% pull(cls) %>% unique() setdiff(K1, K2) } # Lecțiile care pot fi trecute din ziua Z1 în ziua Z2 P1 <- profs_to_move(Z1, Z2) P2 <- profs_to_move(Z2, Z1) DF <- data.frame(pr1 = "", pr2 = "", cls = "") for(p1 in P1) { K1 <- clss_to_move(p1, Z1, Z2) if(length(K1) == 0) next # p1 nu are clase de mutat for(p2 in P2) { K2 <- clss_to_move(p2, Z2, Z1) if(length(K2) == 0) next # p2 (curent) nu are clase de mutat K <- intersect(K1, K2) if(length(K) == 0) next # nicio lecție de interschimbat DF <- DF %>% add_row(pr1 = p1, pr2 = p2, cls = K) } } if(nrow(DF) == 1) # nicio lecție nu poate trece din Z1 în Z2, fără return(NULL) # a deteriora caracterul perfect al repartizării lDZ DF[2:nrow(DF), ] }
Este de observat că în formularea ad hoc de mai sus, get_intersch() nu ține seama de posibila existență (dar nu-i cazul de față) a unor cuplaje sau tuplaje…
Prin următoarea funcție schimbăm un profesor cu altul, pe una dintre lecțiile primului la o anumită clasă, în cadrul setului de lecții prof|cls ale unei anumite zile; se returnează setul de lecții rezultat astfel pentru ziua respectivă:
change_lesson <- function (Dz, P1, P2, K) { wh <- which(with(Dz, prof == P1 & cls == K) == TRUE) if(length(wh) > 1) # Dacă P1 are mai multe lecții la clasa K, în acea zi wh <- wh[1] Dz[wh, "prof"] <- P2 Dz }
Interschimbarea lecțiilor P1/K/Z1 și P2/K/Z2 se obține apelând change_lesson() o dată cu argumentele (D1, P1, P2, K) și încă o dată cu (D2, P2, P1, K), unde D1 și D2 sunt seturile inițiale de lecții pe zilele Z1 și respectiv Z2..
S-ar putea să existe vreo interschimbare de lecție care să diminueze pe ambele zile (sau măcar pe una), numărul de ferestre inițial…
Deocamdată, fixăm două zile și determinăm trecerile posibile de lecții din prima în a doua zi; apoi, pentru fiecare dintre aceste interschimbări, aplicăm recast() de câte 4 ori pe matricele-orar rezultate și doar înregistrăm într-un fișier, numărul de ferestre găsit în fiecare caz:
library(tidyverse) library(hours2lessons) library(refitgaps) LSD <- readRDS("lss2days_cvp.RDS") # seturile zilnice de lecții prof|cls z1 <- "Lu"; z2 <- "Vi" # fixăm două zile între care schimbăm câte o lecție Sch <- get_intersch(LSD, z1, z2) # trecerile de lecții din prima zi în a doua # print(Sch) D1 <- LSD[[z1]] # distribuția inițială prof|cls pe prima zi D2 <- LSD[[z2]] # distribuția inițială prof|cls pe a doua zi finm <- paste0(z1, z2, ".txt") sink(finm) # înregistrează în fișier urmele trecerii câte unei lecții show_time("\n") for(i in 1:nrow(Sch)) { S <- as.character(Sch[i, ]) G1 <- change_lesson(D1, S[1], S[2], S[3]) G2 <- change_lesson(D2, S[2], S[1], S[3]) W <- long2matrix(mount_hours(G1)) # o matrice-orar pentru prima zi print(S, quote=FALSE) cat(z1, " ") for(j in 1:4) { R <- recast(W) # reduce ferestrele apărute în prima zi cat(R[[2]], " ") } cat("\n") W <- long2matrix(mount_hours(G2)) # matrice-orar pentru a doua zi cat(z2, " ") for(j in 1:4) { R <- recast(W) # reduce ferestrele apărute în a doua zi cat(R[[2]], " ") } cat("\n") } show_time("\n") sink()
Durata execuției este proporțională cu numărul de interschimbări; ea poate fi estimată, ținând seama că fiecare aplicare recast() consumă aproape constant, cam 50-60 secunde (pe calculatorul nostru). Este de observat că pentru o distribuție pe zile perfectă am avea mult mai puține interschimbări posibile, decât în cazul uneia cvasi-perfecte — fiindcă pentru fiecare profesor, numărul de ore/zi diferă de la o zi la alta, cel mult cu 1 în primul caz, dar cel mult cu 2 în cazul "cvasi-perfect"; deci șansele de a găsi interchimbări care să micșoreze numărul de ferestre sunt mai mari pentru cazul cvasi-perfect, decât pentru cel al unei distribuții perfecte.
În programul de mai sus, în scopul experimentării, am specificat direct fișierul "lss2days_cvp.RDS", în care avem repartizarea cvasi-perfectă pentru care în [1]-IV găsisem un orar cu (9 6 9 9 10) ferestre și deasemenea, am specificat direct cele două zile (Lu și Vi) între care am vrea să găsim o interschimbare de lecție care să asigure posibilitatea unor orare zilnice cu mai puține ferestre (decât 9 și respectiv 10).
Am constatat că între aceste două zile sunt posibile 159 de interschimburi (iar execuția programului a durat aproape o zi; estimativ, 160×8 minute = 21 ore). Filând fișierul LuVi.txt rezultat în final, constatăm că pe orarele zilnice care ar rezulta prin interschimbările respective numărul de ferestre oscilează între 8 și 11 (rar, 12) — redăm aici câteva exemple tipice:
[1] p08 p50 10G
Lu 9 9 8 9
Vi 10 10 11 10
[1] p10 p01 9G
Lu 10 11 10 12
Vi 8 8 8 8
[1] p28 p34 12D
Lu 10 10 10 10
Vi 10 10 12 11
[1] p32 p50 11F
Lu 8 8 8 8
Vi 9 10 10 9
[1] p32 p64 11J
Lu 10 9 10 10
Vi 9 9 10 11
[1] p32 p71 11J
Lu 8 8 8 8
Vi 9 10 10 9
Ne-a rezultat (cel mai puține) 8 fie pe Lu, fie pe Vi, dar niciodată pe ambele zile; am ales o interschimbare (boldată mai sus) care permite un orar cu 8 ferestre pe Lu și cu 9 pe Vi (față de 9 și respectiv 10 câte erau inițial):
D1 <- change_lesson(LSD[["Lu"]], "p32", "p50", "11F") LSD[["Lu"]] <- D1 D2 <- change_lesson(LSD[["Vi"]], "p50", "p32", "11F") LSD[["Vi"]] <- D2
Analog, rulând programul de mai sus pentru alte două zile (obținând fișierele "JoVi.txt" și "LuMi.txt"), am reușit să micșorăm puțin numărul de ferestre pe o zi sau alta, încât distribuția pe zile rezultată ne asigură orare cu (7 6 8 8 9) ferestre — în total 38 de ferestre, adică numai 3.24% din totalul de 1172 lecții.
Pentru repartizarea LSD rezultată mai sus, fixăm câte o matrice-orar pe fiecare zi (folosind mount_hours() și long2matrix()) și apoi căutăm pe fiecare zi câte un orar cu număr de ferestre cel mult egal cu cel estimat mai sus pentru acea zi:
W <- lapply(LSD, mount_hours) Wmo <- lapply(W, long2matrix) Best <- c(7, 6, 8, 8, 9) %>% setNames(names(LSD)) WW <- list() for(zi in names(LSD)) { cat(zi, " "); show_time(" ") repeat{ R <- recast(Wmo[[zi]]) cat(R[[2]], " ") if(R[[2]] <= Best[zi]) { WW[[zi]] <- R show_time("\n") break } } } # Lu 08:37:41 7 08:38:27 # Ma 08:38:27 7 6 08:39:58 # Mi 08:39:58 8 08:40:42 # Jo 08:40:42 10 8 08:42:17 # Vi 08:42:17 9 08:43:02
Putem zice că am avut noroc: recast() n-a trebuit repetat de mai mult decât două ori (și aceasta numai pe două zile, Ma și Jo); dar într-o nouă execuție a secvenței de mai sus, se poate să avem și o serie lungă, precum Vi: 10 10 10 10 10 11 10 ..., prin care să nu se reușească coborârea la valoarea scontată pentru numărul de ferestre — în acest caz, n-avem decât să renunțăm la matricea-orar pe care o fixasem din start pentru ziua respectivă și să formulăm o nouă matrice-orar pe acea zi, recunoscând implicit, că recast() depinde uneori și de matricea-orar pe care o asociem zilei, nu cum ziceam (îndreptățit în general) numai de setul lecțiilor acelei zile.
Este de analizat și distribuția celor 38 de ferestre, pe orarele zilnice obținute:
> lapply(WW, function(W) have_gaps(W[[1]])) $Lu prof 1 2 3 4 5 6 7 ore 1 p43 9A 11E 12H - 12C 11I - ***-**- 2 p11 11I 11D 10I - 11G 12B - ***-**- 3 p65 10B 11K 10A - 9C 10G - ***-**- 4 p15 12E 11C - 10A 9D 11D - **-***- 5 p69 9D 9H - 10G 10E 9A - **-***- 6 p54 10A 12I 11E - 11I 10H - ***-**- 7 p30 11G 12E 9I - 9F 9G - ***-**- $Ma prof 1 2 3 4 5 6 7 ore 1 p58 9B 9C - 12E 9B 10F - **-***- 2 p39 12G 12C 10C - 11G 10B - ***-**- 3 p50 11F 11B 12H - 11E 11A - ***-**- 4 p42 9A 12E 11B - 12B 9C - ***-**- 5 p44 10I 9F - 10A 9D 9E - **-***- 6 p28 11E 12A - 11I 11H 12I - **-***- $Mi prof 1 2 3 4 5 6 7 ore 1 p50 11I 11A 12D - 10E 11E - ***-**- 2 p64 9H 9C 11H - 11J 10H - ***-**- 3 p28 11E 12B 11B - 12H 11A - ***-**- 4 p63 11B 12E - 12F 11K 9E - **-***- 5 p57 11J 9G - 10B 10C 9C - **-***- 6 p17 9I 9F - 10I 12C 9G - **-***- 7 p33 9G 11J 10I - 10H 12B - ***-**- 8 p39 10E 10I 9G - 10F 9B - ***-**- $Jo prof 1 2 3 4 5 6 7 ore 1 p07 11A 11B 9A - 9I - - ***-*-- 2 p26 12E 10C 12C - 10J 9B - ***-**- 3 p48 10C 9H 11F - 12A 11E - ***-**- 4 p44 - 10D - 9C 9A 9H - -*-***- 5 p37 12H 9F 10A - 10G 11C - ***-**- 6 p70 11G 10J - 12H 12G 10G - **-***- 7 p30 11B 11C 10B - 10E 11J - ***-**- 8 p64 10F 11H 12G - 9C 10A - ***-**- $Vi prof 1 2 3 4 5 6 7 ore 1 p43 11I 12C 11G - 9A 12H - ***-**- 2 p34 9E 9I - 11B 12D 9G - **-***- 3 p65 9H 9D - 10G 10B 12G - **-***- 4 p72 12H 9E 11H - 11G 11K - ***-**- 5 p50 11H 11I 11D - 10G 11B - ***-**- 6 p17 9G 10I 9I - 9F 11G - ***-**- 7 p24 10D 10E - 10H 10J 10A - **-***- 8 p64 12D 11J 12A - 9H 10E - ***-**- 9 p40 11G 10D 12F - 9I 11F - ***-**-
De regulă pentru recast(), ferestrele apar în ora a 3-a sau a 4-a dintre cele 7 ale zilei, la profesorii care au multe ore.
Mai sus, profesorii care au ferestre sunt dintre cei cu câte 5 ore/zi (bine, în zilele în care nu au ferestre pot avea între 3 și 6 ore/zi) și numai în două cazuri (p07 și p44 în ziua Jo), dintre cei cu câte 4 ore/zi. În oricare zi, toți care au ferestre, au numai câte una singură (în ziua respectivă); sunt 7 profesori care au câte două zile cu câte o fereastră (de exemplu, p43 are fereastră Lu și Vi); sunt doi profesori (p50 și p64) care au trei zile cu câte o fereastră (repetând, putem găsi orare cu alte distribuții de ferestre).
Poate fi cazul să listăm orarul complet al vreunui profesor:
orar_prof <- function(P) { lapply(WW, function(W) W[[1]][P, ]) %>% as.data.frame() %>% t() } > print(orar_prof("p11"), quote=FALSE) 1 2 3 4 5 6 7 Lu 11I 11D 10I - 11G 12B - Ma 11I 10I 12D 12F - - - Mi 12D 12F 12B - - - - Jo 11D 12B 11G 10I 11I - - Vi 11D 11G 12D 12F - - -
Exemplul redat arată că p11 are o distribuție cvasi-uniformă de ore/zi a celor 21 de ore din încadrarea sa, anume (5 4 3 5 4) și are o fereastră, anume în ora a 4-a din ziua Lu; intră la clasa 11I în câte o oră din zilele Lu, Ma și Jo, ș.a.m.d.
p11 este încadrat pe câte 3 ore/săptămână la 7 clase (10I, 11DGI și 12BDF) și cele 3 ore la o aceeași clasă sunt alocate în zile diferite.
Experimentele evocate mai sus ne-au arătat că prin interschimbarea între două zile a unei singure lecții (păstrând însă echilibrele existente în repartizarea lecțiilor pe zile), putem micșora numărul de ferestre — dar în general numai cu 1 (pe una dintre zile) sau 2 (pe ambele zile, câte una), iar lecția respectivă poate fi aleasă dintr-un set foarte restrâns față de gama tuturor interschimburilor posibile între cele două zile.
E drept însă că aplicând câte un interschimb de lecție mai multor perechi de zile, putem obține o diminuare sensibilă a numărului total de ferestre; mai sus, aplicând pe trei perechi de zile, am redus numărul de ferestre de la 43 câte erau inițial, la 38 (și probabil, considerând încă o anumită pereche de zile, la 36)…
Este de încercat (dacă au rămas prea multe ferestre, nu ca în cazul de față) și ideea de a schimba între două zile nu o singură lecție, ci deodată două sau trei lecții (sau poate mai multe), alese (în lipsa vreunui criteriu fezabil) la întâmplare, din setul interschimburilor posibile (cu sublinierea că pentru a fi siguri că nu perturbăm caracterul "perfect", lecțiile pe care alegem să le interschimbăm trebuie să nu aibă profesori comuni — fiindcă schimbând P1/K1/Z1 cu P2/K1/Z2 și apoi, P1/K2/Z1 cu P3/K2/Z2, profesorul P1 ar căpăta o distribuție pe zile care nu mai este cvasi-omogenă).
vezi Cărţile mele (de programare)