programació d’horaris per a les defenses de treballs de final de … · 2017-12-18 · com ja...
TRANSCRIPT
TreballdeFideMàster
MàsterUniversitarienEnginyeriaIndustrial
Programaciód’horarisperalesdefensesdeTreballsdefinaldeGrauiMàster
MEMÒRIA
Autor: BlancaBertranSubirana
Director: ManelMateoDoll Convocatòria: Abril2017
Escola Tècnica Superior d’Enginyeria Industrial de Barcelona
I
Resum
Elprincipalobjectiud’aquestprojecteésdeterminar laprogramacióòptimadelshorarispera la
defensa del Treball de Fi d’Estudis que es presenten en una convocatòria a l'Escola Tècnica
Superiord’EnginyeriaIndustrialdeBarcelona(ETSEIB).
Actualment a l’ETSEIB s’imparteix el Grau en Enginyeria en Tecnologies Industrials i més de 10
titulacions de màster, a més de dobles titulacions. L’assignació que es desenvolupa en aquest
projecte engloba els treballs de fi d’estudi de totes aquestes titulacions presentats en una
convocatòria.
Partint dels projectes amb el corresponent tribunal ja assignat, es programaran els horaris de
presentació d’aquests en funció de diferents paràmetres i dades disponibles. Per fer-ho es
desenvoluparàprimeramentunmodelmatemàtic. Es discutirà els diferents criteris a considerar.
Per tant, pot tractar-se d'un problema monocriteri o multicriteri. Aquest ha de permetre fer
l’assignaciód’horarisdemaneraòptimasegonselscriterisconsiderats.Posteriorment,encasque
lacomplexitatsiguielevada ipertantel tempsderesolució,esdissenyaràunalgorismeheurístic
peralaobtenciód’unasolucióbonapartintd’unasolucióinicialobtingudaambunalgorismeque
utilitzi reglesbàsiques.Elscriterismitjançantelsqualss’optimitzarà lasolucióesdeterminaranal
llargdelprojecteis’ajustaranrealitzantprovesambdiferentsjocsdedades.
II
SumariRESUM_____________________________________________________________I
SUMARI___________________________________________________________ II
1. INTRODUCCIÓ__________________________________________________ 6
2. L’ETSEIB ______________________________________________________ 7
2.1. Titulacions..................................................................................................................72.1.1. Grau.................................................................................................................................72.1.2. Màsters...........................................................................................................................82.1.3. Doctorats.......................................................................................................................11
2.2. Unitatsacadèmiquesiderecerca...........................................................................112.2.1. Departaments...............................................................................................................112.2.2. InstitutsUniversitarisdeRecerca.................................................................................132.2.3. GrupsdeRecerca..........................................................................................................14
2.3. Relacionsambl’exteriordelauniversitat...............................................................142.3.1. Càtedresd’empreses....................................................................................................142.3.2. Relacionsinternacionals...............................................................................................152.3.3. Relacionsambempreses..............................................................................................152.3.4. Altres.............................................................................................................................16
2.4. PersonalDocentiInvestigador................................................................................162.4.1. PDILaboralTemporal....................................................................................................17
2.4.1.1. Ajudant(AJ)...........................................................................................................17
2.4.1.2. ProfessoratLector(LEC)........................................................................................17
2.4.1.3. ProfessoratAssociat(ATP)....................................................................................172.4.2. PDILaboralPermanent.................................................................................................17
2.4.2.1. ProfessoratCol·laborador(COL)...........................................................................17
2.4.2.2. InvestigadorOrdinari(IO)......................................................................................17
2.4.2.3. Directord’Investigació(DI)....................................................................................18
2.4.2.4. ProfessoratAgregat(AG)......................................................................................18
2.4.2.5. CatedràticContractat............................................................................................182.4.3. PDIFuncionari...............................................................................................................18
2.4.3.1. ProfessorTitulatd’EscolaUniversitària(TEU)......................................................18
III
2.4.3.2. ProfessorTitulat(TU)............................................................................................18
2.4.3.3. Catedràticd’Universitat(CU)................................................................................18
3. ELTREBALLDEFID’ESTUDIS(TFE)_________________________________ 20
3.1. ElTreballdeFinaldeGrau(TFG).............................................................................20
3.2. ElTreballdeFinaldeMàster(TFM).........................................................................20
3.3. Modalitatsderealització..........................................................................................20
3.4. Etapesdedesenvolupament...................................................................................21
3.5. ComposiciódelstribunalsdeTFGiTFM..................................................................24
4. DEFINICIÓDELPROBLEMAIMODELMATEMÀTIC_____________________ 26
4.1. Definiciódelproblemaiobjectiu.............................................................................26
4.2. Dadesdepartida......................................................................................................27
4.3. Criteris......................................................................................................................284.3.1. Mínimnombrededies:ladispersió.............................................................................284.3.2. Mínimnombred’interrupcions:lairregularitat...........................................................29
4.4. Modelitzaciómatemàtica........................................................................................314.4.1. Dades.............................................................................................................................324.4.2. Variables........................................................................................................................32
4.4.2.1. Variablededecisió................................................................................................33
4.4.2.2. Variablecomúdelscriteris....................................................................................33
4.4.2.3. Variablequemodelaladispersió..........................................................................33
4.4.2.4. VariablequemodelalaIrregularitat.....................................................................33
4.5. Restriccions..............................................................................................................344.5.1. Restriccionsbàsiques....................................................................................................344.5.2. Restriccionsassociadesalscriterisd’optimització.......................................................35
4.6. Funcióobjectiu.........................................................................................................364.6.1. Definició........................................................................................................................364.6.2. Pesosdelafuncióobjectiu...........................................................................................36
5. RESOLUCIÓUTILITZANTUNÚNICPROGRAMALINEAL _________________ 38
5.1. Valorestablertdelsparàmetres..............................................................................38
5.2. SoftwareUtilitzat.....................................................................................................39
5.3. Implementacióiexecució........................................................................................39
6. PROCEDIMENTHEURÍSTIC_______________________________________ 43
IV
6.1. Especificacionstècniques........................................................................................44
6.2. Pre-procés:Assignaciódelsprojectesaundiaconcret..........................................456.2.1. Objectiu.........................................................................................................................456.2.2. Entrades........................................................................................................................46
6.2.2.1. LecturaInicialdeDades........................................................................................46
6.2.2.2. Estructuradedadesons’inclouràl’assignació.....................................................486.2.3. ProcedimentHeurístic:assignaciódelsprojectesadies.............................................49
6.2.3.1. ALGORISME1.........................................................................................................49
6.2.3.2. ALGORISME2.........................................................................................................526.2.4. Sortides.........................................................................................................................556.2.5. Càlculdelvalordelavariabledispersió........................................................................556.2.6. GeneraciódelsfitxersdedadespelCPLEX...................................................................55
6.3. Minimitzaciódelairregularitatdel’assignacióinicial.............................................566.3.1. Objectiu.........................................................................................................................566.3.2. Dades.............................................................................................................................566.3.3. Variables........................................................................................................................576.3.4. Restriccions...................................................................................................................576.3.5. Funcióobjectiu..............................................................................................................586.3.6. Tempsd’execuciódelmodel........................................................................................59
6.4. Post-procés:Milloradelasolució............................................................................606.4.1. Objectiu.........................................................................................................................606.4.2. Càrrega..........................................................................................................................606.4.3. Procedimentheurísticdemilloradelasolució............................................................61
6.5. Minimitzaciódelairregularitatdel’assignaciómillorada.......................................65
7. RESULTATS___________________________________________________ 667.1.1. Pre-procés:Assignaciódelsprojectesaundiaconcret...............................................667.1.2. Optimització:Assignaciódelsprojectesaunahoraconcreta.....................................677.1.3. Post-procés:Milloradelasolució.................................................................................67
8. PLANIFICACIÓIPROGRAMACIÓ___________________________________ 74
9. PRESSUPOST__________________________________________________ 75
10. IMPACTESOBREL’ENTORN ______________________________________ 76
11. CONCLUSIONS ________________________________________________ 77
12. BIBLIOGRAFIA_________________________________________________ 78
V
Pàg.6 Programaciód’horarisperalesdefensesdeTreballsdeFinaldeGrauiMàster
1. Introducció
El Treball de Fi d’Estudis és un exercici de caràcter obligatori que els estudiants desenvolupen
durantl’últimquadrimestredelatitulació(Grau-TreballdefinaldeGrauTFGoMàster-Treballde
final de Màster TFM) amb l’objectiu de posar de manifest la seva capacitat per aplicar les
competènciesadquiridesdurantelsestudis.
Perònonoméselsestudiantsdediquentempsalarealitzaciód’aqueststreballs,elPersonalDocent
iInvestigador(PDI)del’escolatambéprenpartenelprocésdedesenvolupamentdelsprojectesja
siguicomadirectorsoponents,oessentmembresdel tribunaldepresentació idefensad’algun
d’ells.
L’objectiu principal d’aquest projecte és obtenir una programació òptima dels horaris de les
defensesdeTFGs i TFMsqueespresentendurantunadeterminadaconvocatòriaa l’ETSEIB.Per
aconseguir-ho,esconsiderarandiferentscriterisqueafavoreixenparticularmentalprofessoratque
formapartdelstribunalsdelespresentacions.
Perfer-hoesdefiniranprimeramentelscriterisaconsiderar,peradesenvoluparposteriormentun
model matemàtic que permeti fer l’assignació d’horaris obtenint un resultat optimitzat.
S’establirantambélesrestriccionsquecalafegiralmodelperaconseguirquelaprogramacióesfaci
demaneracoherentifactible.
Com ja s’ha comentat l’abast del projecte es limita a les presentacions de TFG i TFM, i més
concretamentalesmodalitatsderealitzacióqueimpliquenferlapresentacióidefensaal’escola.El
modelescrearàconsiderantlescaracterístiquesd’aquestsprojectesperòpodriaserutilitzatpera
programardemaneraòptimaaltreshorarisquepuguinassimilar-sealsquesónobjected’aquest
projecte. Queda fora de l’abast d’aquest estudi l’assignació dels membres del tribunal per a
cadascundelstreballs,considerantaixíaquestacomposiciócomunadadainicialques’utilitzaràen
elmodel.
Elcontingutdelprojectes’estructuradelasegüentmanera.Alsegoncapítols’expliquenbreument
lestitulacionsques’ofereixenal’ETSEIB,aixícomelstipusdeprofessoratquehiestanvinculats.Al
tercer,s’aprofundeixen lescaracterístiquesdelTFGidelTFM.Elmodelmatemàticdesenvolupat
peraferl’assignaciódelespresentacionsespresentaalquartcapítol.Alcinquèesresolelmodel
linealdesenvolupatperdiferents instàncies.Elprocedimentheurísticdesenvolupatesdefineixal
capítol sis, i els resultats obtinguts de les diferents proves realitzades es presenten al set.
Finalment,s'inclouenelscapítolsdeplanificacióiprogramació,pressupostiimpactesobrel'entorn,
ilesconclusionsd'aquestestudi.
BlancaBertranSubirana Pàg.7
2. L’ETSEIB
L’Escola Tècnica Superior d’Enginyeria Industrial de Barcelona (ETSEIB) és un centre docent que
formapartdelaUniversitatPolitècnicadeCatalunya(UPC),instituciópúblicaderecercaieducació
superiorenelsàmbitsdel’arquitectura,l’enginyeria,lesciènciesilatecnologia.[56]
L’ETSEIBtalicomesconeixavuidatadel1.964,quanesvaproduireltrasllatal’edificiqueocupa
actualment situatal campusDiagonal suddesprésd’una llarga trajectòriaquehaviacomençatal
1.851amb lacreacióde laEscuela IndustrialBarcelonesa.Desde llavorss’han titulatuns18.000
enginyers a l’escola especialitzats en diferents àrees tecnològiques: automàtica, construcció,
elèctrica,electrònica,energètica,informàtica,materials,mecànica,organitzacióindustrial,química,
transports,logística,bioenginyeria,etc.[23]
Actualmentl’escolacomptaamb16departamentsenelsqualss’hiintegrenmésde410professors
iprofessoresqueformenauns3.200estudiants.L’ETSEIBaculltambéInstituts,GrupsdeRecercai
càtedresd’empresa.[23]
2.1. Titulacions
L’oferta acadèmica actual de l’ETSEIB consta de tres cicles estructurats en estudis de Grau, de
Màster i de Doctorat, juntament amb altres programes formatius en col·laboració amb altres
centresnacionals i internacionals.Aquestaestructuravaseradoptadaapartirdel cursacadèmic
2010-2011 quan va entrar en funcionament la implementació de l’Espai Europeu d’Educació
Superior (EEES),popularmentconegutcomProcésdeBolonyaa l’escola,deixantd’admetrenous
estudiantsalestitulacionsdellicenciaturaidiplomaturadesd’aquellmoment.
2.1.1. Grau
Les titulacions de Grau proporcionen als estudiants la capacitat per a la incorporació al món
laboral,amésdel’accésalsestudisdeMàster.
Des del curs 2016-2017 l’oferta de graus a l’ETSEIB ha quedat reduïda únicament al Grau en
EnginyeriaenTecnologiesIndustrials,traspassantlaimparticiódelGrauenEnginyeriaQuímicaiel
GrauenEnginyeriadeMaterialsal’Escolad’EnginyeriadeBarcelonaEst(EEBE),inauguradadurant
aquestmateixcurs.Finsalcurs2017-2018,encaras’imparitranalgunesassignaturesdelsdarrers
cursosdelGrauenEnginyeriaQuímicaielsestudiantspodrandefensarelseuTFG.
El Grau en Enginyeria en Tecnologies Industrials (GETI) proveeix formació enmatèries bàsiques
Pàg.8Programaciód’horarisperalesdefensesdeTreballsdeFinaldeGrauiMàster
científiques i tecnològiquesquedotena l’alumnedeconeixementsen totsels camps industrials,
des del vessant més tecnològic fins al més empresarial. Aquesta titulació ofereix una visió
multidisciplinària i integradorade l’enginyeria industrial queproporciona als estudiantsun ampli
ventalldesortidesprofessionals.[55]
La càrrega lectiva del GETI és de 240 crèdits ECTS1 que s’imparteixen durant uns 4 anys
aproximadament. El pla d’estudis s’estructura en un total de 8 quadrimestres durant els quals
s’imparteixen un total de 30 crèdits ECTS distribuïts en diferents assignatures. Durant l’últim
quadrimestre de la titulació es desenvolupa el Treball final de Grau (TFG), projecte original i
tutoritzat en el que es sintetitzen i s’apliquen els coneixements i competències assolides per
l’estudiantalllargdelatitulació.LacàrregalectivadelTFGvariasegonslamodalitatderealització
delmateix,essent12crèditsECTSelmínim.[55]
2.1.2. Màsters
L’ETSEIBofereix actualment (curs 2016-2017)10 titulacionsdeMàsterUniversitari diferentsque
proporcionenespecialització acadèmicaoprofessional, i permeten també l’accés al doctorat. Els
títolsdeMàsters’obtenendesprésd’haversuperatentre60i120crèditsECTSdepenentdelaseva
durada, i es classifiquen en professionals, de recerca i acadèmics segons quina sigui la seva
orientació.[24]
AtravésdelestitulacionsdeMàsterimpartidesal’ETSEIBelsestudiantsadquireixen,amésdeles
competències específiques de cadascun d’ells, competències transversals com emprenedoria i
innovació,sostenibilitaticompromíssocial,itreballenequip,entred’altres.
S’especifiquentotseguitlestitulacionsdeMàsterques’imparteixenal’escola:
§ Màster Universitari en Enginyeria Industrial - MUEI (120 ECTS): formació avançada en
l’àmbitdelestecnologiesindustrialsqueproporcionaunavisióglobalimultidisciplinàriaals
estudiants,facilitantaixílasevaincorporacióalmónlaboral.[30]
Elprogramapermetl’especialitzacióenalgunadelessegüentsdisciplinesdelaindústriaa
travésdelesassignaturesoptatives:
o Especialitat Automàtica: anàlisi i disseny de tècniques de control avançades
aplicatsasistemesautomàtics
o EspecialitatBiomèdica:formacióenàmbitstecnològicsaplicatsalamedicina.
1UncrèditECTSequivalaunadedicacióde25a30hores,incloentclasseslectives,horesd’estudi,tutories,
seminaris,treballs,pràctiquesoprojectes.
BlancaBertranSubirana Pàg.9
o EspecialitatElèctrica:anàlisiicàlculdesistemeselèctricsdepotència.
o EspecialitatElectrònica:anàlisiidissenydesistemeselectrònics.
o EspecialitatEnergia: formacióavançadaenenergiesrenovables,energianuclear i
màquinestèrmiques.
o EspecialitatEstructuresiConstrucció:dissenyicàlculd’estructuresmetàl·liques,de
formigóimixtes.
o Especialitat Materials: formació en materials biomèdics, la nanotecnologia, i el
dissenyireciclatgedematerials.
o EspecialitatMecànica:càlcul,dissenyiassaigdemàquines.
o Especialitat Organització Industrial: formació per exercir la direcció general i
tècnicadetottipusd’organitzacions.
o Especialitat Química: formació en les tecnologies químiques que s’apliquen al
sectordelspolímers,labiotecnologiailaindústriaalimentària.
AquestMàster, de dos anys de durada, habilita per a l’exercici de la professió regulada
d’enginyer/aindustrial.Existeixenacordsdedobletitulacióvinculatsambaltrestitulacions
delmateixcentre,universitatsestatals,id’altresuniversitatsinternacionals.[30]
§ MàsterUniversitarienAutomàticaiRobòtica(120ECTS):formaciócentradaenl’àmbitde
l’enginyeria de l’automàtica i la robòtica integrant també coneixements propis de
l’enginyeria industrial, de l’electrònica industrial i alguns aspectes de la intel·ligència
artificial.[25]
§ MàsterUniversitari en Enginyeria d’Automoció (120 ECTS): formació especialitzada en el
sector de l’automoció que permet l’adaptació als llocs de treball de responsabilitat en
empresesocentresderecercad’aquestsector.[27]
§ Màster Universitari en Enginyeria d’Organització (120 ECTS): formació d’experts amb les
habilitats necessàries per a la gestió, l’organització i la direcció de persones, projectes,
departamentsiempreses.[29]
§ MàsterUniversitarienSupplyChain,TransportiMobilitat(120ECTS):formaciódetècnics
ambunaltgraud’excel·lènciaenl’anàlisi,lagestióil’optimitzaciódesistemeslogísticside
transportenl’àmbitdel’enginyeriacivilil’enginyeriaindustrial.[32]
§ MàsterUniversitarienEnginyeriaBiomèdica(60ECTS):formacióprofessionalenaspectes
de disseny, fabricació, avaluació, comercialització, instal·lació, manteniment i utilització
d’equipament mèdic per tal de donar resposta als problemes d’enginyeria que es
plantegenenelsàmbitsdelabiologiailamedicina.Estractad’unatitulaciócoordinadaper
laUniversitatdeBarcelona(UB)enlaqualhiparticipalaUPC.[26]
Pàg.10Programaciód’horarisperalesdefensesdeTreballsdeFinaldeGrauiMàster
§ MàsterUniversitarienEnginyeriadel’Energia(120ECTS):formacióprofessionald’experts
amblescapacitatsihabilitatsnecessàriesperanalitzarcasospràcticsigestionarprojectes
degeneració,transformació,distribucióoconsumdediferentsfontsenergètiques.Màster
Internacionalenfocatadonar respostaalsactualsproblemesenergèticsdesdediferents
vessants.TitulacióvinculadaalprogramaInnoEnergy.[28]
§ Màster Universitari en Enginyeria Nuclear (90 ECTS): formació que proporciona als
estudiants les habilitats necessàries per ocupar càrrecs de responsabilitat en empreses i
centresderecercadelsectornuclear.S’ensenyenconeixementsexhaustiusdelsfonaments
teòricsipràcticsdel’enginyerianuclear.TitulacióvinculadaalprogramaInnoEnergy.[31]
L’ETSEIB participa en el programa Europeu KIC InnoEnergy a través del qual s’imparteixen
titulacionsdemàsterdel’àmbitdel’energiaconjuntamententrevariesuniversitatseuropees.
El programa permet estudiar cada any en una universitat diferent, a més d’oferir cursos
d’emprenedoria i innovacióqueesdesenvolupenen centres col·laboradorseuropeus. [44]A
l’escolas’ofereixenelssegüentsmàsters:
§ MScEnergyforSmartCities:programaqueestudiareptesrelacionatsambl’augmentdela
poblacióurbana,comdissenyurbà,infraestructurescivilsigestiódel’energia.[44]
§ MScSENSE-SmartElectricalNetworksandSystems:màstervinculatal’enginyeria,disseny
igestiódelesxarxeselèctriquesintel·ligentsdelfutursorgidesdelapossibilitatcreixentde
ferúsdelesenergiesrenovables.[44]
§ MScEMINE-InnovationinNuclearEnergy:programaespecialitzatenl’estudidel’energia
nuclearenl’àmbittecnològic,socialieconòmic,aixícomelsimpactesambientals.[44]
§ MScRENE-RenewableEnergy:màsterqueproporcionaconeixementenprofunditatdeles
tecnologiesvinculadesalesenergiesrenovables,aixícomcapacitatsdegestiói innovació
perdesenvoluparl’energiadelfutur.[44]
§ MScSELECT-EnvironomicalPathwaysforSustainableEnergySystems:programaatravés
delquals’estudia l’impacteambiental isocialdavant l’actualescenaricanvianten l’àmbit
delesenergiesrenovables.[44]
Laduradad’aquestes titulacionsoscil·laentre1 i2anys,estructuratsenquadrimestresambuna
càrrega lectivade30crèditsECTScadascund’ells.DemanerasimilaralsestudisdeGrau,durant
l’últimquadrimestredelMàsterelsestudiantsrealitzenelTreballfinaldeMàster(TFM),lacàrrega
lectivadelqualvedeterminadaperlasevamodalitatderealitzacióilatitulaciódeMàsteralaque
correspon.
BlancaBertranSubirana Pàg.11
2.1.3. Doctorats
Eldoctoratésl’últimcicleacadèmicd’educaciósuperiorqueespotcursaralqualespotaccedirsi
s’està en disposició d’un títol de Grau i d’un títol de Màster. Entre altres coses, permet
posteriormentiniciarlacarreraacadèmicaperarribaraserprofessoruniversitari.[21]
Elprogramadedoctoratconsisteixenunperíodedurantelquall’estudiantesdedicaalarecerca
especialitzada d’alguna temàtica, combinat ambuna iniciació a la docència, que finalitza amb la
lecturapúblicad’unprojecteotesidoctoral.
Actualmentdesdel’ETSEIBesgestionenelsprogramesdedoctoratespecialitzatsenelssegüents
àmbitsdeconeixement:
§ Administracióidirecciód’empreses
§ Automàtica,robòticaivisió
§ CiènciaienginyeriadeMaterials
§ EnginyeriaBiomèdica
§ EnginyeriadeProcessosQuímics
§ PolímersiBiopolímers
§ EnginyeriaElèctrica
§ EnginyeriaNuclearidelesRadiacionsIonitzants
§ AdvancedMaterialsScienceandEngineering(ErasmusMundus)
§ EnvironomicalPathwaysforSustainableEnergyServices(ErasmusMundus)
§ EnginyeriaMecànica,FluidsiAeronàutica
Alguns d’aquests àmbits formen part del programaErasmusMundus, programa de cooperació i
mobilitaten l’àmbitde l’educaciósuperior,compartitentreunmínimde3universitatseuropees
que compten amb el suport de la Unió Europea. El principal objectiu és millorar la qualitat de
l’educació superior europea i promoure el diàleg intercultural mitjançant la cooperació entre
països.
2.2. Unitatsacadèmiquesiderecerca
L’ETSEIB s’organitza en centres docents, departaments, instituts, laboratoris, centres i grups de
recerca,pertaldeduratermeladocènciailarecercaquetéencomanada.[20]
2.2.1. Departaments
Actualment a l’ETSEIB hi ha 16 departaments diferents enfocats a una àmplia varietat de
Pàg.12Programaciód’horarisperalesdefensesdeTreballsdeFinaldeGrauiMàster
temàtiquesdinsdelsqualss’hiorganitzaelprofessoratpertaldecoordinarladocènciaifomentar
larecercaenelsdiferentsàmbits.[20]
S’indiquen a continuació els noms dels departaments, especificant-ne el camp de docència i
recercaencadacas:
§ CiènciesdelaComputació(CS):departamentespecialitzatentemàtiquesrelacionadesamb
els àmbits de la algorísmica, gràfics per computador, intel·ligència artificial, lògica i
programació.[4]
§ Ciències dels Materials i Enginyeria Metal·lúrgica (CMEM): departament enfocat a
l’enginyeria de materials i l’enginyeria metal·lúrgica, especialitzat en aliatges lleugers i
tractaments de superfície; biomaterials, biomecànica i enginyeria de teixits; integritat
estructural, micromecànica i fiabilitat dels materials; processos de conformació de
materialsmetàl·lics;itecnologiadepolímersicompòsits.[3]
§ Enginyeria de Projectes i de la Construcció (EPC): departament orientat als àmbits de
l’enginyeriadeprojectes,l’enginyeriadelaconstrucció,l’eficiènciaenergèticadelsedificis,
elprocésdedissenydenousproductesil’enginyeriaambiental,entred’altres.[11]
§ Enginyeriade Sistemes,Automàtica i Informàtica Industrial (ESAII): departamentorientat
tantaaspectesbàsicscomd’ampliacióderobòtica,senyalsisistemesbiomèdics,sistemes
avançatsdecontrolivisióperordinador.[13]
§ Enginyeria Elèctrica (EE): departament enfocat a àrees relacionades amb instal·lacions i
sistemeselèctricsdepotència,iambmàquinesiaccionamentelèctrics.[5]
§ Enginyeria Electrònica (EEL): departament que realitza la seva activitat en l’àmbit dels
dispositius semiconductors imicrosistemes, electrònica industrial i de potència, circuits i
sistemesintegrats,isistemesdemesuraiinstrumentacióbiomèdica.[7]
§ Enginyeria Mecànica (EM): departament que consta de grups de recerca enfocats a la
contaminacióperemissióacústicaimecànica,lesvibracions,teoriaianàlisidemàquines,i
alestecnologiesdefabricació.[10]
§ Enginyeria Química (EQ): departament orientat a diversos àmbits dins el camp de
l’enginyeria química com enginyeria molecular, biotecnologia, o reactors químics, entre
d’altres.[12]
§ Estadística i InvestigacióOperativa (EIO):departament involucrateneldesenvolupament
BlancaBertranSubirana Pàg.13
d’interfícies intel·ligents isistemesautomàticsdeprocessamentdedades, l’optimització i
simulaciódefluxosenxarxaiaplicacionsdetotl’anterior.[9]
§ Expressió Gràfica en l’Enginyeria (EGE): departament amb activitat desenvolupada en
l’àmbitdel’enginyeriagràfica,dissenydeproducte,multimèdiaiinformàticagràfica.[8]
§ Física (FIS): departament integrat per grups de recerca enfocats a l’enginyeria nuclear,
propietatsfísiquesdelsmaterialsoenergiairadiació,entred’altres.[43]
§ Màquines iMotorsTèrmics(MMT):departamentenfocataàreesfonamentals iaplicades
d’enginyeriatèrmicacomtransferènciadecaloromotorsiinstal·lacionstèrmiques.[49]
§ Matemàtiques (MAT):departamentquetractacontingutsde lamatemàticacomàlgebra,
càlcul,mètodesnumèricsoequacionsdiferencials.[47]
§ MecànicadeFluids(MF):departamentquedesenvolupaactivitatsorientadesasistemesde
turbomàquines, sistemes de control i potència oleohidràulics i pneumàtics, i medis
materialsenestatfluid.[48]
§ Organització d’Empreses (DOE): departament especialitzat en un ampli ventall de
temàtiquescomsónl’administraciód’empreses,l’economia,l’enginyeriad’organització,la
logísticaielsrecursoshumans.[6]
§ Resistència deMaterials i Estructures a l’Enginyeria (RMEE): departament amb línies de
recerca enfocades a l’anàlisi d’estructures i demecànica delsmedis continus, a l’anàlisi
estructural avançatmitjançantmètodesnumèrics i experimentals, i a l’estudid’elements
resistents iprocessosdedefabricaciómitjançanttècniquesexperimentals idesimulació.
[50]
2.2.2. InstitutsUniversitarisdeRecerca
L’ETSEIB acull l’activitat de dos Instituts Universitaris, entitats que es dediquen a la recerca
científicaialatransferènciadetecnologiaenunàmbitdeconeixementdeterminat.[20]
Al’escolahiconstenelssegüentsinstituts:
§ InstitutdeTècniquesEnergètiques (INTE): lesactivitatsqueportaa termeaquest institut
estan relacionades amb la utilització de les radiacions ionitzants i els riscs associats,
l’energiaielsacceleradors.[45]
§ Institut d’Organització i Control de Sistemes Industrials (IOC): la seva actuació fusiona
Pàg.14Programaciód’horarisperalesdefensesdeTreballsdeFinaldeGrauiMàster
conceptesdelsàmbitsdel’automàtica,larobòticail’organitzacióindustrialperaplicar-hoa
l’anàlisi,eldisseny, ladirecció iel controldels sistemes logístics ideproducciódebéns i
serveis.[46]
2.2.3. GrupsdeRecerca
LaUniversitatreconeixelssegüentstipusdeGrupsdeRecerca[22]:
§ GrupsdeRecerca (GR):organitzacióbàsicade la recercaenequipsamb l’objectiude fer
arribarelsresultatsalasocietatuniversitària.
§ CentresEspecíficsdeRecerca(CER):centresenfocatsadonarrespostaencampsespecífics
derecercaalesdemandesd’entitatspúbliquesoprivadesexternes.
§ Grups de Recerca reconeguts per la Generalitat (SGR): grups destinats a la recerca i
transferènciadelconeixement integratsperuniversitats i centrespúblicsoprivats, sense
ànimdelucreireconegutsperlaGeneralitat,pertaldepotenciar-neeldesenvolupament
olaconsolidació.
§ Centres TECNIO: grups universitaris i centres tecnològics dedicats a la investigació
industrial, expertsen transferència tecnològicaaCatalunya,quepertanyena laXarxade
CentresdeSuportalaInnovacióTecnològica.
2.3. Relacionsambl’exteriordelauniversitat
Ambl’objectiudefacilitaral’estudiantatlapossibilitatdeparticiparenprogramesd’intercanviide
ferpràctiquesprofessionals,amésdepotenciarlatransferènciaderesultatsdelarecerca,l’ETSEIB
mantéunaàmpliaxarxaderelacionsambinstitucions,empresesd’enginyeriaicentresderecercai
docèncianacionalsiinternacionals.[14]
2.3.1. Càtedresd’empreses
LesCàtedresd’empresasóncol·laboracionsestratègiquesestablertesentreunaomésempresesi
l’ETSEIB-UPC a través de les quals es desenvolupen activitats de docència, recerca, difusió,
innovació i transferència de tecnologia en temesd’interès tant per a les empreses comper a la
universitat. L’empresa proposa i orienta els projectes d’investigació que es realitzaran a la
universitat,quiposaalasevadisposicióinfraestructuresirecursoshumans.[19]
Atravésd’aquestescàtedress’organitzenactivitatsd’interèscomseminaris,conferènciesicursos
específics,esproposentreballsdefidetitulació itesisdoctorals iespromouenlespràctiquesen
empreses.
BlancaBertranSubirana Pàg.15
Actualmental’ETSEIBtéadscriteslessegüentscàtedresdecol·laboracióentreempresesilaUPC:
§ CàtedraARGOS:col·laboracióambelConsellNacionaldeSeguretatNuclearpercontribuir
alamilloradelaseguretatalescentralsnuclearsiinstal·lacionsassociades.[51]
§ Càtedra SEAT-UPC: col·laboració amb l’empresa automobilística SEAT amb l’objectiu de
donar a conèixer el sector de l’automoció als universitaris i a la societat en general,
fomentant l’excel·lència en la innovació i la mobilitat sostenible a través de projectes
conjuntsdetransferènciadetecnologiaiinnovació,depràctiquesformativesal’empresa,i
d’activitatsrelacionadesambelsector.[2]
§ CàtedraEndesaRed:col·laboracióambEndesaqueorientalasevaactivitata laformació,
recerca, i transferència de resultats, així com la divulgació científica, en l’àmbit de la
innovacióenergèticaenelsectorelèctric,pertald’aconseguirunmodelenergèticeficienti
sostenible.Espretén també involucrar totselsagentssocials implicatsen lacreaciód’un
model energètic que permeti aconseguir l’excel·lència tecnològica. A través d’aquesta
càtedraesdesenvolupenprojectes conjuntament ambel Centred’Innovació Tecnològica
enConvertidorsEstàticsiAccionaments(CITCEA),tambédelaUPC.[53]
§ Càtedra GRUPO JG: col·laboració amb el Grupo JG amb la finalitat de promoure la
sostenibilitataplicadaal’enginyeriadeserveidelsedificisatravésdebeques,conferències
iclassesmagistrals,entred’altres.[52]
Amés,encol·laboraciótambéamblesempresesMecaluxiSchneider,s’hancreata l’escoladues
aules que porten el nom d’ambdues empreses amb l’objectiu de formar futurs professionals
especialitzatsenl’àmbitd’actuaciód’aquestesempreses.[19]
2.3.2. Relacionsinternacionals
Actualment l’ETESIB disposa de convenis d’intercanvis amb 22 països Europeus i 13 països
d’Amèrica iÀsia,oferintaixí lapossibilitatde realitzarprogramesdemobilitat internacionalamb
mésde130universitatsdiferents.[16]
2.3.3. Relacionsambempreses
L’Escola ofereix la possibilitat a l’alumnat, tant de Grau com deMàster, de realitzar pràctiques
acadèmiques externes en més de 350 empreses diferents a través de convenis de cooperació
educativa. Aquestes pràctiques poden o no ser reconegudes com a part del pla d’estudis
(curriculars o extracurriculars), i permeten ser desenvolupades tant en empreses, institucions i
entitatspúbliquesiprivadesd’àmbitnacionalointernacional.[37]
Pàg.16Programaciód’horarisperalesdefensesdeTreballsdeFinaldeGrauiMàster
Abandadelespràctiquesacadèmiques,destacadesempreses,càtedresiinstitucionshansignatun
conveniambl’ETSEIBperpatrocinarpremisibequesperestudiantatdestacat.[15]
2.3.4. Altres
Addicionalment, l’Escola manté relacions amb el Col·legi Oficial d’Enginyers Industrials de
Catalunya,l’Associaciód’EnginyersdeCatalunya,ilaMútuadelsEnginyers.[14]
2.4. PersonalDocentiInvestigador
Les unitats docents presentades en l’apartat anterior estan dirigides i integrades per personal
docent i investigador (d’araenendavantPDI)quedesenvolupa tasquesdedocència i recercaen
líniaambl’especialitatdecadadepartament.
Figura2.1Taula-resumdelscol·lectiusdelaUPC.Font:UPC[57]
LaFigura2.1classificaiindicalescaracterístiquesprincipalsdelscol·lectiuspresentsenelscentres
de la UPC. A continuació es descriuen ambmés detall els diferents tipus de PDI, segons siguin
personal contractat o funcionari, i segons quines siguin les seves capacitats docents i
investigadores.
BlancaBertranSubirana Pàg.17
2.4.1. PDILaboralTemporal
2.4.1.1. Ajudant(AJ)
ElsAjudantssóndoctorandsquetenenlaconsideraciódePDIenformació.Duenatermelaseva
activitatalauniversitatambdedicacióatempscompleticol·laborenentasquesdocentsfinsaun
màximde60horesanuals,durantunmínimde1anyiunmàximde4.[1]
2.4.1.2. ProfessoratLector(LEC)
La figura de Lector obre les portes de la carrera acadèmica a través d’un contracte temporal a
tempscompletquepermetaccedirposteriormentafiguressuperiorsambcontracteindefinit,ique
proporciona plena capacitat docent i investigadora. Per optar a la contractació com a professor
lector cal estarendisposiciód’undoctorat. Laduradadel contracteoscil·laentreun i cincanys,
limitant-seeltempstotaldeduradaconjuntadelcontractedeprofessoratlectorield’ajudanta8
anys.[1]
2.4.1.3. ProfessoratAssociat(ATP)
Es tracta de personal que exerceix la seva activitat professional fora de l’àmbit acadèmic
universitariperòqueescontractaperadesenvolupartasquesdocentsalauniversitat.Elcontracte
ésenrègimdededicacióatempsparcialipresentenplenacapacitatdocentenl’àmbitdelaseva
competència. La seva dedicació màxima és de 480 hores anuals equivalents a 180 hores de
docènciapresencial,120horesd’atencióalsestudiants,ilarestad’horesesdediquenaprepararla
docència, elaborar material de suport, corregir treballs i participar en tasques de planificació,
avaluacióicoordinació.[54]
2.4.2. PDILaboralPermanent
2.4.2.1. ProfessoratCol·laborador(COL)
Elprofessorcol·laboradorésunafiguracontractualaextingirdesque,d’acordambelReialDecret
989/2008, al 2013 va finalitzar el termini per convocar concursos per a la contractació d’aquest
tipus de professorat, que tenen plena capacitat docent i, en cas de ser doctor, també plena
capacitatd’investigació.[54]
2.4.2.2. InvestigadorOrdinari(IO)
Els Investigadors ordinaris són doctors amb una capacitat investigadora provada contractats de
forma permanent o temporal, en funció de si s’està vinculat a un projecte concret de recerca
científicaotècnica.Desenvolupamajoritàriamenttasquesderecercaieventualmentdedocència.
Pàg.18Programaciód’horarisperalesdefensesdeTreballsdeFinaldeGrauiMàster
[54]
2.4.2.3. Directord’Investigació(DI)
Elsdirectorsd’investigaciósóndoctorsquedesenvolupenmajoritàriamenttasquesderecercaide
maneraeventualdedocència,desprésd’haveradquiritunacapacitatd’investigacióconsolidada.Es
tractadepersonalcontractatpermanentmentodeformatemporalsiestàvinculataunprojecte
concret.[54]
2.4.2.4. ProfessoratAgregat(AG)
Es tracta d’una figura contractual de caràcter permanent que desenvolupa tasques docents i de
recerca amb plena capacitat amb una dedicació a temps complet. Per poder aconseguir un
contracte de professor agregat cal acreditar una trajectòria investigadora postdoctoral i una
activitatdocentiunaderecercamínimes.[54]
2.4.2.5. CatedràticContractat
Es tracta de personal amb una carrera docent i investigadora consolidada que presenta una
categoriacontractualquecorresponal’etapamésavançadadelacarreraacadèmica.Desenvolupa
lasevaactivitatambunadedicacióatempscomplet.[54]
2.4.3. PDIFuncionari
2.4.3.1. ProfessorTitulatd’EscolaUniversitària(TEU)
Elprofessortitulatd’escolauniversitàriaésunafiguraque,desprésdedemostrarunescapacitats
docentsiinvestigadoresmínimes,desenvolupatasquesdocentsiderecerca.Estractad’uncàrrec
defuncionarienviesd’extincióalqualespodiaaccedirsensehaverrealitzatundoctorat.[54]
2.4.3.2. ProfessorTitulat(TU)
Esconsideraprofessor titulataquellquedesenvolupa tasquesdocents ide recercaa travésd’un
càrrecdefuncionaridecaràcterpermanent.Perpoderoptaraunaplaçadeprofessortitulat,cal
haverprovatunacapacitatdocentiinvestigadoramínimes.[54]
2.4.3.3. Catedràticd’Universitat(CU)
Es tracta de personal amb una carrera docent i investigadora consolidada que presenta una
categoriacontractualquecorresponal’etapamésavançadadelacarreraacadèmica.Desenvolupa
lasevaactivitatambunadedicacióatempscompletatravésd’uncàrrecdefuncionari.Nomésen
BlancaBertranSubirana Pàg.19
el cas de pertànyer a aquesta categoria es pot arribar a ser rector de la universitat. [54]
Pàg.20Programaciód’horarisperalesdefensesdeTreballsdeFinaldeGrauiMàster
3. ElTreballdeFid’Estudis(TFE)
Durantl’últimquatrimestredelestitulacionsdeGrauideMàster,esdesenvolupaelTreballdefi
d’Estudis,exercicidecaràcterobligatorimitjançantelqualessintetitzenelsconeixementsadquirits
durantlatitulació.[40]
3.1. ElTreballdeFinaldeGrau(TFG)
Comjas’hacomentatanteriorment,elTFGésunexercicidecaràcterobligatoriqueelsestudiants
realitzendurant l’últimquadrimestrede la titulaciódeGrau (equivalental8èquadrimestrede la
titulació,oal2onquadrimestrede4tcurs).Es tractad’unprojecteoestudid’enginyeriaoriginal
desenvolupat normalment de manera individual, mitjançant el qual els estudiants han de
sintetitzar les competències assolides durant la titulació posant de manifest la seva capacitat
d’aplicardemaneraintegradaelsconeixementsadquirits.[41]
Lacàrregalectivaequivalentdeltreballvariaenfunciódelatitulacióqueescursa,essentdemínim
12crèditsECTSenelcasdelGETI.Encasquelapresentacióidefensaesfacienunauniversitato
centrederecercadiferental’ETSEIBambelqualhihagiunconvenidecol·laboracióqueincloguiel
TFG,elscrèditsobtingutspeltreballpodenvariar.[41]
3.2. ElTreballdeFinaldeMàster(TFM)
ElTFMésunprojectedecaràcterobligatoriqueesdesenvolupadurantl’últimquatrimestredela
titulació (en el cas del Màster Universitari d’Enginyeria Industrial i de la majoria de màsters
impartits a l’ETSEIB, equivalent al 4t quadrimestre de la titulació, o al 2on quadrimestre de 2on
curs).Estractad’unexerciciobligatoriquesintetitzaelsconeixementsadquiritsdurantlatitulació,
elcontingutdelqualestàrelacionatambl’àmbitdelestecnologiesdecadascundelsmàsters.[42]
Lacàrregade treballequivalentassociadaalsTFMsésde12crèditsECTSpera totselsmàsters,
excepteperalMàsterd’EnginyeriaNuclearqueésde15crèditsECTS.Aquestacàrregalectivapot
variarsieltreballesrealitzaenelmarcd’unprogramademobilitat,osiessol·licitaunTFMampliat
(30crèditsECTS).LarealitzaciódelTFMhad’implicarunadedicaciód’unes30horesdetreballper
crèditECTS.[42]
3.3. Modalitatsderealització
La possibilitat que s’ofereix als estudiants de participar en programes de mobilitat nacionals i
BlancaBertranSubirana Pàg.21
internacionals,ode realitzarpràctiquesexternescurricularsenempreses,permetqueexisteixen
diferentsmodalitatsderealitzaciódelTFGiTFM.(TFG:[38],TFM:[39])
§ MODALITATA:treballrealitzat,presentatidefensatalmateixcentredocent,dirigitperun
professorquepot seronode l’ETSEIB. En casdeque siguide forade l’Escola, caldrà la
intervenciód’unmembredelPDIdel’ETSEIBcomaponent.
§ MODALITATB:treballdesenvolupatenempresesoentitats,sotaladirecciód’unmembre
external’escolavinculatal’empresaoentitatambtitulaciósuperior,iambunponentde
l’ETSEIB que assessorarà a l’estudiant a assolir els objectius establerts. La presentació i
defensadelprojecteesrealitzaal’escola.
§ MODALITATC:treballrealitzatdurantunprogramademobilitat,dirigitperunprofessorde
launiversitatdedestíiambeldirectord’internacionalitzaciódel’ETSEIBcomaponent.El
projecteesconfeccionaseguintlesnormesestablertesalauniversitatdedestíiesdefensa
alamateixa.
§ MODALITAT D: treball realitzat en empreses estrangeres dins d’un marc de mobilitat,
seguintlesmateixespautesqueenelcasdelaModalitatB.
3.4. Etapesdedesenvolupament
El procediment que es segueix per al desenvolupament del TFG i del TFM és molt similar. A
continuaciós’expliquenlesdiferentsetapesdedesenvolupamentcorresponentsalesmodalitatsA
iB,iescomentenlesdiferenciessegonsestractideTFGoTFM.(TFG:[38],[41],TFM:[39],[42])
1. Elecciódeltema
Primeramentelsestudiantshaurand’escolliruntemad’interèsperapoderdesenvolupar
eltreball.L’elecciódelatemàticadelTFG/TFMvaassociadaal’assignaciód’undirectoro
ponent de l’escola que tutoritzarà la feina de l’estudiant. Qualsevol membre del PDI
assignat a l’ETSEIBpot actuardedirectoroponent i, en casos justificats per la temàtica
escollida,dosmembresdelprofessoratpodenactuarcomacodirectorsdelTFG/TFM.
Elsestudiantspodenelegirlatemàticadeltreballconsultantlespropostesdelsprofessors
del’escolaatravésdelaBorsadeProjectesiTreballs2,obépodenproposarellsmateixos
untemaibuscarunprofessorqueliinteressidirigir-lo.Enaquestúltimcascaltambéque
l’escolaaprovilatemàticaproposada.
Quan el Treball de Fi d’Estudis (TFE) es realitza en una empresa o entitat externa
2Borsadeprojectes:https://etseib.upc.edu/ca/estudis/treballs-fi-destudis/borsa-de-projectes-i-treballs
Pàg.22Programaciód’horarisperalesdefensesdeTreballsdeFinaldeGrauiMàster
(Modalitat B), la temàtica s’hade consensuar ambel professor de l’Escola que actuade
ponent.
Un cop escollit el tema i assignat el director o ponent de l’escola, l’estudiant ha de
desenvoluparel seutreball seguint lanormativaestablertaa l’ETSEIB. ([33]perTFG, [34]
perTFM).
2. Registre
Prèviament a la formalització de la matrícula i un cop s’hagin acordat els objectius del
treball ambel director o ponent, els estudiants haurande fer el registre del TFG/TFMa
través de l’e-secreteria. Aquest registre serà validat posteriorment pelmateix director o
ponent del projecte. El registre podrà formalitzar-se si es disposa del 75% dels crèdits
superatsenelcasdelTFG,idel50%delscrèditsdelatitulaciósuperatsenelcasdelTFM.
Figura3.1ExempledeCalendarideTFG(esquerra)iTFM(dreta)curs2016-17.Font:ETSEIB[17][18]
3. Matrícula
La matrícula del treball es formalitzarà durant els períodes de matriculació ordinaris
(principi del quadrimestre) o extraordinaris (normalment a meitat del quadrimestre) de
cadatitulacióestablertsperl’escola,uncops’hagiregistrativalidateltreball.
Encasqueladefensanoesfacidurantelquadrimestreenelquals’hamatriculateltreball,
l’estudiantpodrà sol·licitarunapròrrogade lamatrículaqueseràvàlida finsa ladatade
lliurament establerta al calendari de TFE del quadrimestre següent, abonant només
l’importdelsserveisadministratius.
LaFigura3.1mostracomaexempleelCalendarideTFGiTFMdelcurs2016-2017.
4. Avaluacióparcial
Només en el cas dels TFGs, el director o ponent avaluarà la feina feta per l’estudiant a
mitjans del quatrimestre, segons el calendari establert. Aquesta avaluació obligatòria es
BlancaBertranSubirana Pàg.23
realitzaràenfunciódelsobjectiusestablertsiindicaràsil’estudiantésApteoNoAptepera
dipositarelTFGdurantelperíodeordinariestablertenelcalendaridelcurs.
Encasdequel’estudiantsiguideclaratNoApte,disposaràd’unperíoded’avaluacióparcial
idedipòsitextraordinaris.
5. Designaciódeltribunal
Elmembresdeltribunal(veureapartat3.5)seranestablertsperelcoordinadordelGrauo
del Màster, o el sots-director de Projectes Acadèmics, o per la persona en qui aquests
deleguin.
L’assignació dels tribunals serà publicada pel SIAE (Servei d'Informació i Atenció als
Estudiants),proposantunllociunadataperalapresentacióidefensa.
El president del tribunal serà l’encarregat de validar la data i lloc establerts per a la
presentació, icoordinaràunadatai llocalternatiusamblarestademembresdeltribunal
encasquesiguinecessari.
EltribunalesmantindràambindependènciadelaconvocatòriaenlaqualesdefensielTFE.
6. DipòsitiExamendeNormes
ElcalendaridelsTFEestableixelsperíodesdedipòsitdelstreballs,havent-niund’ordinarii
und’extraordinariacadaquadrimestre(GeneriAbrilpeldeTardor,iJunyiSetembrepel
dePrimavera).
Eltreballesdipositaenformatdigitaluniversal(tipus.pdf)alaintranetdurantelperíode
establert,ambelvistiplaudeldirectorodelponent.
Ésimportantqueelstreballscompleixinamblespautesdeconfeccióqueestableixl’escola.
([35] per TFG, [36] per TFM) En cas d’incomplir-les, el treball podria ser esmenat pel
presidentdeltribunalicaldriatornar-loadipositar.
NomésenelcasdelTFM,caldràqueeltreballsuperiunexamendenormesperapoder
serpresentatidefensat.[34]
7. Presentacióidefensa
Enunaprimerafase,l’estudiantexposaràunresumdelcontingutdeltreballenuntemps
fixatpeltribunald’aproximadament25minutsenelcasdelTFGi30minutsenelcasdel
TFM. Posteriorment, durant la fase de defensa del treball, l’estudiant respondrà a les
preguntes que formulin els membres del tribunal sobre el contingut i realització del
projecte.
En cas que el treball l’hagin desenvolupat dos estudiants conjuntament, la presentació i
defensaseràconjuntaiambunaparticipacióequivalentd’ambdósalumnes.
Pàg.24Programaciód’horarisperalesdefensesdeTreballsdeFinaldeGrauiMàster
8. Qualificació
Desprésdelapresentació idefensadeltreball,eltribunaldeliberaràensessiótancadala
qualificacióassignadaal treball i la comunicaràposteriormenten sessiópública.Aquesta
qualificacióesveuràinfluïdaperlainformacióqueproporcionieldirectori/oelponentals
membres del tribunal sobre el treball realitzat per l’estudiant durant tot el període de
desenvolupament.
ElTFEesconsideraràAprovatsis’obtéunanotaentre5i6,9,Notablesilanotaoscil·lade7
a8,9,Excel·lentsilanotaestàentre9i10,isuspèssilanotaésinferiora5.
En el cas del TFG, es pot obtenirmatrícula d’honor (MH) si la nota és un 10 i no s’han
atorgatmésmatriculesquel’equivalental5%d’estudiantsmatriculats.
3.5. ComposiciódelstribunalsdeTFGiTFM
EltribunaldelsTFGs iTFMs,formatperdiferentsmembresdelprofessoratassignata l’escola,és
l’encarregatdevalorarelcontingut,lapresentacióiladefensadelprojecteperacabaracordantla
qualificacióquefinalments’atorgaràal’estudiant.
L’assignaciódels professorsque formaranpart de cada tribunal es realitza a travésd’un sorteig,
respectantunesespecificacionsconcretesquefomentenladiversitatdelsmembresenquantala
sevaespecialitat.
La composició dels tribunals presenta lleugeres diferències si es compara el cas dels TFGs i els
TFMs. En general un tribunal està format per 3 o 4membres amb les següents característiques
(TFG:[41],TFM:[42]):
§ Directoroponent:s’esculldurantlaprimerafasededesenvolupamentdelprojecteiestà
vinculataldepartamentenelqualesdesenvolupaelprojecte.NomésenelcasdelTFGel
directoroponentformaràpartdeltribunal.
§ President: pertanyent al mateix departament que el director o ponent del projecte. El
presidentactuaràd’intermediarientreelsmembresdeltribunalpercoordinar ladata iel
llocdelapresentació.EnelcasdelTFG,lafiguradepresidentcoincideixambladeVocal
deldepartament.
§ Vocaldeldepartament:membredeltribunalqueformapartdelmateixdepartamentque
el director o ponent. En el cas del TFG, la seva figura coincideix amb la del director o
ponent.
§ Vocal extern: membre del tribunal no vinculat al departament del director o ponent.
BlancaBertranSubirana Pàg.25
Avaluaràlafeinadel’estudiantdesd’unaperspectivaexternaal’àmbitdeconeixementdel
departamentassociatalprojecte.
§ Suplents: un d’ells vinculat al departament del director o ponent del projecte i l’altre
externaaquest.Passaranaformarpartdeltribunalencasquealgundelsmembrestitulars
nopuguiassistirfinalmentalapresentacióidefensadelTFGoTFMassignat,semprequeel
nombremàximdemembresd’undepartamenteneltribunalsigui2.
A lafiguraTaula3.1espresentaunquadre-resumsobrelesposicionsquepodenocupardinsdel
tribunald’unTGFoTFMlesdiferentsfiguresdePDIques’hanpresentatal’apartat2.4.
Taula3.1Quadre-resumdeposicionsquepodenocuparlesdiferentsfiguresdelPDIdinsdelstribunals
Director President Vocal Suplent
Ajudant � � � �
Lector � � � �
Associat � � � �
DirectordeRecerca � � � �
InvestigadorOrdinari � � � �
Agregat � � � �
Col·laborador � � � �
TU/TEU � � � �
CU � � � �
Pàg.26Programaciód’horarisperalesdefensesdeTreballsdeFinaldeGrauiMàster
4. Definiciódelproblemaimodelmatemàtic
DesprésdeposarencontextelTFGielTFMdinsdelestitulacionsdel’ETSEIB,iuncopdefinitsmés
detalladamentelselementsoparticipantsqueprenenpartenlafasedepresentacióidefensadels
treballs, es proposa un model matemàtic per a l’assignació òptima dels horaris d’aquestes
presentacions.
Els conceptes que s’han explicat en els apartats anteriors permetran definir més fàcilment els
criterisd’optimitzacióilesrestriccionsqueesconsideraranenelmodel.
4.1. Definiciódelproblemaiobjectiu
El programamatemàtic lineal que es desenvolupa en aquest apartat sorgeix de la necessitat de
programarlespresentacionsdelsTreballsdefinald’Estudisqueespresentenenunaconvocatòria
concretaal’ETSEIB.
Al’horaderealitzarl’assignacióhoràriadelsprojectescaltenirencomptelessegüentspremisses:
- Esparteixd’unnombredeterminatdeTFGs i TFMsassociats aundepartament concret,
ambuntribunalquejas’hauràassignatprèviament
- UnmembredelprofessoratpotformarpartdeltribunaldediferentsTFGsiTFMs
- Elsrecursos(llocs)onesdefenseselstreballssonlimitats.Elllochabitualsónaulespròpies
decadadepartament,delesqualsengeneraln’hihaunaacadascund’ells
- Esdisposadepocsdiespera fer lesdefensesperevitarquenohihagigransdiferències
entrel’alumnatquepresentaelstreballs
Amb tot això es planteja unproblemaque es resoldràmitjançant programaciómatemàtica amb
l’objectiu d’obtenir una assignació dels projectes a una hora concreta d’un dia concret el més
òptima possible en relació als criteris que es considerin. Per a fer-ho, s’establiran les hipòtesis i
restriccions necessàries que vindran en part generades per les premisses presentades
anteriorment.
Comjas’hacomentat,l’assignaciódelsdiferentsmembresalstribunalsdecadascundelprojectes
no és objecte delmodel que es desenvolupa en aquest projecte. La composició es determinarà
prèviamentis’introduiràcomadadadepartidadelmodel.Tampocesconsideraràdirectamentel
lloconesduenatermelesdefenses,totiqueindirectamentestindràencompte,doncs,coms’ha
esmentatanteriorment,esdisposad’unaaulaperdepartament.
Caldestacartambéquelaprincipallimitacióperaferlaseqüenciaciódiàriaihoràriadelstreballses
BlancaBertranSubirana Pàg.27
generapelfetqueunprofessorpotformarpartdemésd’untribunal.SiunmembredelPDIestà
associataunúnictribunal,enprincipinogeneracapproblemaal’horadeferlesassignacionsde
lespresentacions.
4.2. Dadesdepartida
Inicialmentesdisposaràdelessegüentsdades:
! Nombretotaldeprojectes(")aassignar:" = 1, … , !
' Nombre total de professors (() associats als tribunals dels! projectes: ( =1, … ,'
) Nombretotaldedepartaments(*)associatsals!projectes::* = 1,… , )
+,-,. Variablequeval1sielprofessor(hadeparticiparenladefensadelprojecte";i0altrament
+,0-,. Variablequeval1sielprofessor(hadeparticiparenladefensadelprojecte
"comatitular;i0altrament
12+3-,4 Variable que val 1 si el projecte " està associat al departament *; i 0altrament
5+. = +,-,.
6
-78 Nombretotaldetribunalsdeprojectesdelsqualsformapartelprofessor(
ApartirdelcalendarideTFEdefinitperaquellquadrimestreiconsiderantelnombredeprojectes
queesdefensarandurantlaconvocatòria,espodranestablirelnombredediesdisponiblespera
ferlespresentacions(:).Dinsdecadadia,elnombredefranges < queelconformenpodràser
determinatperelresponsabled’assignarelshorarisdelstreballs.
També serà decisió del responsable determinar el nombrede projectes quepodenpresentar-se
paral·lelament durant una hora (=>?), així com el nombre de projectes màxim d’un mateix
departamentquepodendefensar-seenunamateixafranja(=@ABC),iellímitdepresentacionsa
lesquepotassistirunprofessor,tantocupantqualsevolfiguradeltribunal <ABC comessent-ne
titular(<:ABC).
Pàg.28Programaciód’horarisperalesdefensesdeTreballsdeFinaldeGrauiMàster
4.3. Criteris
Enaquestapartatespresentenelscriterisqueesconsideraranperalaresoluciódelproblema,que
s’hanescollitpertald’afavoriralsmembresdeltribunalal’horad’assistiralespresentacionsdels
TFEs.
Esproposafer l’assignaciódelsprojectesafavorintque,percadascundelsprofessorsqueformen
partdelstribunals,lespresentacionsalesquehand’assistirestiguinperunabandaconcentrades
enelmínimdediespossibles,iperl’altreelmésseguidespossibledinsd’unmateixdia.
Aixòfacilitaràl’assistènciadelsmembresdeltribunalalesdefensesielspermetràplanificarmillor
elseutempsdurantelsperíodesestablertsperaferlespresentacions.
4.3.1. Mínimnombrededies:ladispersió
El criteri de la dispersió permetrà assignar els projectes demanera tal que els professors hagin
d’assistiradefensesdeTFEsdurantelmínimdediespossibles.
EsdefineixladispersiócomlavariablequecomptaelnombredediesenquèunmembredelPDIha
d’assistir a almenys una presentació de TFG o TFM. La variable 1"D+.,E indica la presèncianecessàriadelprofessoroprofessora(eneldia3.Ésunavariablebinàriaqueperaunprofessorserà 1 quan formi part d’almenys una de les presentacions assignades en un dia 3. Sigui' el
nombretotaldeprofessorat,i:eltotaldediesdepresentacions:
1"D+.,E( = 1, … ,'
3 = 1, … , :
Perapodermodelaraquestavariable,caldefinirunaltreconjuntdevariables(F.,E,G)queindiquinsiunprofessorestàlliureoocupat(presentenunadefensa)durantunafranjad’undia.Estracta
una variable binària que per a un professor ( serà 1 quan assisteix a una presentació durant lafranjaHdeldia3,i0altrament.LarelacióentrelesvariablesF.,E,Gi1"D+.,Es’estableixal’Equació1.
F.,E,GJG78 > 0 → 1"D+.,E = 1∀(, ∀3 Equació1
Al’Equació2esdefineixlavariabledispersiótotalpercadaprofessor(, i lasevacotainferior,queconsideraelnombretotaldepresentacionsalesqueestàassignatunprofessor(5+.),ielnombre
màximdedefensesalesquepotassistirunmembredurantundia(<ABC),esmodelaal’Equació3.
@"D+. = 1"D+.,E0E78 ∀( Equació2
BlancaBertranSubirana Pàg.29
@"D+. ≥OAPJQRS
∀( Equació3
4.3.2. Mínimnombred’interrupcions:lairregularitat
Mitjançantlairregularitats’intentaràassignarlesdefensesdemaneraque,peralsprofessorsque
formenpartdeltribunal,quedinelmésseguidespossibledinsd’undiaconcret.Ésadir,l’objectiu
ésminimitzarelnombred’interrupcionsenlatascad’estarpresententribunalsdeTFEs.
Esdefineix la irregularitatcomunconjuntdevariablesquemesurapercadascundelsprofessors,
lesvegadesquepassad’estarpresentenladefensad’unTFEdurantunahoraofranjaanoestara
cappresentaciódurantlasegüent,oalrevés.Dinselmodel,esfixacomunavariablebinàriaque
indica siunprofessor canviaomanté la sevaocupaciód’una franja (hora)d’undia,a la següent
franjadelmateixdia.
La irregularitat associada al membre del professorat ( en la franja H del dia 3 es defineix com
"??2T.,E,G.Siguieltotaldeprofessorat',eltotaldediesdepresentació:,ieltotaldefrangesperdia<,enprincipi:
"??2T.,E,G
( = 1, … ,'
3 = 1, … , :
H = 1, … , <
Peraconseguirunaassignacióelmésregularpossibleperelsprofessorsmembresdelstribunalso
directorsi/oponentsdelstreballspresentats,caldràminimitzarlairregularitattotal.
LairregularitatesdefineixapartirdelavariableF.,E,G,siaquestavariablecanviade0a1ode1a0enpassarde la franjaH a la franjaH + 1, la irregularitat serà1; en casque la variableF.,E,G i lavariableF.,E,GV8tinguinelmateixvalorlairregularitatserà0.
F.,E,G − F.,E,GV8 = 1 → "??2T.,E,G = 1 Equació4
L’Equació 4 modelitza matemàticament la relació entre aquestes dues variables, i la Figura 4.1
exemplifica lesdiferents casuístiquesquepodendonar-se i el valorqueprenen les variablesper
cadascunad’elles.
Pàg.30Programaciód’horarisperalesdefensesdeTreballsdeFinaldeGrauiMàster
Figura4.1Casuístiquesquepodendonar-sedelesvariables"??2T.,E,GiF.,E,G,perunmembre(,undia3ilesfrangesHi
H + 1
Pertald’evitarqueelmodelafavoreixil’assignaciódelsprojectesalaprimeraoal’últimafranjadel
dia,lavariableF.,E,GesdefineixdesdelafranjaH = 0finsalafranjaH = < + 1.Dinselmodel,es
forçaràquetoteslesvariablesperaquestesduesfrangesfictíciessiguinzeroindependentmentdel
professorat ( i del dia 3 (F.,E,X = 0, F.,E,JV8 = 0, ∀(∀3). Addicionalment, això implica que per un
professorladitamínimadelairregularitatserà2(Equació5).
"??2T(,3,H
<+1
H=0
0
E78≥ 2
∀3 3 = 1, … , :
∀( ( = 1, … ,' Equació5
Observacions:
1. Tenint en compte això, s’ha determinat que en el model només es considerarà la
irregularitatd’aquellsmembresqueforminpartdeltribunaldemésd’unprojecte(5+. >1).
2. Amés,tenintencomptequelairregularitatdepèndesiunprofessorestàlliureoocupat
durantunafranja(F.,E,G)ilasegüent(F.,E,GV8),lavariable"??2T.,E,Ghad’estardefinidaperunafranjamenysquelavariableF.,E,G.Així,s’hadeciditqueperlairregularitatlesfrangesesrecorrerande0finsa<.
A continuació es presenten tres casos que exemplifiquen el comportament esperat d’aquestes
variablesuncopimplementatelmodelperunprofessoriundiaconcret.
!""#$%,',( = 0
!""#$%,',( = 1
,%,',(-. = 0,%,',( = 0 ,%,',(-. = 1,%,',( = 1
,%,',(-. = 0,%,',( = 1 ,%,',(-. = 1,%,',( = 0
BlancaBertranSubirana Pàg.31
Figura4.2Exempled’assignació–Irregularitattotalde6
Figura4.3Exempled’assignació–Irregularitattotalde4
Figura4.4Exempled’assignació–Irregularitattotalde2
Enelcasquelacombinaciódetoteslesrestriccionshopermetessin,elresultatòptimunavegada
assignats3projectesd’aquestmembredelprofessorataaquestdiaseriaelde laFigura4.4,que
programa les presentacions seguides, aconseguint així el valor mínim de la irregularitat.
Contràriament,elcasmésdesfavorableéselqueespresentaalaFigura4.2.
4.4. Modelitzaciómatemàtica
Es defineix a continuació elmodel lineal que dissenya per poder resoldre el problema plantejat
inicialment.A l’Annex1espotconsultarelmodel tal i coms’hadefinitalsoftwareespecíficque
s’utilitzaràperimplementar-lo.
!",$,% = 0 !",$,()* = 0!",$,* = 1 !",$,, = 1 !",$,- = 0 !",$,. = 1 !",$,/ = 0 !",$,0 = 0
12234",$,% =1 12234",$,* =0 12234",$,, =1 12234",$,- =1 12234",$,. =1 12234",$,0 =0 12234",$,0 =0
!",$,% = 0 !",$,()* = 0!",$,* = 0 !",$,+ = 1 !",$,- = 0 !",$,. = 1 !",$,/ = 0 !",$,0 = 1
12234",$,% =0 12234",$,* =1 12234",$,+ =1 12234",$,- =1 12234",$,. =1 12234",$,0 =1 12234",$,0 =1
!",$,% = 0 !",$,()* = 0!",$,* = 0 !",$,+ = 1 !",$,- = 1 !",$,. = 1 !",$,/ = 0 !",$,0 = 0
12234",$,% =0 12234",$,* =1 12234",$,+ =0 12234",$,- =0 12234",$,. =1 12234",$,0 =0 12234",$,0 =0
Pàg.32Programaciód’horarisperalesdefensesdeTreballsdeFinaldeGrauiMàster
4.4.1. Dades
Considerantelques’hacomentatal’apartat4.2,espresentaacontinuaciólanomenclaturadeles
dadesques’utilitzaranperamodelitzarelproblema.
! " = 1, … , !Nombretotaldeprojectesqueespresentendurantunquadrimestre
concret
' ( = 1, … ,'NombretotaldemembresdelPDIqueformenpartd’algundels
tribunalsdelsprojectes
) * = 1,… , )Nombrededepartamentsalsqualsestanassociatselsprojectes
: 3 = 1, … , :Nombredediesdurantelsqualsespodenferlespresentacions,
segonselcalendarideTFGoTFM
< H = 1, … , <Nombredefrangesqueconformenundia,considerantqueeltemps
totaldestinatacadascunadelespresentacionsidefensesésde1hora
=>? -Nombredeprojectesqueespodenpresentarenparal·leldurantuna
mateixafranja,endiferentsaules
FABC -Nombredefrangesmàximesdurantlesqualsunprofessorpotestar
ocupatdurantundia
FTABC -Nombredefrangesmàximesdurantlesqualsunprofessortitularpot
estarocupatdurantundia
=@ABC -Nombredeprojectesd’unmateixdepartamentquepodenassignar-se
enunamateixafranjad’undiaconcret
+,-,. " = 1, … , !( = 1, … ,'
Matriuqueindicasielprofessor(ésmembredeltribunaldelprojecte"
5+. ( = 1, … ,' Vectorqueindicaelnombredetribunalsdeprojectesdelsqualsformapartcadascundelsmembres(representantqualsevoldelesfigurespossibles
+,0-,. " = 1, … , !
( = 1, … ,'
Matriuqueindicasielprofessor(ésmembretitular(director,presidentovocal)deltribunaldelprojecte"
12+3-,4 " = 1, … , !* = 1,… , )
Matriuqueindicasielprojecte"formapartdeldepartament*
\8,\] Pesosdecadacriterialafuncióobjectiu
4.4.2. Variables
En aquest apartat es presenten les variables que formaran part del programa, les quals s’han
BlancaBertranSubirana Pàg.33
classificatsegonssiguindedecisióonecessàriesperamodelarelscriterisqueesconsideraran.
4.4.2.1. Variablededecisió
Éslavariablequeindicaràaquinafranjadequindiaespresentacadascundelsprojectes.
^-,E,GVariablebinàriaqueval1si lapresentaciódelprojecte"s’assignaeldia3durant lafranjaH
" = 1, … , !;3 = 1, … , :;H = 1, … , <
4.4.2.2. Variablecomúdelscriteris
Variablequeindicasiunprofessorestàlliureoocupatdurantunafranjad’undiaconcret.S’utilitza
perdefinirlesvariablesdelscriterisdispersióiirregularitat.
F.,E,G Variablebinàriaqueval1sielprofessor(assisteixaunapresentacióprogramadael
dia3durantlafranjaH
( = 1, … ,';3 = 1, … , :;H = 0, … , < + 1
4.4.2.3. Variablequemodelaladispersió
Variableintroduïdaal’apartat4.3,utilitzadaperamodelitzarlacondiciódedispersió.
1"D+.,EVariablebinàriaqueval1sielprofessor(assisteixaalmenysunapresentaciódurant
eldia3
( = 1, … ,';3 = 1, … , :
4.4.2.4. VariablequemodelalaIrregularitat
Variablepresentadaal’apartat4.3,necessàriaperamodelarelcriterid’irregularitat.
"??2T.,E,G
Variablebinàriaqueval1si:
§ Elprofessor(noassisteixacappresentaciódurant la franjaHdeldia3 i siqueassisteixaunapresentaciódurantlafranjaH + 1deldia3
§ El professor ( assisteix a una presentació durant la franjaH del dia 3 i noassisteixacappresentaciódurantlafranjaH + 1deldia3
( = 1, … ,';3 = 1, … , :;H = 0, … , <
Pàg.34Programaciód’horarisperalesdefensesdeTreballsdeFinaldeGrauiMàster
4.5. Restriccions
4.5.1. Restriccionsbàsiques
Pelfetdetractar-sed’unproblemad’assignaciód’horaris,hihaunasèriederestriccionsbàsiques
ques’haurandecomplirsempre,independentmentdelscriterisd’optimitzacióques’utilitzin.
1. Toteslespresentacions(")s’hand’assignaraunhorari(dia3ifranjaH).
^-,E,GJ
G78= 1
0
E78 ∀" " = 1, … , ! Restricció1
2. Elsprofessorsnoméspodenassistiraunapresentaciódurantcadafranjadecadadia.
^-,E,G · +,-,. ≤ 16
-78
∀3 3 = 1, … , :
∀H H = 1, … , <
∀( ( = 1, … ,'
Restricció2
3. Eslimitaelnombrededefensesalesquepotassistirunprofessorocupantqualsevolfigura
deltribunala<ABC.
^-,E,G · +,-,.
6
-78≤ FABC
J
G78
∀( ( = 1, … ,'
∀3 3 = 1, … , : Restricció3
4. Peranosobrecarregarelsprofessors,esrestringeixelnombredepresentacionsalesque
poden assistir enundia concret comadirector, president o vocal del tribunal (membre
titulardelprojecte).
^-,E,G · +,-,.0
6
-78≤ FTABC
J
G78
∀( ( = 1, … ,'
∀3 3 = 1, … , : Restricció4
5. Cada franja de cada dia pot tenir, com a màxim, tants projectes assignats com
presentacionsenparal·lelespermeten(=>?).
^-,E,G ≤ =>?6
-78
∀3 3 = 1, … , :
∀H H = 1, … , < Restricció5
6. Durantunamateixafranjad’undiaconcret,noméspodràpresentar-seunnombrelimitat
deprojectedecadadepartament(=@ABC).
BlancaBertranSubirana Pàg.35
^-,E,G · 12+3-,4 ≤ =@ABC6
-78
∀* * = 1, … , )
∀3 3 = 1, … , :
∀H H = 1, … , <
Restricció6
4.5.2. Restriccionsassociadesalscriterisd’optimització
Comjas’ha introduïta l’apartat4.3.1,calmodelitzar l’expressiórepresentadaa l’Equació4pera
considerar lacondicióde irregularitatde lespresentacions.Aquestaexpressiónoés lineal jaque
conté un valor absolut i una implicació i per tant, s’ha de linealitzar. Al tractar-se de variables
binàriesaquestalinealitzacióesmodelitzamésfàcilment,sensenecessitatdecrearnovesvariables
addicionals.
1. DefiniciódelavariableF.,E,G
F.,E,G = ^-,E,G · +,-,.
6
-78
∀3 3 = 1, … , :
∀H H = 1, … , <
∀( ( = 1, … ,'
Restricció7
2. ForçarquelavariableF.,E,Gsiguizeroperlesfranges0iF + 1
F.,E,X = 0
F.,E,JV8 = 0
∀3 3 = 1, … , :
∀H H = 1, … , < Restricció8
3. Linealització de l’expressió de la irregularitat (Equació 4). Aquesta variable només es
defineixperaquellsmembresqueformenpartdemésd’untribunaljaque,encasqueun
professorestiguivinculataunsoltribunal, lasevaaportacióa la irregularitattotalseria2
enqualsevolcas.
"??2T.,E,G ≥ F.,E,G − F.,E,GV8
∀3 3 = 1, … , :
∀H H = 1, … , <
∀(3b5+. > 1 ( = 1, … ,'
Restricció9
"??2T.,E,G ≥ F.,E,GV8 − F.,E,G
∀3 3 = 1, … , :
∀H H = 1, … , <
∀(3b5,. > 1 ( = 1, … ,'
Restricció10
4. Modelització matemàtica de l’expressió introduïda a l’Equació 1, que permet definir la
Pàg.36Programaciód’horarisperalesdefensesdeTreballsdeFinaldeGrauiMàster
variable1"D+.,E
F.,E,GJ
G78≤ < · c.,E
∀( ( = 1, … ,'
∀3 3 = 1, … , : Restricció11
4.6. Funcióobjectiu
4.6.1. Definició
La funció objectiu (F.O. 1) s’ha definit considerant els criteris presentats anteriorment amb la
finalitatdeminimitzarpercadascundelsprofessorsprimeramentelnombredediestotalenque
cadascund’ellshad’assistiraalmenysunapresentació,isegonamentlasevairregularitattotal.
'd! e = \8 · c.,E0
E78
f
.78+ \] · "??2T.,E,G
J
G7X
0
E78
f
.78 F.O.1
4.6.2. Pesosdelafuncióobjectiu
Quantalpesqueesdónadinsdelafuncióobjectiuacadascundelscriterisdefinits,d’entradas’ha
determinatponderarambunvalormajorelcriterideladispersió.
S’ha establert així ja que es considera que concentrar les presentacions en el mínim de dies
possibleafavoreixméspositivamentalsprofessors,sobretotquanestractadeprofessorsassociats
ques’handedesplaçarexpressamentalauniversitat.
Elcriteride la irregularitatesconsideramenyspreferent, tot iquetambéafavoreixalsmembres
quantaorganitzaciódel’agenda.
Enelcasqueunprofessorassociathagid’assistira,perexemple,6presentacions,éspreferibleque
aquestesdefensesestiguinconcentradesenunúnicdiaquenoqueestiguinentresdiesperòen
horesseguides.
A causa de que els valors de tots dos criteris són del mateix ordre de magnitud, no ha calgut
normalitzar-los. Per tant, s’ha atribuït un coeficient (\) per únicament ponderar cadascun dels
criteris.
Així, s’ha establert que el pes atorgat al criteri de la irregularitat serà 1 (\]=1), i el pes de ladispersió serà igual al nombre de dies durant els quals s’assignen les presentacions (\8 = :).D’aquesta manera es donarà més importància a aquest últim criteri com més dies durin les
BlancaBertranSubirana Pàg.37
defenses,atèsqueseriamésprobablequeelsprojectesd’unmateixprofessorsquedinrepartitsen
mésdiesdiferents.
LafuncióobjectiuponderadaquedatalicomesmostraalaF.O.2.
'd! e = : · c.,E0
E78
f
.78+ "??2T.,E,G
J
G7X
0
E78
f
.78 F.O.2
Pàg.38Programaciód’horarisperalesdefensesdeTreballsdeFinaldeGrauiMàster
5. Resolucióutilitzantunúnicprogramalineal
Enaquestcapítolesresolelmodel linealpresentatanteriormentutilitzant3 instànciesdiferents.
S’estableixen també els valors dels paràmetres definits al capítol anterior, i es presenta el
programautilitzarperaimplementariresoldreelmodel.
5.1. Valorestablertdelsparàmetres
Peraldesenvolupamentd’aquesttreballs’haestablerta8elnombredefrangesdisponiblesdurant
undiapera ferpresentacions < , considerantqueel tempsnecessaripera fer lapresentació i
defensaésd’1hora.Elnombredeprojectesquepodendefensar-sedeformaparal·leladurantuna
horad’undiaconcrets’halimitata4(=>?).
Tenintencompteaquestesduesdades,espotcalcularelnombredediesnecessarisperapoder
ferl’assignaciódels!projectes,talicomesdefineixal’expressiódel’Equació6.Esconsideracom
a coeficient de seguretat un diamés que els teòricament necessaris, per tal d’assegurar que la
resoluciódelproblemaseràfactible.
T =!
< · =>? + 1 Equació6
Considerant que les defenses es duen a termenormalment en aules pròpies dels departaments
associats al projecte i quemajoritàriament les unitats no disposen demés d’una aula d’aquest
tipus, s’ha determinat que només un projecte (=@ABC) de cada departament podrà esser
presentatdurantunafranjaconcretad’undiaconcret.
Finalment,enquantarestringirelnombredepresentacionsalesquepotassistirunprofessorcom
a titular (<:ABC)oocupantqualsevol figuradel tribunal (<ABC), s’hanestablertels límitsa5 i8,
respectivament.Perunabanda,s’haconsideratqueelsmembresnopodensobrepassarelnombre
d’horesestàndardd’unajornadalaboraldiàriaaCatalunya.Perl’altre,ambl’objectiudenosobre-
carregar els professors, s’ha delimitat a 5 el nombrededefenses a les quepoden acudir coma
titular.Així,unprofessorpotestarassignata8presentacionsdurantundiaperònomésenelcas
quehagidesubstituiraunmembretitulard’untribunalassistiràamésde5.
Cal comentar que tal i com s’handefinit els paràmetres per al desenvolupament del projecte la
Restricció3ésredundant,doncsjaeslimitaa1elnombredepresentacionsalesquepotassistir
un professor durant una franja concreta, i s’ha establert que com màxim durant un dia els
membres del tribunal poden tenir 8 presentacions (Fghi = F = 8). Així, la Restricció 2 ja inclou
BlancaBertranSubirana Pàg.39
intrínsecamentaquestalimitació.Enelcasqueesdefinísqueelnombredefrangesd’undiaésun
valordiferentalnombremàximdepresentacionsa lesqueassisteixunprofessor, laRestricció3
serianecessària.
LaTaula5.1inclouunresumdelsvalorsdetotsaquestsparàmetres.
Nombredefrangesperdia < = 8
Nombredeprojectesmàximquepodenpresentar-seenparal·lel =>? = 4
Nombredeprojectesalsquepotassistirunprofessordurantundia <ABC = 8
Nombredeprojectesalsquepotassistirunprofessorcomatitulardurantundia <:ABC = 5
Nombredeprojectesd’unmateixdepartamentquepodenpresentar-sedurantla
mateixafranja=@ABC = 1
Taula5.1Resumdelsparàmetresestablerts
5.2. SoftwareUtilitzat
Per a la implementació i posterior resoluciódelmodel s’hautilitzat el software IBM ILOGCPLEX
OptimitzationStudio3.S’haescollitaquestprogramaperquèesteniafamiliaritatambelseuúsies
coneixiaelllenguatgequeutilitzapermodelarelprogramamatemàtic.Amésestractad’unaeina
integrada que, a part d’incloure el seu propi llenguatge i optimitzadors, permet vincular els
projectesambfullsdecàlculd’Exceldesdelsqualss’importenlesdadesdelmodelienelsquees
poden escriure els resultats obtinguts de les variables. Això permet que els usuaris del model
puguinmanejar les dades i els resultats còmodament, sense necessitat d’adquirir coneixements
específicsd’unprogramaconcret,icomportatambéqueespuguiferunanàlisiiinterpretaciódela
solucióambmésfacilitat.
L’ordinadorutilitzatperafer lesexecucionsdisposad’unprocessadorde2.5GHz,undiscdurde
500Gbdememòriai8GbdememòriaRAM.
5.3. Implementacióiexecució
Pera la implementació iexecuciódelmodelpresentat, s’hanutilitzat3 instànciesdiferents reals
facilitades per la direcció de l’ETSEIB que tenen les característiques en quant a nombre de
3http://www-03.ibm.com/software/products/es/ibmilogcpleoptistud
Pàg.40Programaciód’horarisperalesdefensesdeTreballsdeFinaldeGrauiMàster
projectes,membresimplicatsenaquestsprojectes,idiesqueesresumeixenalaTaula5.2.
Taula5.2Característiquesdecadainstància
On:s’hacalculatemprantl’expressiópresentadaal’Equació6.
La magnitud del problema és significativa a causa de l’elevat nombre de dades, restriccions i
variables (veure Taula 5.3). Sabent que per aquesta dimensió dels casos el programa CPLEX
necessitamoltdetempsperatrobarlasolucióòptima,s’hadeciditlimitareltempsd’execucióper
cada joc de dades a 2 hores (7.200 segons). Veient els resultats obtinguts amb aquesta
implementacióespodràavaluarquinaés lamillormaneradeprocedir.S’analitzaràelvalorde la
funcióobjectiu,elvalordecadacriteri ielpercentatgedediscrepànciadelamillorsolucióactual
trobadarespectel’objectiualqueelprogramacreuquepotarribarconsiderantelsnodesactuals
(GAP).
Taula5.3Nombrederestriccionsivariablesdelmodelpercadajocdedades
Els resultats obtinguts després de deixar el model executant durant 2 hores són els que es
presentenalaTaula5.4,laTaula5.5i laTaula5.6.Destacal’altpercentatgequepresentaelGAP
sobretotpelque faa les instàncies1 i3.Aquest fet indicaque la solució trobadadurantaquest
tempsdistasignificativamentdefita inferiorqueelprogramaté, iquepertantnoésunresultat
proubo.
N M T
Instància1 265 289 10
Instància2 106 271 5
Instància3 341 321 12
RESTRICCIONS VARIABLES
Instància1 149.927 129.103
Instància2 56.748 49.133
Instància3 208.567 181.035
BlancaBertranSubirana Pàg.41
Taula5.4Resultatsdel’execuciódelaInstància1(Límittemps:7.200s)
Taula5.5Resultatsdel’execuciódelaInstància2(Límittemps:7.200s)
Taula5.6Resultatsdel’execuciódelaInstància2(Límittemps:7.200s)
S’observa també que la diferencia de cadascun dels criteris respecte a la fita mínima és
significativament inferiorenel casde ladispersió, fet lògic jaaque se lidonaunmajorpesa la
funcióobjectiu.
Quantaladistribuciódelsprojectesenelsdies,quedatalicomesmostraalaTaula5.7.Engeneral
el programadóna coma resultat unadistribució forçauniformedel nombredeprojectes enels
dies,sobretotenelcasdelesinstàncies1i3.
GAP 78,92% FITAINFERIOR DIFERÈNCIA
Iregularitat 2.336 448 421%
Dispersió 993 335 196%
ValorF.O. 12.266 3.798 223%
Instància1
GAP 34,12% FITAINFERIOR DIFERÈNCIA
Iregularitat 520 246 111%
Dispersió 340 274 24%
ValorF.O. 2.220 1.616 37%
Instància2
GAP 81,41% FITAINFERIOR DIFERÈNCIA
Iregularitat 3.162 538 488%
Dispersió 1.356 393 245%
ValorF.O. 19.434 5.254 270%
Instància3
Pàg.42Programaciód’horarisperalesdefensesdeTreballsdeFinaldeGrauiMàster
Taula5.7Distribuciódelsprojectesenelsdies
El fet de que les solucions trobades presentin un GAP tan elevat s’atribueix a què el programa
afronta moltes possibilitats a l’hora de fer l’assignació dels projectes. Tot i que s’han modelat
diversesrestriccions,elprogramaencarapresentaungraudellibertatprouimportantperassignar
elsprojectesenundiaiunafranjaconcreta.Amés,elproblemapossiblementtémésd’unasolució
òptima, amb els projectes assignats de diferentmanera però amb elmateix valor dedispersió i
irregularitat.Totaixòprovocaquedurantl’execució,elnombredenodesaugmenticontínuament
sensepoderdescartar-necap.
Pertaldelimitarlespossibilitatsd’assignaciódelmodelireduireltempsd’execució,esproposaun
procedimentheurísticque, considerant lesmateixes restriccionsque s’hanexplicatper almodel
matemàtic,assignaràenunaprimerapartelsprojectesendiesconcrets,ienunasegonapartse’ls
assignaràaunahoradinsdeldia.
Instància1 Instància2 Instància3N N N
Dia1 29 24 28Dia2 26 12 30Dia3 26 14 30Dia4 28 28 26Dia5 25 28 28Dia6 27 - 28Dia7 26 - 29Dia8 26 - 27Dia9 27 - 29Dia10 25 - 31Dia11 - - 28Dia12 - - 27TOTAL 265 106 341Mitjana 26,5 21,2 28,42σ 1,27 7,69 1,44
BlancaBertranSubirana Pàg.43
6. ProcedimentHeurístic
Per a poder aconseguir una solució factible del problema reduint significativament el temps
necessari en relació a la resoluciódelprograma lineal, esproposaunprocedimentheurísticque
consideraràelsmateixoscriterisques’hapresentatperelprogramamatemàticdelcapítol4.
L’heurísticaconstaràdetrespartsclaramentdiferenciades:
1. Pre-procés (dispersió): Assignació dels projectes en un dia concret, considerant les
restriccionsquesiguinnecessàriesperpoderassegurarlafactibilitatdelasolució.
2. Minimitzaciódelairregularitatdel’assignacióinicial:Assignaciódelsprojectesaunafranja
concreta del dia en el que se’ls ha assignat. Per fer-ho s’executarà una adaptació del
programa matemàtic desenvolupat inicialment per cadascun dels dies, minimitzant la
irregularitat per cadascun dels professors. Això permetrà disposar d’una solució inicial
factible.
3. Post-procés (dispersió): Millora de l’assignació inicial (etapa 1) fent canvis de projectes
entreelsdies.
4. Minimitzacióde la irregularitatde l’assignaciómillorada:Uncop realitzats les intercanvis
deprojectes,s’optimitzarànovamentlasolucióperapoderassignarelsprojectesafranges
deformaòptimaquantairregularitat.
S’avaluarà lamateixa funció objectiu que s’ha presentat al apartat anterior però el seu valor es
calcularàdeformaseparada.D’unapart,unavegadas’haginassignatelsprojectesaundiaconcret
es podrà avaluar el criteri de ladispersió delsmembres del tribunal de la solució inicial. D’altra
banda,elvalordelavariableirregularitatdelasolucióinicialescalcularàdurantlasegonapartdel
procedimentheurístic.Ambdóscriterisseranrecalculatsdesprésdemillorar lasolució inicial,a la
tercerapartdel’heurística.
En els següents apartats s’explicarà més detalladament el desenvolupament de cadascuna
d’aquestes parts. Exceptuant la part d’optimització que es realitzarà amb el software IBM ILOG
CPLEX Optimitzation Studio, l’assignació dels projectes a un dia i la millorar de la solució
s’implementaran mitjançant un programa informàtic desenvolupat amb Python que llegirà i
escriuràdadesafitxersExcel.
Pàg.44Programaciód’horarisperalesdefensesdeTreballsdeFinaldeGrauiMàster
Figura6.1Esquemadelfuncionamentdelprocedimentdesenvolupat
A la Figura 6.1 es presenta un esquema simplificat del funcionament del procediment
desenvolupat. Tal i com s’observa a la imatge, les etapes 1 i 2 permeten obtenir el valor de la
funcióobjectiud’unaprimerasolució(m).Mitjançantlesetapes3i4escalculaelvalordelafunció
objectiuperaunasoluciómillorada(n).Elfetd’obtenirelvalordelafuncióobjectiuperlessolucióm in, permet comparar-les i verificar que el procés demillora desenvolupat és efectiu.Un cop
fetes totes les proves amb diferents jocs de dades, quan s’hagi provat que el procediment
desenvolupat permet millorar la solució m, es podrà reduir l’heurística a trobar una primera
assignaciódelespresentacionsaundia(etapa1),milloraraquestaassignació(etapa3)ioptimitzar
la irregularitat (pas 4) per tenir una assignació horària òptima en quant als dos criteris definits
inicialmentperobtenirunasolución.L’optimitzaciódelasolucióinicial(pas2)noserànecessària
quanesvulguiutilitzarelprocedimentperal’assignaciódelespresentacions,sensecompararles
duessolucionsmin.
6.1. Especificacionstècniques
Com ja s’ha comentat, el programa s’implementarà utilitzant Python. S’ha escollit aquest
llenguatgeperquè,apartdesersenzilld’aprendreiutilitzar,ésdeprogramarilliure.
Perapoderexecutarelprogramadesenvolupat,caldisposardelsmòdulsespecíficsdePythonque
esdetallenala,totsellsdisponiblesdeformalliurealaxarxa
math Mòdulqueproporcionaaccésafuncionsmatemàtiques.4
4https://docs.python.org/2/library/math.html
BlancaBertranSubirana Pàg.45
string Llibreriaquepermet‘operar’ambstrings.5
copy Mòdulquepermetcrearcòpiesd’elementsimodificar-lesseparadament.6
random Mòdulquepermetgenerarvalorsaleatòriament.7
operator MòdulquepermetoperarmésfàcilmentamblesfuncionsdePython.8
openpyxl LlibreriaquepermetinteractuarambfitxersExcel.9
Taula6.1Mòdulsnecessarisperalaimplementacióiexecuciódelprogramadesenvolupat
6.2. Pre-procés:Assignaciódelsprojectesaundiaconcret
6.2.1. Objectiu
L’objectiud’aquestapartdelprocésésferunaprimeraassignaciódelsprojectesaundiaconcret
pertaldefacilitarlaposteriorassignacióhoràriadinsdeldiamitjançantoptimització.
L’assignaciódelsprojectesaundia concretes faràafavorintque lesdefensesd’undepartament
estiguin concentrades en els mateixos dies. En general, els projectes que formen part d’un
departament concret poden tenir membres del tribunal en comú. Així, el fet d’assignar les
presentacionsd’undepartamentagrupadesenelsdiesafavoreixaminimitzartantladispersiócom
lairregularitat.
Per fer-ho, s’ha desenvolupat un programa que primer de tot llegeix les dades de partida d’un
fitxerformatExcel.Uncopdisposadelacomposiciódelsmembresdecadascundelsprojectes,així
comdeldepartamentassociatacadascund’ellselprogramaassignaelsprojectesaundiaconcret
segons el procediment que s’explicarà en apartats posteriors. Finalment, el programa escriu les
dadesalfitxerExcelseparadesperdiesiestructuradesdemaneraquesiguinllegiblespelprograma
IBMILOGCPLEXOptimitzationStudio.LaFigura6.2representaesquemàticamentelpre-procés,on
lesentradescorresponenalesdadesllegidesdelfitxerExceliaunaestructuradedadesbuidaon
5https://docs.python.org/2/library/string.html6https://docs.python.org/2/library/copy.html7https://docs.python.org/2/library/random.html8https://docs.python.org/2/library/operator.html9https://openpyxl.readthedocs.io/en/default/
Pàg.46Programaciód’horarisperalesdefensesdeTreballsdeFinaldeGrauiMàster
s’anirà afegint informació dels projectes assignats a cada dia, el procediment correspon amb el
procésd’assignarelsprojectesaundia, i lasortidaamb l’estructuradedadesamb l’assignacióa
partirdelaqualespotcalcularelvalordelaDispersióiambelsfitxersgeneratsquealimentenel
CPLEX.
Figura6.2Esquemabàsicdel’etapadelpre-procés
6.2.2. Entrades
Eldetalldelprogramainformàtic implementatpera llegir lesdades inicials icrear l’estructurade
dadesons’inclouràl’assignacióespotconsultaral’Annex3.
6.2.2.1. LecturaInicialdeDades
Elprimerquefaelprogramadesenvolupatés llegir lesdades inicialsde lesqueesdisposa.Pera
poder-lesllegir,elfitxerhadeserExcelenformat.xlsx,lesdadeshand’estaralaprimerapestanya
delfitxeriordenadestalicoms’observaalaFigura6.3.
Figura6.3DisposicióencolumnesquehandetenirlesdadesenelfitxerExcelqueesllegeix
El programa emmagatzema les dades en estructures de dades pròpies de Python anomenades
Diccionaris,queemmagatzemenparaulesclauivalorspercadascunad’aquestesparaulesclau.
Quanelprogramallegeixlesdadesinicialsesgenerentresdiccionaris:
=?o( Emmagatzemapercadaprojecteelsprofessorsqueformenpartdelseutribunal
=?o(:"3 Contépercadaprojecteelsprofessorsquesónmembrestitularsdelseutribunal
@2+D Llistaelsprojectesdecadadepartament
A B C D E F G H I J
PROJECTE DEP Director Codirector Ponent President Vocal Unitat Vocal extern Vocal suplent Unitat
Vocal suplent extern
PROJ 1 CITCEA 2L G2M 3C SÁN S S53N 2L G2M 2N3 S2 M4N4G3 D2L2RSPROJ 32 EE 4P 5ND 2N3 S1 34L M2 2N3 S1 R2 C5M N 5NT2 14L V4
BlancaBertranSubirana Pàg.47
Siguin:
+- " = 1, … , ! Projecte"dels!aassignar
:p:- = +,-,.
f
.78
" = 1, … , ! Nombretotaldemembresdeltribunaldelprojecte"
:p:- serà:
- 5:peralamajoriadeTFGs
- 6:peralamajoriadeTFMsiperelsTFGsque
estiguinco-dirigitsoquetinguinponent
- 7:peralsTFMsqueestiguinco-dirigitsoque
tinguinponent
:p:0- = +,0-,.
f
.78
" = 1, … , ! Nombretotaldemembrestitularsdeltribunaldel
projecte"
:p:0- serà:
- 3:peralamajoriadeTFGs
- 4:peralamajoriadeTFMsiperelsTFGsque
estiguinco-dirigitsoquetinguinponent
- 5:peralsTFMsqueestiguinco-dirigitsoque
tinguinponent
,. ( = 1, … ,' Membre(dels'queformapartd’undelstribunals
d’algunadelespresentacions
,0. ( = 1, … ,' Membretitular(dels'queformapartd’undels
tribunalsd’algunadelespresentacions
12+4 * = 1,… , ) Departament*dels)quehihaentotal
:p:4 = 12+3-,46
-78
* = 1,… , ) Nombretotaldeprojectesdeldepartament*
L’estructura dels diccionaris d’entrada al procediment heurístic és tal i com es mostra a
continuació:
Pàg.48Programaciód’horarisperalesdefensesdeTreballsdeFinaldeGrauiMàster
=?o( =+8: ,8,,], … ,,., … ,,0r0s , … , +-: ,8,,], … ,,., … ,,0r0t , … ,
+6: ,8,,], … ,,., … ,,0r0u
=?o(:"3 =+8: ,08, … ,,0., … ,,0r0vs , … , +-: ,08, … ,,0., … ,,0r0vt , … ,
+6: ,08, … ,,0., … ,,0r0vu
@2+D =
12+8: :p:8, +8, … , +-, … , +0r0s , … ,
12+4: :p:4, +8, … , +-, … , +0r0w , … ,
12+x: :p:x, +8, … , +-, … , +0r0y
6.2.2.2. Estructuradedadesons’inclouràl’assignació
Elprocedimentheurísticparteixdelesdadesllegidesinicialment,id’unnoudiccionari(@"2D)quees genera en funció del nombre de dies que seran necessaris per a fer l’assignació, calculat
utilitzant l’expressiópresentadaa l’Equació 6, i queemmagatzemadiferentsdadesdelsprojectes
assignatsacadascundelsdies.
Siguin:
@">E 3 = 1, … , : Dia3dels:alsqualss’assignaranpresentacions
5*,=?o(E 3 = 1, … , : Nombretotaldeprojectesassignatsaldia3
1:p:E 3 = 1, … , : Nombretotaldedepartamentsimplicatsenelsprojectes
assignatsaldia3
:p:4,E * = 1,… , )
3 = 1, … , :
Nombretotaldeprojectesdeldepartament*assignatsaldia3
,:p:E 3 = 1, … , : Nombretotaldeprofessorsimplicatsenelstribunalsdels
projectesassignatsaldia3
,:p:0E 3 = 1, … , : Nombretotaldeprofessorstitularsimplicatsenelstribunalsdels
projectesassignatsaldia3
5+.,E ( = 1, … ,'
3 = 1, … , :
Nombretotaldepresentacionsalesquehad’assistirelprofessor
(duranteldia3
5+:.,E ( = 1, … ,' Nombretotaldepresentacionsalesquehad’assistirelprofessor
BlancaBertranSubirana Pàg.49
3 = 1, … , : (comatitularduranteldia3
L’estructuradeldiccionari@"2Ddinslaquals’aniranafegintelsprojectesaldiaonse’lsassigni,éstalicomesmostratotseguit:
@"2D =
@">8:5*,=?o(8,
12+8: :p:8,8, +8, … , +0r0s,s , … ,
12+z0r0s: :p:z0r0s,8, +8, … , +0r0{v|vs,s,
,8: 5+8,8, … ,,A0r0s: 5+A0r0s,8 ,,08: 5+:8,8, … ,,A0r0vs: 5+:A0r0vs,8
, … ,
@">E:5*,=?o(E,
12+8: :p:8,E, +8, … , +0r0},s , … ,
12+z0r0}: :p:z0r0},E, +8, … , +0r0{v|v},},
,8: 5+8,E, … ,,A0r0}: 5+A0r0s,E ,,08: 5+:8,E, … ,,A0r0v}: 5+:A0r0v},E
, … ,
@">0:5*,=?o(0,
12+8: :p:8,0, +8, … , +0r0s,v , … ,
12+z0r0v: :p:z0r0v,0, +8, … , +0r0{v|vv,v,
,8: 5+8,0, … ,,A0r0v: 5+A0r0v,0 ,{,08: 5+:8,0, … ,,A0r0vv: 5+:A0r0vv,0}
6.2.3. ProcedimentHeurístic:assignaciódelsprojectesadies
6.2.3.1. ALGORISME1
Comjas’hacomentatanteriorment, l’assignacióesfaràperdepartaments,començantperelque
té més projectes assignats, per tal d’afavorir que les presentacions dels membres del tribunal
quedinconcentradesenelsmateixosdies.Esdescriuacontinuacióelprocedimentdesenvolupat.
P0. Seleccionarelprimerdia(@">E = @">8)P1. Ordenarelsdepartamentsenordredecreixentsegonselnombredeprojectesassociats
P2. Seleccionareldepartament(12+4)quetinguimajornombredeprojectes
Encasd’empat:
i) Escollireldepartamentqueimpliquiamésprofessorsentotal
Encasd’empat:
ii) Escollireldepartamentquecontinguielprofessorimplicatamésprojectes
Encasd’empat:
iii) Escollireldepartamentperordrealfabètic
P3. Nombredeprojectesdeldepartamentescollit::p:4P3.1. Si:p:4 > <:SeleccionarÄ = <projectesaleatòriament
Pàg.50Programaciód’horarisperalesdefensesdeTreballsdeFinaldeGrauiMàster
P3.2. Si:p:4 = <:seleccionarelsÄ = :p:4projectesP4. Siéspossible(ALGORISME2)assignarelsÄprojectesaldia3:
§ AssignarelsÄprojectesaldia3§ EliminarelsÄprojectesdelesllistes=?o(,=?o(:"3i@2+D§ :p:4 = :p:4 − ħ Passaralsegüentdia(@">EV8)P4.1. Si:p:4 > 0:
§ TornaraP2
P4.2. Altrament:
P4.2.1. Siquedenprojectesalallista=?o(:§ TornaraP1
P4.2.2. Altrament(sinoquedenprojectesalallista=?o():§ FI:s’hanassignattotselsprojectes
P5. Altrament(sinoéspossible):
§ EliminaraleatòriamentundelsÄprojectes§ TornaraP3(3tornaràaser@">E)
A la Figura 6.4 es mostra un diagrama de flux del procediment descrit per a fer una primera
assignaciódiàriadelsprojectes.Eldetalldelprogramainformàticdesenvolupatespotconsultara
l’Annex4.
BlancaBertranSubirana Pàg.51
Figura6.4DiagramadeFluxdelprocedimentques’utilitzaperassignarelsprojectesaundiaconcret
ALGORISME1
INICI
Proj – Llistat demembres decadaprojecte
ProjTit – Llistat demembres titurlars decadaprojecte
Deps– Llistat dedepartaments
Dies– Diccionari on s’aniràn incloent els projectes aldia on s’hagin assignat
Seleccionar depu tqmax(TOTu)
TOTu≥ F ?
Seleccionar b=Fprojectesaleatoriament
si
noSeleccionar els b=TOTu projectes
ALGORISME2Espossible
assignar els bprojectes aDiat ?
Seleccionar primerdia Diat=Dia1(t=1)
si
no
Assignar els projectes alDiat dins DiesEliminarels projectes deProj,ProjTit ideDeps
TOTu =TOTu – bPassar alsegüent dia (d=dt+1)
TOTu= 0 ?
si
no
Quedenprojectesalallista Proj ?
si
no
FI
Eliminaraleatoriament unprojecte delsescollits (b=b-1)
FUNCIÓGRUPS2
Ordenarels departaments perordredecreixent deprojectes associats
Pàg.52Programaciód’horarisperalesdefensesdeTreballsdeFinaldeGrauiMàster
6.2.3.2. ALGORISME2
EnelspassosP4iP5del’algorisme1,quanescomprovasiéspossibleassignarelsÄprojectesaldia@">E,elqueesfaésassegurarqueescompleixenlesrestriccionsdelmodelmatemàticquefan
referènciaaundiaconcret(Restricció3-Restricció6),pertaldegarantirquelasolucióobtinguda
amb el procediment heurístic és comparable a la que s’obtindria si es resolgués el model
matemàticsencer.Totseguitesdescriumésdetalladamentl’algorisme2,quedeterminasiésono
éspossibleassignarelsÄprojectes.
Siguin:
=?o(Å>51"1>3D LlistadelsÄprojectes(associatsaldepartament12+)ques’intentenassignarconjuntament
,2,Ä?2D Llistatdemembres(()queformenpartdelstribunalsdelsÄ=?o(Å>51"1>3D
5'2, NombretotaldemembresqueformenpartdelstribunalsdelsÄ=?o(Å>51"1>3D
,2,Ä?2D0 Llistatdemembres(()titularsqueformenpartdelstribunalsdelsÄ=?o(Å>51"1>3D
5'2,: NombretotaldemembresqueformenpartdelstribunalsdelsÄ=?o(Å>51"1>3Dcomatitulars
:p:. ( = 1, … , 5'2, NombredepresentacionsdelsÄprojectesalesquehad’assistirelprofessor(
::p:. ( = 1, … , 5:'2, NombredepresentacionsdelsÄprojectesalesquehad’assistirelprofessor(comatitular
Elprogramacomprovaràsiéspossibleassignarelsprojectesaldia@">E i,denoserpossible,hocomprovaràambelsegüentdiafinsahaver-hointentatambtotsells.
P0. Posarazeroelcomptador,perdeterminarsis’haprovatambtotselsdies(co,+3>1o? =0)
P1. co,+3>1o? < :(nos’haprovatd’assignarelsÄprojectesatotselsdies)P1.1. Comprovarlimitaciódeprojectesenundia(@">E):
P1.1.1. Si < · =>? − 5*,=?o(E ≤ Ä:§ PassaraP1.2
P1.1.2. Altrament < · =>? − 5*,=?o(E > Ä:
BlancaBertranSubirana Pàg.53
§ Passaralsegüentdia(@">EV8)§ TornaraP1
P1.2. Comprovarlimitaciódeprojectesd’unmateixdepartament:
P1.2.1. Si < · =@ABC − :p:4,E ≤ Ä:§ PassaraP1.3
P1.2.2. Altrament < · =@ABC − :p:4,E > Ä:§ Passaralsegüentdia(@">EV8)§ TornaraP1
P1.3. Comprovarlimitaciódeprojectespels5'2,membresdinsde,2,Ä?2D:P1.3.1. Si<ABC − 5+.,E ≤ :p:. ∀(:
§ PassaraP1.4
P1.3.2. Altrament∃( ∈ 1, … , 5'2, :<ABC − 5+.,E > :p:.:§ Passaralsegüentdia(@">EV8)§ TornaraP1
P1.4. Comprovarlimitaciódeprojectespels5'2,:membresdinsde,2,Ä?2D0:P1.4.1. Si<:ABC − 5+:.,E ≤ ::p:.∀(:
§ FI:RetornaPOSSIBLE(éspossibleassignarelsÄprojectesaldia1)P1.4.2. Altrament∃( ∈ 1, … , 5'2,: :<:ABC − 5+:.,E > ::p:.:
§ Passaralsegüentdia(@">EV8)§ TornaraP1
P2. Altrament(co,+3>1o? = 5*,@"2D)§ FI:RetornaNOPOSSIBLE(noéspossibleassignarelsÄprojectesaldia1)
ElpuntP1.1permetgarantirelcomplimentdelaRestricció5(presentadaal’apartat4.5.1),elpunt
P1.2assegura la factibilitatde laRestricció 6,que restringeixelnombredeprojectesd’unmateix
departament que poden presentar-se durant la mateixa franja a=@ABC. Els passos P1.3 i P1.4assegurenelcomplimentdelaRestricció3ilaRestricció4,respectivament.Nomésenelcasquees
compleixintoteslesrestriccionsalafegirelsÄprojectesal@">Eesdiràqueéspossibleassignar-los.
AlaFigura6.5esrepresentaenformadediagramadefluxunesquemasobrelapartdelprograma
quecomprovasiéspossiblel’assignaciódelsprojectesaundiaconcret.L’Annex4incloueldetall
delprogramainformàticimplementat.
Pàg.54Programaciód’horarisperalesdefensesdeTreballsdeFinaldeGrauiMàster
Figura6.5DiagramadeFluxdelprocésperdeterminarsiésonoéspossibleassignarÄprojectesaldia1
Resumidament,elprocediment(Algorisme1iAlgorisme2)permetassignarlespresentacionsper
departament,començantpelquetémésprojectes,iperfer-hocomprovasiéspossibleassignar-ne
unblocaundiaconcret.Encasquenosiguipossible,hoprovaambeldiasegüentfinsaprovar-ho
amb tots els dies. Si no és possible assignar-los en cap del dies, el programa elimina un dels
projectes del bloc i ho torna a provar. Així successivament fins que troba un bloc de projectes
possiblesd’assignaraundia.
Un cop finalitzat aquest procés, es disposarà de la programació diària dels projectes continguda
dinseldiccionari@"2D.
Diat - DiaProjCandidats - Llistat dels b projectes
membres- Llistat demembres quecomponenels tribunals dels bprojectesmembresT - Llistat demembres titulars quecomponenels tribuanls dels bprojectes
comptador =0
comptador <T ?
si
noFI:NOpossible
(F·Par)-numProjt ≤ ??
si
Passaralsegüent dia (Diat=Diat+1)comptador =comptador +1
no
(F·PDmax)-CDCE,G ≤ ??
si
no
Percadascundels membres
HIJK − MNO,G ≤ CDCO i
HCIJK − MNCO,G ≤ CCDCO?
si
no
FI:SIpossible
ALGORISME2
INICI
BlancaBertranSubirana Pàg.55
6.2.4. Sortides
Eldetalldelprogramainformàticdesenvolupatqueincloulesfuncionsqueesdescriuranenaquest
apartatespotconsultaralsAnnexos3i4.
6.2.5. Càlculdelvalordelavariabledispersió
Uncops’haginassignatlespresentacionsaundiaconcretespotcalculardirectamentelvalordela
dispersiópercadascundelsprofessors,aplicantl’Equació2:
@"D+. = 1"D+.,E0E78 ∀(
D’aquesta manera es disposa de la primera part de la funció objectiu. El valor de l’altra part
(irregularitat)escalcularàquans’optimitziaquestcriteripercadascundelsdies,alasegüentetapa
del’algorisme.
6.2.6. GeneraciódelsfitxersdedadespelCPLEX
Per tal de facilitar la introducció de la informació al programa d’optimització IBM ILOG CPLEX
Optimitzation Studio, s’estructuraran les dades obtingudes a partir del programa informàtic
desenvolupatenunfitxerExcel iesgeneraranfitxersformat.datquepermetenenllaçarelCPLEX
amblesdadesdelfitxerExcel.
Dinsdelmateixfitxerdelqual inicialments’han llegit lesdades,esgeneraranduespestanyesper
cadascun dels dies (3) als quals s’han assignat projectes, una amb la informació que alimenta el
CPLEX(PREt),iunaaltraons’escriuranelsresultatsgeneratsdesprésdel’optimització(POSTt).
Lesdadesques’inclouranalapestanyaPREtsónlessegüents:
! " = 1, … , ! Nombretotaldeprojectesqueespresentenduranteldiat
' ( = 1, … ,'Nombre total de membres del PDI que formen part d’algun dels
tribunalsdelsprojectesassignatsaldiat
) * = 1,… , ) Nombrededepartamentsalsqualsestanassociatselsprojectesdeldiat
< H = 1, … , <Nombre de franges que conformen un dia, considerant que el temps
totaldestinatacadascunadelespresentacionsidefensesésde1hora
=>? -Nombre de projectes que es poden presentar en paral·lel durant una
mateixafranja,endiferentsaules
+,-,. Matriuqueindicasielprofessor(ésmembredeltribunaldelprojecte"deldiat
Pàg.56Programaciód’horarisperalesdefensesdeTreballsdeFinaldeGrauiMàster
5+. Vectorqueindicaelnombredetribunalsdeprojectesdelsqualsformapartcadascundelsmembres(representantqualsevoldelesfigurespossiblesduranteldiat
12+3-,4 Matriuqueindicasielprojecte"estàassignataldepartament*
A lapestanyaPOSTts’hiescriurà informacióquepermetràvisualotzarmésfàcilmentelsresultats
obtingutsuncopexecutatelmodeld’optimització.
6.3. Minimitzaciódelairregularitatdel’assignacióinicial
6.3.1. Objectiu
L’objectiud’aquestapartdelprocedimentheurísticésdeterminarunahoraconcretaperaferles
presentacionsdinsdeldiaquese’lshaassignatdurantelpre-procés.
Es descriurà unmodel matemàtic adaptat del que s’ha descrit al capítol 4 que s’executarà per
cadascundelsdiespertald’obtenirunasolucióòptimaenquantairregularitatdelsprofessorsque
assisteixen a presentacions durant aquell dia. L’Annex 2 inclou aquest model implementat en
CPLEX.
6.3.2. Dades
Lesdadesquealimentenelmodelsónadaptadesde lesques’hanpresentatperalmodel inicial,
doncs les que fan referència a undia concret ara no sonnecessàries ja queelmodel es resol a
nivell de dia. Tot i això, les restriccions associades a aquestes dades (com limitar el nombre de
presentacionsperelsmembresengeneral<ABCiperelsmembrescomatitulars<:ABC)jas’hantingut en compte a l’hora de fer l’assignació als dies. Tampoc serà necessària la matriu que
determina si un professors és membre titular d’un projecte, doncs la restricció associada als
membrestitularsjas’haconsideratalafaseanterior.
! " = 1, … , ! Nombretotaldeprojectesqueespresentenduranteldiat
' ( = 1, … ,'Nombre total de membres del PDI que formen part d’algun dels
tribunalsdelsprojectesassignatsaldiat
) * = 1,… , ) Nombrededepartamentsalsqualsestanassociatselsprojectesdeldiat
< H = 1, … , <Nombre de franges que conformen un dia, considerant que el temps
totaldestinatacadascunadelespresentacionsidefensesésde1hora
=>? -Nombre de projectes que es poden presentar en paral·lel durant una
mateixafranja,endiferentsaules
BlancaBertranSubirana Pàg.57
=@ABC -Nombredeprojectesd’unmateixdepartamentquepodenassignar-se
enunamateixafranja
+,-,. " = 1, … , !( = 1, … ,'
Matriuqueindicasielprofessor(ésmembredeltribunaldelprojecte"
5+. ( = 1, … ,' Vectorqueindicaelnombredetribunalsdeprojectesdelsqualsformapart cadascun dels membres ( representant qualsevol de les figurespossibles
12+3-,4 " = 1, … , !* = 1,… , )
Matriuqueindicasielprojecte"formapartdeldepartament*
6.3.3. Variables
Enquant a les variables, també s’hanhagut d’adaptar i s’han reduït en unadimensió, eliminant
aquella que feia referència als dies. Com ja s’ha comentat, les variable que fa referència a la
dispersiódecadamembre ( per cadadia3 (1"D+.,E)noes consideraranenaquestmodel,doncs
estandefinidesperdia.Elseuvalorescalculaforad’aquestprogramalineal.
^-,GVariablebinàriaqueval1silapresentaciódelprojecte"s’assignaalafranjaH
" = 1, … , !;H = 1, … , <
"??2T.,GVariablebinàriaqueval1si:
§ El professor ( no assisteix a cap presentació durant la franja H i si queassisteixaunapresentaciódurantlafranjaH + 1
§ Elprofessor ( assisteixaunapresentaciódurant la franjaH inoassisteixacappresentaciódurantlafranjaH + 1
( = 1, … ,';H = 0, … , <
F.,GVariablebinàriaque val 1 si el professor ( assisteix aunapresentacióprogramada
durantlafranjaH
( = 1, … ,';H = 0, … , < + 1
6.3.4. Restriccions
Enreferènciaalesrestriccions,s’hanmodificatperalimitar-lesalaresoluciód’unúnicdia,is’han
eliminataquellesquejanoerennecessàries.
Pàg.58Programaciód’horarisperalesdefensesdeTreballsdeFinaldeGrauiMàster
^-,GJ
G78= 1 ∀" " = 1, … , ! Restricció12
^-,G · +,-,. ≤ 16
-78
∀H H = 1, … , <
∀( ( = 1, … ,' Restricció13
^-,G ≤ =>?6
-78 ∀H H = 1, … , < Restricció14
^-,G · 12+3-,4 ≤ =@ABC6
-78
∀* * = 1, … , )
∀H H = 1, … , < Restricció15
F.,G = ^-,G · +,-,.
6
-78
∀H H = 1, … , <
∀( ( = 1, … ,' Restricció16
"??2T.,G ≥ F.,G − F.,GV8∀H H = 1, … , <
∀(3b5,. > 1 ( = 1, … ,' Restricció17
"??2T.,G ≥ F.,GV8 − F.,G∀H H = 1, … , <
∀(3b5,. > 1 ( = 1, … ,' Restricció18
F.,X = 0
F.,JV8 = 0
∀3 3 = 1, … , :
∀H H = 1, … , < Restricció19
6.3.5. Funcióobjectiu
Finalment,pelquefaalafuncióobjectiu,s’haeliminatlapartqueavaluaelcriterideladispersió,
doncs el valor d’aquesta variable es calcula en funció dels dies on està previst que assisteixi a
presentacionscadamembredels tribunals,noestà referenciadaa leshoresconcretesenquèes
programenlesdefenses.
'd! e = "??2T.,GJ
G7X
f
A78 F.O.3
BlancaBertranSubirana Pàg.59
6.3.6. Tempsd’execuciódelmodel
A causa de la naturalesa de les dades, en alguns casos trobar la solució òptima pot implicar
executarelmodeldurantmésdediverseshores,itenintencomptequeundelsobjectiusd’aquest
procediment heurístic és reduir significativament el temps d’execució general fins a trobar una
solució factible prou bona, en aquest apartat es discutirà el temps al que es limitaran les
execucionsdelmodelpercadadia.Aquestlímitdetempss’utilitzaràtantperlesexecucionsquees
faranperobtenir lasolució inicialpercada jocdedades(etapa2),comper l’optimitzacióquees
duràatermedesprésdemillorarlasolucióinicial(etapa4).
Peradeterminaraquesttemps,s’hanexecutat5instànciesdiferentsamblimitacionsdetempsa2
minuts,5minuts i10minuts.Decada instàncias’haestudiatelvalorde la irregularitat, ielGAP
obtingutuncopexhauriteltemps.
Les instàncies tenen lescaracterístiquesqueespresentena laTaula6.2.Apartirdelnombrede
professorsqueassisteixenamésd’unapresentacióeneldiaques’optimitza,espotcalcularlacota
mínimadelcriteriirregularitat,talicoms’haexplicatanteriormental’Equació5.
Taula6.2Característiquesdelsparàmetresifitamínimadecadainstància
AlaTaula6.3espresentenelsresultatsdesprésd’executarles5instàncieslimitanteltempsa2,5i
10minuts.Percadalimitaciódetemps,escalculaelvalordelairregularitatielGAPmitjans.
Taula6.3ResultatsdelvalordelaIrregularitatidelGAPenfunciódeltempsd’execució
Comésevident,tantelvalordelairregularitatcomelGAPdisminueixenquans’augmentaeltemps
N M j tqnmj>1FitaMínimaIrregularitat
Dia2 Instància1 25 73 32 64Dia1 Instància2 29 78 37 74Dia4 Instància3 32 91 43 86Dia5 Instància4 32 93 35 70Dia3 Instància5 32 100 37 74
IRREG GAP IRREG GAP IRREG GAP
Instància1 74 17,64% 74 13,49% 74 10,66%Instància2 104 32,55% 102 27,16% 102 24,37%Instància3 112 29,61% 112 23,95% 110 19,05%Instància4 92 29,12% 88 22,30% 88 19,77%Instància5 98 30,23% 98 26,09% 98 23,36%
96 27,83% 94,8 22,60% 94,4 19,44%
5min 10min2min
Pàg.60Programaciód’horarisperalesdefensesdeTreballsdeFinaldeGrauiMàster
d’execució.Totiaixò,lamilloraquerepresentalamitjanadelairregularitatésrelativa,doncsen
valorabsolutmilloranomésen1,6puntsquanespassade limitar l’execucióde2a10minuts.A
més,en2dels5casoslairregularitatnocanvia.
Cal teniren comptequeel valord’aquest criteri és secundari,doncs coms’hadefinit a l’apartat
4.6.2elpesatorgatalairregularitatéssignificativamentinferiralquetéladispersió.Amés,ellímit
establert pot ser modificat per el responsable de fer la programació de les presentacions si
consideraquealgunaltrevalorseriamésadequat.
Pertotaixò,ijaqueundelsobjectiusésdisminuireltempsd’execuciótotaldelprocediment,s’ha
deciditposarlalimitacióa2minuts.
6.4. Post-procés:Milloradelasolució
6.4.1. Objectiu
Aquestaúltimapartdel’algorismeheurísticpreténmillorarlasolucióinicial(generadaapartirdel
pre-procésil’optimització)mitjançantcanvisqueafavoreixennotablementelcriterideladispersió.
Els canvis impliquen moviments entre dies dels projectes, i es faran en un funció d’un nou
concepte anomenat càrrega. En següents apartats s’explicarà què és i comes calcula la càrrega
d’unprojecte.
Un cop realitzats els canvis necessaris, es tornarà a executar elmodelmatemàtic per a assignar
novament els projectes a una hora concreta, i s’avaluarà una altra vegada la funció objectiu,
consideranttantladispersiócomlairregularitat.
6.4.2. Càrrega
La càrrega és un paràmetre associat a cada projecte que es calcula en funció del nombre de
presentacions a les que han d’assistir els membres del tribunal d’aquell projecte durant el dia
assignatperaferladefensadelprojecteenqüestió.
Siguinelssegüentsparàmetres:
5+.,E Nombredeprojectesalsqueassisteixelmembre(duranteldia3
:p:- Nombretotaldemembresassociatsaltribunaldelprojecte"
BlancaBertranSubirana Pàg.61
A l’Equació 7 es presenta l’expressiómatemàtica que permet definir el càlcul de la càrregaper
cadascundelsprojectes.
cà??2T>-,E =5+.,E.
:p:- ∀( ∈tribunal": ^-,G ≥G 1 Equació7
A laTaula3.1es representaunexempledel càlculd’aquestparàmetreperun jocdedadesque
inclou5projectesdiferentsi15membresassociatsalsseustribunals.
Taula6.4Exempledelcàlculdelacàrregai,tdonatundiat
6.4.3. Procedimentheurísticdemilloradelasolució
S’ha desenvolupat un programa informàtic ambPython que, partint de l’assignació inicial de les
presentacionsendies i d’altresdadesde lesqueesdisposa inicialment, i considerant lacàrrega
delsprojectes,elsre-ubicaambl’objectiudemillorarglobalmentaquestparàmetre.
Millorar la càrrega implica augmentar per cada projecte el sumatori 5+.,E. , cosa que suposa
també una millora en el criteri dispersió que s’avalua a la funció objectiu. En quant al criteri
Projecte1 Projecte2 Projecte3 Projecte4 Projecte5
Membre1 x x x 3
Membre2 x 1
Membre3 x x 2
Membre4 x 1
Membre5 x 1
Membre6 x x 2
Membre7 x x 2
Membre8 x x 2
Membre9 x 1
Membre10 x x x 3
Membre11 x 1
Membre12 x x x 3
Membre13 x 1
Membre14 x x 2
Membre15 x x 2
12 10 11 9 15
6 5 5 5 6
2 2 2,2 1,8 2,5
!"#,%
&'&(
)à++,-.(,%
/!"#,%#
Pàg.62Programaciód’horarisperalesdefensesdeTreballsdeFinaldeGrauiMàster
irregularitat,semblalògicpensarquetambémilloraràdesprésderealitzarelscanvisnecessaris.
Els diccionaris =?o(, =?o(:"3 i @2+D definits a l’apartat 6.2.2 seran dades que alimentaran el
programa,juntamentambl’assignacióinicialqueestàrecollidadinseldiccionari@"2D,ielnombre
de canvis que es volen realitzar (5Å>5á"D). Cada canvi nou que s’intenti fer es farà per aquellprojectequetinguicàrregamínima.Encasquenosiguipossiblecanviaraquellprojecte,s’afegiràa
la llista de denegats i es provarà amb el següent que tingui càrregamínima en un cert dia. Així
successivament fins que sigui possible fer un canvi, quan es buidarà la llista de denegats i es
tornaràacomençarelprocés.
Encasqueesvulguinrealitzarelmàximnombredecanvispossibles,caldràintroduirun5Å>5á"Delevat(500perexemple).Elprogramas’aturauncophagifettotselscanvispossibles,encaraque
siguinmenysqueelsintroduïts.
L’output del programa serà el diccionari @"2D amb la nova assignació dels projectes un cop
realitzatselscanvis.
S’especificaacontinuacióelprocésdesenvolupatperlamilloradelasolució,queesrepresentaen
formadediagramadefluxalaFigura6.6.L’Annex4detallaelprogramainformàticdesenvolupat
peramillorarlasolució.
P0. Posar a zero el comptador que suma el nombre de canvis que s’han realitzat
(co,+3>1o? = 0)P1. Calcularlacà??2T>-,Edetotselsprojectes(")ipertotselsdies(3)P2. Seleccionarelprojectequetinguicà??2T>-,Emínima(projecteassignatal@">E)
Encasd’empat:
i) Seleccionarelprojecte"quepertanyaldepartamentambmenornombredeprojectes
Encasd’empat:
ii) Seleccionarelprojecte"quetindriacàrregamàximauncopcanviataqualsevoldia
Encasd’empat:
iii) Seleccionarelprimerprojecteperordrealfabètic
P3. Calcular la càrrega que tindria el projecte " si es mogués a qualsevol dels altres dies
(@">Eà ≠ @">E)P4. Seleccionar el dia@">Eà corresponent a la càrregamàxima si esmogués el projecte " a
aquestdia
P5.1. Siéspossiblecanviardirectamentelprojecte"del@">Eal@">Eà:§ Treureelprojecte"deldia@">E§ Posarelprojecte"aldia@">Eৠco,+3>1o? = co,+3>1o? + 1
BlancaBertranSubirana Pàg.63
§ Buidarlallistadenegats
P5.1.1. Sinos’hanfettotselscanvis(co,+3>1o? < 5Å>5á"s):§ TornaraP1
P5.1.2. Altrament(co,+3>1o? = 5Å>5á"D):§ FI:s’hanfettotselscanvis
P5.2. Altrament(noéspossiblecanviarelprojecte"del@">Eal@">Eà):§ PassaraP6
P6. Seleccionarelprojecte"′assignatinicialmentaldia@">Eàquetinguicàrregamínima(Encas
d’empats’apliquenelsmateixoscriterisquealpasP2)
P7.1. Siéspossibleintercanviarelprojecte"pelprojecte"′:P7.1.1. Similloralacàrregadesprésdelscanvis
cà??2T>-,E + cà??2T>-ã,Eã < cà??2T>-,Eà + cà??2T>-ã,E:§ Treureelprojecte"de@">Eiposar-loa@">EৠTreureelprojecte"′de@">Eàiposar-loa@">E§ co,+3>1o? = co,+3>1o? + 1§ Buidarlallistadenegats
P7.1.1.1. Sinos’hanfettotselscanvis(co,+3>1o? < 5Å>5á"s):§ TornaraP1
P7.1.1.2. Altrament(co,+3>1o? = 5Å>5á"D):§ FI:s’hanfettotselscanvis
P7.1.2. Altrament(nomilloralacàrregadesprésdelscanvis)
cà??2T>-,E + cà??2T>-ã,Eã ≥ cà??2T>-,Eà + cà??2T>-ã,E:§ PassaraP8.1
P7.2. Altrament(noéspossibleintercanviarelprojecte"pelprojecte"′):§ PassaraP8.1
P8.1. Sis’haprovatelcanviambtotselsdies(∀3′ ≠ 3):§ Afegirprojecteadenegats
P8.1.1. Sijas’handenegattotselsprojectes:§ FI:jas’hanfettotselscanvispossibles
P8.1.2. Altrament(nos’handenegattotselsprojectes):
§ TornaraP2
P8.2. Altrament(nos’haprovatelcanviambtotselsdies):
§ Passaralsegüentdia(@">Eà)talqueelprojecte"tindriacàrregamàxima
§ TornaraP5.1
Pàg.64Programaciód’horarisperalesdefensesdeTreballsdeFinaldeGrauiMàster
Figura6.6DiagramadeFluxdelprocésdemilloradelasolució
De forma similar a la comprovació que es feia a l’hora d’assignar les presentacions a un dia, en
aquest algorisme també es comprova, en quant al compliment de les restriccions, si és possible
canviarunprojecteaunaltrediaointercanviardosprojectes(veureapartat0).
INICI
numCanvis - Nombredecanvis queesvolen realitzar
Proj - Llistat demembres decadaprojecte
ProjTit - Llistat demembres titulars decadaprojecte
Deps - Llistat dedepartaments
Dies - Estructura dedades quecontél’assignacióinicial
Calcular carregai,t’ ∀89:;′≠ 89:;
Seleccionar89:;′tqmax(carregai,t’)
siTreure proji deDiat iposar-loa
Diat’comptador =comptador +1
Buidar lallista denegats
Espossible canviardirectament pi aDiat’ ?
Seleccionar proji ∈ Diat tqmin(carregaj,t)
Calcular carrega dels projectes
no
si
Espossible intercanviarpi perpi’ ?
Seleccionar pi’ tqmin(carregai’,t’)
Treure pi deDiat iposar-loaDiat’Treure pi’ de Diat’ iposar-loaDiatcomptador =comptador +1
Buidar lallista denegats
carregai,t’+carregai’,t>
carregai,t +carregai’,t’?
si
no
no
S’han provat totsels dies ?
si
no
Descartarpi(Afegir-loalallista descartats)
S’han denegattots els
projectes?
si
no
FI
Seleccionar següentDiat’ tqmax(carregai,t’)
comptador =0
S’hanfet tots els canvis?
comptador= numCanvis
si
FI
no
BlancaBertranSubirana Pàg.65
6.5. Minimitzaciódelairregularitatdel’assignaciómillorada
En aquesta etapa, un cop es disposi de l’assignació diària de les presentacions millorada, es
procedirà a optimitzar novament cada dia per tal d’aconseguir una programació horària dels
projecteselmésòptimapossiblequantadispersióiairregularitat.Perfer-ho,esresoldràelmodel
simplificatpresentatal’apartat6.3.
Pàg.66Programaciód’horarisperalesdefensesdeTreballsdeFinaldeGrauiMàster
7. Resultats
Per a poder comprovar el correcte funcionament del procediment heurístic desenvolupat, s’han
realitzatprovesambles3instànciesques’hanpresentatal’apartat5.3.
S’especifiquen a continuació els resultats obtinguts en cada pas dels que s’han descrit
anteriorment.
7.1.1. Pre-procés:Assignaciódelsprojectesaundiaconcret
La Taula 7.1 resumeix comqueden distribuïts en la primera assignació els projectes en els dies,
objectiuprincipaldelpre-procésdel’algorismedesenvolupat.
S’observa que la distribució en quant a nombre de projectes per dia és considerablement
uniforme:encapcashihaalgundiapràcticamentbuitiunexcésdeconcentracióenaltresdies.En
comparació amb la distribució obtinguda amb l’execució del programa lineal (veure Taula 5.7),
s’observa que la uniformitat del nombre de projectes millora notablement per la instància 2 i
empitjorapocsignificativamentperlesinstàncies1i3.
Uncopobtingudal’assignacióinicialespotcalcularpercadainstànciaelvalordeladispersió, i la
càrrega total dels projectes. Tots dos valors haurien de millorar en posteriors passos del
procediment.
Taula7.1Distribucióinicialdelsprojectesenelsdiespercadajocdedades
N M N M N MDia1 29 78 21 69 27 98Dia2 25 73 23 90 32 106Dia3 32 100 24 83 25 90Dia4 32 91 18 70 32 109Dia5 32 93 20 72 22 81Dia6 19 72 - - 31 88Dia7 27 79 - - 28 76Dia8 26 75 - - 30 88Dia9 24 76 - - 32 96Dia10 19 60 - - 27 88Dia11 - - - - 29 91Dia12 - - - - 26 87
TOTAL 265 106 341Mitjana 26,5 79,7 21,20 76,80 28,42 91,50σ 4,93 11,78 2,39 9,26 3,18 9,48Dispersió 797 384 1.098Càrrega 642,98 208,80 778,03
Instància3Instància2Instància1
BlancaBertranSubirana Pàg.67
7.1.2. Optimització:Assignaciódelsprojectesaunahoraconcreta
La Taula 7.2 recull els resultats per cada joc de dades i cada dia de les execucions en CPLEX
(limitantdeltempsa2minuts)pertald’optimitzarlairregularitatpercadaprofessoriaconseguir
aixíunaassignacióhoràriadelsprojectesqueconstitueixlasolucióA.
S’observaque,pertalicoms’halimitateltempsdelesexecucions,nosempreéspossiblearribara
una solució òptima. Per això en molts casos el GAP és diferent de 0%. En general, com més
projecteshihaginassignatsenundiamésdifícilésperalprogramaarribaral’òptim.Totiaixò,en
apartatsanteriorsjas’hacomprovatqueallarganteltempsd’execucióa5o10minuts, lasolució
nomilloramoltsignificativament.
Ambelresultatsobtingutsenaquestapartdelprocésjaéspossiblecalcularunprimervalordela
funció objectiu per cadascuna de les dades. Mitjançant els canvis que es faran en el següent
apartat,s’intentaràmilloraraquestvalor.
Al’Annex6espodenconsultaramoded’exemplelesdadesquealimentenelCPLEXielsresultats
quegeneraenaquestaetapadelprocésperlesinstàncies1i2.
Taula7.2Resultatsdel’optimitzacióperdiesdel’assignacióinicial
7.1.3. Post-procés:Milloradelasolució
En aquesta part del procés s’ha modificat l’assignació inicial dels dies per tal de maximitzar la
càrrega de cada projecte. S’han fet proves generant diferent nombre de canvis per veure com
influeixen en la millora de la solució. A la Taula 7.3, la Taula 7.4 i la Taula 7.5 es presenta la
distribuciódelsprojectesenelsdiesdesprésdeferuncertnúmerodecanvispercadainstància.
Irregularitat GAP Irregularitat GAP Irregularitat GAPDia1 104 32,54% 44 0,00% 86 17,69%Dia2 82 22,63% 36 0,00% 98 0,00%Dia3 100 34,56% 48 0,00% 68 21,80%Dia4 124 33,84% 40 0,00% 94 23,31%Dia5 92 25,38% 38 0,00% 46 0,00%Dia6 54 0,00% - - 118 37,83%Dia7 88 27,24% - - 82 17,88%Dia8 78 0,00% - - 94 12,94%Dia9 58 0,00% - - 102 32,38%Dia10 42 0,00% - - 66 0,00%Dia11 - - - - 106 28,03%Dia12 - - - - 90 26,44%
Dispersió 797 384 1.098Irregularitat 822 206 1.050VALORF.O. 9.017 1.414 13.698
Instància3Instància1 Instància2
Pàg.68Programaciód’horarisperalesdefensesdeTreballsdeFinaldeGrauiMàster
Comjas’hacomentatanteriorment,sialafuncióquegeneraelscanviss’hiintrodueixunnúmero
suficientment gran el programa fa tots els canvis possibles. El nombre total de canvis que s’han
generatencadacassón180,44i344respectivamentperlesinstàncies1,2i3.
Desprésdelscanvis,s’observaunatendènciaaaglutinarelsprojectesenelsdies,deixantaixíalgun
diaambpocsprojectesid’altresambelmàximnombrepossible(32projectes-< = 8, =>? = 4).Així doncs, la desviació estàndard del nombre projectes per dia augmenta significativament al
incrementarelnombredecanvis.
Taula7.3Distribuciódelsprojectesacadadiadesprésdelscanvis–Instància1
Taula7.4Distribuciódelsprojectesacadadiadesprésdelscanvis–Instància2
Instància1 N M N M N M N M N M N MDia1 29 78 30 82 32 84 32 81 32 79 31 87Dia2 25 73 24 68 24 68 24 68 24 66 26 61Dia3 32 100 32 91 32 91 32 87 32 77 30 68Dia4 32 91 32 90 32 86 32 86 32 84 27 76Dia5 32 93 32 93 32 91 31 84 32 87 30 77Dia6 19 72 19 70 18 60 15 52 7 24 5 18Dia7 27 79 28 83 28 79 29 83 28 82 28 75Dia8 26 75 27 78 26 73 31 85 32 79 32 77Dia9 24 76 22 66 21 62 22 58 22 59 24 55Dia10 19 60 19 59 20 63 17 54 24 66 32 78
TOTAL 265 797 265 780 265 757 265 738 265 703 265 672
Mitjana 26,5 79,7 26,5 78 26,5 75,7 26,5 73,8 26,5 70,3 26,5 67,2
σ 4,93 11,78 5,21 11,78 5,52 12,09 6,55 14,30 7,93 18,58 8,00 19,57
Dispersió
Càrrega
Abanscanvis 10canvis 20canvis Totscanvis
642,98
797
661,18
780
681,95
757
709,62
50canvis 100canvis
738
765,90
703
848,95
672
Instància2 N M N M N M N MDia1 21 69 19 60 19 60 20 60Dia2 23 90 20 75 19 70 19 67Dia3 24 83 29 101 28 97 23 79Dia4 18 70 18 67 18 66 16 57Dia5 20 72 20 72 22 75 28 94
TOTAL 106 384 106 375 106 368 106 357
Mitjana 21,2 76,8 21,2 75 21,2 73,6 21,2 71,4
σ 2,39 9,26 4,44 15,60 4,09 14,19 4,55 15,21
Dispersió
Càrrega
Abanscanvis 10canvis 20canvis Totscanvis
208,80 245,97
384
213,90
375
220,33
368 357
BlancaBertranSubirana Pàg.69
Taula7.5Distribuciódelsprojectesacadadiadesprésdelscanvis–Instància3
Com era d’esperar, la càrrega augmenta al augmentar el nombre de canvis generats, així com
també el valor de la dispersió. En general la càrrega millora més significativament, el doble
aproximadament,quenodisminueix ladispersió.Enelcasdela Instància1, lacàrregamilloraun
32%de l’assignació inicial respectea l’assignaciódesprésde fer totselscanvispossibles,mentre
que ladispersiódisminueixun16%(veure laTaula7.3).Aquestspercentatgessónd’unaugment
del18%quantalacàrregaiunareducciódel7%pelquèfaaladispersióperlaInstància2(veure
Taula7.4), iun incrementde lacàrregadel46% iunadisminucióde ladispersiódel20%per la
Instància3(veureTaula7.5).
Aquestes tendènciesvanacompanyadesd’unadisminucióevidentdelnombredemembres total
implicatenelsprojectes.El fetque lespresentacionspercadamembreesconcentrinenelsdies
provocaqueaquestfactoresredueixi,doncsunmembrequeenuncasestavapresenten3dies
passaaestarpresentanomésundia,perexemple.
A la Taula 7.6, la Taula 7.7 i la Taula 7.8 hi consten els resultats de l’execució del model per
cadascundelsdiesipercadajocdedadesabansidesprésdelscanvis.S’himostrala irregularitat
per cada dia i total, i el GAP de cada execució i la mitjana per cada dia. S’observa que
contràriamenta lacàrrega ia ladispersió, la irregularitatnomilloraamesuraqueaugmentenel
nombre de canvis realitzats. No segueix una tendència clara associada amb el número de
modificacions, però en comparació amb la solució inicial calculada abans dels canvis, el valor
d’aquestcriteriempitjora.
Instància3 N M N M N M N M N M N MDia1 27 98 25 83 25 74 29 79 32 88 32 85Dia2 32 106 31 100 31 98 32 94 32 92 32 90Dia3 25 90 25 86 24 76 31 91 26 72 30 82Dia4 32 109 32 98 32 98 29 87 32 86 32 78Dia5 22 81 24 83 23 77 25 83 21 68 23 70Dia6 31 88 32 86 32 86 32 79 32 75 31 68Dia7 28 76 30 80 31 82 32 85 32 83 32 72Dia8 30 88 31 91 30 84 31 84 32 85 32 71Dia9 32 96 31 92 32 88 32 88 32 83 32 76Dia10 27 88 26 83 26 81 24 68 32 92 30 86Dia11 29 91 29 91 31 92 32 89 32 89 32 87Dia12 26 87 25 82 24 76 12 38 6 19 3 10
TOTAL 341 1.098 341 1.055 341 1.012 341 965 341 932 341 875
Mitjana 28,42 91,50 28,42 87,92 28,42 84,33 28,42 80,42 28,42 77,67 28,42 72,92
σ 3,18 9,48 3,15 6,47 3,65 8,34 5,87 14,98 7,86 20,00 8,40 21,15
Dispersió
Càrrega
932 875
778,03 822,20 869,30 922,65
1.098 1.055 1.012 965
1.011,81 1.132,66
Abanscanvis 20canvis 50canvis 100canvis 200canvis Totscanvis
Pàg.70Programaciód’horarisperalesdefensesdeTreballsdeFinaldeGrauiMàster
Amés, lamitjanadelGAPaugmentadegutaqueaugmentenelsdiesambelnombremàximde
projectes (32 projectes) assignats. Al haver-himés concentració de projectes en un dia, ésmés
difícilqueelprogramatrobilasolucióòptima,ipertantelGAPaugmenta.
Pelquefaa lasegona instància(veureTaula7.7),s’observaqueelprogramaarribaa l’òptimper
gairebétotselscasos.Aixòs’atribueixalfetquelacàrregadefeinadelsprofessorsimplicatsenels
projectesd’aquestquadrimestreésmésbaixa:cadamembretémenysprojectesassignatsiaixòfa
quesiguimésfàciltrobarsolucionsfactiblesiarribaralasolucióòptima.
Excepcionalment, en el procés demillora de la solució s’arriba a alguna assignació de projectes
diàriaambcàrreguestantelevadesquenoéspossibletrobarunasoluciófactible.Enaquestscasos,
s’haafegituna(*)odues(**)frangesexclusivamentpelsdiesafectatspertaldepoderobteniruns
horariscompatiblesamblesrestriccionsestablertes.
Taula7.6Irregularitatdecadadiaitotal,iGAPobtingutpercadaexecucióimitjanapercadadia–Instància1
Taula7.7Irregularitatdecadadiaitotal,iGAPobtingutpercadaexecucióimitjanapercadadia–Instància2
Instància1 IRREG GAP IRREG GAP IRREG GAP IRREG GAP IRREG GAP IRREG GAPDia1 104 32,5% 104 32,7% 122 40,0% 132 41,5% 132 40,1% 106 27,5%Dia2 82 22,6% 80 23,2% 80 27,4% 78 15,9% 70 10,8% 76 9,8%Dia3 100 34,6% 120 34,5% 116 32,1% 128 35,2% 120 27,9% 114 * 37,7%Dia4 124 33,8% 122 38,2% 124 33,4% 118 36,8% 124 37,6% 74 23,8%Dia5 92 25,4% 90 25,3% 96 30,1% 96 32,4% 104 40,0% 98 34,0%Dia6 54 0,0% 56 0,0% 64 0,0% 48 0,0% 20 0,0% 16 0,0%Dia7 88 27,2% 90 25,5% 92 29,4% 88 26,1% 68 11,8% 70 14,6%Dia8 78 0,0% 82 16,8% 80 11,9% 98 26,6% 110 28,6% 112 28,2%Dia9 58 0,0% 52 0,0% 50 0,0% 58 11,5% 56 56,8% 66 12,7%Dia10 42 0,0% 42 0,0% 42 0,0% 36 0,0% 70 0,0% 110 27,7%
TOTAL 822 18% 838 20% 866 20% 880 23% 874 25% 842 22%
100canvis TotscanvisAbanscanvis 10canvis 20canvis 50canvis
Instància2 IRREG GAP IRREG GAP IRREG GAP IRREG GAPDia1 44 0,0% 42 0,0% 42 0,0% 40 0,0%Dia2 36 0,0% 36 0,0% 34 0,0% 38 0,0%Dia3 48 0,0% 60 12,2% 62 0,0% 42 0,0%Dia4 40 0,0% 44 0,0% 38 0,0% 32 0,0%Dia5 38 0,0% 36 0,0% 46 0,0% 60 0,0%
TOTAL 206 0% 218 2% 222 0% 212 0%
Abanscanvis 10canvis 20canvis Totscanvis
BlancaBertranSubirana Pàg.71
Taula7.8Irregularitatdecadadiaitotal,iGAPobtingutpercadaexecucióimitjanapercadadia–Instància3
AlaTaula7.9esmostraunacomparativadelvalordecadacriteri(dispersióiirregularitat)aixícom
delafuncióobjectiupercadajocdedades.
S’apreciaunamillorasignificativadelafuncióobjectiudesprésderealitzarelscanvis,sobretotsies
comparaambelvalorobtingutresolentelmodelmatemàticsencer.
Tot i que la irregularitat tendeix a augmentar, el fet que la dispersió disminueixi més
accentuadament juntamentambel fetquese lidonaunmajorpesa la funcióobjectiu,provoca
queelseuvalormilloriconsiderablement.
Taula7.9Comparativadelvalordelafuncióobjectiu
Instància3 IRREG GAP IRREG GAP IRREG GAP IRREG GAP IRREG GAP IRREG GAPDia1 86 17,7% 78 16,1% 96 26,0% 126 38,2% 118 32,7% 120 35,7%Dia2 98 0,0% 98 7,6% 100 20,1% 120 26,0% 120 32,4% 108 37,0%Dia3 68 21,8% 70 19,8% 72 21,7% 104 34,7% 86 14,5% 90 * 29,8%Dia4 94 23,3% 122 35,4% 122 36,2% 106 16,7% 126 41,3% 114 34,2%Dia5 46 0,0% 54 5,6% 50 10,4% 48 0,0% 52 * 4,5% 62 ** 25,5%Dia6 118 37,8% 138 44,1% 138 46,9% 130 42,7% 116 * 43,6% 104 * 42,8%Dia7 82 17,9% 86 *36,4% 104 *38,1% 108 *38,7% 110 * 40,2% 118 * 41,2%Dia8 94 12,9% 94 19,6% 98 18,5% 104 20,9% 90 15,7% 92 15,9%Dia9 102 32,4% 100 34,3% 104 24,4% 110 33,2% 112 27,0% 118 * 43,9%Dia10 66 0,0% 62 5,2% 64 7,3% 76 25,4% 100 29,4% 74 22,7%Dia11 106 28,0% 110 35,3% 114 25,5% 124 32,5% 102 35,8% 96 26,6%Dia12 90 26,4% 86 27,1% 92 22,0% 42 0,0% 22 0,0% 8 0,0%
TOTAL 1.050 18% 1.098 24% 1.154 25% 1.198 26% 1.154 26% 1.104 30%
200canvis TotscanvisAbanscanvis 20canvis 50canvis 100canvis
Model AbansCanvis 10Canvis 20Canvis 50Canvis 100Canvis TOTSCanvis
Dispersió 2.336 822 780 757 738 703 672
Irregularitat 993 797 838 866 880 874 842
ValorF.O. 12.266 9.017 8.638 8.436 8.260 7.904 7.562
Model AbansCanvis 10Canvis 20Canvis 50Canvis
Dispersió 520 206 375 368 357
Irregularitat 340 384 218 222 212
ValorF.O. 2.220 1.414 2.093 2.062 1.997
Model AbansCanvis 20Canvis 50Canvis 100Canvis 200Canvis TOTSCanvis
Dispersió 3.162 1.050 1.055 1.012 965 932 875
Irregularitat 1.356 1.098 1.098 1.154 1.198 1.154 1.104
ValorF.O. 19.434 13.698 13.758 13.298 12.778 12.338 11.604
Instància3
Instància2
Instància1
Pàg.72Programaciód’horarisperalesdefensesdeTreballsdeFinaldeGrauiMàster
A mode d’exemple, l’Annex 6 inclou les dades que llegeix el CPLEX i els resultats generats per
cadascunaperelsjocsdedadescorresponentsatotselscanvisdelesinstàncies1i2.
ElsgràficsdelaFigura7.1,delaFigura7.2idelaFigura7.3,mostrenl’evoluciódelvalordecada
criteripercadainstància.
S’observalatendènciajacomentadadedisminuciódelvalordeladispersió,iengeneral,augmenti
posterior disminució de la irregularitat. Destaca també la clara disminució d’ambdós criteris
respectelasolucióobtingudaapartirdel’execuciódelmodellineal,méssignificativaenelcasdela
irregularitat.
Figura7.1Evoluciódelscriterisperlainstància1
0
500
1.000
1.500
2.000
2.500
Model AbansCanvis 10Canvis 20Canvis 50Canvis 100Canvis TOTSCanvis
Dispersió
iIrregularitat
Instància1
Dispersió Irregularitat
BlancaBertranSubirana Pàg.73
Figura7.2Evoluciódelscriterisperlainstància2
Figura7.3Evoluciódelscriterisperlainstància3
0
500
1.000
1.500
2.000
2.500
Model AbansCanvis 10Canvis 20Canvis 50Canvis 100Canvis TOTSCanvis
Dispersió
iIrregularitat
Instància1
Dispersió Irregularitat
0
500
1.000
1.500
2.000
2.500
Model AbansCanvis 10Canvis 20Canvis 50Canvis 100Canvis TOTSCanvis
Dispersió
iIrregularitat
Instància1
Dispersió Irregularitat
Pàg.74Programaciód’horarisperalesdefensesdeTreballsdeFinaldeGrauiMàster
8. Planificacióiprogramació
Peralarealitzaciódelprojectes’handesenvolupatlesactivitatsqueesdetallenacontinuació.La
Figura8.1inclouuncronogramadel’evolucióeneltempsd’aquestesactivitats.
- Anàlisi del problema: S’ha analitzat el problema plantejat i s’han buscat estudis de
problemes similars existents que poguessin facilitar-ne la seva resolució. S’ha decidit el
procedimentautilitzarperalaresolució.
- Model matemàtic: S’han establert els criteris i restriccions a considerar en el model
matemàtic.S’hadesenvolupatelmodelis’haimplementatalCPLEX.
- Avaluació del model matemàtic: S’ha executat el model implementat per a diferents
instàncies.Prèviament,hacalgutgenerarelsfitxersdedadesnecessarisquealimentenel
softwareCPLEX.
- Disseny del procediment heurístic: S’ha creat un procediment heurístic per a facilitar la
resoluciódelproblema.
- Programaciódelprocedimentdesenvolupat: S’haprogramatambPython el procediment
desenvolupat.
- Avaluació del procediment desenvolupat: S’ha provat el procediment heurístic dissenyat
amblesmateixesinstànciesques’havienutilitzatperaexecutarelmodelmatemàtic.
- Redacció de la memòria: Al llarg de gairebé tot el projecte, s’ha redactat el
desenvolupament de totes les activitats citades en la present memòria. Aquesta part
tambéincloul’estuditeòricques’hafetdel’ETSEIBidelsTFEs.
Figura8.1DiagramadeGanttdel’execuciódelprojecte
08 / 16 09 / 16 10 / 16 11 / 16 12 / 16 01 / 17 02 / 17 03 / 17 04 / 17 05 / 17
Anàlisidelproblema
Modelmatemàtic
Avaluaciódelmodelmatemàtic
Dissenydelprocedimentheurístic
Programaciódelprocedimentheurístic
Avaluaciódelprocedimentheurístic
Redacciódelamemòria
BlancaBertranSubirana Pàg.75
9. Pressupost
EsdetallaalaTaula9.1continuacióelpressupostperalarealitzaciód’aquestprojecte.
Taula9.1Pressupostderealitzaciódelprojecte
Tot i que l’evolució en el temps de cadascuna de les activitats que s’han dut a terme per a la
realització d’aquest projecte ha durat mesos, no totes les hores hàbils del mes s’han dedicat
exclusivament al seu desenvolupament. El total d’hores dedicades s’ha estimat considerat la
càrregalectivaquerepresentaelTFM(12crèditsECTS)ielnombred’horesdetreballqueimplica
cadascund’aquestscrèdits(30hores).
Enquant al costde l’amortitzacióde l’ordinador, s’ha calculat considerantun cost aproximatde
750€iunavidaútilde5anys,talicomesdetallaalaTaula9.2.
Taula9.2Costd’amortitzaciódel’ordinador
Quantitat CostUnitari Total
Horesdededicació 360Hores 30€/h 10.800€DepreciacióOrdinador 8mesos 12,50€/mes 100€LlicènciesExcel 1Unitats 149€/u 149€CPLEX 1Unitats 9.500€/u 9.500€
Subtotal 20.549€
IVA 21% 4.315€
TOTAL 24.864€
Cost 750€VidaÚtil 5anys
Costd'amortització 150€/any 12,50€/mes
Pàg.76Programaciód’horarisperalesdefensesdeTreballsdeFinaldeGrauiMàster
10. Impactesobrel’entorn
Elsimpactessobrel’entorndelarealitzaciód’aquestprojectehanestatmínims.Laimplementació
del programa informàtic desenvolupat per a programar les presentacions dels TFEs de
quadrimestresfutursgeneradiferentsimpactessobretotalasocietatuniversitàriaques’explicaran
acontinuació.
Enel casdeldesenvolupamentdelprojecte,ha tingutun impacteambientalmenoracausapels
residusgeneratspelmaterialusatperaferanotacionsenbrut,comfullsialtresmaterialsd’oficina,
i per les impressions realitzades per a revisar el contingut de lamemòria. Aquest últim tipus de
residus podrien haver-se estalviat si les correccions s’haguessin fet directament en format
electrònic.
Quant a la implementació del programa informàtic desenvolupat, té impacte ambiental mínim,
doncs tot el procés es du a terme informàticament. Únicament genera desgast dels aparells
informàtics(ordinadors)utilitzatsperaexecutar-lo.
Pelquefaaaltrestipusd’impactes,elfetd’utilitzarelprogramadesenvolupatperaprogramarles
presentacionsdelsTFGsiTFMsd’unaconvocatòriaafavoreixperunabandaalresponsabledefer
aquestesassignacions,doncsse liproporcionaunprocedimentmoltautomatitzatque li facilitarà
notablement la feina, i al professorat implicat als tribunals de les presentacions. Com ja s’ha
comentat al llarg del projecte, el procediment creat ha estat dissenyat per a beneficiar als
membresdelPDIjaques’intentareduirelnombredediesquehaurand’assistiraalgunadefensa,i
dinsdecadadias’intentaminimitzarelnombred’interrupcionsentre lespresentacions.Totaixò
permet que els professors puguin planificar-se millor i que, en cas que hagin de desplaçar-se
expressament a l’escola durant els dies de les presentacions, ho facin el mínim de vegades
possible.Aquestúltimfetgeneraunimpacteambientalpositiu.
BlancaBertranSubirana Pàg.77
11. Conclusions
Enaquestprojectes’hadesenvolupatunprocedimentquepermetgenerarunaprogramaciódeles
presentacionsdeTFGsiTFMsqueoptimitzalesagendesdelsprofessorsqueformenpartdelsseus
tribunals.
En primer lloc, s’ha comprovat que per resoldre el problema plantejat únicament mitjançant
l’optimitzaciódelmodelmatemàticmulticriteridesenvolupat iobteniruna solucióproubona,és
necessariexecutarelmodeldurantunllargperíodedetemps.Aixòesdeuaquèelvolumdedades
és important i aquè lespossibilitatsnoestan suficientment restringides, fetqueprovocaqueel
tempsd’execuciópertrobarunasoluciófactibleraonablementbonasiguimassaelevat.
En segon lloc, s’ha creat un procediment heurístic que, combinat ambuna adaptació delmodel
matemàticqueoptimitzalesdadesperparts(dies),permetobtenirunasoluciófactiblemoltmillor
amb aproximadament un quarta part del temps d’execució (depenent del volum de dades a
tractar). S’ha comprovat que després dels canvis efectuats per aquest algoritme el valor de la
dispersió millora respecte l’assignació inicial (generada al pre-procés), mentre que el de la
irregularitat empitjora. Tot i això, el valor de la funció objectiu disminueix obtenint d’aquesta
maneraunaprogramaciódelespresentacionsmésfavorablepelprofessorat.
Finalment,un copdemostratqueelprocedimentdesenvolupatésefectiu imillorael valorde la
funcióobjectiuenrelacióalmodelmatemàtic,espotutilitzarperaprogramarlespresentacionsde
TFEsquadrimestralsgenerantprimeramentunaassignacióinicialdelsprojectesenundia,millorar-
la posteriorment, i finalment optimitzar-la dia a dia per a obtenir l’assignació horària. Aquest
procés és molt senzill gràcies a les eines informàtiques que s’han desenvolupat, atès que
únicament requereix executar una rutina amb Python que genera els fitxers necessaris per a la
posterioroptimitzacióambCPLEX.
Pàg.78Programaciód’horarisperalesdefensesdeTreballsdeFinaldeGrauiMàster
12. Bibliografia
[1] Agència per la Qualitat del Sistema Universitària. Professorat. Disponible a:
http://www.aqu.cat/professorat/calendari.html#.WOVWcqMzmCQ [Consulta: Novembre
2016]
[2] CàtedraSeat.Inici.Disponiblea:http://catedraseat.upc.edu[Consulta:Octubre2016]
[3] CMEM.Inici.Disponiblea:https://cmem.upc.edu/ca[Consulta:Setembre2016]
[4] CS.Inici.Disponiblea:http://www.cs.upc.edu/?set_language=ca[Consulta:Setembre2016]
[5] DEE.Inici.Disponiblea:http://www.dee.upc.edu/ca[Consulta:Setembre2016]
[6] DOE.Inici.Disponiblea:http://doe.upc.edu/ca[Consulta:Setembre2016]
[7] EEL.Inici.Disponiblea:http://eel.upc.edu/ca[Consulta:Setembre2016]
[8] EGE.Inici.Disponiblea:https://ege.upc.edu/ca[Consulta:Setembre2016]
[9] EIO.Inici.Disponiblea:http://www.eio.upc.edu/ca[Consulta:Setembre2016]
[10] EM.Inici.Disponiblea:http://em.upc.edu/ca[Consulta:Setembre2016]
[11] EPC.Inici.Disponiblea:http://depc.upc.edu/ca[Consulta:Setembre2016]
[12] EQ.Inici.Disponiblea:http://eq.upc.edu/ca[Consulta:Setembre2016]
[13] ESAII.Inici.Disponiblea:http://esaii.upc.edu/ca[Consulta:Setembre2016]
[14] ETSEIB.Aliances.Disponiblea:https://etseib.upc.edu/ca/lescola/aliances [Consulta:Octubre
2016]
[15] ETSEIB. Aliances amb Empreses. Disponible a: https://etseib.upc.edu/ca/lescola/aliances/
aliances-amb-empreses[Consulta:Octubre2016]
[16] ETSEIB. Aliances Internacionals. Disponible a: https://etseib.upc.edu/ca/lescola/aliances/
aliances-internacionals[Consulta:Octubre2016]
[17] ETSEIB. Calendari TFG. Disponible a:
https://etseib.upc.edu/ca/estudis/calendaris/documents_ calendari/calendari_tfg.pdf
[Consulta:Novembre2016]
[18] ETSEIB. Calendari TFM. Disponible a: https://etseib.upc.edu/ca/estudis/calendaris/
documents_calendari/calendari_tfm.pdf[Consulta:Novembre2016]
[19] ETSEIB. Càtedres i Aules d’empresa. Disponible a: https://etseib.upc.edu/ca/universitat-
empresa/solucions-per-a-lempresa/catedres-i-aules-dempresa[Consulta:Octubre2016]
[20] ETSEIB. Departaments i Recerca. Disponible a:
https://etseib.upc.edu/ca/lescola/departments-i-recerca[Consulta:Octubre2016]
[21] ETSEIB.Doctorats.Disponiblea:http://www2.etseib.upc.edu/ca/calendaris-/3260-titulacions-
doctorat [Consulta:Setembre2016]
[22] ETSEIB. Grups de Recerca. Disponible a: https://etseib.upc.edu/ca/lescola/departaments-i-
recerca/produccio-cientifica[Consulta:Octubre2016]
BlancaBertranSubirana Pàg.79
[23] ETSEIB.L’Escola.Disponiblea:https://etseib.upc.edu/ca/lescola[Consulta:Setembre2016]
[24] ETSEIB.Màsters.Disponiblea:https://etseib.upc.edu/ca/estudis/masters[Consulta:Setembre
2016]
[25] ETSEIB.MàsterUniversitari en Automàtica i Robòtica. Disponible a: https://etseib.upc.edu/
ca/estudis/masters/masterROBOTICA[Consulta:Setembre2016]
[26] ETSEIB. Màster Universitari en Enginyeria Biomèdica. Disponible a: http://www.ub.edu/
estudis/ca/mastersuniversitaris/engbiomedica/presentacio[Consulta:Setembre2016]
[27] ETSEIB.MàsterUniversitarienEnginyeriad’Automoció.Disponiblea:https://etseib.upc.edu/
ca/estudis/masters/masterAUTO[Consulta:Setembre2016]
[28] ETSEIB.MàsterUniversitarienEnginyeriadel’Energia.Disponiblea:https://energia.masters.
upc.edu/ca[Consulta:Setembre2016]
[29] ETSEIB. Màster Universitari en Enginyeria d’Organització. Disponible a:
https://etseib.upc.edu/ ca/estudis/masters/masterORGANITZACIO [Consulta: Setembre
2016]
[30] ETSEIB. Màster Universitari en Enginyeria Industrial. Disponible a: https://etseib.upc.edu/
ca/estudis/masters/masterMUEi[Consulta:Setembre2016]
[31] ETSEIB.Màster Universitari en Enginyeria Nuclear. Disponible a: http://nuclearengineering.
masters.upc.edu/ca/informacio-general[Consulta:Setembre2016]
[32] ETSEIB. Màster Universitari en Supply Chain, Transport i Mobilitat. Disponible a:
https://etseib.upc.edu/ca/estudis/masters/masterSCTM[Consulta:Setembre2016]
[33] ETSEIB. Normativa TFG. Disponible a: https://etseib.upc.edu/ca/lescola/estructura-i-
organitzacio/documents%20normatives/grau/Normativa%20TFG[Consulta:Novembre2016]
[34] ETSEIB. Normativa TFM. Disponible a: https://etseib.upc.edu/ca/lescola/estructura-i-
organitzacio/documents%20normatives/master/Normativa%20TFM [Consulta: Novembre
2016]
[35] ETSEIB. Pautes TFG. Disponible a: https://etseib.upc.edu/ca/estudis/documents-destudis/
tfg_pautes_confeccio.pdf[Consulta:Novembre2016]
[36] ETSEIB. Pautes TFM. Disponible a: https://etseib.upc.edu/ca/estudis/documents-destudis/
tfm_pautes_confeccio.pdf[Consulta:Novembre2016]
[37] ETSEIB. Pràctiques Acadèmiques Externes. Disponible a: https://etseib.upc.edu/ca/estudis/
practiques/practiques-acad-exter-grau[Consulta:Octubre2016]
[38] ETSEIB. Protocol TFG. Disponible a: https://etseib.upc.edu/ca/estudis/documents-destudis/
tfg_protocol.pdf[Consulta:Novembre2016]
[39] ETSEIB. Protocol TFM. Disponible a: https://etseib.upc.edu/ca/estudis/documents-destudis/
protocol_tfm.pdf[Consulta:Novembre2016]
[40] ETSEIB.TreballFid’Estudis.Disponiblea:https://etseib.upc.edu/ca/estudis/treballs-fi-destudis
[Consulta:Setembre2016]
Pàg.80Programaciód’horarisperalesdefensesdeTreballsdeFinaldeGrauiMàster
[41] ETSEIB.TreballFinaldeGrau.Disponiblea:https://etseib.upc.edu/ca/estudis/graus/treballFG
[Consulta:Novembre2016]
[42] ETSEIB. Treball Final de Màster. Disponible a: https://etseib.upc.edu/ca/estudis/masters/
treballFM[Consulta:Novembre2016]
[43] Física.Inici.Disponiblea:http://fisica.upc.edu/ca[Consulta:Setembre2016]
[44] INNOENERGY.Inici.Disponiblea:http://www.innoenergy.com[Consulta:Setembre2016]
[45] INTE.Inici.Disponiblea:http://inte.upc.edu/es[Consulta:Octubre2016]
[46] IOC.Inici.Disponiblea:http://ioc.upc.edu/ca[Consulta:Octubre2016]
[47] MAT.Inici.Disponiblea:http://mat.upc.edu/ca[Consulta:Setembre2016]
[48] MF.Inici.Disponiblea:http://www.mf.upc.edu[Consulta:Setembre2016]
[49] MMT.Inici.Disponiblea:http://mmt.upc.edu/ca[Consulta:Setembre2016]
[50] RMEE.Inici.Disponiblea:https://rmee.upc.edu/ca[Consulta:Setembre2016]
[51] Secció d’Enginyeria Nuclear. Càtedra Argos. Disponible a: http://www-sen.upc.es/
i+d/argos/presargos_cata.htm[Consulta:Octubre2016]
[52] UPC. Càtedra Grupo JG. Disponible a: http://www.upc.edu/web/catedraupcjg/ [Consulta:
Octubre2016]
[53] UPC. Càtedra Endesa Red. Disponible a: https://www.upc.edu/unitat/fitxa_unitat.php?id_
unitat=758&lang=ca[Consulta:Octubre2016]
[54] UPC.FiguresdelPDI.Disponiblea:http://www.upc.edu/sdp/ca/concursos-personal-docent-i-
investigador/informacio-general/figures-de-personal-docent-i-investigador-1 [Consulta:
Novembre2016]
[55] UPC.GETI.Disponiblea:http://www.upc.edu/aprendre/estudis/graus/enginyeria-en-tecnolo-
gies-industrials-barcelona-etseib[Consulta:Setembre2016]
[56] UPC.LaUPC.Disponiblea:http://www.upc.edu/la-upc[Consulta:Setembre2016]
[57] UPC. Presentació dels col·lectius. Disponible a: http://www.upc.edu/comunitat/pdi-pas/
treball/presentacio-dels-colb7lectius[Consulta:Novembre2016]