Momente ale problemei orarului
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)