[1] Problema orarului școlar echilibrat și limbajul R
[2] V. Bazon - Orare școlare echilibrate și limbajul R https://books.google.ro/books?id=aWrDEAAAQBAJ
Ne-am grăbit anterior să exprimăm bănuiala că din cauza existenței unor perechi și triplete de clase cuplate, ar fi „(mult) mai complicat decât în [2]” să repartizăm lecțiile unei zile pe orele 1:7… Totuși temerile subînțelese de aici, sunt nejustificate – instrumentarea din [2] este suficientă pentru a acoperi și cazul când avem clase cuplate: montăm orele fără a ține seama de existența claselor cuplate și apoi exploatăm procedura de reducere a ferestrelor în sensul potrivirii în câte o aceeași coloană orară a unor clase precizate.
Ca în [2] (sau eventual, v. [1]), din repartizarea pe zile R12i.RDS obținem lista R12_ldz.RDS care asociază fiecărei zile, lecțiile prof|cls din acea zi; pregătim listele lTz1 și lTz2 care indică pe fiecare zi, dependențele (extrase din Tw12.Rda) între profesorii angajați în cuplaje pe acea zi; constituim pe fiecare zi, grafurile de profesori și de clase care reflectă existența unor clase comune, respectiv a unor profesori comuni și reținem în BTW.rda coeficienții "betweenness" ai nodurilor celor două grafuri (am justificat în [2] că parcurgând lecțiile în ordini „apropiate” acestor coeficienți, obținem cel mai rapid, un orar).
Funcția mount_hours() din [2] etichetează lecțiile unei aceleiași zile cu orele 1:7 ale zilei, astfel încât să se evite suprapunerea de lecții într-o aceeași oră, să se respecte programul normal (care începe de la prima oră a zilei, pentru toate clasele) și să se creeze cumva premise pentru existența unui număr cât mai mic de ferestre (asigurând minimal, că orarele individuale – „pe orizontale” – nu conțin mai mult de câte două ferestre).
Subliniem că mount_hours() nu are în vedere și dependențele pe care le-am exprimat mai demult aici în setul Tw3, referitoare la perechile și tripletele de clase cuplate – pe care deocamdată, pur și simplu le ignorăm.
Am putea complica mount_hours(), vizând și condiția ca anumite clase, la unii profesori, să fie plasate în câte o aceeași oră – dar va trebui să ținem seama de această condiție și în cursul procedurii ulterioare de reducere a ferestrelor; am prefera să ne ocupăm într-un singur loc de clasele cuplate, deci alegem să le vizăm cumva abia în reduce_gaps().
Cu pregătirile evocate pe scurt mai sus, putem lansa mount_hours() și alegând ca plafon pentru numărul (estimativ) de ferestre pe zi, 16% din totalul lecțiilor (185 în două zile și 186 în celelalte trei) – obținem ("de exemplu" – fiindcă la fiecare nouă invocare vor rezulta alte valori și alte orare, ca urmare a naturii aleatoare a procedurii de montare a orelor), în mai puțin de 1 minut:
15:40:55 # momentul lansării montării pe ore a lecțiilor fiecărei zile 27 Lu 15:40:56 # orarul pe Lu (în 1 sec.; 27 ferestre "pe orizontale") 27 Ma 15:41:35 # orarul pe Ma (în 39 sec.; 27 ferestre) 30 Mi 15:41:35 29 Jo 15:41:39 27 Vi 15:41:43
Am salvat în orr1.RDS, lista celor 5 orare zilnice rezultate.
Dar în continuare ne ocupăm de orarul pentru Lu (problema fiind aceea de a vedea cum să-l modificăm, pentru a corespunde condițiilor referitoare la clasele cuplate); întâi, să reducem ferestrele (până pe la 20% din câte erau inițial), prin programul reduce_gaps.R din [2]:
# "program principal" în reduce_gaps.R (v. [2]) ORR <- readRDS("orr1.RDS") # orarele prof|cls|ora pe fiecare zi zi <- "Lu" set_globals(zi) Mop <- ORR[[zi]] %>% hourly_matrix() # matricea orară a zilei Cmb <- combn(ncol(Mop), 2) # combinările de 7 (sau 6) luate câte două NG1 <- count_gaps(Mop) # numărul iniţial de ferestre Good <- NG1 %/% 5 # numărul redus sperat de ferestre prnTime(paste0(" (", NG1, " ferestre)\n")) lu <- search_better(Mop) prnTime("\n")
De la orarul inițial cu 27 de ferestre (este o întâmplare că de data aceasta avem același număr, socotind nu numai „pe orizontale”, dar și „pe verticale” – cum impune existența cuplajelor), s-a ajuns succesiv la un orar cu 25, 23, 22, ... și în final unul cu 7 ferestre, care n-au mai putut fi reduse (se ajunge la 8 sau chiar 7 ferestre într-un timp cuprins între 2 și 5 minute; restul timpului este consumat de încercările – rar reușite – de a coborâ și mai mult, numărul de ferestre):
> source("reduce_gaps.R") 09:43:44 (27 ferestre) 25 23 22 21 20 19 17 16 15 14 13 12 11 10 9 8 * 8 * 8 7 * 7 * 7 * 7 * 7 10:16:17 > saveRDS(lu, "Lu7.RDS")
Redăm orarul cu 7 ferestre rezultat, ordonând după prof și formatând pe două coloane:
> lu <- lu[order(rownames(lu)), ] > lu <- cbind(rownames(lu), lu) > data.frame(lu[1:30, 2:8], rep(" ", 30), rbind(lu[31:59, ], " "), check.names = FALSE, fix.empty.names = FALSE) 1 2 3 4 5 6 7 1 2 3 4 5 6 7 Bl1 - - - 11C 10F 12C - LI2 - - - - 9A 10C - Bl2 10C 11B 9C 7A - - - LI2LI1 - - - 10A - - - Bl3 9D 12D 6B 11D - - - LI3 - - - - 11D 11B - CC1 - - 8A 6A 10B 7B - LR1 - - 12B 9A 10A 12A - Ch1 11D 11A 10D - - - - LR2 - - 5A 9B 5B 10B - Ch2 8A 7A 9E - - - - LR3 10E 9F 11F - - - - Ch3 - - - - 11C 12D - LR4 7A 8B 7B - - - - Ch4 12C - - - - - - LR5 6A 9D 12C 10F - - - Ds1 - - 6A 5A 12F 9A - LR6 11E 9E 12E - - - - ET1 - - - - 8A 8B - LR7 9C 11C 12D - - - - Fl1 12A 12F - 12E 12C - - Lt1 9E 10E - - - - - Fz1 11B 10B 11D 10C 10D - - Mt1 12D 6A 5B 12C 7B - - Fz2 11A 9A - 12D 9B - - Mt2 - - 9A 9D 12A 11A - Fz3 - - - 9C 12B 9F - Mt3 12B 9B 11B 8B - - - Fz5 - - - - 6B 6A - Mt4 - - 11C 9E 9F 11D - Gg1 - - 11E 5B 5A 9D - Mt5 - - - 10D 10E 11E - Gg2 11F 6B 10C 8A - - - Mt6 - - - 6B 9C 8A - IH1 - - - - 11B 11C - Mt7 - - - - 12E - - Is1 - - - 10E 6A 7A 8A Mz1 5A 7B 9B - - - - Is2 12E 9C 9F - - - - Ps1 10D 10F 12F - - - - Is3 5B 10D 10F 12F - - - Ps2 - - - - 11E 11F - Is4 - 11F - - - - - Rl1 9F 11E - 12A 10C 12E - LE1 8B 10C 9D - - - - Rl2 10A 5A 11A - - - - LE2 - - - 12B 11A 9B - Sp1 6B 12B 8B 10B - - - LE3 11C 10A - 11F 9E - - Sp2 9A 5B 10A - 7A - - LG1 - - 10B 11B 9D 12F - Sp3 12F - - - - - - LG2 - 12E - 11E 8B 10A - Tc1 - - 10E 9F 12D 9C - LG3 7B 12C - 11A 11F - - Tc2 10B 8A - - - - - LG4 10F 11D 7A 7B - - - Tc2LI1 - - 12A - - - - LI1 9B 12A - - - - -
Să ne amintim că în ziua Lu avem niște perechi sau triplete, de clase cuplate:
> P23 <- readRDS("cls23_days.RDS>") %>% rename(zl = zi) > P23 %>% filter(zl == "Lu") %>% select(prof, cls) prof cls 1 Ds1Mz1 9A 9B 2 LG2LG1 10A 10B 3 LG2LG1 12E 12F 4 LG2LG3 11E 11F 5 LG3LG1LG4 11A 11B 11D
Deci la Ds1 și Mz1, clasele 9A și respectiv 9B ar trebui să cadă într-o aceeași oră – și nu în ora a 6-a și a 3-a, cum avem în matricea orară lu pe care am obținut-o mai sus; celelalte cuplaje de clase din P23 nu sunt, nici ele, corect reflectate în lu.
Subliniem că în matricea orară, fiecare clasă apare câte o singură dată pe fiecare coloană (dar poate lipsi pe coloana 6 sau 7, dacă are numai 5 sau 6 ore/zi) – pentru a evita suprapunerea a doi profesori la o aceeași clasă într-o aceeași oră a zilei. Deci mutarea unei clase dintr-o coloană orară h1 într-o altă coloană h2, impune și mutarea inversă a acelei clase, din h2 în h1 – și se ajunge la un lanț de interschimbări obligatorii de clase între cele două coloane (cum am arătat în [2], un lanț-Kempe în graful claselor din cele două coloane, adiacența fiind dată de prezența pe o aceeași linie); funcția move_cls() (v. [2]) realizează asemenea mutări de clasă și este ingredientul de bază pentru procedura de reducere a ferestrelor.
Până ce vom reuși cândva să corelăm într-un program, move_cls() cu datele din P23 – să observăm că în cazul concret de aici este ușor să procedăm „manual” (interactiv)…
Să observăm întâi linia lui Mz1 și liniile care au 9A sau 9B în coloana 6:
> lu[c(which(lu[,3]=="9B"), which(lu[, 6] %in% c("9B", "9A"))), ] %>% print.table() 1 2 3 4 5 6 7 Mz1 5A 7B 9B - - - - Ds1 - - 6A 5A 12F 9A - LE2 - - - 12B 11A 9B -
Prin move_cls(3, 6, "9B") am crea posibilitatea ca Ds1 și Mz1 să intre (în ora 6) la 9AB, alternând apoi săptămânal între ei, cele două clase (iar LE2 ar rămâne tot cu 0 ferestre). Însă astfel, Mz1 ar căpăta deodată 3 ferestre – încât s-ar cuveni să căutăm o altă soluție.
Aducem 9A din coloana 6 în coloana 2 și 9B din coloana 3 în coloana 2:
> lu <- move_cls(lu, 6, 2, "9A") 1 2 3 4 5 6 7 1 2 3 4 5 6 7 Ds1 - - 6A 5A 12F 9A - | - 9A 6A 5A 12F - - Fz2 11A 9A - 12D 9B - - | 11A - - 12D 9B 9A - # capătă o a doua fereastră > lu <- move_cls(lu, 3, 2, "9B") 1 2 3 4 5 6 7 1 2 3 4 5 6 7 Mz1 5A 7B 9B - - - - | 5A 9B 7B - - - - LR4 7A 8B 7B - - - - | 7A 7B 8B - - - - Sp1 6B 12B 8B 10B - - - | 6B 8B 12B 10B - - - LR1 - - 12B 9A 10A 12A - | - 12B - 9A 10A 12A - # capătă o fereastră Mt3 12B 9B 11B 8B - - - | 12B 11B 9B 8B - - - Bl2 10C 11B 9C 7A - - - | 10C 9C 11B 7A - - - Is2 12E 9C 9F - - - - | 12E 9F 9C - - - - LR3 10E 9F 11F - - - - | 10E 11F 9F - - - - Is4 - 11F - - - - - | - - 11F - - - -
Astfel, în ora 2 Ds1 are la 9A și Mz1 la 9B (și invers în săptămâna următoare); totalul de ferestre s-a mărit însă, cu 2 (una la Fz2 și una la LR1). Ulterior, va trebui să refuzăm o mutare care ar implica schimbarea din coloana 2 a uneia dintre clasele cuplajului 9AB.
Pentru a asigura și celelalte cuplaje de profesori și clase din P23, putem folosi de exemplu această secvență de mutări consecutive:
lu <- lu %>% move_cls(6, 2, "12F") %>% # 12EF la LG2LG1 move_cls(3, 1, "5A") %>% move_cls(3, 6, "10B") %>% # 10AB la LG2LG1 move_cls(5, 3, "11F") %>% move_cls(4, 3, "11E") %>% # 11EF la LG2LG3 move_cls(4, 5, "7B") %>% move_cls(2, 4, "11D") %>% move_cls(5, 2, "7B") %>% move_cls(5, 4, "11A") # 11ABD la LG1LG3LG4 print(count_gaps(lu)) # 15 ferestre saveRDS(lu, "Lu_1.RDS")
Pentru clasele cuplate specificate în P23 pentru ziua Lu avem acum acest orar:
> lu[c("Ds1", "Mz1", paste0("LG", 1:4)), ] %>% print.table() 1 2 3 4 5 6 7 Ds1 - 9A 6A 5A 12F - - Mz1 7B 9B 5A - - - - LG1 - 12F - 11B 9D 10B - LG2 - 12E 11E 8B - 10A - LG3 - 12C 11F 11A 7B - - LG4 10F 7B 7A 11D - - -
Dar acum orarul curent lu (pe care l-am și salvat, în Lu_1.RDS) are 15 ferestre; pentru a micșora numărul de ferestre putem folosi iarăși programul reduce_gaps.R, cu modificări minore pe care le vom face pe o copie a sa, reduce_gaps_1.R.
Întâi, prevedem în reduce_gaps_1.R o funcție (împreună cu „inversa” ei) prin care vom interzice acțiunea lui move_cls() pe anumite clase, la anumiți profesori – clasa marcată cu "X" nu trebuie mutată într-o altă coloană orară (de exemplu, în cazul nostru, 9A și 9B trebuie să rămână în ora 2 la profesorii Ds1 și Mz1):
taboo_hours <- function(Mop) { # maschează anumite ore, după caz Mop[c("Ds1", "Mz1"), 2] <- rep("X", 2) # 9AB Mop[c("LG1", "LG2"), c(2, 6)] <- rep("X", 4) #12EF și 10AB Mop[c("LG2", "LG3"), 3] <- rep("X", 2) # 11EF Mop[c("LG1", "LG3", "LG4"), 4] <- rep("X", 3) #11ABD Mop } untaboo_hours <- function(Mop) { # reconstituie clasele reale Mop[c("Ds1", "Mz1"), 2] <- c("9A", "9B") Mop[c("LG1", "LG2"), c(2, 6)] <- c("12F", "12E", "10B", "10A") Mop[c("LG2", "LG3"), 3] <- c("11E", "11F") Mop[c("LG1", "LG3", "LG4"), 4] <- c("11A", "11B", "11D") Mop }
Dacă o mutare de clasă (dintre cele propuse în scopul acoperirii vreunei ferestre) ar implica schimbarea într-o altă coloană a unui 'X', atunci vom refuza mutarea respectivă (astfel, clasele cuplate pe verticală își vor păstra locurile, până la sfârșit; din păcate, în cazul de aici, LG1 și LG2 nu vor putea scăpa de ferestre).
Interzicerea mutării lui "X" se face inserând o singură instrucțiune, la începutul blocului repeat din funcția path_kempe() aflată în interiorul funcției move_cls() (v. [2]):
if(q == "X") return(NULL) # de adăugat în move_cls() din [2]
Nu este necesară vreo altă modificare, pe funcțiile existente deja în [2]; totuși, putem scurta „lista mutărilor corectoare” produsă de funcția cover_gaps(), evitând înregistrarea de mutări care angajează X (scutind transmiterea lor spre încercare, lui move_cls()):
if(Mop[id, h1] != "X" & Mop[id, h2] != 'X') { # conservă 'X' lql <- c(lql, Mop[id, h1]) lh1 <- c(lh1, h1) lh2 <- c(lh2, h2) }
Drept „program principal” în reduce_gaps_1.R, prevedem:
lu <- readRDS("Lu_1.RDS") %>% taboo_hours() set_globals("Lu") Cmb <- combn(ncol(lu), 2) # combinările de 7 (sau 6) luate câte două NG1 <- count_gaps(lu) Good <- 7 # numărul sperat de ferestre, în final prnTime(paste0(" (", NG1, " ferestre)\n")) lu1 <- search_better(lu) # declanșează procesul de reducere a ferestrelor prnTime("\n") lu1 <- lu1 %>% untaboo_hours()
Într-una dintre execuțiile programului, am obținut un orar cu 7 ferestre, pe care îl și redăm aici (în alte câteva execuții, n-am trecut de 9 sau 8 ferestre):
> source("reduce_gaps_1.R") 16:34:27 (15 ferestre) 14 13 12 11 10 9 * 9 * 9 8 * 8 7 * 7 16:50:38 # (50-34 = 16 minute) > saveRDS(lu1, "Lu_2.RDS") 1 2 3 4 5 6 7 1 2 3 4 5 6 7 Bl1 - - - 11C 10F 12C - LI2 - - - - 9A 10C - Bl2 10C 9C 11B 7A - - - LI2LI1 - - - 10A - - - Bl3 6B 11D 9D 12D - - - LI3 - - - - 11B 11D - CC1 - - - 6A 10B 7B 8A LR1 - - 12B 9A 10A 12A - Ch1 11A 10D 11D - - - - LR2 5B 10B - 5A 9B - - Ch2 8A 7A 9E - - - - LR3 11F 10E 9F - - - - Ch3 - - - - 12D 11C - LR4 8B 7B 7A - - - - Ch4 12C - - - - - - LR5 10F 9D - 12C 6A - - Ds1 6A 9A 5A 12F - - - LR6 9E 11E 12E - - - - ET1 - - - - 8A 8B - LR7 9C 12D 11C - - - - Fl1 - - 12C 12A 12F 12E - Lt1 10E 9E - - - - - Fz1 11D 11B 10B 10C 10D - - Mt1 12D 5B 6A 7B 12C - - Fz2 9A 11A 12D 9B - - - Mt2 - - 9A 9D 12A 11A - Fz3 - - - 9F 12B 9C - Mt3 11B 12B 9B 8B - - - Fz5 - - - - 6B 6A - Mt4 9F 11C - 9E 11D - - Gg1 - - 5B 11E 5A 9D - Mt5 - - - 10D 10E 11E - Gg2 - - 6B 8A 10C 11F - Mt6 - - - 6B 9C 8A - IH1 - - - - 11C 11B - Mt7 - - - - 12E - - Is1 7A 6A 8A 10E - - - Mz1 5A 9B 7B - - - - Is2 12E 9F 9C - - - - Ps1 10D 10F 12F - - - - Is3 - - 10D 10F 5B 12F - Ps2 11E 11F - - - - - Is4 - - - - 11F - - Rl1 12A 10C - 12E 11E 9F - LE1 9D 8B 10C - - - - Rl2 10A 5A 11A - - - - LE2 - - - 12B 11A 9B - Sp1 12B 6B 8B 10B - - - LE3 11C 10A - 11F 9E - - Sp2 - - 10A 5B 7A 9A - LG1 - 12F - 11A 9D 10B - Sp3 12F - - - - - - LG2 - 12E 11E - 8B 10A - Tc1 - - 10E 9C 9F 12D - LG3 7B 12C 11F 11B - - - Tc2 10B 8A - - - - - LG4 - - 10F 11D 7B 7A - Tc2LI1 - - 12A - - - - LI1 9B 12A - - - - -
Ne-a reușit astfel, pentru ziua Lu, folosind numai instrumentele dezvoltate în [2] (cu una sau două modificări chiar minore, de câte o linie cu "if()"), un orar onorabil; sunt respectate bineînțeles, condițiile de cuplare impuse pentru unii profesori pe anumite clase, sau pe anumite perechi sau triplete de clase; în total sunt numai 7 ferestre, câte una singură (în ora a 3-a sau a 4-a) la 7 profesori.
Putem construi la fel, orarele pe celelalte zile; dar scopul nostru nu este acela de a construi orarul, ci de a arăta cum se poate construi (folosind limbajul R, cu pachetul tidyverse)…
Rămâne de văzut cândva, dacă n-ar fi totuși mai bine să înglobăm direct în mount_hours(), tratarea situației de clase cuplate (în perechi sau în triplete) pe unele discipline; am scăpa atunci, de intervențiile interactive desfășurate mai sus (foarte greu de modelat într-un program) pentru a aduce clasele cuplate în câte o aceeași coloană orară.
vezi Cărţile mele (de programare)