[1] partea a II-a
Repartizarea pe zile a celor 1172 de lecții prof|cls obținută și redată în format CSV în [1] este chiar perfectă — pentru zile, clase, profesori și discipline, distribuția numărului de ore/zi este uniformă, adică pe fiecare zi avem $\boldsymbol{\left\lfloor\frac{N}{5}\right\rfloor} + \left/0\;sau\,1\right/$ ore, unde $N$ este fie totalul de 1172 ore, fie numărul total de ore ale unei clase oarecare, respectiv ale unui profesor oarecare. Dar este "perfectă"… până una-alta; ar fi "chiar perfectă" dacă am reuși să o transpunem într-un orar în care și numărul total de ferestre, cât mai mic posibil, să aibă deasemenea, distribuție uniformă pe zile.
Vom aloca lecțiile fiecărei zile pe ore; aceasta durează numai câteva secunde (dacă precum în cazul de față, nu există cuplaje și tuplaje), fiindcă pe lângă obligația ca oricare două lecții să nu se suprapună într-o aceeași oră, avem o singură pretenție: să nu apară mai mult de două ferestre la vreun profesor.
Orarul rezultat pe fiecare zi conține atunci foarte multe ferestre; urmează să reducem pe cât se poate, numărul total de ferestre (operație care pentru o zi, durează de obicei, neavând cuplaje și tuplaje, cam un minut). Dacă după reducere, numărul de ferestre nu depășește 4% (…hai 5%) din totalul lecțiilor, atunci putem fi mulțumiți (chiar dacă n-ar fi distribuit uniform pe zile); altfel… înseamnă până la urmă că repartizarea pe zile, chit că "perfectă", trebuie totuși corijată (păstrând totuși echilibrele).
Recuperăm repartizarea pe zile din [1], având grijă să transformăm prof din 'factor' în 'character' (cum pretinde mai jos mount_hours()); apoi separăm lecțiile pe zile (eliminând de pe ziua curentă câmpul zl) și salvăm lista rezultată:
library(tidyverse) DZ <- readRDS("by_days.RDS") %>% mutate(prof = as.character(prof)) lDZ <- lapply(split(DZ, ~ zl), function(D) D[, 1:2]) saveRDS(lDZ, "lss2days.RDS") # fiecărei zile, setul lecțiilor prof|cls ale ei
Pentru a deduce duratele de execuție folosim o funcție care afișează (într-o formatare convenabilă) timpul curent:
show_time <- function(NL = " ") cat(strftime(Sys.time(), format="%H:%M:%S"), NL)
Pentru fiecare zi, alocăm lecțiile pe orele 1:n (unde n este numărul maxim de ore/zi pentru clase, în ziua respectivă), folosind pachetul hours2lessons; salvăm pe disc lista orarelor zilnice în "format lung" (cu linii prof|cls|ora) și deasemenea (pentru reducerea ferestrelor apărute), lista acestora în format de "matrice-orar":
library(hours2lessons)
LSS <- readRDS("lss2days.RDS") # 235 234 234 235 234 prof|cls (chr)
W <- list() # pregătește lista orarelor zilnice
show_time()
for(zi in names(LSS))
W[[zi]] <- mount_hours(LSS[[zi]]) # orar inițial pentru zi
show_time("\n")
saveRDS(W, "lst_day_orr1.RDS")
Wm <- lapply(W, long2matrix) # matricele-orar inițiale
saveRDS(Wm, "lst_day_orr1_mat.RDS")
Încărcăm acest program și pentru încă o edificare, inspectăm datele rezultate:
> source("1.R") # lansează programul scris mai sus 06:30:12 06:30:16 # durata obținerii orarelor zilnice: 4 secunde > glimpse(W[["Lu"]]) # ilustrăm orarul rezultat pentru Lu (cu 235 lecții) Rows: 235 Columns: 3 $ prof <ord> p69, p06, p24, p65, p15, p37, p45, p69, p06, p12, p65, p63, p19 ... $ cls <chr> "10A", "10A", "10A", "10A", "10A", "10A", "10B", "10B", "10B", ... $ ora <int> 2, 6, 1, 5, 4, 3, 1, 5, 4, 6, 3, 2, 6, 5, 2, 3, 1, 4, 6, 2, 4, 1, ... > glimpse(Wm[["Lu"]]) # ilustrăm matricea-orar pe Lu chr [1:63, 1:7] "-" "-" "-" "-" "9F" "11C" "-" "10B" "-" "9H" "12I" "-" ... - attr(*, "dimnames")=List of 2 ..$ : chr [1:63] "p49" "p05" "p02" "p10" ... ..$ : chr [1:7] "1" "2" "3" "4" ...
Din orarul rezultat pe Lu, listăm subsetul celor la care au apărut ferestre (pe seama acestuia vom face apoi anumite precizări asupra alocării pe ore a lecțiilor zilei):
> have_gaps(Wm[["Lu"]]) # profesorii care au căpătat ferestre în ziua Lu
prof 1 2 3 4 5 6 7 șablonul alocării orelor
1 p05 - - 12A - - 12A - --*--*-
2 p31 11I - - 12E - - - *--*---
3 p56 9G 10H - 9I - - - **-*---
4 p66 - 12D - 9C 10E 12D - -*-***-
5 p53 - 10F - 12G 11B - - -*-**--
6 p33 9C 11J - 10I 10H - - **-**--
7 p55 9E - 10J - 9H - - *-*-*--
8 p03 10E 9E - - 10J 9A - **--**-
9 p59 11E - 11J 9A - 12B - *-**-*-
10 p43 12H - - 11A 11I 12C - *--***-
11 p69 10A - - 10B 10I 10G - *--***-
12 p21 11J 12B - 11H 12C - - **-**--
13 p60 10I 11A - - 11J 10H - **--**-
14 p06 - 10B 10E - 10A 9C - -**-**-
15 p28 12D 11H 11E - 12B - - ***-*--
16 p07 9A - 11A 10E - 12H - *-**-*-
17 p57 10H - 9C - 9G 9E - *-*-**-
18 p51 10G - 9D - 12G 11K - *-*-**-
19 p26 - 11F - 12C 12E 10J - -*-***-
20 p70 9I - 12C 11G 12H - 11H *-***-*
21 p34 9D 9G - 12D - 11D - **-*-*-
22 p24 - 10A 10H 10D - 10E - -***-*-
23 p09 - 10E - 9H 9A 11E - -*-***-
24 p17 - 10I 11C - 9I 9G - -**-**-
25 p08 11B - 10G - 11C 10C - *-*-**-
26 p13 11K 11G - 10C 11A - - **-**--
27 p36 12C 12I 12F - 9D 11B - ***-**-
28 p01 - 10D 9G - 9F 12I - -**-**-
29 p54 - 11I 12D 12A - 9D - -***-*-
30 p65 10B 9D 12G 10A - 9H - ****-*-
31 p67 10C - - 12B 11E 9B - *--***-
32 p30 10D - 9F 10G - 11J - *-**-*-
33 p15 11D 11C 12E - - 10A - ***--*-
34 p29 12G 9H 11B - 11K 10D - ***-**-
35 p40 12B 11K 9I 11F - 11H 11A ****-**
36 p48 12A - 11F 11E 10D - - *-***--
37 p11 12F 11D 11G - 12D 10I - ***-**-
38 p20 10J - 9A 11D 12I 11I - *-****-
39 p37 9F - 10A 9D 11G 11C - *-****-
40 p42 11A 12A - 12F 9E 12E - **-***-
41 p64 10F - 11H 10H 9C 9F - *-****-
42 p58 12E 9C 9B 10F - 11A - ****-*-
mount_hours() alocă pe ore lecțiile unei clase, apoi ale alteia, ș.a.m.d. până ce se trece prin toate clasele (evitând de fiecare dată, suprapunerea de lecții) — dar într-o anumită ordine a claselor (în principiu, crescător după numărul de profesori comuni) și profesorilor (după numărul de clase comune); de aceea, pe primele linii din matricea-orar rezultată (cum vedem și pe submatricea redată mai sus) apar profesorii care au numai două sau trei ore (deci au puține clase în comun cu următorii) — cu unele excepții, din cauza faptului că eventualele reluări ale parcurgerii claselor (până ce se reușește trecerea prin toate clasele) se face într-o ordine ușor modificată față de trecerea tocmai eșuată, a acestora.
Numărând orele libere "-" aflate între clase propriu-zise în submatricea redată mai sus, constatăm că pe ziua Lu a rezultat un număr uriaș de ferestre, 55 (aproape un sfert din totalul 235 al lecțiilor) — toate de câte o oră sau de câte două ore (consecutive sau nu), la 42 de profesori. Reducerea numărului de ferestre (prin refitgaps::recast()) se bazează pe faptul că în matricea-orar fiecare clasă apare câte o singură dată pe fiecare coloană (permisă de numărul de ore/zi la acea clasă) și pleacă de la "șabloanele orare" ale liniilor cu ferestre (adăugate mai sus pe o coloană separată de matricea-orar) — ideea fiind de a acoperi cât mai multe ferestre prin interschimbări de clase de pe o coloană în alta:
library(refitgaps) # v. https://cran.r-project.org/package=refitgaps Wmo <- readRDS("lst_day_orr1_mat.RDS") # lista matricelor-orar inițiale W <- list() # pregătește lista noilor orare zilnice for(zi in names(Wmo)) { cat(zi, ": ", sep=""); show_time() Orr <- recast(Wmo[[zi]]) #, Niter = 6000) show_time(" "); cat(Orr[[2]], "gaps\n") W[[zi]] <- Orr[[1]] } saveRDS(W, "lst_day_orr2_mat.RDS") # un orar cu mult mai puține ferestre # Lu: 18:44:18 18:45:09 17 gaps # inițial erau 55 de ferestre # Ma: 18:45:09 18:45:59 12 gaps # Mi: 18:45:59 18:46:48 13 gaps # repetând, coboară la 12 ferestre # Jo: 18:46:48 18:47:38 15 gaps # Vi: 18:47:38 18:48:25 12 gaps
Bineînțeles că am repetat secvența redată mai sus de vreo zece ori, obținând alte orare zilnice, cu alte distribuții de ferestre — dar numai pe Mi, numărul de ferestre a putut fi coborât, la 12, în loc de 13; deci în cel mai bun caz, am avea în total 68 de ferestre, însemnând 5.80% din totalul 1172 al lecțiilor.
Totuși, numărul de ferestre apărute Lu și Jo, 17 respectiv 15, este prea mare față de celelalte zile (pe care 12 ferestre pare iarăși, cam mult).
Nu prea vedem cum să mai "perfecționăm" recast(), care în starea actuală (după atâtea "perfecționări" anterioare) asigură un compromis bun, general, între durată (50-60 secunde) și numărul ferestrelor rezultate pe orarul zilei curente (cel mult vreo 7% din totalul lecțiilor zilei).
Cel mai simplu mecanism pentru a încerca să obținem pentru lecțiile unei zile un orar cu cât mai puține ferestre ar fi acesta: generăm în mod repetat un orar (aplicând mount_hours() pe setul de lecții ale zilei) și de fiecare dată, pe matricea-orar rezultată aplicăm repetat de un anumit număr de ori, recast() — reținând acel orar dintre cele rezultate astfel, care are mai puține ferestre decât cel generat la început:
try_drop_gaps <- function(zi, Best) { # Best: cam câte ferestre așteptăm Z <- LSS[[zi]] # setul lecțiilor de pe ziua respectivă repeat { W <- long2matrix(mount_hours(Z)) # montează un nou orar show_time(" ") R <- recast(W) show_time(" "); cat(R[[2]], "gaps\n") for(i in 1:6) { # încercări de reducere a ferestrelor Orz <- recast(W) # repetă reducerea show_time(" "); cat(Orz[[2]], "gaps\n") if(Orz[[2]] < R[[2]]) R <- Orz # "cel mai bun" până la momentul curent } if(R[[2]] < Best) break } R # "cel mai bun" orar (mai puține ferestre decât estimarea Best) }
De exemplu, să căutăm pe Lu un orar cu mai puțin decât Best=18 ferestre:
> R <- try_drop_gaps("Lu", 18) 09:44:14 09:45:06 18 gaps 09:45:58 17 gaps 09:46:49 18 gaps 09:47:41 19 gaps 09:48:32 17 gaps 09:49:24 18 gaps 09:50:15 18 gaps # în R avem acum un orar cu 17 ferestre
Dintre orarele generate, al doilea are 17 ferestre (mai mic decât Best) și niciunul dintre cele rezultate după aceea nu are mai puțin de 17 ferestre — prin urmare, în final este returnat al doilea dintre cele 7 orare produse mai sus.
Dar dacă încercăm cu Best=17, șansele ca execuția funcției de mai sus să ajungă la break (pentru a ieși de sub repeat{ ), adică șansele de a returna un orar R cu mai puține ferestre decât 17, scad spre zero (și după mai bine de o oră, am întrerupt execuția).
Am experimentat mecanismul try_drop_gaps() și pentru celelalte zile, dar pentru niciuna, numărul de ferestre n-a putut fi coborât mai jos de limitele redate mai sus…
Experimentele tocmai evocate se dovedesc inutile, dar evidențiază o subliniere care ne-a scăpat "printre degete" cam de pe când am început să ne referim pe aici la funcția de reducere a ferestrelor: recast() nu are de-a face cu orarul inițial, ci doar cu faptul că acesta este unul corect (adică nu conține suprapuneri de lecții); orice orar (corect) am avea pentru lecțiile date ale zilei, recast() va reduce ferestrele existente nu mai jos decât o anumită valoare, aproape constantă față de repartiția pe zile dată (pot fi diferențe de numai una sau două ferestre, într-o serie de orare pe care le-ar produce).
Vom încerca mai încolo o altă idee, plecând de la rădăcina lucrurilor, adică de la repartizarea pe zile… Cel mai simplu (dar… simplist) este să generăm o nouă repartizare pe zile (ceea ce durează numai câteva secunde), cu speranța că pe aceasta (după ce-i aplicăm mount_hours() pentru a avea un orar inițial), recast() va reuși să micșoreze numărul de ferestre, față de repartizarea pe zile anterioară; necazul este că noua repartizare pe zile nu este "perfectă" și trebuie să intervenim interactiv (v. [1]) pentru a omogeniza distribuțiile individuale (și abia apoi, să ne ocupăm de ferestre).
Dar oare nu găsim vreo clasă K (mai multe?) și distribuții individuale prof|K pe care să le schimbăm între cele două zile (fără a perturba "perfecțiunea" repartiției pe zile), astfel încât după modificare, orarele rezultate prin mount_hours() pe cele două zile, să aibă după ce aplicăm recast(), mai puține ferestre (decât 17 și 15, în cazul de mai sus) ?
Și probabil că aceste două idei pot fi îmbinate și simplificate: de ce să regenerăm întreaga repartiție pe zile, dacă ne interesează numai cele două zile? În loc să depistăm vreo clasă K și distribuții individuale prof|K pe care să le schimbăm între cele două zile, am putea regenera (cu grijă față de omogenitate) noi repartiții numai pentru cele două zile (repetând, dacă recast() nu coboară suficient, numărul de ferestre pe orarele celor două zile).
vezi Cărţile mele (de programare)