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

Momente ale problemei orarului

perl | randomizare
2015 may

La un anumit moment şcolile au primit de la minister ceea ce s-a denumit "laborator AEL" - în care SIVECO a integrat prin 2007 şi aplicaţia de orar creată de ascTimeTables; probabil că după aceasta, obţinerea orarului va fi devenit o chestiune "de rutină" - în rând cu bagatelizarea generală instituită de informatizarea de tip point-and-click cu iz comercial-funcţionăresc clădită în decada 2000-2010.

Evaluăm aici unele momente dinaintea "informatizării" oficiale, interesante prin faptul că aveam de explicitat sau de inventat formulări şi procedee de rezolvare pe care astăzi (în orice caz - după apariţia prin 2005, a furnizorilor de Internet) le putem raporta şi la formulări sau angajări teoretice consacrate de către diversele articole ştiinţifice relevate cu termeni de căutare ca "timetable problem" (pentru cazul problemelor de orar specifice învăţământului găsim şi sinteze bibliografice instructive: N. Pillay - A survey of school timetabling research, Annals of Operations Research, 2014).

Problema orarului…

Chiar şi până spre anii 2010, elaborarea şi întreţinerea orarului şcolii era o sarcină manuală dificilă, delegată de obicei vreunui profesor de matematică; dacă-l întărâtai cumva, cel care muncea la orar te apostrofa: "ia fă tu orarul - să vezi şi tu cum vine asta". Prin 1985 a venit şi rândul meu…

Nu mi-a plăcut ce văzusem pe la confraţi: se lucra pe un carton uriaş, liniat şi rubricat desigur pe profesori (începând cu directorii şi continuând pe discipline), pe zile şi ore; în principiu, orarul era lucrat de sus în jos (fixând întâi orele directorilor) şi de la stânga spre dreapta: întâi orarul pe ziua de "Luni", apoi cel pentru "Marţi", ş.a.m.d. (fiind urgent orarul primelor două zile).

Am avut de la bun început, în mod tacit, pretenţia ambiţioasă că mi-am asumat nu o sarcină obişnuită într-o şcoală, ci o problemă - independentă de şcoală şi de timp. Nu are de ce să conteze cine sunt profesorii şi ce funcţii au; iar clasele pot fi indicate prin câte o singură literă - încât pentru lucrul la orar ar fi suficientă o pagină obişnuită dintr-un caiet de matematică.

Pentru a începe lucrul aveai nevoie de "încadrarea profesorilor" - document la care directorul muncea toată vara (mereu lăudându-se sau plângându-se, că încă mai are de lucru). Încadrarea (dată de obicei cu vreo două zile înainte de a se deschide anul şcolar) consta dintr-un maldăr de astfel de pagini:

Încadrarea precizează fiecărui profesor clasele sale şi numărul corespunzător de ore pe săptămână; iar pe de altă parte, permite secretarei care se ocupă de salarizare (pe lângă serviciul de contabilitate) să evalueze câte ore suplimentare (sau ce fracţiune de normă) urmează să plătească fiecăruia, în anul şcolar respectiv.

În multe şcoli, numărul total de clase (de-a IX-a, a X-a, etc.) este aproape dublu faţă de numărul de săli de clasă; de aceea, conducerea şcolii împarte clasele în două schimburi - de exemplu astfel: clasele a XI-a şi a XII-a învaţă dimineaţa (schimbul I), iar clasele a IX-a şi a X-a după-amiaza (schimbul al II-lea).

În loc să mă apuc să fac orarul pe "Luni" şi să-l dau la scris în condică, apoi pe "Marţi" ş.a.m.d. (cum puteam învăţa de la confraţi) - eu am preferat să "complic" lucrurile…

Cream câte o matrice de încadrare pentru schimbul I şi respectiv pentru al II-lea, pe câte o pagină de caiet obişnuit ("caiet studenţesc, de matematică"): numele profesorilor şi numărul de ore la clasele (din schimbul respectiv) care le-au fost repartizate; pe aceste matrici puteam depista uşor şi eventualele scăpări sau greşeli existente în încadrarea pe care o primisem şi deasemenea, puteam întreprinde imediat diversele modificări de încadrare care apăreau pe parcursul anului şcolar.

Aveam de făcut două orare: pentru schimbul I şi respectiv pentru al II-lea - separare justificată de faptul că acestea au intervale orare disjuncte. Dar încă nu mă apucam de făcut orarul propriu-zis…

Ce spune o adnotare precum cea de pe prima dintre cele două pagini redate în imaginea de mai sus: "FILIPESCU are câte 2 ore la clasele IX G,F,H,I" neapărat în zilele "luni şi marţi"? În mod firesc, orarul şi pe Luni şi pe Marţi - ignorând deocamdată ordinea orelor - va fi "FGHI" (desigur că evităm să-i punem două ore la o aceeaşi clasă - ca în "FFGG" şi "HHII").
Analog, dacă profesorul are 6 ore la clasa A şi săptămâna are 6 zile de lucru - atunci, în modul cel mai firesc, va trebui să-i plasăm în fiecare zi câte o oră la clasa A (şi ceea ce va mai trebui stabilit ulterior este numărul de ordine al acestei ore în cadrul orelor clasei A pe ziua respectivă).

Prin urmare, în loc să fac orarul propriu-zis pe "luni", apoi pe "marţi", etc. - m-am apucat să repartizez pe zilele săptămânii orele indicate pe matricea de încadrare, obţinând câte o schemă de orar pentru fiecare schimb. Desigur că mă străduiam la fiecare pas, să asigur o anumită omogenitate: era de dorit ca diferenţa dintre numărul de ore într-o zi şi în alta la o clasă sau alta să nu fie mai mare de 1; analog pentru numărul de ore pe zi la un profesor sau altul.

Exemplu: încadrare, schemă de repartizare pe zile, orarele zilnice

Să zicem că săptămâna are 3 zile de lucru şi că avem clasele 'a', 'A', 'x', 'y' şi profesorii 'rP', 'rD', etc. - având specificată încadrarea următoare:

    a A x y
rP  3 3 2 -  'rP' are 3 ore/săpt. la clasele 'a' şi 'A' şi 2 la 'x'
rD  - - - 2
mC  3 - 3 -
mZ  - 3 - 3
fU  2 - 3 -
fZ  - 3 - 3
cP  1 2 3 3
bP  1 2 1 1  -2 (fără ziua 2)
SN  2 1 2 2
Gr  3 1 1 1  -1 (fără ziua 1)

Pentru 'rP', fiecare zi dintre cele 3 va conţine cuplul 'Aa'; pentru cele 2 ore 'x' avem trei posibilităţi de repartizare (în primele două zile, sau în prima şi a treia, sau în ultimele două zile) şi rămâne să facem o alegere. Însă la 'Gr', cele 3 ore 'a' trebuie plasate în două zile. Completând deocamdată ceea ce am arătat mai sus că este obligatoriu, avem următoarea schemă de repartizare parţială:

    zi_1  zi_2  zi_3
rP  aA    aA    aA   la 'rP' rămân de pus 2 ore 'x'
rD                   de pus 2 ore 'y'
mC  ax    ax    ax
mZ  Ay    Ay    Ay
fU  x     x     x    la 'fU' rămân de pus 2 ore 'a'
fZ  Ay    Ay    Ay
cP  xy    xy    xy
bP  A     ----- A
SN  
Gr  ----- a     a    de adăugat 1 oră 'a' şi câte una 'Axy'

De-acum încolo - instrumentul principal va fi guma de şters: avem de încercat diverse plasamente pentru orele rămase de pus şi ne străduim să păstrăm un anumit echilibru în repartizarea orelor. De exemplu, putem finaliza schema de repartizare parţială de mai sus, astfel:

    zi_1  zi_2  zi_3
rP  aAx   aAx   aA   
rD  y     y          
mC  ax    ax    ax
mZ  Ay    Ay    Ay
fU  xa    xa    x    
fZ  Ay    Ay    Ay
cP  Axy   Axy   axy
bP  aA    ----- Axy
SN  axy   Ay    ax
Gr  ----- aax   aAy  

Fiecare clasă apare aici de 5 ori în fiecare zi. Corespunzător acestei scheme de repartizare a orelor pe zilele săptămânii, vom putea construi câte un orar propriu-zis pentru fiecare zi:

    zi_1    zi_2    zi_3
rP  aAx..   aAx..   Aa...    Română
rD  ....y   ..y..   .....    a 5-a oră în zi_1 şi a 3-a oră în zi_2
mC  xa...   xa...   ax...    Matematică
mZ  Ay...   ...Ay   yA...
fU  ...xa   ...xa   x....    Fizică
fZ  ..Ay.   ...yA   .yA..
cP  ..yAx   yxA..   ..yax    Chimie
bP  ...aA   -----   ..xyA    Biologie
SN  yxa..   Ay...   ...xa    specialităţi
Gr  -----   ..aax   ..aAy

În ziua 'zi_1' clasa 'a' are prima oră cu 'rP', a doua oră cu 'mC', a treia cu 'SN', a patra cu 'bP' şi a cincea cu 'fU'. În ziua 'zi_2' profesorul 'Gr' intră a treia şi a patra oră la clasa 'a' şi apoi face a cincea oră la clasa 'x'.

La constituirea orarului zilei am urmărit în principal să nu las "ferestre"; însă când avem două schimburi, chiar dacă orarul pe fiecare schimb nu prezintă ferestre - va fi greu de evitat ca unii dintre profesorii cu ore în ambele schimburi să aibă totuşi ferestre în ansamblul uneia sau alteia dintre zile.

Particularizări remarcabile

Chiar şi mai înainte de a-mi asuma efectiv lucrul la orarul şcolii, am avut inspiraţia unor speculaţii teoretice pe seama a două cazuri particulare artificiale:

Vlad Bazon - "O clasă de pătrate latine şi aplicaţii", Gazeta Matematică - M, Nr. 1-2/1983 (p. 62-67)

Vlad Bazon - "Factorizarea grafului K2n şi aplicaţii", Gazeta Matematică - M Nr. 1/1987 (p. 32-35)

Să presupunem că matricea de încadrare este pătratică şi are toate elementele egale cu 1 - adică numărul de profesori este egal cu numărul de clase şi fiecare profesor are câte o singură oră la fiecare clasă. Atunci, repartizarea în cadrul unei singure "zile" a orelor respective (orarul propriu-zis) conduce la un pătrat latin - pe fiecare linie ("oră" a zilei) şi deasemenea, pe fiecare coloană ("clasă") apar toţi profesorii (câte o singură dată):

1  1 2 3 4   prof. 1 are I oră la '1', a II-a la '2', a III-a la '3' şi a IV-a la '4'
2  2 1 4 3   2 intră pe rând la clasele '2', '1', '4' şi respectiv '3'
3  3 4 1 2   prof. 3 are orarul '3','4','1','2'
4  4 3 2 1   orarul prof. 4

Să presupunem o matrice de încadrare pătratică, cu valori 0 pe diagonala principală şi valori 1 în rest. Presupunem că trebuie îndeplinită următoarea condiţie: pentru oricare numere de ordine J şi K, dacă profesorul J are oră la clasa K, atunci simultan, profesorul K are oră la clasa J - sau cu altă interpretare: dacă J "joacă" cu K, atunci şi K joacă cu J. Identificând "profesorii" şi "clasele" cu participanţii la un turneu de şah (unde fiecare trebuie să joace câte o singură partidă cu fiecare dintre ceilalţi jucători), se obţine un orar de desfăşurare pe runde ("ore") a partidelor:

În figura de mai sus graful K6 (asociat unui turneu cu 6 jucători) este reprezentat printr-o piramidă regulată, cu vârful 1; o rundă se obţine selectând o latură a bazei - de exemplu, [3, 4] - şi diagonala paralelă acelei laturi ([2, 5]), completând apoi cu muchia laterală corespunzătoare vârfului rămas bazei; rundei I obţinute astfel ([3,4], [2,5], [1,6]) îi corespunde "ora I": "profesorul" 3 intră la "clasa" 4, iar "profesorul" 4 intră la "clasa" 3, etc.

Automatizare parţială, completare manuală şi trucuri

Ghidat de ce găsisem prin cursuri uzuale de teoria grafurilor, prin 1988-90 modelam problema orarului ca problemă de colorare a unor grafuri asociate matricei de încadrare şi produceam un program corespunzător, în limbaj Beta Basic pentru ZX Spectrum (inclus alături de alte aplicaţii "în slujba şcolii" - cum ar fi prelucrările ocazionate de examenele şcolare - în lucrarea mea de gradul I din 1991); în "Un model pentru problema orarului" publicat după mulţi ani în Gazeta de Informatică Nr. 8/1999 (p. 38-42), am reluat acest model, reformulând programul în Pascal.

Am folosit mulţi ani acest program, într-o versiune sau alta (la un anumit moment, prin anul 2000 - în C++ şi limbaj de asamblare, relaxând "colorarea" la un procedeu "greedy"), practicând diverse trucuri pentru a reuşi să obţin rezonabil o schemă de repartizare a majorităţii orelor şi apoi (după definitivarea manuală a schemei de repartizare), orarele zilnice; un astfel de "truc" este ignorarea unora dintre ore (de adăugat manual ca a VII-a oră, într-o zi sau alta) - încât să fie de pus prin program un acelaşi număr de ore pe zi (6 ore) la fiecare clasă.

În situaţia în care nu obţineam într-un timp rezonabil orarul final pe o anumită zi, "trucul" care de obicei rezolva situaţia consta în mutarea (de fapt, interschimbarea) unor anumite două-trei ore din ziua respectivă într-o altă zi, în cadrul schemei de repartizare pe zilele săptămânii a orelor (lansând apoi din nou, programul de obţinere a orarelor zilnice).

În orice caz, am fost foarte mulţumit să pot obţine automat o schemă parţială, repartizând pe zilele săptămânii circa 95% din totalul orelor; apoi, mă ocupam să completez manual schema respectivă şi să o echilibrez (interschimbând ore între zile, încât să evit discrepanţe între încărcătura pe o zi şi pe alta, la un profesor sau altul); iar după definitivarea astfel a repartizării, puneam în lucru o subrutină scrisă în limbaj de asamblare pentru obţinerea orarelor zilnice (folosind metoda backtracking).

Programul constituia o schemă de repartizare a orelor printr-o metodă de tip "greedy" şi bineînţeles că cel mai important "truc" s-a dovedit a fi reordonarea profesorilor. Am tot experimentat cu diverse criterii de ordonare (crescător sau descrescător, după numărul de ore sau/şi după numărul de clase comune), alternându-le în diverse contexte de încadrare; când nu reuşeam să obţin schema într-un timp rezonabil, schimbam criteriul de ordonare şi reluam programul…

Reluarea manuală repetată a programului (încercând un alt criteriu de ordonare) era foarte incomodă şi la un anumit moment am avut o idee fericită: am abandonat criteriile "bine-gândite" de ordonare şi am încercat completarea schemei de repartizare într-o ordine aleatorie a profesorilor.

Dar am preferat (în 2002) să realizez această idee folosind Perl; în C++ puteam folosi doar metoda clasică rand() (care generează numere pseudo-aleatoare), ori în Perl exista List::Util::shuffle:

vb@Home:~$ perl -MList::Util -e 'print List::Util::shuffle(1,2,3,4,5,6), "\n"'
563421
vb@Home:~$ perl -MList::Util -e 'print List::Util::shuffle(1,2,3,4,5,6), "\n"'
435216

O invocare imediată my @prof = shuffle(@prof_initial) ordonează aleatoriu (şi este diferenţă, faţă de "pseudo-") tabloul iniţial al profesorilor şi reţine rezultatul în noul tablou "@prof"; acesta urmează acum să fie parcurs "greedy" pentru a constitui o schemă de repartizare a orelor - iar dacă rămân prea multe ore nerepartizate, atunci se invocă din nou shuffle() reluând automat repartizarea.

În practică (pe circa 20 de clase şi 70 de profesori) această idee s-a dovedit a fi suficient de bună: după câteva mii sau zeci de mii de reordonări aleatorii a tabloului iniţial al profesorilor (încercând din nou repartizarea "greedy" a orelor), se ajungea la o schemă convenabilă (în 2-5 minute).

Şabloanele de repartizare pe zile a încadrării unui profesor

De prin 1990, săptămâna standard are 5 zile de lucru (erau 6 până atunci). Pentru unii profesori, orarul va trebui să evite anumite zile: pentru cei care au ore şi într-o altă şcoală şi deasemenea, în cazul anumitor oficialităţi şcolare (inspectori, metodişti, etc.) cărora li s-au alocat ore în cadrul şcolii; poate fi vorba de încă un caz - pentru unii profesori care au ore şi într-un schimb şi în celălalt, am putea rezerva unele zile primului, iar celelalte celui de-al doilea schimb.

Fie "An" încadrarea profesorului p1 la clasa A, unde n este numărul total de ore pe săptămână (dacă "p1" face mai multe discipline la clasa 'A', cumulăm în n orele pe săptămână de la toate acestea). Repartizăm această încadrare pe zilele săptămânii în funcţie de cât este n, câte zile "libere" avem de lăsat lui p1 şi care sunt acestea; în principiu, evităm să plasăm două sau mai multe ore la o aceeaşi clasă, unui aceluiaşi profesor, într-o aceeaşi zi.

Dacă profesorul nu are zile libere şi n ≥ 5 atunci repartizăm câte n/5 ore în fiecare zi şi rămâne de ales o repartizare pentru n%5 ore (unde "/" şi "%" dau respectiv câtul întreg şi restul împărţirii); prin urmare cazurile de care trebuie să ne ocupăm sunt n = 4, 3, 2 sau 1. Avem situaţii similare pentru cazul când există zile libere; de exemplu, dacă profesorul are o zi liberă şi n ≥ 4 atunci repartizăm câte n/4 ore în fiecare dintre cele patru zile de lucru ale sale şi rămâne de ales o repartizare (în cele patru zile) pentru n%4 ore la clasa respectivă - fiind de considerat astfel doar n = 3, 2 sau 1.

Fie Z numărul zilelor libere - 0, 1, 2, sau 3 zile libere - pentru profesorul curent şi N numărul de ore la clasa respectivă care au rămas de repartizat (N ≥ 1 şi N < 5 - Z); pentru fiecare situaţie (Z, N) avem de precizat lista şabloanelor de repartizare posibile. Un exemplu simplu este situaţia (Z=0, N=4): avem patru posibilităţi de plasare a acestor 4 ore în cele 5 zile.

Z zile libere pot fi alese dintre cele 5 ale săptămânii în "combinări de 5 luate câte Z" moduri (1, 5, 10, respectiv 10) şi pentru fiecare dintre acestea, putem avea de repartizat între N = 1 şi N = 4 - Z ore la clasa respectivă. Rezultă că numărul total de chei (Z, N) este 1*4 + 5*3 + 10*2 + 10*1 = 49.

Am ales să definesc aceste 49 de situaţii folosind 8 biţi, astfel: primii 5 biţi (de ranguri 0..4) corespund respectiv celor 5 zile de lucru (în ordinea obişnuită); ultimii 3 biţi sunt '000' pentru cazul a 4 ore de repartizat (caz în care Z = 0), respectiv '001' - '1' fiind bitul de rang 5 al octetului - pentru cazul a 3 ore de repartizat (când Z = 0, sau Z = 1), respectiv '010' pentru 2 ore (când Z = 0, sau Z = 1, sau Z = 2) şi '100' pentru cazul când trebuie repartizată o singură oră. De exemplu, pentru cazul Z = 1 avem următoarele 15 chei posibile:

3 ore / 2 ore / 1 oră  Zile Liber     chei (hexazecimal)
  001 /   010 /   100 11110 luni      0x3E / 0x5E / 0x9E
                      11101 marţi     0x3D / 0x5D / 0x9D
                      11011 miercuri  0x3B / 0x5B / 0x9B
                      10111 joi       0x37 / 0x57 / 0x97
                      01111 vineri    0x2F / 0x4F / 0x8F

Dar concatenarea într-o "cheie" a celor 3 biţi "de ore" cu cei 5 biţi "de zile" este o formulă teoretică… Pentru practică, să observăm că ultimii 3 biţi (cei "de ore") corespund valorilor 0x20 (=001 00000 adică "3 ore"), respectiv 0x40 (=010 00000, cazul "2 ore") şi 0x80 (=100 00000 în cazul "o oră"); ca urmare, cheia dorită se obţine prin disjuncţia uneia dintre valorile 0x00 (dacă sunt de repartizat 4 ore în 5 zile), 0x20, 0x40, respectiv 0x80 cu octetul care indică zilele de lucru şi zilele libere. De exemplu, reobţinem cheia "010 11110" (2 ore în 4 zile, afară de "luni") astfel:

my $nr_ore = 0x40;  # = 010 00000  (2 ore)
my $zile = 0x1E;    # = 000 11110  ("luni" = bit_de_rang_0 = 0 = "Liber")
my $cheie = $nr_ore | $zile;  # operaţia "OR" pe biţi. Rezultă cheia 01011110 = 0x5E

Fiecăreia dintre cele 49 de chei îi asociem câte un tablou conţinând toate şabloanele posibile pentru repartizarea celor N ore în cele (5 - Z) zile; de exemplu, pentru cheia 0x5E (constituită mai sus pentru cazul Z = 1 - luând "luni" ca zi liberă - şi N = 2) determinăm şabloanele de repartizare astfel:

şabloane de repartizare pt. 0x5E [= 01011110: 2 ore (010), "luni"=liber (11110)]
000 00110  marţi, miercuri   0x06
000 01010  marţi, joi        0x0A
000 10010  marţi, vineri     0x12
000 01100  miercuri, joi     0x0C
000 10100  miercuri, vineri  0x14
000 11000  joi, vineri       0x18

rezultând asocierea 0x5E => [0x06, 0x0A, 0x12, 0x0C, 0x14, 0x18]; alegerea uneia sau alteia dintre aceste valori (în cursul execuţiei programului de repartizare pe zile a orelor din încadrare) va depinde în principal de încărcarea curentă a clasei şi a profesorului: de exemplu, vom abandona valoarea 0x06 dacă într-una dintre zilele asociate acestei valori (în speţă, "marţi" şi "miercuri") clasa respectivă are deja plasate anterior, 6 sau 7 ore (numărul maxim de ore pe zi).

Desigur că aceste şabloane binare pot fi generate automat, dar la nivelul anului 2000 le construiam manual, formând următorul hash Perl:

my %sabloane = (
# FĂRĂ ZILE LIBERE
    0x1F => [0x0F,0x17,0x1B,0x1D,0x1E,0,0], # 4 ore 
    0x3F => [0x15,0x0B,0x19,0x16,0x1A,0x0D,0x13,0x0E,0x1C,0x07,0,0], # 3 ore
    0x5F => [0x03,0x05,0x09,0x11,0x06,0x0A,0x12,0x0C,0x14,0x18,0,0], # 2 ore
    0x9F => [0x01,0x02,0x04,0x08,0x10,0,0], # o oră
# O ZI LIBERĂ
        # Luni = liber    
    0x3E => [0x0E,0x16,0x1A,0x1C,0,0], # 3 ore 
    0x5E => [0x06,0x0A,0x12,0x0C,0x14,0x18,0,0], # 2 ore
    0x9E => [2,4,8,16,0,0], # o oră
        # Marţi = Liber
    0x3D => [0x0D,0x15,0x19,0x1C,0,0], # 3 ore 
    0x5D => [0x05,0x09,0x11,0x0C,0x14,0x18,0,0], # 2 ore
    0x9D => [1,4,8,16,0,0], # o oră
        # Miercuri = Liber
    0x3B => [0x0B,0x13,0x19,0x1A,0,0], # 3 ore
    0x5B => [0x03,0x09,0x11,0x0A,0x12,0x18,0,0], # 2 ore
    0x9B => [1,2,8,16,0,0], # o oră
        # Joi = Liber
    0x37 => [0x07,0x13,0x15,0x16,0,0], # 3 ore
    0x57 => [0x03,0x05,0x11,0x06,0x12,0x14,0,0], # 2 ore
    0x97 => [1,2,4,16,0,0], # o oră
        # Vineri = Liber
    0x2F => [0x07,0x0B,0x0D,0x0E,0,0], # 3 ore
    0x4F => [0x03,0x05,0x09,0x06,0x0A,0x0C,0,0], # 2 ore
    0x8F => [1,2,4,8,0,0], # o oră
# DOUĂ ZILE LIBERE
        # Luni şi Marţi = Liber
    0x5C => [0x0C,0x14,0x18,0,0], # 2 ore
    0x9C => [4,8,16,0,0], # o oră
        # Luni şi Miercuri = Liber
    0x5A => [0x0A,0x12,0x18,0,0], # 2 ore
    0x9A => [2,8,16,0,0], # o oră
        # Luni şi Joi = Liber
    0x56 => [0x06,0x12,0x14,0,0], # 2 ore
    0x96 => [2,4,16,0,0], # o oră
        # Luni şi Vineri = Liber
    0x4E => [0x06,0x0A,0x0C,0,0], # 2 ore
    0x8E => [2,4,8,0,0], # o oră
        # Marţi şi Miercuri = Liber
    0x59 => [0x09,0x11,0x18,0,0], # 2 ore
    0x99 => [1,8,16,0,0], # o oră
        # Marţi şi Joi = Liber
    0x55 => [0x05,0x11,0x14,0,0], # 2 ore
    0x95 => [1,4,8,0,0], # o oră
        # Marţi şi Vineri = Liber
    0x4D => [0x05,0x09,0x0C,0,0], # 2 ore
    0x8D => [1,4,8,0,0], # o oră
        # Miercuri şi Joi = Liber
    0x53 => [0x03,0x11,0x12,0,0], # 2 ore
    0x93 => [1,2,16,0,0], # o oră
        # Miercuri şi Vineri = Liber
    0x4B => [0x03,0x09,0x0A,0,0], # 2 ore
    0x8B => [1,2,8,0,0], # o oră
        # Joi şi Vineri = Liber
    0x47 => [0x03,0x05,0x06,0,0], # 2 ore
    0x87 => [1,2,4,0,0], # o oră
# TREI ZILE LIBERE  
    0x98 => [8,16,0,0], # o oră, Joi sau Vineri (Luni, Marţi, Miercuri = Liber)
    0x94 => [4,16,0,0], # o oră, Miercuri sau Vineri (Luni, Marţi, Joi = Liber)
    0x8C => [4,8,0,0], # o oră, Miercuri sau Joi (Luni, Marţi, Vineri = Liber)
    0x92 => [2,16,0,0], # o oră, Marţi sau Vineri (Luni, Miercuri, Joi = Liber)
    0x8A => [2,8,0,0], # o oră, Marţi sau Joi (Luni, Miercuri, Vineri = Liber)
    0x86 => [2,4,0,0], # o oră, Marţi sau Miercuri (Luni, Joi, Vineri = Liber)
    0x91 => [1,16,0,0], # o oră, Luni sau Vineri (Marţi, Miercuri, Joi = Liber)
    0x89 => [1,8,0,0], # o oră, Luni sau Joi (Marţi, Miercuri, Vineri = Liber)
    0x85 => [1,4,0,0], # o oră, Luni sau Miercuri (Marţi, Joi, Vineri = Liber)
    0x83 => [1,2,0,0], # o oră, Luni sau Marţi (Miercuri, Joi, Vineri = Liber)
);

Am prevăzut la sfârşitul fiecărui tablou de şabloane două valori zero - marcând încheierea listei şi respectiv, pentru a înregistra acel şablon din listă care este ales la momentul curent, sau a indica printr-o valoare extremă faptul că încercările de a repartiza orele respective conform unuia dintre aceste şabloane au eşuat.

Structurări şi iniţializări

Fixăm direct (chiar la începutul programului) denumirile de câte o literă preconizate pentru clasele din schimbul curent, numele fişierului care conţine încadrarea profesorilor pentru acest schimb şi numele fişierului în care vom înscrie scheme de repartizare pe zile a încadrării respective:

#!/usr/bin/perl -w
my $clase = "ABCDEFGTabcdefgxyz"; # XI A..G, XII a..g, X A = T, IX ABC = xyz
my $incadrare = "incadrare1.txt"; # încadrarea profesorilor pentru schimbul I
my $scheme = "scheme1.txt"; # scheme de repartizare pe zile a încadrării

Presupunem că în fişierul respectiv încadrarea este deja exprimată în formatul canonic <nume>: [<literă><număr>]+ [-[1-5]+] - de exemplu:

prof1: a2 F2 A2 e2 g2 z3 d2 E2  # nu are zile libere
prof2: A1 a1 T2  -135  # Luni, Miercuri, Vineri = liber
...

Aici, profesorul denumit "prof2" are câte o oră pe săptămână la clasele 'A' şi 'a' şi are 2 ore la clasa 'T', iar aceste 4 ore trebuie repartizate în două zile (Marţi şi Joi).

Pe lângă hash-ul %sabloane deja definit mai sus, considerăm un tablou @Z definind zilele de lucru prin anumite măşti binare - anume, ziua de rang z=0..4 este reprezentată prin valoarea 2z:

my %sabloane = ( # cele 49 de şabloane de repartizare pe zile a orelor
    0x1F => [0x0F,0x17,0x1B,0x1D,0x1E,0,0],
    0x3F => [0x15,0x0B,0x19,0x16,0x1A,0x0D,0x13,0x0E,0x1C,0x07,0,0],
    0x5F => [0x03,0x05,0x09,0x11,0x06,0x0A,0x12,0x0C,0x14,0x18,0,0],
    0x9F => [0x01,0x02,0x04,0x08,0x10,0,0],
    /* ... */
);
my @Z = (1, 2, 4, 8, 16); # în $Z[$zi] este 1 numai bitul al $zi-lea ($zi=0..4) 

Considerăm încă aceste trei variabile "globale", în care urmează să structurăm datele din fişierul de încadrare, anticipând prelucrările necesitate de obţinerea schemei de repartizare pe zile a orelor:

my %hInc = (); # structurează în Perl datele din fişierul de încadrare
my (@sb, %hNoq); # structuri angajate la repartizarea orelor pe zile

În prima parte a subrutinei initialize() se parcurge fişierul de încadrare, constituind hash-ul global %hInc şi hash-ul local %ZL, care împreună "traduc" în Perl liniile fişierului; de exemplu, pentru linia "prof2: A1 a1 T2 -135" se va crea câte o cheie 'prof2' şi se va înscrie încadrarea $hInc{'prof2'} = { 'a' => '1', 'A' => '1', 'T' => '2' } şi respectiv, zilele de lucru corespunzătoare $ZL{'prof2'} = 10:

sub initialize {
    open my $fh, '<', $incadrare or die("Fişier inaccesibil: $!");
    my %ZL = ();
    while(<$fh>) { # linii cu sintaxa exemplificată de 'prof2: A1 a1 T2  -135'
        next unless s/^(.*?):\s*//; 
        my $t = $1; # numele profesorului ('prof2')
        $ZL{$t} = 0x1F; # şablonul zilelor de lucru
        if(index($_, "-") > 0) {
            s/(\s*-.+)//;
            $t2 = $1; # specificaţia zilelor libere ('  -135')
            $t2 =~ s/\s*-//; # rămâne '135'
            for my $i (split / */, $t2) {
                $ZL{$t} &= ~$Z[$i-1]; # maschează zilele libere
            }
        }
        for my $f (split) {
            if(length($f) == 3) { # 'A11' - are peste 9 ore/săpt. la clasă
                my ($k, $v1, $v0) = split //, $f;
                $hInc{$t}{$k} = $v1*10 + $v0;
            }
            else { # sub 10 ore/săpt. la clasă
                my ($k, $v) = split //, $f;
                $hInc{$t}{$k} = $v; # 'prof2' => {'a' => '1', 'A' => '1', 'T' => '2'},
            }
        }                             
    }

De fapt, cele două structuri create astfel (%hInc şi %ZL) joacă un rol secundar şi le-am păstrat numai pentru comoditate (structurile care urmează puteau fi create şi folosind direct fişierul de încadrare); în partea a doua a subrutinei initialize() instituim acele structuri de date care vor servi drept suport pentru încercările de constituire a unei scheme de repartizare pe zile a orelor din încadrare, încercări pe care urmează să le modelăm mai departe:

    foreach $q (split //, $clase) {
        $hNoq{$q} = [0, 0, 0, 0, 0]; # Numărul zilnic de ore plasate deja clasei
    }
    foreach $p (keys %hInc) {
        my $rec = { PROF=>$p };
        $rec->{NOP} = [0, 0, 0, 0, 0, 0]; # Numărul zilnic de ore plasate deja profesorului
        for(my $i=0; $i < 5; $i++) {
            $rec->{ORAR}{$i} = "       "; # Orele repartizate zilnic profesorului
        }
        my $zile = $ZL{$p}; # Şablonul zilelor de lucru ale profesorului curent
        my $nz = 0; 
        foreach (@Z) {
            if($zile & $_) {
                $nz++; # Numără zilele de lucru ale profesorului curent
            }
        }
        my $n = 0; # Constituie numărul de ore/săpt. ale profesorului curent
        foreach my $k (keys %{$hInc{$p}}) {
            my $v = $hInc{$p}{$k}; # Numărul de ore la clasa curentă
            $n += $v;
            while($v >= $nz) { # Repartizează câte [$v / $nz] ore pe zi
                for($i=0; $i < 5; $i++) {
                    if($zile & $Z[$i]) {
                        $rec->{NOP}[$i]++; # Contorizează orele puse profesorului, zilnic
    	                $rec->{ORAR}{$i} =~ s/(\w*)\s/$1$k/; # Adaugă clasa zilei
    	                $hNoq{$k}[$i]++; # Contorizează orele puse clasei, zilnic
    	            }
                }
                $v -= $nz; # Vor rămâne de repartizat $v % $nz ore
            }
            next if $v==0;
            my $N = 0x00; # Asociază clasei şabloanele de repartizare (conform $N şi $zile) 
            if($v==3) { $N = 0x20;}
            elsif($v==2) { $N = 0x40;}
            elsif($v==1) {$N = 0x80;}
            $rec->{SAB}{$k} = [@{$sabloane{$N|$zile}}];
        }
        $rec->{NOP}[5] = int($n/$nz) + 1; # Maxim de ore pe zi repartizate profesorului
        push(@sb, $rec); # Înscrie profesorul curent în tabloul ce va fi
    }                    # angajat ulterior de procedura de repartizare
}

În tabloul global @sb avem acum câte un hash pentru fiecare profesor - reprezentând numele lui, numărul de ore plasate pe fiecare zi la momentul curent al execuţiei programului, clasele plasate la momentul curent în fiecare zi de-a lungul schimbului respectiv, precum şi şabloanele de repartizare care vor trebui încercate pentru a definitiva plasarea orelor acelui profesor:

{
    'PROF' => 'prof2', 
    'NOP' => [0, 1, 0, 1, 0, # S-a repartizat câte o oră, Marţi şi Joi
              3], # Se pot repartiza max. 3 ore/zi
    'ORAR' => { '0' => '       ',
                '1' => 'T      ', # Marţi: o oră la 'T'
                '2' => '       ',
                '3' => 'T      ', # Joi: o oră la 'T'
                '4' => '       ',
              },
    'SAB' => { # Orele rămase de repartizat după şabloanele prestabilite
               'A' => [2, 8, 0, 0], # O oră 'A', fie Marţi, fie Joi
               'a' => [2, 8, 0, 0], # O oră 'a', fie Marţi, fie Joi
             }
},

Pe de altă parte, hash-ul global %hNoq înregistrează pentru fiecare clasă orele plasate profesorilor în a căror încadrare se întâlneşte la momentul curent clasa respectivă.

Dirijarea încercărilor de repartizare pe zile a încadrării

Prin execuţia subrutinei initialize() obţinem tabloul @sb în care profesorii apar cu câte o înregistrare complexă (precum cea tocmai exemplificată ceva mai sus), în aceeaşi ordine în care apar şi pe fişierul de încadrare; deasemenea, obţinem hash-ul %hNoq indicând orele plasate iniţial claselor.

Parcurgem pe rând înregistrările din @sb - cât timp reuşim să plasăm orele profesorului curent la clasele date de cheile hash-ului 'SAB' din înregistrarea acestuia, conform vreunuia dintre şabloanele asociate acelei clase; dacă reuşim să parcurgem astfel toate elementele din @sb - atunci am terminat, rezultând o schemă completă de repartizare pe zilele săptămânii a orelor din fişierul de încadrare.

Dar dacă pentru profesorul curent găsim o clasă căreia nu mai reuşim să-i plasăm orele după unul dintre şabloanele aferente (şi desigur - fără a încălca anumite reguli de bun-simţ, cum este aceea de a nu depăşi un număr maxim de ore la clasă sau la profesor), atunci… ce facem? Aplicarea unui mecanism obişnuit de backtracking s-a dovedit prea costisitoare şi incomodă, neputând să-l bazăm pe vreun criteriu general valabil de ordonare prealabilă convenabilă, a tabloului respectiv.

Postulăm existenţa unei ordini de parcurgere a tabloului pentru care vom obţine soluţia în mod liniar, fără vreo revenire (ignorăm cazurile extreme şi contraexemplele construite artificial în scopul de a ne arăta că greşim!). Considerăm un nou tablou global @sb1, în care copiem într-o ordine aleatorie înregistrările din tabloul iniţial @sb. Parcurgem pe rând înregistrările din @sb1, încercând să repartizăm orele respective; dacă nu putem încheia, atunci reconsiderăm de la capăt, tabloul @sb1 - copiind din nou, aleatoriu, înregistrările din @sb - şi reluăm parcurgerea "noului" tablou @sb1.

Cât de sigur este acest procedeu - nimerim ordinea postulată, după un anumit număr de încercări? Bineînţeles că generatorul de numere aleatoare implicat este important; dacă ar fi unul defectuos, favorizând sau ciclând diverse valori - atunci se poate ca ordinea dorită să fie mereu evitată.

Pe de altă parte, dacă există o astfel de ordine - atunci există chiar mai multe (în fond, putem avea mai multe orare pentru o aceeaşi încadrare iniţială) şi cu cât sunt mai multe, cu atât mai puţine încercări de a găsi una vom avea de făcut; am reuşit să reducem numărul de încercări la / sub ordinul zecilor de mii (depinzând desigur şi de mărimea încadrării iniţiale) - prin renunţarea la impunerea prin program a numărului de ore pe zi la clase: ne mulţumim să obţinem şi repartizări în care o clasă are 3 ore într-o zi, iar în celelalte are câte 6 sau 7 ore (rămânând să retuşăm manual).

Subrutina distribute() modelează cu pretenţii minimale, procedeul argumentat mai sus:

use Storable qw(dclone);       # Copiază o structură complexă de date
use List::Util qw(shuffle);    # Amestecă aleatoriu, elementele unui tablou

my (@sb1, %hNoq1); # Repartizarea pe zile a încadrării şi încărcarea pe zile a claselor
my $fail; # Va semnala eventual, eşecul încercării curente de repartizare

sub distribute {
    $fail = 0;
    %hNoq1 = %{ dclone(\%hNoq) }; # Copiază încărcarea iniţială pe zile a claselor
    @sb1 = shuffle(@{ dclone(\@sb) }); # Amestecă aleatoriu înregistrările iniţiale
    my ($t,$T,$s,$z,$moz,$d,$M,$m) = (0) x 8;
    foreach (@sb1) { # Parcurge înregistrările, încercând repartizarea pe zile a orelor
        $moz = $_->{NOP}[5]; # Numărul maxim de ore pe zi pentru profesorul curent
        foreach $k (keys %{$_->{SAB}} ) { # Clasa curentă din încadrarea profesorului
            my $n = $hInc{$_->{PROF}}{$k}; # Numărul iniţial de ore/săptămână la clasă
            $t = 0; # Indexul curent în lista şabloanelor de repartizare a orelor
            $T = 200; # Dacă s-ar încerca fără succes, toate şabloanele de repartizare
            $d = 4; # Limită iniţială a diferenţei Max-Min de ore pe zi, pentru profesor
            $s = $_->{SAB}{$k}[$t]; # Şablonul curent de repartizare a orelor 
            while($s > 0) { # Valoarea 0 lista încheie lista şabloanelor de repartizare
                for($z=0; $z < 5; $z++) {
	                if($s & $Z[$z]) {
                        if($hNoq1{$k}[$z] > 6) { 
	                        $z = 10; # Zi în care clasa are deja 7 ore
	                        last;
	                    }
	                    if($_->{NOP}[$z] >= $moz) { 
	                        $z = 10; # Zi în care profesorul are deja maximum admis de ore
	                        last;
	                    }
	                }
                }
                if($z == 10) { # Există o zi cu prea multe ore la clasă sau la profesor
	                $t++; # Vizează următorul şablon din listă
	                $s = $_->{SAB}{$k}[$t];
	                last if $s == 0; # Încheie 'while', dacă s-a ajuns la capătul listei
	                redo; # Reia 'while' pentru noul şablon vizat
                }
                $M = $m = $_->{NOP}[0]; 
                for($z=0; $z < 5; $z++) {
	                if($s & $Z[$z]) {
	                    my $crt = $_->{NOP}[$z] + 1;
	                    if($crt < $m) {
	                        $m = $crt; # Minimul de ore, pe zilele indicate în şablon
	                    }
	                    if($crt > $M) {
	                        $M = $crt; # Maximul de ore, pe zilele indicate în şablon
	                    }
	                }
                }
                if($d == ($M-$m)) {
	                if($n < 3) {  
	                    $T = $t;
	                }
                }
                if(($M-$m) < $d) { # Caută un şablon pentru care încărcarea pe zile 
	                $d = $M - $m;  # să fie cât mai echilibrată.
	                $T = $t;
                }
                $t++;
                $s = $_->{SAB}{$k}[$t];
            }
            if($T == 200) { # Nu s-a putut reţine (în T) niciunul dintre şabloane
                $fail = 1; # Încercarea curentă de repartizare a eşuat
                last; # Nu mai trece la o altă clasă, pentru profesorul curent
            }
            else {
                $t = $T; # Indexul sablonului ales mai sus
                $_->{SAB}{$k}[-1] = $t;
                $s = $_->{SAB}{$k}[$t];
                for($z=0; $z < 5; $z++) {
	                if($s & $Z[$z]) {
	                    $hNoq1{$k}[$z]++; # Încărcarea pe zile a clasei
	                    $_->{NOP}[$z]++; # Încărcarea pe zile a profesorului
	                    $_->{ORAR}{$z} =~ s/(\w*)\s/$1$k/; # Înscrie orele repartizate 
	                }
                }
            }
        }
        if($fail) { # Încercarea de repartizare pe zile a orelor profesorului curent a eşuat
            last; # (return;) Sistează parcurgerea înregistrărilor
        }
    }
}

Este drept că la nivelul anului 2000 procedam şi mai modest, în cadrul subrutinei distribute(): aveam o variabilă $total în care cumulam orele pentru care la momentul curent nu s-a reuşit repartizarea pe zile (conform unuia dintre şabloanele prevăzute pentru aceasta); dacă $total depăşea o valoare prefixată (10 ore, de exemplu), atunci abandonam parcurgerea tabloului curent @sb1, iar altfel - încheind parcurgerea acestuia - reţineam în fişierul prevăzut repartizarea respectivă, împreună desigur cu datele necesare identificării celor mai puţin de $total ore care au rămas nerepartizate (v. [1]).

Angrenarea lucrurilor

În fişierul "incadrare1.txt" avem înscrisă încadrarea pentru schimbul I, valabilă la un anumit moment într-o anumită şcoală; preferăm să înlocuim numele reale cu "profN", unde N este numărul liniei:

vb@Home:~/ORAR$ perl -pi -e "$i++; s/^(.*):/prof$i:/" incadrare1.txt

Redăm aici această încadrare, cu 45 de profesori pe 18 clase "ABCDEFGTabcdefgxyz":

prof1: a2 F2 A2 e2 g2 z3 d2 E2
prof2: A1 a1 T2  -135  # 2 ore la 'T' şi câte una la 'a' şi 'A'; afară de zilele 1, 3, 5
prof3: G1 F1 d1 y1 b1 E1  -24
prof4: E1 b2 d3 e3 f2 z5 A1
prof5: e3 x2 y3  -24
prof6: E2 G2 e6
prof7: D2 c4 d4 B2
prof8: E2 b2 d2 g4 B2
prof9: E1 D1 b1 c1 d1 f1 C1 g1 z2 B1 G1 F1 e1
prof10: f2 C2 y2 G2  -3
prof11: E2 D2 c2 d2 e2 f2 g2 T1 b2
prof12: c3 g3 B3 G3 F3
prof13: B3 T3 b3  -5
prof14: x2 z1 y2 -135
prof15: T1
prof16: T1 f1 B2 y1 F2  -13
prof17: E2 D2 F6 d2 e2 C2 B2
prof18: G8 f5 g3
prof19: F1 A1 a1 B1 x1 z2 y1 T1 e1
prof20: E6 D2 b1 F4 d1 B2 c1
prof21: y4 T4 C3 a4
prof22: A1
prof23: G2 T2 C2 B2 y2 c2
prof24: a7 A7 x4
prof25: E3 b3 A4 f3 z2 d3
prof26: G3 A3 C3 g3 y4
prof27: D2 b2 F2 d2 e3 C2
prof28: E2 a1 G2 c1 A1 C2 g1 x1 b1 D2
prof29: G1 c2 C1 a1 x1 y1 F1 T1 g2 D1 B1
prof30: D4 b2 c4 C4 f2 B2
prof31: G2 F2 A1 a1 C2 B2 z2 y1 x1
prof32: a1 y2 x2 z1 T2
prof33: E2 D2 d2 e2 a2 g2
prof34: b4 c2 C4
prof35: x3 a3 T3
prof36: T5   -135
prof37: E1 D1 b1 c1 d1 C1 f1 g1 z1 y1 x1 T1 G1
prof38: a3 c3 e3 D3 z5
prof39: D3 x4 y1
prof40: a1 c1 A1 e1 C1 g1 z1 T2 B1 f1 x1 D1
prof41: D2 b2 c2 B2 x2 T2
prof42: G2 f4 g4 B2
prof43: b2 F2 A2 f2 x2 z2
prof44: A3 z2 y3
prof45: E3 F3 d3 f3 x4 -2

În fişierul "i4c-scheme" în care am scris cele două subrutine redate mai sus, adăugăm acest "program principal" (care le angrenează, înscriind apoi schema rezultată):

initialize();
my $scor = 0; # câte încercări de repartizare, până la una reuşită
do { 
    distribute(); 
    $scor ++;
} while($fail);

open my $fsc, '>>', $scheme; # adaugă schema de repartizare obţinută
print $fsc $scor, "\n";
foreach (sort { substr($a->{PROF},4) # ordonează după rang "profRANG"
                <=> substr($b->{PROF},4)} @sb1) {
    my $h = sprintf("%-10s", $_->{PROF});
    print $fsc $h;
    for($i=0; $i < 5; $i++) { # orele repartizate pe fiecare zi
        $o = $_->{ORAR}{$i};
	    $o =~ s/ /./g;
	    print $fsc $o,"  ";
    }
    print $fsc "\n";
}
print $fsc "----------\n";
foreach $k (sort keys %hNoq1) { # încărcarea zilnică rezultată pentru clase
    print $fsc "$k: ", join(" ", @{$hNoq1{$k}}), "\n";
}
print $fsc "\n";

Bineînţeles că am setat flagul de "executabil" pentru fişierul respectiv, putând invoca direct:

vb@Home:~/ORAR$ time ./i4c-scheme
real	0m3.935s
user	0m3.754s
sys	0m0.028s

După 4 secunde, în fişierul indicat de $scheme am obţinut - în urma a 1800 de încercări eşuate - repartizarea pe zile redată mai jos:

1800  # 1800 de încercări eşuate, până la obţinerea acestei scheme
prof1     z......  AFag...  zFag...  AdEe...  zdEe...  
prof2     .......  TA.....  .......  Ta.....  .......  
prof3     Eb.....  .......  Fd.....  Gy.....  .......  
prof4     zed....  zfA....  zEed...  zbf....  zbed...  
prof5     ey.....  .......  eyx....  .......  eyx....  
prof6     ee.....  eE.....  eE.....  eG.....  eG.....  
prof7     cd.....  cd.....  cDd....  Bcd....  BD.....  
prof8     g......  bEg....  bEg....  dBg....  dB.....  
prof9     Cb.....  EGf....  BDz....  edz....  gFc....  
prof10    fG.....  yG.....  .......  fC.....  yC.....  
prof11    T......  Dcge...  Dcge...  fbdE...  fbdE...  
prof12    FcBG...  cBGg...  FcBG...  g......  Fg.....  
prof13    TBb....  TBb....  TBb....  .......  .......  
prof14    .......  xy.....  .......  xyz....  .......  
prof15    .......  .......  .......  .......  T......  
prof16    .......  fB.....  .......  FB.....  FyT....  
prof17    FDdF...  FED....  FEd....  FBeC...  FBeC...  
prof18    GfGg...  Gf.....  GfGg...  Gf.....  GfGg...  
prof19    az.....  ez.....  Ty.....  FA.....  xB.....  
prof20    EFE....  EFB....  EFB....  EFbD...  EdcD...  
prof21    TaCy...  TaCy...  Tay....  TaCy...  .......  
prof22    .......  .......  .......  .......  A......  
prof23    .......  BTC....  BTC....  cGy....  cGy....  
prof24    AaxA...  AaxA...  Aaxa...  Aaxa...  Aa.....  
prof25    EbAf...  Afd....  EbzA...  Afd....  Ebzd...  
prof26    CAyg...  yG.....  CAyg...  yG.....  CAgG...  
prof27    e......  eCd....  eCd....  DbF....  DbF....  
prof28    aD.....  gDG....  CAG....  CEb....  xEc....  
prof29    aG.....  By.....  CgD....  xgc....  FTc....  
prof30    DcC....  DcCf...  DbcC...  DBcC...  Bbf....  
prof31    Ay.....  xFz....  aFz....  BCG....  BCG....  
prof32    x......  x......  ay.....  Ty.....  Tz.....  
prof33    Dg.....  aD.....  agd....  Ee.....  Eed....  
prof34    bC.....  bC.....  bC.....  bc.....  cC.....  
prof35    Ta.....  ax.....  T......  ax.....  Tx.....  
prof36    .......  TTT....  .......  TT.....  .......  
prof37    CD.....  dc.....  Tbz....  gGy....  Exf....  
prof38    zDec...  zDac...  zec....  zDa....  zea....  
prof39    xD.....  x......  xD.....  x......  yD.....  
prof40    fa.....  ze.....  ATx....  cTC....  DgB....  
prof41    .......  BDx....  BDx....  cbT....  cbT....  
prof42    gf.....  g......  BGf....  gBf....  gGf....  
prof43    zx.....  fz.....  fxb....  FA.....  FAb....  
prof44    yA.....  z......  yA.....  z......  yA.....  
prof45    xEdFf..  .......  xEdFf..  xEdFf..  x......  
----------
A: 6 6 6 5 5
B: 2 7 7 7 7
C: 6 5 7 7 5
D: 7 7 7 4 5
E: 5 5 7 6 7
F: 5 4 7 7 7
G: 5 6 5 7 7
T: 4 7 7 7 6
a: 7 6 7 6 2
b: 5 3 7 7 7
c: 4 6 5 7 7
d: 4 4 7 7 7
e: 6 5 6 5 7
f: 6 7 4 7 5
g: 5 6 7 5 6
x: 5 7 7 6 6
y: 5 5 6 7 6
z: 5 7 7 5 5

Pe exemplul redat mai sus se vede că n-am reuşit foarte bine, să "echilibrăm" repartizarea orelor fiecărui profesor; de exemplu "prof1" are în prima zi o singură oră, iar în celelalte zile câte 4 ore - şi la fel sau analog, "prof11" şi "prof45". Echilibrarea dorită este realizată în distribute() folosind variabila $d în care se iniţializează cu 4, limita diferenţei dintre maximul şi minimul de ore pe zi la profesorul curent (şi se încearcă apoi alegerea unui şablon de repartizare care să micşoreze această limită iniţială); valoarea de iniţializare 4 a fost aleasă în urma unor experimente cu valori mai mici, când timpul de obţinere a schemei creştea însă prea mult.

La sfârşit este redată încărcarea pe zi a claselor; avem trei clase cu o repartizare defectuoasă: 'B', 'a' şi 'b' (astfel, 'B' are numai 2 ore în prima zi şi apoi are câte 7 ore).

Defectele de echilibrare tocmai evidenţiate se pot corecta relativ uşor, manual; dar înainte de a decide să definitivăm manual schema respectivă - este foarte bine să mai obţinem câteva scheme, alegând pentru definitivare pe cea care este mai convenabilă:

vb@Home:~/ORAR$ time ./i4c-scheme
real	0m19.336s

Schema obţinută acum (după 7681 de încercări, în 20 secunde) pare mai bună:

7681  # 7681 de încercări eşuate, până la obţinerea acestei scheme
prof1     dzg....  dEg....  ezE....  aeAF...  azAF...  
prof2     .......  Ta.....  .......  TA.....  .......  
prof3     dG.....  .......  Fb.....  Ey.....  .......  
prof4     zde....  zbE....  zdef...  zbA....  zdef...  
prof5     ye.....  .......  yex....  .......  yex....  
prof6     ee.....  eE.....  eE.....  eG.....  eG.....  
prof7     cd.....  cd.....  cBd....  cDd....  DB.....  
prof8     gb.....  gb.....  gB.....  dgE....  dBE....  
prof9     gE.....  fcb....  BzD....  Czd....  FGe....  
prof10    yC.....  yC.....  .......  Gf.....  Gf.....  
prof11    T......  cdDg...  cdDg...  Eebf...  Eebf...  
prof12    cFBG...  FBG....  cgG....  FgB....  cg.....  
prof13    BbT....  BbT....  BbT....  .......  .......  
prof14    .......  xy.....  .......  xyz....  .......  
prof15    .......  .......  .......  .......  T......  
prof16    .......  FB.....  .......  Ff.....  TBy....  
prof17    FF.....  FBdD...  FBdD...  FECe...  FECe...  
prof18    GfGg...  Gf.....  GfGg...  Gf.....  GfGg...  
prof19    xe.....  Ba.....  Tz.....  Ay.....  Fz.....  
prof20    EFE....  EFDB...  EFb....  EFcB...  EDd....  
prof21    TCay...  .......  TCay...  Tay....  TCay...  
prof22    .......  .......  .......  .......  A......  
prof23    .......  TCy....  TCy....  cBG....  cBG....  
prof24    aAxA...  aAxA...  aAxa...  aAxa...  aA.....  
prof25    dfbA...  AEz....  dfbA...  AEz....  dfbE...  
prof26    GACg...  Gy.....  AyCg...  Gy.....  AyCg...  
prof27    e......  ebF....  ebF....  CdD....  CdD....  
prof28    xA.....  bgG....  DcG....  DEC....  aEC....  
prof29    GD.....  gy.....  gxT....  Bac....  CFc....  
prof30    DfCc...  DfCc...  DBCc...  DbCc...  bB.....  
prof31    Cy.....  CFz....  GFz....  GBa....  ABx....  
prof32    y......  y......  za.....  Tx.....  Tx.....  
prof33    .......  daE....  daE....  Dge....  Dge....  
prof34    Cb.....  Cc.....  Cb.....  Cb.....  bc.....  
prof35    ax.....  xT.....  aT.....  x......  aT.....  
prof36    .......  TTT....  .......  TT.....  .......  
prof37    TD.....  gx.....  fEd....  Ccb....  Gzy....  
prof38    zcDe...  zea....  zcDa...  ze.....  zcDa...  
prof39    Dx.....  x......  Dx.....  yx.....  D......  
prof40    zB.....  DC.....  xTA....  eTg....  acf....  
prof41    .......  bBc....  bBc....  DxT....  DxT....  
prof42    fg.....  fg.....  fgG....  fBG....  Bg.....  
prof43    .......  xAF....  xAF....  fbz....  fbz....  
prof44    Ay.....  z......  Ay.....  z......  Ay.....  
prof45    xdfE...  .......  xfEF...  xdfF...  xdEF...  
A: 6 4 6 6 6
B: 3 7 7 6 7
C: 6 6 5 7 6
D: 5 5 7 6 7
E: 4 6 6 7 7
F: 4 7 7 6 6
G: 6 4 6 7 7
T: 4 7 7 7 6
a: 3 5 7 6 7
b: 4 7 7 6 5
c: 4 6 7 6 6
d: 6 5 7 5 6
e: 7 3 5 7 7
f: 5 4 6 7 7
g: 6 7 7 4 5
x: 6 6 7 7 5
y: 6 6 5 6 6
z: 4 5 7 7 6

Corectăm manual, plecând de la tabelul care conţine încărcarea zilnică a claselor. De exemplu, la clasa 'B' am avea de mutat câte o oră din zilele 2, 3 şi 5 în ziua 1 (rezultând atunci câte 6 ore în fiecare zi); dintre toţi, 'prof17' pare cel mai potrivit pentru mutarea unui 'B' din ziua 2 în ziua 1 (avea în ziua 1 numai 2 ore, iar în celelalte zile câte 4 ore; acum - va avea fie 3, fie 4 ore în fiecare zi); mutăm apoi 'B' din ziua 3 în ziua 1 să zicem la 'prof11' şi din ziua 5 în ziua 1 la 'prof8'.

Procedăm analog pentru clasele 'a' şi 'e', care au iniţial câte o zi cu numai 3 ore. Apoi ne ocupăm de clasele care au iniţial o zi cu 4 ore, încercând să mutăm ore astfel încât în fiecare zi să fie 5, 6 sau (eventual) 7 ore. Bineînţeles că mutările de ore vor putea avea în vedere şi alte criterii, ţinând de gruparea unor ore la o anumită clasă, eliberarea unei zile la vreun profesor, etc.

vezi Cărţile mele (de programare)

docerpro | Prev | Next