Ce vrem noi, de la un orar școlar

Nu vrem ca vreun profesor să aibă într-o zi două ore și în alta, 7 ore; nici vreo clasă cu 4 ore într-o zi și cu 7, în alta. Evităm ca la vreo disciplină să fie două lecții într-o aceeași zi la o aceeași clasă. Lecțiile la clase încep de la prima oră a zilei, fără derogări; pentru simplitate, presupunem că toate clasele funcționează într-un același schimb, cu câte cel mult 7 ore/zi (dar nu mai mult de două zile, cu 7 ore).

Cu alte cuvinte, vrem un orar echilibrat; lecțiile prof|obj|cls trebuie repartizate cât mai uniform pe zile, pe clase și pe profesori, iar pentru fiecare obiect, lecțiile la o aceeași clasă trebuie distribuite uniform pe zilele de lucru. Rezultă atunci, acest principiu de lucru: întâi repartizăm (echilibrat) pe zile și abia apoi alocăm pe orele 1:7 lecțiile repartizate într-o aceeași zi; nu ne ocupăm ad hoc de ferestrele care apar în orarele individuale, imaginând în schimb o procedură generală prin care să reducem în final, numărul total de ferestre.

De observat că în multe lucrări, problema orarului școlar School Timetable Problem (v. //en.wikipedia.org/wiki/School_timetable) este tratată (implicând de regulă, fie un pseudocod, fie limbajul C) ca problemă combinatorială de optimizare: anumite resurse (profesori, clase, săli de clasă) trebuie repartizate pe anumite "sloturi de timp" (cupluri zi + oră), respectând anumite constrângeri "hard" și cât mai multe cerințe "soft".
Dar prin programele dezvoltate în [1] (doar "filosofate" mai jos), repartizăm separat pe zile și respectiv, pe orele zilei, obținând fără constrângeri explicite, orare echilibrate; tratăm STP prin prisma lucrului cu seturi de date (sau "baze de date"), folosind limbajul R (dar fără ingredientele și scopurile de analiză statistică a datelor, pentru care a fost înființat și este folosit de obicei, acest limbaj; v. //www.r-project.org/).

Datele problemei orarului

"Datele" sunt niște entități indivizibile și inconfundabile, ale căror valori urmează a fi prelucrate. Avem de considerat 5 variabile independente: prof|obj|cls|zi|ora; primele trei au valori cunoscute din start: numele profesorilor, denumirile adoptate pentru disciplinele școlare și pentru clase. Valorile posibile pentru zi și ora sunt deasemenea cunoscute, numai că pentru a avea un orar, ele trebuie montate (pe parcurs) în așa fel încât să se evite suprapunerile de lecții (în principiu, nu pot fi într-o aceeași oră, doi profesori la o clasă, sau un profesor la două clase).

Asupra datelor brute inițiale facem niște simplificări convenabile, plecând de la disciplinele școlare. Profesorii sunt încadrați pe câte o disciplină "principală" și eventual, cu câte un număr restrâns de ore, pe unele discipline "secundare"; abreviem prin câte două litere numele disciplinelor și denumim profesorii concatenând disciplina principală a fiecăruia cu un număr de ordine în cadrul acesteia (de exemplu, Bi2 ar desemna unul dintre profesorii de "Biologie"). Simplificarea constă în faptul că mai departe putem omite variabila obj; pentru a decide în final, ce obiect înscriem pentru fiecare lecție, deducem disciplina principală din numele de profesor, iar una secundară o depistăm după caz într-un dicționar auxiliar.

Documentul oficial referitor la încadrarea profesorilor în școală precizează pentru fiecare profesor, care clase îi sunt atribuite, pe ce discipline și pe câte ore; dar în orar avem de repartizat fiecare lecție în parte: dacă din încadrare deducem "Bi2 12D=3 ore/săptămână" (două pe "Biologie" și una pe "Dirigenție"), atunci în setul datelor inițiale prof|cls trebuie să înregistrăm 3 linii consecutive "Bi2|12D", urmând să montăm pe fiecare dintre ele, câte o anumită valoare pentru zi și ora.

Fie $\boldsymbol{\mathcal{L}}$ setul tuturor lecțiilor prof|cls, un tabel cu două coloane (sau "variabile"), prof și respectiv cls, având un număr de linii egal cu numărul tuturor lecțiilor ce se desfășoară în cursul unei săptămâni.

Cuplaje și tuplaje; orar parțial (prin etichetare)

Numărul de ore alocat anual pentru "Muzică" și "Desen" este jumătate din numărul de săptămâni; ca urmare, există obiceiul de a împărți clasa în două grupe de elevi, urmând ca profesorii Mz1 și Ds1 să intre (într-o aceeași oră a zilei) fie la grupa_1 și respectiv grupa_2, fie invers, după rangul săptămânii curente.

Dacă nu vedem altă posibilitate, inventăm un profesor fictiv (sau cuplaj) Mz1Ds1 care preia de la Mz1 și Ds1 clasele pe care aceștia trebuie să le partajeze "pe grupe"; aceasta înseamnă că în $\boldsymbol{\mathcal{L}}$ păstrăm liniile celor doi profesori pentru clasele la care intră singuri (nu în cuplaj), iar pentru clasele pe care le partajează reținem câte o singură linie pe care înlocuim valoarea curentă din câmpul prof, cu "Mz1Ds1".
Totodată, constituim două "dicționare de dependențe": unul ne va duce de la fiecare membru al unui cuplaj, la cuplajul respectiv; celălalt va duce invers, de la cuplaj la membrii acestuia. Ulterior, aceste dicționare de dependențe ne vor servi pentru a evita suprapunerile de lecții; de exemplu, valorile zi|ora pe care le vom monta pe lecțiile lui Ds1 și respectiv Mz1 trebuie să difere nu numai între ele, dar și de cele montate lecțiilor cuplajului Mz1Ds1.

Probabil că și pentru alte discipline trebuie înființate cuplaje, de exemplu limbi străine (la care întâlnim frecvent gruparea elevilor clasei în "avansați" și "începători"); procedăm desigur, ca în cazul etalat mai sus.

Dar adesea, observând clasele care trebuie împărțite pe grupe, putem opta pentru o soluție mai bună decât aceea bazată pe dicționarele de dependențe. De exemplu, să presupunem că avem 5 clase a IX-a și 5 clase a X-a și fiecare face și "Muzică" și "Desen", pe câte o jumătate de oră/săptămână, cu profesorii Mz1 și respectiv, Ds1. în loc să înființăm profesorul fictiv "Mz1Ds1" pentru cele 10 lecții "pe grupe", putem înființa 5 tuplaje — perechi de clase întregi la care intră cu alternare săptămânală, Ds1 și respectiv Mz1, conform unui orar parțial prestabilit, de exemplu:

În ziua Lu de exemplu, Ds1 și Mz1 vor intra fie la clasele 10A și respectiv 10B, fie invers, în funcție de paritatea rangului săptămânii; iar când ne vom ocupa de alocarea pe ore a lecțiilor, vom avea grijă ca lecțiile astfel împerecheate pe zile, ale lui Ds1 și Mz1, să cadă într-o aceeași oră a zilei respective.

Bineînțeles că în setul de tuplaje constituit ca mai sus, putem adăuga și tuplajele sau "simultanele" pe care le putem imagina pentru limbi străine și deasemenea, oricare lecții necuplate pentru care ar exista obligația repartizării în zile precizate apriori.

Desigur, lecțiile pe care le-am prevăzut în orarul parțial vor trebui eliminate din setul $\boldsymbol{\mathcal{L}}$ — unde ar rămâne astfel, lecțiile cu profesori propriu-ziși, împreună cu cele cu profesori fictivi (cuplaje); de fapt, având puține cuplaje față de totalul lecțiilor, putem genera un "orar parțial" și pentru cei angajați în cuplaje, lăsând în $\boldsymbol{\mathcal{L}}$ numai lecțiile din afara cuplajelor (dar trebuie să avem în vedere o generare dinamică: re-generăm orarul parțial, până ce distribuțiile finale — după ce îmbinăm cu repartiția lecțiilor necuplate și cu aceea din orarul parțial al tuplajelor — sunt suficient echilibrate).

Un "orar parțial" se poate construi astfel: se listează lecțiile prof|cls în ordinea tuplajelor și se adaugă o coloană zi pe care se repetă de sus în jos o permutare oarecare a zilelor (mai sus, Lu Jo Mi Ma Vi; desigur, elementele unui aceluiași tuplaj trebuie etichetate cu o aceeași zi).
Chiar acest algoritm îl vom specula, pentru a repartiza echilibrat lecțiile pe zile și deasemenea, pentru a le aloca pe orele zilei (când în loc să etichetăm cu permutări de zile, vom eticheta cu permutări de 1:7).

Repartizarea echilibrată a lecțiilor, pe zilele de lucru

Aranjăm liniile din $\boldsymbol{\mathcal{L}}$ după prof și cls: lecțiile fiecărui profesor sunt pe linii consecutive, iar dintre acestea, cele de la o aceeași clasă sunt și ele, pe linii consecutive. Apoi, etichetăm toate lecțiile, de sus în jos, plasând succesiv în coloana zi o aceeași permutare a vectorului Zile (aici, enumerarea uzuală a zilelor):

În total, în setul $\boldsymbol{\mathcal{L}}$ de pe care am exemplificat mai sus primele 30 de linii, aveam 101 lecții de "română", pe 6 profesori. Fiindcă le-am plasat pe linii consecutive, lecțiile unui profesor la o aceeași clasă cad în zile diferite, iar distribuțiile orare ale profesorilor respectivi sunt toate, uniforme; deasemenea, distribuția pe zile a celor 101 lecții de Ro este și ea, uniformă (Lu are 21 de ore de Ro, iar pe celelalte zile avem câte 20).
Dar este uniformă și distribuția pe clase a lecțiilor? Pentru o singură disciplină — da, fiindcă fiecare clasă apare numai la unul dintre profesorii pe disciplina respectivă (10B de exemplu, are distribuția omogenă (1,1,1,0,0)). Însă dacă repartizăm pe zile (ca mai sus pentru "Română") și lecțiile de la alte discipline, atunci este de așteptat să apară și clase care într-o zi au 3 ore și într-o alta ajung la 10 ore…

Totuși în [1] am procedat altfel: am etichetat nu lecțiile fiecărei discipline, ci lecțiile fiecărei clase; astfel, în mod implicit, pentru clase rezultă distribuții omogene pentru numărul de ore/zi, iar pentru profesori, sub un anumit control, asigurăm distribuții cvasi-omogene (cu diferență de cel mult două ore, între zile). Dacă alocarea pe zile făcută astfel clasei curente, corelată cu alocările făcute anterior altor clase, implică mai mult de 6 (excepțional 7) ore pe zi la un profesor sau altul — atunci fixăm o altă ordine a zilelor de lucru și reluăm etichetarea; la fel, dacă în urma alocării curente, distribuția pe zile a unuia dintre profesori se dezechilibrează.
Dacă într-o suită de încercări, nu se reușește etichetarea cu zile pentru clasa curentă (pentru niciuna dintre cele 120 de permutări de Zile) — atunci abandonăm toate alocările făcute unor clase până la momentul respectiv și reluăm procesul, dar într-o altă ordine (aleatorie) de parcurgere a claselor.

Pe ce ne bazăm, de credem că procedând astfel, ajungem la o repartizare pe zile a tuturor lecțiilor? Păi știm din capul locului, că încadrarea dată admite repartizări pe zile: însuși planul anual de încadrare, din care am derivat încadrarea săptămânală, asigură corelațiile necesare asupra numărului de ore pe profesori, discipline și clase; dacă ar exista o singură posibilitate de repartizare pe zile a încadrării, atunci într-adevăr, ar fi aproape imposibil de a o nimeri procedând "la întâmplare" — dar este clar că sunt posibile foarte multe repartizări pe zile, încât avem suficient de multe șanse de a nimeri una, într-un număr (mai mic sau mai mare) de încercări.

Precizăm că în [1], [2] (și în mai multe articole de pe acest site) am pus la punct și proceduri de lucru interactiv (din "consola R") prin care putem echilibra complet, distribuțiile rezultate (de exemplu, transformând pe cele "cvasi-omogene" în "omogene") și pe de altă parte, putem să corelăm între ele, cât mai bine posibil, distribuțiile lecțiilor acelor discipline la care avem cuplaje sau/și tuplaje.

În final, $\boldsymbol{\mathcal{L}}$ conține toate lecțiile prof|cls|zi unde prof este un profesor propriu-zis sau eventual, unul fictiv (cuplaj) — dar distribuite acum, în mod echilibrat, pe zilele de lucru.

Montarea orelor 1:7 pe lecțiile unei zile

Datele trebuie raportate acum la fiecare zi în parte: extragem din $\boldsymbol{\mathcal{L}}$ subsetul lecțiilor pe ziua curentă (separând totuși pe cele implicate în cuplaje), iar din dicționarele de dependențe și din orarul parțial al tuplajelor extragem datele aferente cuplajelor și respectiv tuplajelor din ziua respectivă.

Procedăm la fel ca în cazul repartizării lecțiilor pe zile: considerăm una după alta câte o clasă și etichetăm lecțiile prof|cls ale acesteia (pentru ziua curentă) cu o permutare de 1:n, unde n este numărul de ore (cel mult 7) ale clasei în ziua respectivă; etichetarea curentă trebuie însă căutată (printre cele n! permutări), astfel încât să nu aibă valori comune cu etichetări aplicate 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). Iar dacă, oricum am permuta secvența 1:n din coloana ora, nu putem evita conflictul cu alocările făcute anterior altor clase — atunci stopăm procesul, reordonăm cumva clasele (aleatoriu?) și apoi reluăm pentru noua ordine, încercările de alocare pe ore a lecțiilor fiecăreia.

Succesul și eficiența procedeului parafrazat mai sus, depind de ordinea în care considerăm clasele și de ordinea în care așezăm liniile prof|cls. Ordonarea după numărul de ore este insuficient de relevantă, fiindcă sunt multe cazuri de profesori cu un același număr de ore; trebuie să conteze nu atât numărul de ore, cât clasele asociate orelor respective.

Încercând să formalizăm bănuiala sugerată mai sus — asupra poziționării fiecărui profesor în raport cu ceilalți, condiționată de prezența unor clase comune (și asupra unei ordonări a claselor care să țină seama cumva, de numărul de profesori comuni) — ajungem la măsura numită betweenness (întâlnită în statistica rețelelor de socializare; v. Barabási, Albert-László "Network science" //networksciencebook.com).

Considerăm un graf $\Gamma$ având drept vârfuri profesorii existenți în ziua curentă, două vârfuri fiind adiacente dacă profesorii respectivi au măcar o clasă comună; analog, avem un asemenea graf pentru clase (dar, cu muchii multiplicate după numărul de profesori comuni la câte două clase).

Am vrea să parcurgem cât mai "ușor" acest graf, trecând deci de la un vârf la următorul pe un cel mai scurt (o geodezică) dintre drumurile existente în $\Gamma$ între cele două vârfuri. Considerând arbitrar două vârfuri, $P_1$ și $P_2$, probabilitatea ca un anumit vârf $P$ să fie "între" cele două date — adică să se afle pe o geodezică de la $P_1$ la $P_2$ — este dată de raportul dintre numărul geodezicelor între $P_1$ și $P_2$ care trec prin $P$ și numărul tuturor geodezicelor de la $P_1$ la $P_2$; valoarea acestui raport este "notată" betweenness(P1, P, P2), iar însumând toate aceste valori când $P_1$ și $P_2$ variază în mulțimea tuturor vârfurilor — obținem betweenness(P) pentru fiecare vârf $P$ (pentru calculul betweenness() putem folosi de exemplu //igraph.org/).

Considerăm vectorii de coeficienți betweenness pentru grafurile claselor și respectiv profesorilor, pentru ziua curentă. Acești vectori vor trebui vizați în ordine crescătoare, fiindcă fixarea orarului unei clase de coeficient mare, diminuează posibilitățile de alocare ulterioară pentru mult mai multe clase (cele aflate pe câte o aceeași geodezică cu clasa respectivă), decât fixarea orarului unei clase de coeficient mai mic.

Prin urmare, lista claselor va fi parcursă într-o ordine aleatorie "preferențială", urmărind crescător coeficienții betweenness. Folosim un vector auxiliar în care înregistrăm (prin șabloane binare) alocările pe ore și începem să parcurgem lista claselor, etichetând în coloana ora lecțiile fiecăreia; dacă aceasta eșuează la clasa curentă, atunci se reinițializează vectorul alocărilor pe ore, se reordonează aleatoriu (ponderat totuși de coeficienții betweenness) lista claselor și se reia — până când se nimerește o ordine în care lista claselor este parcursă de la un capăt la celălalt (într-o singură trecere).

Reducerea ferestrelor din orarul zilei

Formatul lung (linii prof|cls|ora) facilitează oricare extragere de date (orarul unei discipline, al unei clase sau grup de clase, orarul tuplajelor sau cuplajelor, etc.); dar pentru a reda orarul și pentru a ne referi la ferestre este mai convenabil un format matriceal, în care liniile sunt numite după prof și pe fiecare linie sunt specificate clasele la care intră profesorul respectiv, în fiecare oră:

          1   2   3   4   5   6             - tuplaje -     ora
Ds1       -  9F  6B 10E   -   -          Ds1Mz1     10E 10F   4
Mz1       -   -  8B 10F 12F   -          Gr2Gr1     10A 10B   3
Gr4       -   - 10E 11D  7A 10F          Gr2Gr1     12E 12F   6
Gr1       -   - 10B 11B  6B 12F          Gr2Gr3     11E 11F   5
Gr2       -   - 10A  5A 11E 12E       Gr3Gr1Gr4 11A 11B 11D   4
Gr3       -   -  7B 11A 11F 10E          Gr3Gr4     10E 10F   6
# angajați în cuplaje:
If2      5A   -   -   -   -   -   
If3     11B   - 11A   -   -   -   # are o "fereastră falsă"
If2If3    -  9A   -   -   -   -
If1      9B 10B   -   -   -   -   # are două ferestre "ascunse"
Tc2If1    -   -   -   - 12A   -
Tc2       - 10A 12F  9A   -   -  
# din afara cuplajelor și tuplajelor:
Fz1     10D  9E 10F 11C  9D 10B   
Is1     10C 10F   -   -  5A  8A   # are două ferestre
Is2      9E   - 11B   -  9B   -  
Is3       -  5B 11D   - 12D   - 
# și așa mai departe...

În acest exemplu, profesorii angajați în tuplaje nu au ferestre; dintre cei angajați în cuplaje, If3 intră în orele 1 și 3 la clasele 11B și 11A și are o "fereastră falsă" în ora 2 (în care intră în cuplaj cu If2 la 9A); iar If1 are două ferestre ascunse (în orele 3 și 4): are lecțiile proprii 9B|1 și 10B|2 și apoi, tocmai în ora 5 intră împreună cu Tc2 la 12A. Am redat și orarul câtorva profesori neimplicați în tuplaje sau cuplaje; Is2 de exemplu, are două ferestre, în orele 2 și 4.

Dacă vizăm ferestrele, nu interesează clasa la care intră profesorul (singur, sau într-un cuplaj), ci doar faptul că intră sau nu, la una oarecare dintre clase, într-una sau alta dintre orele zilei. Cu alte cuvinte, interesează șablonul orelor profesorului; de exemplu, șablonul orelor lui If1 este "**--*-", exprimând faptul că are de intrat (eventual, în cuplaj) la anumite clase în orele 1, 2, 5 și are ferestre în orele 3 și 4 — desigur, acest șablon rezultă "însumând" pe cel corespunzător liniei sale, cu cele corespunzătoare liniilor cuplajelor în care este implicat.

Bineînțeles că putem înlocui '*' cu 1 și '-' cu 0; indexând orele nu de la stânga spre dreapta (cum avem pe liniile din matricea orară), ci de la dreapta spre stânga (cum sunt indexați biții dintr-un byte) – ajungem, pentru linia lui If1, la șablonul binar '00010011', care în baza 10 are valoarea 16 + 3=19. "Fereastră" va însemna atunci orice bit '0' aflat între biți '1', în cadrul șablonului binar respectiv; șablonând toate liniile, vom putea calcula ușor numărul total de ferestre din matricea-orar curentă.

În matricea-orar, fiecare clasă apare câte o singură dată pe fiecare coloană 1:n, unde n este numărul de ore/zi pentru clasa respectivă (dacă ar apărea de două ori pe coloană, ar însemna că în ora respectivă am avea doi profesori la o aceeași clasă). Putem elimina o fereastră mutând în locul ei, una dintre clasele existente în șablonul respectiv; dar pentru a păstra unicitatea claselor pe coloane, trebuie făcută imediat și o mutare inversă: depistăm linia care în coloana ferestrei inițiale conținea clasa mutată și pe acea linie, trebuie mutată clasa respectivă în coloana din care fusese mutată pe locul ferestrei.

Deci secvența de mutări care asigură schimbarea unei clase dintr-o coloană în alta, formează un circuit (drum închis) al grafului $\Gamma$ care are drept arce q1 --> q2, unde (q1 q2) este o linie din setul format de cele două coloane din matricea-orar. Dat fiind că singura valoare care se poate repeta pe o coloană este "-" (ora liberă, nu și vreo clasă), rezultă că circuitele lui $\Gamma$ fie trec prin vârful "-", fie sunt componente conexe ale lui $\Gamma$ (și în termenii teoriei grafurilor, sunt lanțurile Kempe ale lui $\Gamma$; v. //en.wikipedia.org/wiki/Kempe_chain).

Plecând de la matricea-orar curentă, funcția move_cls(Mop, h1, h2, Cls) va produce matricea-orar rezultată după mutarea clasei Cls din coloana h1 în coloana h2 și avem de reținut noul orar, dacă în urma mutării efectuate au rezultat mai puține ferestre (altfel, pe orarul inițial ar trebui încercată o altă mutare).

Pentru 7 ore/zi, avem 99 de șabloane de orar individual cu ferestre (v. problema L445, Recreații Matematice Nr. 2, 2023); constituim un dicționar (de "mutări corectoare") care asociază fiecăruia dintre cele 99 de șabloane, câte doi vectori paraleli h1 și h2, astfel încât pentru fiecare index i, perechea (h1[i], h2[i]) reprezintă mutarea lecției din ora h1[i] pe locul liber (eventual, fereastră) h2[i].
De exemplu, pentru șablonul de 4 lecții cu două ferestre "-*--***", avem 12 mutări "corectoare" (una dintre cele 4 lecții se mută pe unul dintre cele 3 locuri libere); dintre acestea, numai mutarea (2, 4) elimină ambele ferestre (rezultând "---****") — dar trebuie să le avem în vedere pe toate, fiindcă urmărim reducerea numărului total (și nu individual) de ferestre.

Nu vedem vreun criteriu pentru a alege câte o "cea mai bună" mutare, așa că procedăm iarăși (ca și pentru repartizarea lecțiilor pe zile și respectiv, pe orele zilei) "la întâmplare", cam așa: din matricea-orar curentă, selectăm aleatoriu câteva dintre liniile pe care avem ferestre și încercăm (aplicând move_cls()) una oarecare, dintre mutările corectoare asociate liniilor respective; repetăm aceasta până când, fie se depășește un număr prestabilit, suficient de mare, de iterații (caz în care încheiem, returnând ultimul orar obținut), fie obținem un orar cu mai puține ferestre (caz în care acesta devine "orarul curent" și reluăm pentru el, iterațiile respective).

Note bibliografice

Am referit pe undeva mai sus aceste cărți, înregistrate pe Google Books:
[1] Vlad Bazon - Orare școlare echilibrate și limbajul R
[2] Vlad Bazon - De la seturi de date și limbajul R, la orare școlare

Pe //cran.r-project.org/ am înregistrat următoarele pachete R:
days2lessons pentru repartizarea lecțiilor pe zile;
recastlessons omogenizarea interactivă (din R) a distribuțiilor pe zile;
hours2lessons montarea orelor pe lecțiile unei zile;
refitgaps reducerea ferestrelor din orarul zilei.

În "on its way to CRAN (crearea orarului școlar)" (din mai 2025) am considerat o încadrare cu 1260 de lecții (într-un singur schimb) și am arătat cum se pot folosi aceste 4 pachete R pentru a obține un orar școlar echilibrat, în care numărul total de ferestre este sub 3% față de totalul lecțiilor.