Dicționarele dependențelor

Existența cuplajelor complică foarte mult „problema orarului”… Alocarea pe zile și ore a lecțiilor cuplajelor și profesorilor care sunt angajați în cuplaje, va depinde mereu de alocările făcute celor cu care sunt astfel conexați; la fel, ferestrele din programul zilnic al fiecăruia.

Împărțim lecțiile din setul CDL în trei părți, după lungimea codului (3, 6 sau 9) din câmpul prof și degajăm profesorii din fiecare parte:

S3 <- CDL %>% split(nchar(.$prof))
P1 <- S3[[1]] %>% pull(prof) %>% unique() %>% sort()  # care au (și) ore proprii
P2 <- S3[[2]] %>% pull(prof) %>% unique() %>% sort()  # cuplaje cu 2 profesori
P3 <- S3[[3]] %>% pull(prof) %>% unique() %>% sort()  # cuplaje cu 3 profesori

Următorul dicționar are drept chei profesorii din setul P1 care intră măcar într-un cuplaj (având și ore proprii), iar drept valori – vectorii care conțin profesorii de care depind aceștia, la alocarea pe zile și ore:

Tw1 <- map(P1, function(P) union(P2[grepl(P, P2)], P3[grepl(P, P3)])) %>%
       setNames(P1) %>% compact()

Dacă P este una dintre cheile lui Tw1, ora din zi care poate fi alocată uneia dintre lecțiile lui P trebuie să nu coincidă cu vreuna dintre orele alocate deja cuplajelor din vectorul Tw1[[P]]:

  P     Tw1[[P]]
 $Ds1  "Ds1Mz1"
 $LE3  "LE3Mz1"
 $LG1  "LG1LG4" "LG2LG1" "LG3LG1LG4"
 $LG2  "LG2LG1" "LG2LG3"
 $LG3  "LG2LG3" "LG3LG4" "LG3LG1LG4"
 $LG4  "LG1LG4" "LG3LG4" "LG3LG1LG4"
 $LI1  "LI1LI3" "LI2LI1" "Tc2LI1"
 $LI2  "LI2LI1" "LI2LI3"
 $LI3  "LI1LI3" "LI2LI3"
 $Mz1  "Ds1Mz1" "LE3Mz1"
 $Tc2  "Tc2LI1"

Constituim și un dicționar cumva invers, în care cheile sunt cuplajele existente, iar valorile sunt vectori care conțin profesorii (propriu-ziși, sau „fictivi” adică în cuplaje) de care depinde alocarea orelor cheii respective:

Tw2 <- map(P2, function(PP) {
           p1 <- substr(PP, 1, 3)
           p2 <- substr(PP, 4, 6)
           setdiff(c(p1, p2, Tw1[[p1]], Tw1[[p2]]), PP) %>% unique()
       }) %>% setNames(P2) %>% compact()

La alocarea lecțiilor unui cuplaj PP (cheie din Tw2), va trebui să ținem seama de alocările făcute deja profesorilor și cuplajelor din vectorul Tw2[[PP]]:

  PP       Tw2[[PP]]
 $Ds1Mz1  "Ds1" "Mz1" "LE3Mz1"
 $LE3Mz1  "LE3" "Mz1" "Ds1Mz1"
 $LG1LG4  "LG1" "LG4" "LG2LG1" "LG3LG1LG4" "LG3LG4"   
 $LG2LG1  "LG2" "LG1" "LG2LG3" "LG1LG4" "LG3LG1LG4"
 $LG2LG3  "LG2" "LG3" "LG2LG1" "LG3LG4" "LG3LG1LG4"
 $LG3LG4  "LG3" "LG4" "LG2LG3" "LG3LG1LG4" "LG1LG4"   
 $LI1LI3  "LI1" "LI3" "LI2LI1" "Tc2LI1" "LI2LI3"
 $LI2LI1  "LI2" "LI1" "LI2LI3" "LI1LI3" "Tc2LI1"
 $LI2LI3  "LI2" "LI3" "LI2LI1" "LI1LI3"
 $Tc2LI1  "Tc2" "LI1" "LI1LI3" "LI2LI1"

De exemplu, LI1LI3 nu se va putea afla într-o aceeași oră a zilei ca și vreunul dintre cei 5 profesori (sau cuplaje) din vectorul Tw2$"LI1LI3".

Am văzut deja anterior și un cuplaj de trei profesori (și este unic):

Tw3 <- map(P3, function(PPP) {
           p1 <- substr(PPP, 1, 3)
           p2 <- substr(PPP, 4, 6)
           p3 <- substr(PPP, 7, 9)
           setdiff(c(p1,p2,p3,Tw1[[p1]],Tw1[[p2]],Tw1[[p3]]), PPP) %>% unique()
       }) %>% setNames(P3) %>% compact()
#  $LG3LG1LG4  "LG3" "LG1" "LG4" "LG2LG3" "LG3LG4" "LG1LG4" "LG2LG1"

Repartizarea pe zile și pe orele zilei a lecțiilor prof|cls, precum și reducerea ferestrelor din orarele obținute (deasemenea, calculul numărului de ferestre dintr-un orar final dat), se bazează pe dicționarele de dependențe constituite mai sus; le salvăm împreună:

save(Tw1, Tw2, Tw3, file="Tw123.Rda")

Am observat anterior (când am listat lecțiile cuplajului LG3LG1LG4), că există și clase cuplate – clase care depind una de alta, în sensul că la o anumită disciplină, elevii din aceste clase sunt repartizați în grupe care sunt alocate într-o aceeași oră a zilei, câte unui profesor.
Condiţia ca un cuplaj de profesori să lucreze nu pe câte o grupă a unei clase, ci pe clase întregi, rezultate prin combinarea ad_hoc a grupelor a două sau mai multor clase – este apariţia de două sau mai multe ori, într-o aceeaşi zi şi oră, a acelui cuplaj:

Twc <- CDL %>% 
       filter(nchar(prof) > 3) %>% 
       group_by(prof, zi, ora) %>% 
       count() %>% filter(n > 1)  # reţinem numai apariţiile duble (sau triple)
# print(Twc)
    #   prof      zi      ora     n
    # 1 Ds1Mz1    Jo        5     2  # 2 clase în aceeași zi și oră
    # 2 Ds1Mz1    Ma        7     2
    ## ETC.
# adăugăm coloana claselor:
Twc$Cls <- map(1:nrow(Twc), function(i)
               CDL %>%
               filter(prof == Twc$prof[i], 
                      zi == Twc$zi[i], 
                      ora == Twc$ora[i]) %>%
               pull(cls) %>% as.character()) %>%
           sapply(., toString)    
Twc1 <- Twc %>% ungroup() %>% select(prof, Cls) %>% distinct()
print(Twc1, n=Inf)  # tabloul claselor cuplate
       prof      Cls
     1 Ds1Mz1    9C, 9D  # Ds1: 9C și simultan, Mz1: 9D (probabil)     
     2 Ds1Mz1    9A, 9B       
     3 LG1LG4    10E, 10F     
     4 LG2LG1    12E, 12F     
     5 LG2LG1    10A, 10B     
     6 LG2LG1    10C, 10D     
     7 LG2LG1    9A, 9B       
     8 LG2LG3    9E, 9F       
     9 LG2LG3    11E, 11F     
    10 LG3LG1LG4 11A, 11B, 11D
    11 LG3LG1LG4 12A, 12B, 12D
    12 LG3LG4    10E, 10F

Clasele 9A, 9B, 9C și 9D sunt cuplate câte două, pentru lecțiile de "Desen" și "Muzică" (se știe că acestea au alocate câte o jumătate de oră); fie (într-o aceeași zi și oră) Ds1 intră la 9A și Mz1 intră la 9B în săptămânile impare și invers în cele pare – fie, Ds1 intră la clasa constituită din „grupele 1” ale celor două clase și Mz1 intră la clasa constituită din „grupele 2”, în săptămânile impare și invers, în cele pare.
Analog (dar mai complicat), pentru lecții de "Germană"…

Va fi greu de asigurat cuplarea claselor respective, în câte o aceeași zi și oră; o „soluție” care evită dificultățile de analiză ulterioară a cazurilor posibile, ar consta în convenirea din start a unui orar pentru lecțiile cuplate respective (de alipit cumva în final, orarului generat pentru restul lecțiilor).
Pentru orarul CDL existent, acest orar „prefabricat” îl vedem în setul Twc constituit mai sus:

print(Twc[-4], n=Inf)
       prof      zi      ora      Cls
     1 Ds1Mz1    Jo        5      9C, 9D       
     2 Ds1Mz1    Ma        7      9A, 9B       
     3 LG1LG4    Jo        5      10E, 10F     
     4 LG1LG4    Mi        4      10E, 10F 
     ...

9C și 9D sunt cuplate Jo ora a 5-a, iar 9A și 9B sunt cuplate Ma ora a 7-a; dar fiindcă "Desen" și "Muzică" au câte o oră la două săptămâni, nu este necesar să fixăm din start zilele și orele zilei în care să se desfășoare: în orice zi și oră am aloca clasa 9A (de exemplu) profesorului „fictiv” Ds1Mz1, fiecare dintre profesorii „reali” Ds1 și Mz1 (aflați în vectorul de dependențe Tw2$"Ds1Mz1") va fi liber în acea zi și oră – încât este asigurată cerința ca 9A să facă "Desen" în săptămânile impare și "Muzică" în cele pare.

Însă celelalte lecții (diferite de "Desen" și "Muzică") au alocate câte o oră pe săptămână; deci clasele 10E și 10F trebuie să aibă "Germană" simultan, neapărat într-o aceeași zi și oră – pentru a putea repartiza elevii lor în câte două grupe, alocând clasa formată din grupele 1 lui LG1 și pe cea formată din grupele 2 lui LG4.
Prin urmare, pentru clasele cuplate pentru lecții de "Germană" se cuvine să fixăm din start, o alocare convenabilă pe zile și ore a acestora (vom căuta să evităm „înghesuirea” lecțiilor respective). După ce vom fixa un orar pentru lecțiile cuplate de "Germană", evidențiate mai sus în tabelul Twc – vom elimina din CDL lecțiile respective și păstrând doar coloanele prof și cls, vom genera prin programele din [2], un orar echilibrat pentru lecțiile rămase (completându-l apoi, cu orarul parțial pe care-l fixasem din start).

Dar… până să eliminăm din CDL coloanele zi și ora, s-ar cuveni să facem niște statistici simple, asupra datelor existente (pentru a putea compara orarul existent în setul CDL, cu cel pe care urmează să-l generăm); de exemplu, ne-ar interesa distribuția curentă pe zile, pe clase, pe profesori a numărului de ore (și de ferestre).

Statistici pe orarul curent

—v. Partea a IV-a—