momente şi schiţe de informatică şi matematică
To attain knowledge, write. To attain wisdom, rewrite.

Problema orarului școlar echilibrat și limbajul R (IV)

limbajul R | orar şcolar
2023 may

[1] Vlad Bazon - Problema orarului școlar, pe tărâmul limbajului R (Google Play/Books, 2022)

[2] Problema orarului școlar echilibrat și limbajul R (I - III)

Am evidențiat în [2] că search_better() tinde să nu mai poată reduce ferestrele, încât pe ziua respectivă rămân uneori prea multe ferestre; am dat vina pe faptul exterior că există prea multe cuplaje (și întortocheate)… Dar o bună parte de „vină” este ascunsă tocmai în „rețeta” etapizată aplicată pentru reducerea ferestrelor.

Întâi, am repartizat pe zilele de lucru lecțiile prof|cls (urmărind echilibrul, pe fiecare zi, clasă, profesor și obiect); apoi, am repartizat pe orele zilei lecțiile dintr-o aceeași zi (încât să nu existe suprapuneri și… fără să ne pese prea mult de ferestre, urmărind doar ca per profesor să nu avem mai mult de două); în final, ne-am pus și problema reducerii numărului total de ferestre, pe fiecare dintre orarele zilnice obținute.
Cu timpul, a devenit clar că am separat prea tare, aceste etape; de exemplu în [2], rămânând cu 13 ferestre în ziua Ma și constatând că nu mai putem reduce ferestrele respective, am ajuns la „ideea” de a schimba lecții dintr-o zi în alta – altfel spus, la necesitatea reluării parțiale a primei etape.

Pentru a reduce treptat ferestrele din orarul curent al unei zile, operația de bază move_cls() constă în mutarea unei clase într-o altă coloană orară, implicând (pentru a evita apariția de suprapuneri) mai multe schimburi de clase între cele două coloane; dar dacă prin aceste schimburi apare o suprapunere cu vreunul dintre cuplaje, atunci move_cls() refuză mutarea (returnând NULL). Cu alte cuvinte… se operează în principal numai pe profesori neimplicați în cuplaje – ca și când orele alocate cuplajelor ar fi fost cumva fixate în prealabil!

Odată conștientizat acest aspect, avem o soluție simplă pentru a continua reducerea de ferestre; dacă pentru orarul curent al zilei, search_better() nu reușește să mai coboare suficient numărul de ferestre, atunci… o luăm de la capăt: plecăm iarăși de la lecțiile prof|cls repartizate deja în ziua respectivă, alocăm lecțiile pe orele zilei folosind mount_hours() și pe noul orar al zilei obținut astfel – cu altă „fixare” pe ore a cuplajelor și cu altă „listă de mutări corectoare” – aplicăm iarăși search_better().
Cu alte cuvinte, soluția constă în îmbinarea pe fiecare zi în parte, a ultimelor două etape: generăm orarul zilei curente și reducem ferestrele acestuia – repetând până când numărul de ferestre devine suficient de mic (sau, nu mai poate fi redus într-un timp rezonabil).

Pentru exemplificare, să reluăm din [2] repartiția pe zile orarMai.RDS a lecțiilor prof|cls – pentru care, operând separat cele trei etape menționate, obținusem în final orare zilnice cu 6 12 9 5 4 ferestre (și search_better() n-a mai putut reduce ferestrele pe zilele Ma și Mi).

Deocamdată, pentru a lămuri cât mai bine lucrurile, descriem cam cum a decurs încercarea de a obține – prin „îmbinarea” ultimelor două etape – un orar pe ziua de Ma care să aibă totuși mai puțin de 12 ferestre (redăm mai jos programul respectiv, după o anumită completare):

10:11:17  # se pleacă de la repartiția prof|cls pe Ma
31  10:12:13  # orarul prof|cls|ora (după cam 1 minut, cu aproximativ 31 ferestre)
[1] 31  # întâmplător, sunt într-adevăr exact 31 de ferestre...
30  29  27  26  25  24  23  22  20  19  18  17  16  15  14  13  12  * 12  * 12  * 12  * 12  * 12  * 12  10:17:04   # s-a reușit reducerea până la 12 ferestre
[1] 31  # a doua încercare de reducere, pe același orar
28  27  25  24  23  22  21  20  19  18  17  16  14  13  12  * 12  * 12  * 12  * 12  * 12  * 12  10:21:37 

Orarul zilei se obține foarte rapid (până la unu-două minute), fiindcă mount_hours() nu se cramponează de totalul ferestrelor (se ignoră ferestrele induse de cuplaje – motiv pentru care numărul total de ferestre afișat după mount_hours() este doar unul estimativ).
La prima încercare, search_better() a redus numărul de ferestre la 30, apoi la 29, 27, 26, etc. – oprindu-se (după numărul de iterații prevăzut ca parametru) la 12 ferestre. Cam la fel și la a doua încercare (pe același orar, cu 31 de ferestre inițiale).

Continuând, am obținut peste câtva timp un orar care inițial avea 36 de ferestre (nu 38, cât estimase mount_hours()) și după câteva încercări, a rămas cu numai 11 ferestre:

10:40:53  # se pleacă iarăși de la repartiția prof|cls pe Ma
38  10:41:38  # orarul prof|cls|ora (după cam 1 minut, estimând 38 de ferestre)
[1] 36  # numărul real de ferestre
35  33  32  31  30  29  28  27  26  23  22  21  20  19  18  17  16  15  14  13  12  * 12  * 12  * 12  * 12  * 12  * 12  10:46:06 
####  alte câteva încercări de reducere, fără vreo îmbunătățire
[1] 36
35  34  33  31  30  29  28  27  26  25  24  23  22  21  20  18  17  16  15  14  13  12  * 12  * 12  * 12  * 12  * 12  * 12  11:00:06 
[1] 36
35  33  30  29  27  26  25  24  23  22  21  19  18  17  16  15  14  13  * 13  11  * 11  * 11  * 11  * 11  * 11  11:04:42   # în sfârșit - reducere la 11 ferestre

Am continuat astfel încă vreo două ore (se poate observa și din datele redate mai sus, că fiecare încercare de reducere ia nu mai mult de 4-5 minute) – dar n-a rezultat nici un orar cu mai puțin de 11 ferestre (ceea ce este încă nesatisfăcător)… Totuși am învățat din această experiență că sunt necesare numai câteva încercări, nicidecum pe parcursul a două ore.

Epuizând practic, speranțele de a obține pentru lecțiile repartizate zilei Ma un orar cu mai puțin de 11 ferestre, ne rămâne să „îmbinăm” și cu prima etapă: decidem să schimbăm una-două lecții între cele două zile (Ma și Mi, pe care numărul de ferestre este sensibil mai mare, decât pe celelalte zile).
Pentru alegerea lecțiilor de schimbat între cele două zile – vizualizăm (și comparăm cumva) repartițiile ferestrelor din cele două orare, folosindu-ne de funcția emph_gaps() din [2]; dar nu vedem un criteriu infailibil, pentru o alegere promițătoare a lecțiilor de schimbat între zile…

În programul următor preluăm lecțiile repartizate pe Ma și pe cele repartizate pe Mi; înlocuim pe Ma lecția Ch2|8C cu En2|8C și invers pe Mi – lecția En2|8C cu Ch2|8C; deasemenea, schimbăm între Ma și Mi, lecția la clasa 10E între cuplajul GF2GF3 și profesorul Lo1. Subliniem că aceste schimbări nu afectează listele de dependențe între profesori și cuplajele în care sunt angajați (altfel, aceste dependențe trebuie imediat actualizate).
Apoi, căutăm pe un număr rezonabil de iterări, orarul „cel mai bun” pentru Ma – cel care pentru lecțiile prof|cls din repartiția astfel modificată, are un cel mai mic număr de ferestre:

library(tidyverse)
source("support.R")  # v. [1]
source("mount_h.R")  # funcții pentru generarea orarului unei zile 
source("reduce_gaps.R")  # funcții pentru reducerea ferestrelor din orarul zilei

LSS <- readRDS("R12_Mai_ldz.RDS") # dicționar zi ==> lecțiile prof|cls ale zilei

LSS[["Ma"]] <- LSS[["Ma"]] %>% 
               mutate(prof=replace(prof, prof=="Ch2" & cls=="8C", "En2"))
LSS[["Mi"]] <- LSS[["Mi"]] %>% 
               mutate(prof=replace(prof, prof=="En2" & cls=="8C", "Ch2"))
LSS[["Ma"]] <- LSS[["Ma"]] %>% 
               mutate(prof=replace(prof, prof=="GF2GF3" & cls=="10E", "Lo1"))
LSS[["Mi"]] <- LSS[["Mi"]] %>% 
               mutate(prof=replace(prof, prof=="Lo1" & cls=="10E", "GF2GF3"))

zi <- "Ma"  # respectiv, zi <- "Mi"
set_globals(zi)  # listele de dependențe pentru cuplaje (v. [1]); vectorul claselor
bNG <- 12  # cel mai bun număr de ferestre
bW <- NULL  # cel mai bun orar
for(i in 1:10) {
    prnTime('\n') # afișează timpul inițial
    ORR <- mount_hours(LSS[[zi]], zi)  # un nou orar pentru lecțiile de Ma
    prnTime('\n') # timpul curent
    for(i in 1:6) {
        Mop <- ORR %>% prof_matrix()
        Cmb <- combn(ncol(Mop), 2)
        NG1 <- count_gaps(Mop) # numărul iniţial de ferestre
        print(NG1)
        W <- search_better(Mop, Niter = 6000, GD = 4)  # v. [1]
        prnTime("\n")
        if(NG1 < bNG) {  # reține cele mai bune valori
            bW <- W
            bNG <- NG1
        }
    }
}
saveRDS(bW, "orrMa.RDS")  # respectiv, saveRDS(bW, "orrMi.RDS")

După un număr de încercări „eșuate” (terminate cu 13, 12 sau 11 ferestre), am obținut și orare cu 9 ferestre (dar, niciunul cu mai puține – pe parcursul a vreo 3 ore):

13:12:05 
40  13:12:07 
[1] 34
32  31  30  29  28  27  26  25  24  20  19  18  17  16  15  14  13  12  11  * 11  10  * 10  * 10  * 10  * 10  * 10  13:16:56 
[1] 34
32  30  28  27  26  25  24  23  21  20  19  18  17  16  15  14  13  12  11  * 11  10  9  * 9  * 9  * 9  * 9  * 9  13:21:42 

Am repetat apoi programul de mai sus pentru ziua Mi, cu speranța obținerii unui orar cu mai puțin de 9 ferestre – dar fără succes. E clar că n-am nimerit cele mai potrivite schimbări de lecții, între cele două zile… (dar nu mai încercăm altele).

În final, avem acum un orar (echilibrat, spre deosebire de orarul original de pe care dedusesem datele de încadrare) cu 6 9 9 4 4 ferestre zilnice (în total, 32 de ferestre – cu 23 mai puține decât pe orarul original).
Tot „în final”, constatăm în baza celor de mai sus că avem de rescris/completat cel puțin capitolul 4 „Reducerea ferestrelor”, din [1] – aceasta, dacă nu rămânem totuși la ideea că o „carte de programare” trebuie doar să deschidă niște probleme și direcții de abordare și nu neapărat, să le trateze exhaustiv. În orice caz, ne-a devenit clar că titlul cărții ar fi trebuit să fie și mai țintit: Orare școlare echilibrate și limbajul R.

vezi Cărţile mele (de programare)

docerpro | Prev |