Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració

Treball de Fi de Grau Grau en Enginyeria en Tecnologies Industrials Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració MEMÒRIA Autor: Laura Enrique Feliu Director: Alberto García Villoria Convocatòria: Setembre 2017 Escola Tècnica Superior d’Enginyeria Industrial de Barcelona Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 2 1. Resum El present treball té la finalitat de resoldre el problema de l’equilibrat de línia de muntatge considerant l’efecte de la deterioració de les tasques. Definint la deterioració d’una tasca com el fet de que una tasca processada després d’un cert temps consumeix més temps de processament que si la mateixa es processada més aviat. Tot i que és un problema que es troba present en certes línies de muntatge reals, se’n troben pocs estudis a la literatura científica. Amb tal fi, s’ha desenvolupat un procediment heurístic que, donades unes determinades característiques de la línia de producció, concretament el nombre de tasques, els temps de procés constants de cada tasca, les seves relacions de precedència i el temps de cicle màxim de la línia, realitzi la seva distribució a les estacions de treball de la manera més eficient possible i minimitzant el nombre d’estacions utilitzades (el que es coneix com a ALBP-1). El procediment proposat es basa en una heurística de millora coneguda com a optimització local. Aquest mètode parteix d’una solució inicial (en aquest cas trobada a partir d’heurísitiques constructives greedy) i utilitza com a idea fonamental l’exploració del veïnatge per trobar solucions millors. S’han creat 12 variants basades en aquest algorisme que resulten de canvis en els mètodes per obtenir la solució inicial, és a dir, 12 heurístiques amb regles de prioritat diferents per distribuir les tasques en les estacions. Per tal d’avaluar el funcionament del procediment de resolució proposat s’ha realitzat una experiència computacional a partir d’un conjunt d’exemplars de testatge. Per dur a terme l’experimentació, s’ha escollit utilitzar un banc de dades dirigit per la resolució de problemes d’equilibrat de línia de muntatge simple al que se li ha afegit com a dada la taxa de creixement de la deterioració. En concret s’han estudiat 5 variants diferents de taxa de deterioració per tal de poder analitzar la incidència que té en l’equilibrat de la línia. Finalment s’ha fet una comparativa entre les diferents heurístiques aplicades per veure quina d’elles és la més eficaç per resoldre aquest problema. Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 3 Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 4 2. Sumari 1. RESUM ____________________________________________________ 2 2. SUMARI ___________________________________________________ 4 3. INTRODUCCIÓ ______________________________________________ 7 3.1. Objectius del projecte ..................................................................................... 7 3.2. Abast del projecte ........................................................................................... 7 4. ESTAT DE L’ART DEL PROBLEMA DE L’EQUILIBRAT DE LÍNIES DE MUNTATGE ______________________________________________ 9 4.1. Les línies de muntatge ................................................................................... 9 4.1.1. Introducció ........................................................................................................ 9 4.1.2. Conceptes principals ....................................................................................... 10 4.1.3. Classificació de les línies de muntatge ............................................................ 11 4.2. Tipus de problemes de línies de muntatge .................................................. 15 4.2.1. Disseny de línies de muntatge ........................................................................ 15 4.2.2. Equilibrat de línies de muntatge ...................................................................... 16 5. EQUILIBRAT DE LÍNEA DE MUNTATGE AMB TASQUES AMB DETERIORACIÓ __________________________________________ 19 5.1. Estat de l’art .................................................................................................. 19 5.2. Definició del problema .................................................................................. 20 5.3. Formalització del problema .......................................................................... 23 6. PROPOSTA DE RESOLUCIÓ DEL PROBLEMA ________________ 26 6.1. Mètodes de resolució ................................................................................... 26 6.2. Procediment de resolució mitjançant optimització local ............................... 28 6.2.1. Generació de solucions inicials ....................................................................... 28 6.2.2. Generació de solucions veïnes ....................................................................... 32 6.2.3. Selecció de la millor veïna ............................................................................... 33 7. EXPERIÈNCIA COMPUTACIONAL ___________________________ 35 7.1. Exemplars de testeig .................................................................................... 35 7.2. Anàlisis de resultats ...................................................................................... 38 CONCLUSIONS ______________________________________________ 44 BIBLIOGRAFIA ______________________________________________ 45 Referències bibliogràfiques .................................................................................... 45 Bibliografia complementària ................................................................................... 47 Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 5 ANNEX _____________________________________________________ 48 Annex A. Temps d’execució de l’experiència computacional ................................ 48 Annex B. Solucions inicials de l’experiència computacional .................................. 49 Annex C. Solucions de l’optimització local a partir de l’exeperiència computacional .............................................................................................. 66 Annex D. Algorismes ............................................................................................. 78 Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 7 3. Introducció L’equilibrat d’una línia de muntatge és un procediment en que les tasques es distribueixen de manera uniforme a cada estació de treball. Per tal de que una estació estigui ben equilibrada cal que totes les estacions tinguin una càrrega i un cicle de treball el més semblant possible per tal de reduir el temps d’inactivitat dins de la línia. Al món industrial existeixen molts tipus de línies de muntatge. Per aquest motiu s’han realitzat nombrosos estudis per investigar el seu comportament operatiu i trobar noves maneres d’augmentar la seva eficiència. En aquest context apareix el problema d’equilibrat de línies de muntatge (ALBP) del qual en la literatura se n’acostuma a tractar la versió simplificada (SALBP). Aquesta versió, però, no considera característiques reals de les línies de muntatge. D’aquesta manera i per tal de donar resposta a problemes reals, com ara a una característica que es troba present en multitud de línies, el present projecte considera l’efecte de la deterioració de les tasques. 3.1. Objectius del projecte L’objectiu d’aquest projecte és resoldre el problema de l’equilibrat de línia de muntatge considerant l’efecte de la deterioració de les tasques. L’objectiu del problema consisteix en minimitzar el nombre d’estacions de treball donat un temps de cicle determinat. Per tal de portar-ho a terme, es presenta un conjunt de procediments heurístics per obtenir solucions factibles inicials del problema. A partir d’aquí es proposa un mètode d’optimització local. Per tal d’avaluar l’eficiència dels procediments de resolució proposat, es presenta una experiència computacional realitzada a partir de l’avaluació d’exemplars, amb els quals s’avaluen els resultats obtinguts. 3.2. Abast del projecte En aquest projecte es tracta la resolució del problema des d’una perspectiva teòrica i d’investigació. Concretament, la variant estudiada té en compte les següents hipòtesis i característiques:  Es coneix el temps de cicle de la línia.  Les tasques són indivisibles i un cop iniciada la seva execució no es poden interrompre. Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 8  Existeixen relacions de precedència entre les tasques, les quals també es coneixen.  La línia té una duració de les tasques dependent. El temps de processament d’una determinada tasca depèn del seu moment d’inici i del moment en el qual s’acaben de processar les seves predecessores.  El concepte de la deterioració de les tasques es considera lineal.  La línia de muntatge és simple, serial i síncrona.  La línia no diferència entre operadors manuals o robòtics.  La taxa d’entrada de les peces a la línia és fixa.  Les estacions són del mateix tipus. Això implica que estan equipades amb els mateixos components i, conseqüentment, tota tasca pot ser assignada a qualsevol estació. Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 9 4. Estat de l’art del problema de l’equilibrat de línies de muntatge 4.1. Les línies de muntatge 4.1.1. Introducció En la seva forma bàsica, una línia de muntatge consisteix en una seqüència d’estacions de treball, generalment connectades per un mecanisme de transport com ara una cinta transportadora, a través de la qual flueixen les unitats d’un producte. Cada estació de treball realitza repetidament un conjunt de tasques per produir o fabricar un producte específic. Les tasques requereixen un cert temps per processar-se i estan relacionades entre elles d'acord amb les restriccions tecnològiques existents. Un dels exemples més famosos d'una línia de muntatge és la planta de producció de Henry Ford, ja que va ser la primera en assentar les bases modernes de la producció en cadena. Els components del model T de Ford es van fabricar a la primera línia mòbil utilitzant les idees de divisió de treball perseguint dos objectius clars: la disminució dels costos i la producció en massa. Tanmateix, aquests tipus de configuracions daten d'èpoques molt anteriors. L'Arsenal venecià (considerat la primera fàbrica del món), va desenvolupar mètodes de producció massiva de vaixells de guerra que eren molt més ràpids i requerien menys fusta. En el moment àlgid de la seva eficàcia a principis del segle XVI, l'Arsenal va poder produir prop d'un vaixell per dia amb una línia de producció que no es va veure de nou fins a la Revolució Industrial. L’any 1799, Eli Whitney va introduir el concepte d’estandardització en el sistema de fabricació nord-americà a partir de la creació de parts intercanviables en la fabricació d’armament, fent ús dels conceptes de divisió de treball i tolerància en l’àmbit de l’enginyeria, per tal de crear acoblats de parts d’una forma repetitiva. Al 1901 Ransom Eli Olds, creador de la marca automobilística Oldsmobile, va intentar patentar el primer concepte de línia de muntatge per tal de fabricar automòbils en massa, però no va ser fins a 1913 quan Henry Ford va perfeccionar aquesta idea i finalment la va portar a terme. Encara que les línies de muntatge es troben molt sovint a la indústria de l'automòbil, molts altres sectors també estan organitzats d’aquesta manera. Aquest és el cas de la majoria de béns de la vida quotidiana, com, per exemple, el muntatge final de productes elèctrics com ara màquines de cafè, rentadores, refrigeradors, ràdio, televisió i ordinadors personals, etc. Més recentment, les línies de muntatge han guanyat importància en la producció en volum reduït de productes personalitzats així com en els sistemes de servei. Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 10 4.1.2. Conceptes principals Una línia de muntatge té com a objectiu crear un determinat producte, ja sigui final o intermedi, afegint conjunts de peces de manera predefinida. Per realitzar aquest muntatge, es disposa principalment d’un nombre d’estacions i unes determinades tasques, que es caracteritzen cada una d’elles per la seva duració i les relacions entre elles, ja siguin per exemple, de precedència o d’incompatibilitat. A continuació s’exposen els conceptes més significatius dels problemes d’equilibrat de línies de muntatge:  Tasca i: és una unitat de treball indivisible que té associat un temps de procés (ti). El treball total requerit per fabricar un producte en una línia de muntatge es divideix en un conjunt de N tasques.  Temps de procés de la tasca i (ti): temps necessari per realitzar la tasca i.  Estació de treball j: són els components de la línia en els quals es processen les tasques, per tant, una estació de treball està formada per un conjunt de tasques a realitzar. Poden implicar un operador humà o robòtic, determinats equips i alguns mecanismes de processament especialitzats.  Càrrega de treball de l’estació j: és el conjunt de tasques assignades a l’estació de treball j.  Temps de treball de l’estació j: és la suma dels temps de procés de les tasques assignades a l’estació j.  Temps mort o ociós de l’estació j: és la diferència entre el temps de cicle i el temps de treball de l’estació j.  Temps de cicle (TC): és el temps disponible a cada estació de treball per completar les tasques necessàries per processar una unitat de producte. En cas que no estigui especificat, s’acostuma a considerar igual al temps de treball de l’estació més carregada. A la literatura, el temps de cicle també es defineix com l’interval de temps entre el processament de dues unitats consecutives.  Relacions de precedència: es defineixen per les restriccions de prioritat tecnològica que determinen l’ordre en què es poden realitzar les tasques a la línia de muntatge. No es pot processar una tasca fins que no s’hagin processat totes les seves predecessores immediates. Les relacions de precedència normalment estan representades per un diagrama graf de precedències. Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 17  Totes les tasques es processen de la mateixa manera, no hi ha alternatives de processament.  Casa tasca constitueix una unitat indivisible.  La línia té una arquitectura simple i serial, sense línies d’alimentació ni elements paral·lels.  La línia és sincrònica.  L’ordre en que es realitzen les tasques ha de respectar unes restriccions de precedència.  La duració de les tasques és determinista.  La taxa d’entrada de les peces de la línia és fixa.  Les estacions són del mateix tipus. Això implica que estan equipades amb els mateixos components i, conseqüentment, tota tasca podria ser assignada a qualsevol estació. Partint d’aquestes característiques, es poden distingir quatre variants del SALBP en funció de l’objectiu que es vol assolir (Scholl [3]): SALBP-1: es busca minimitzar el nombre d'estacions necessàries per a realitzar el procés productiu a partir d'un temps de cicle màxim assignat (sense sobrepassar la taxa de producció especificada). Aquest tipus de problema és adequat quan es vol instal·lar un nou sistema de muntatge i la demanda externa és coneguda (o se’n pot fer una bona estimació). SALBP-2: en aquest cas es parteix d'un nombre d'estacions fix i es busca minimitzar el temps de cicle de la línia de muntatge (és a dir, maximitzar la taxa de producció). D’aquesta manera es garanteixen temps mínims d’inactivitat. Aquest problema s’acostuma a presentar quan la línia de muntatge ja existeix. SALBP-E: es vol maximitzar l'eficiència de la línia, o el que és el mateix, minimitzar el producte de nombre d'estacions de treball (M) per el temps de cicle (TC). En aquest cas, tant el nombre d’estacions com el temps de cicle són variables del problema donades. SALBP-F: consisteix en trobar una solució factible per una combinació qualsevol de temps de cicle (TC) i nombre d'estacions (M). Serveix per aquells casos en els que es vol conèixer si la línia pot operar amb uns valors determinats de M i TC. GALBP: Problema general d’equilibrat de línia de muntatge. Els problemes tipus ALBP són tots aquells que no són el SALBP i que s’apropen més a problemes reals. Usualment aquests problemes són molt difícils de resoldre òptimament degut a la seva naturalesa combinatòria i a la multitud de tasques i condicions presents en les situacions reals. Els ALBPs, a causa de la seva enorme rellevància en la indústria i en els serveis, han estat àmpliament estudiats des de les últimes dècades com es reflecteix en els nombrosos treballs de Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 18 síntesi que han anat apareixent. Una crítica esmentada freqüentment en aquests treballs és la important diferència existent entre els problemes habitualment investigats per la comunitat científica i els que es donen en la realitat industrial. Un motiu d'aquest fenomen és que s'ha tendit a investigar versions simplificades dels mateixos per reduir la seva complexitat a un nivell abordable a les tècniques de la investigació operativa. Així, aquests últims anys la comunitat científica ha intensificat els seus esforços a estudiar ALBPs que incorporin característiques addicionals presents en sistemes reals. Per exemple, entre d'altres: temps de les tasques dependents de la seqüència de muntatge (Capacho et al. [6]), temps de les tasques dependents dels operaris (Moreira et al. [7]), temps de preparació entre tasques (Martino i Pastor [8]), incertesa en els temps de les tasques (Saïf et al. [9]), restriccions espacials (Bautista i Pereira [10]), recursos limitats (Corominas et al. [11]), consideracions ergonòmiques (Otto i Scholl [12]), línies en forma d'U (Avikal et al. [13]) i línies amb dos costats (Purnomo et al. [14]). Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 19 5. Equilibrat de línea de muntatge amb tasques amb deterioració En aquest apartat es fa la descripció del problema en concret a tractar en aquest treball. En primer lloc es fa una revisió de la literatura on s’ha tractat aquest problema i a continuació es comenten les característiques específiques del problema. 5.1. Estat de l’art En el camp de l’estudi dels problemes d’equilibrat, una gran quantitat d’investigació s’han dut a terme en diversos tipus de línies i diferents funcions objectiu. La majoria dels estudis però, han considerat el temps de processament de les tasques com a un valor constant. Tot i així, en algunes situacions industrials el temps de processament de les tasques augmenta a mesura que tarden en començar en processar-se; per tant, és una característica important a tenir en compte. Aquest treball tracta sobre els efectes que comporta afegir el concepte de la deterioració de tasques al conegut problema d’equilibrat de línies de producció (ALBP). Definint la deterioració d’una tasca com el fet de que una tasca processada després d’un cert temps consumeix més temps de processament que si la mateixa es processada més aviat. Aquest concepte va ser primerament introduït per Gupta and Gupta [15] i Browne i Yechiali [16] anomenant-lo “Task Deterioration” en problemes de programació. Van proposar models matemàtics on el temps de processament d’una tasca és una funció lineal del seu temps d’inici. L’exemple mes popular que es pot trobar a la literatura on es pot observar aquest fenomen és la temperatura d’un lingot, que mentre espera per entrar a la màquina de laminació, la seva temperatura baixa fins a un determinat nivell que suposarà haver de tornar a escalfar-lo abans d’entrar a la màquina. La falta d’una programació eficient en aquest tipus de tasques en cadenes de producció pot portar a un increment significatiu en el temps de cicle, especialment en unitats de manufactura de grans dimensions. Aquest concepte de la deterioració ha sigut força estudiat en problemes de programació com es pot veure en estudis de Ji et al. [17] o Wang et al. [18], però no tant a problemes d’equilibrat de línies. Si fem una revisió de la literatura podem trobar articles com ara el de Toksari et al. [19] en el qual consideren simultàniament l’efecte de la deterioració de les tasques amb l’efecte de l’aprenentatge dels operaris degut a la repetició de les tasques. Proposen representar la deterioració com una funció lineal creixent del temps d’inici d’una tasca juntament amb la corba d’aprenentatge introduïda per Biskup [20], la qual, en la seva forma més bàsica es bassa en que el temps necessari per realitzar una operació disminueix proporcionalment pel nombre de repeticions. L’objectiu del problema és minimitzar el nombre d’estacions per el qual desenvolupen un model de programació entera mixta no lineal. Utilitzen les mateixes taxes Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 20 d’aprenentatge i deteriorament en totes les estacions. En aquest article també es prova l’adaptació de l’enfocament COMSOAL (Computer method of sequencing operations for assembly lines) per a aquest problema d’equilibrat de línia de muntatge a gran escala. Els exemplars utilitzats son varis problemes ja coneguts a la literatura afegint-los les taxes d’aprenentatge i deteriorament. Un altre estudi a tenir en compte és el de Hampta et al. [21] en el qual també es tracta l’equilibrat de línia de muntatge simple de tipus ALBP-2 (per tant es busca minimitzar el temps de cicle per un determinat nombre d’estacions de treball). En aquest estudi es consideren els efectes del deteriorament i l’aprenentatge simultàniament i es desenvolupa un model matemàtic. A més de l’equilibrat de la línia de muntatge, el model desenvolupat presenta la programació de l’execució de les tasques assignades a cada estació. A més a més, es proposa un mètode metaheurístic per tal de resoldre el problema. I per últim podem destacar uns dos altres estudis molt similars entre si, degut al plantejament i els resultats obtinguts. Són el de Noushabadi et al. [22] i el de Shahanaghi et al. [23]. En aquests dos articles s’estudia solament l’efecte del deteriorament d’una tasca al problema d’equilibrat de línia de muntatge simple. En el de Noushabadi et al. es busca una programació de tasques per a minimitzar el nombre d’estacions donat un temps de cicle determinat (per tant, el que es coneix com a ALBP-1). A aquest efecte, es proposa un model matemàtic i posteriorment, degut a que es tracta d’un problema NP-hard, es proposa un algorisme genètic. Resolen diversos problemes coneguts a la literatura per a estudiar el rendiment de l’enfocament proposat. En el cas del estudi de Shahanagui et al. el que busquen és programar les tasques a les estacions de treball per tal de minimitzar el temps de cicle, el que es coneix com a ALBP-2. En aquest estudi també es proposa un model matemàtic i posteriorment un algorisme genètic. De la mateixa manera es resolen diversos exemples coneguts per il·lustrar l’enfocament proposat. A priori aquests dos últims estudis es van seleccionar per a fer una comparativa amb els resultat obtinguts en aquest projecte. Això es va descartar una vegada analitzat bé els articles ja que es va descobrir una errada en la proposta de resolució. Tant en el treball de Noushabadi et al. com el de Shahanaghi et al. no es tenen en compte els temps ociosos de les estacions per calcular el deteriorament, fet que anul·la la validesa dels resultats. 5.2. Definició del problema El problema consisteix en que, donat un temps de cicle determinat, hi ha N tasques dependents que s’han d’assignar i programar a les estacions de treball. Per tant es tracta d’un ALBP-1. Al considerar la deterioració de les tasques, aquestes es deterioren mentre esperen a ser processades. Aquest concepte d’espera es pot definir com el temps que transcorre entre el moment en que una tasca està disponible per ser processada i el moment en que s’inicia aquest processament. Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 21 Aquest temps de processament no constant ha sigut definit a la literatura com la següent funció lineal: 𝑝𝑖=𝑡𝑖+𝑏𝑖×(𝑠𝑡𝑖−𝑎𝑣𝑖) (Eq. 1) on ti és la part constant del temps de processament de la tasca i, bi correspon a la taxa de creixement de la deterioració de la tasca i, sti (start time) és el temps d’inici la tasca i, quan es comença a processar, i avi (available time) és el temps en que la tasca i passa a estar disponible. D’aquesta manera, la diferència entre el temps d’inici i el temps en que està disponible equival al temps de retard de la tasca. Cal remarcar que el temps disponible d’una tasca és el moment en que aquesta es pot realitzar. En les línies de muntatge es pot realitzar una tasca una vegada que s’hagin completat totes les seves tasques predecessores. El moment en que s’acabi de processar l’última predecessora d’una determinada tasca, correspondrà al seu temps disponible. Per tant, com es pot observar a l’Eq. 1, pi correspon al temps de processament de la tasca i tenint en compte la deterioració. Per il·lustrar bé aquest concepte, a continuació es mostra un petit exemple. L’exemplar que es resol és un problema molt conegut de mida petita anomenat Mertens. La informació que es te sobre aquest exemplar és la següent: - El nombre de tasques que té, i la part constant del temps de procés de cada tasca (recollits a la Taula 5.1) - El temps de cicle màxim del que disposen les estacions. En aquest cas de 10 segons. - Les relacions de precedència directa que tenen les tasques. Les relacions de precedències es representen, tal com es fa habitualment, en un graf (Figura 5.1). Els nodes del graf simbolitzen les tasques, i les arestes simbolitzen que la tasca de la qual surt la fletxa és la tasca precedent immediata de la tasca a la qual arriba la fletxa. Per exemple, la tasca 5 té com a tasca precedent immediata la tasca 2, com a precedents totals les tasques 1 i 2, i com a successora immediata la tasca 1. Com a taxa de creixement de la deterioració s’ha assignat 0,1. Tasca i ti 1 1 2 5 3 4 4 3 5 5 6 6 7 5 Taula 5.1. Temps de processament de les tasques del problema Mertens. [Font: Pròpia] Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 22 Figura 5.1. Graf de precedències del problema Mertens. [Font: Pròpia] A partir de les dades de l’exemplar es poden trobar diferents solucions factibles, una de les quals podria ser la proposada a la Taula 5.2. El criteri per col·locar les tasques ha sigut donar prioritat a les tasques que tinguessin temps de procés contant (ti) més elevat, i en cas d’empat, assignar abans les tasques amb menys precedents totals. A la última columna es troben els temps de treball de cada estació. La diferència entre el temps de cicle màxim i el temps de treball correspon al temps mort o ociós de cada estació. Número d’estació Tasca sti avi Temps de procés pi Temps de treball de cada estació 1 1 0 0 1 10 2 1 1 5 3 6 6 4 2 5 10 6 5,4 9,84 4 15,4 1 4,44 3 6 20 15,4 6,46 6,46 4 7 30 19,84 6,016 6,016 Taula 5.2. Càlculs de la solució proposada pel problema Mertens. [Font: Pròpia] A continuació es detallen les hipòtesis i característiques de la línia de muntatge que es considera en aquest treball:  Les tasques són indivisibles i un cop iniciada la seva execució no es poden interrompre.  Existeixen relacions de precedència entre les tasques.  La línia té una duració de les tasques dependent. El temps de processament d’una determinada tasca i depèn del seu moment d’inici i del moment en el qual s’acaben de processar les seves predecessores, essent pi el temps de procés de la tasca i (i=1,...,N). Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 23  El concepte de la deterioració de les tasques es considera lineal.  La línia de muntatge és simple, serial i síncrona.  La línia no diferència entre operadors manuals o robòtics.  La taxa d’entrada de les peces a la línia és fixa.  Les estacions són del mateix tipus. Això implica que estan equipades amb els mateixos components i, conseqüentment, tota tasca pot ser assignada a qualsevol estació. 5.3. Formalització del problema En aquest apartat es formalitza el problema modelitzant-lo mitjançant el següent model matemàtic. Dades N Nombre de tasques. M Fita superior del nombre d’estacions. El seu valor es podria determinar, per exemple, amb el nombre d’estacions d’una solució calculada heurísticament. TC Temps de cicle màxim a respectar. 𝑡𝑖 Temps de procés constant de la tasca i ( 1i ,...,N ). 𝑏𝑖 Taxa del creixement de la deterioració de la tasca i ( 1i ,...,N ). i PR Conjunt de les predecessores immediates de la tasca i ( 1i ,...,N ). i PRT Conjunt de les predecessores totals de la tasca i   1i ,...,N : i i i h h PR PRT PR PRT      . P Conjunt de parelles de tasques tal que no hi ha cap relació de precedència entre elles:     1 1 1 ih P h,i :h ,...,N ;i h ,...,N |h PRT i PRT        . Variables   01 ij x, 1 si la tasca i es assignada a la estació j ; 0 en cas contrari ( 1i ,...,N ; 1j ,...,M )   01 j y, 1 si és necessària l’estació j ; 0 en cas contrari ( 1j ,...,M ) i p Z Temps de procés (tenint en compte la deterioració) de la tasca i ( 1i ,...,N ) i st  Z Instant en que comença a processar-se la tasca i ( 1i ,...,N ). Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 24   01 hi w, 1 si la tasca h es processa abans que la tasca i ; 0 en cas contrari (   h,i P ) i av  Z Instant en que la tasca i està disponible; és a dir, l’instant en que finalitza de processar-se totes les seves precedents ( 1i ,...,N ) Model   1 MIN M j j jy    (Eq. 2) 1 1 M ij j x    1i ,...,N (Eq. 3) h h i st p st 1i ,...,N ; i h PR (Eq. 4)     1 h h i hi st p st M TC w        h,i P (Eq. 5)   i i h hi st p st M TC w       h,i P (Eq. 6)   1 1 M i ij j st TC j x          1i ,...,N (Eq. 7) 1 M i i ij j st p TC j x          1i ,...,N (Eq. 8) ij j xy 1i ,...,N ; 1j ,...,M (Eq. 9)   i i h h h PR av max st p   1i ,...,N (Eq. 10) 𝑝𝑖=𝑡𝑖+𝑏𝑖×(𝑠𝑡𝑖−𝑎𝑣𝑖) 1i ,...,N (Eq. 11) L’objectiu del model (Eq. 2) consisteix en minimitzar el nombre d’estacions necessàries donat un temps de cicle determinat; aquesta equació, a més a més, trenca simetries entre solucions equivalents. L’Eq. 3 assigna cada tasca a una i només una estació. Les tasques estan subjectes a relacions de precedència les quals estan assegurades amb l’Eq. 4. Les Eqs. 5 i 6 asseguren que dues tasques no es realitzen simultàniament a la mateixa estació (cal notar que aquestes restriccions només són necessàries imposar-les per a aquelles parelles de tasques sense relacions de precedència). Les Eqs. 7 i 8 asseguren que cada tasca comença Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 25 i finalitza en l’estació assignada respectant el temps de cicle màxim donat. L’Eq. 9 determina que una estació és necessària si se l’assigna al menys una tasca. L’Eq. 10 fixa l’instant de disponibilitat d’una tasca a l’instant en que acaba l’última de les seves predecessores en processar-se. Finalment, l’Eq. 11 estableix el temps de procés d’una tasca en funció del deteriorament que ha sofert des de que està disponible fins que comença a processar-se. Eq. 10 és la única expressió no lineal del model. Si es volgués provar de resoldre el model amb un solver de programació lineal, aquesta equació es pot linealitzar de la següent manera: Variables addicionals   01 hi v, 1 si la tasca h es la última predecessora de la tasca i en processar-se; 0 en cas contrari ( 1i ,...,N ; i h PR ) Restriccions addicionals (que substitueixen l’Eq. 11) 1 i hi h PR v    1i ,...,N (Eq. 12)       1 i h h hi av st p M TC v      1i ,...,N ; i h PR (Eq. 13)   i h h av st p 1i ,...,N ; i h PR (Eq. 14) L’Eq. 12 imposa que una i només una de les predecessores de cada tasca serà la última en processar-se. Les Eqs. 13 i 14 fixen l’instant de disponibilitat de cada tasca a l’instant en que acaba la última de les seves predecessores en processar-se. Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 26 6. Proposta de resolució del problema 6.1. Mètodes de resolució Per tal de trobar la solució al problema plantejat existeixen diferents mètodes de resolució que es podrien aplicar. Per aquest motiu, en aquest capítol es fa una petita introducció als dos tipus de mètodes que podrien ser adients en la resolució d’aquest problema en concret; els mètodes exactes i els mètodes aproximats (no exactes). Els mètodes exactes són procediments que garanteixen trobar la solució òptima d’un problema en un temps finit, sempre i quan aquesta existeix. De vegades però, el temps invertit pot arribar a ser d’un ordre de magnitud molt superior al dels mètodes aproximats, i per tant inaplicable en molts casos. Els mètodes aproximats són procediments que no garanteixen que les solucions trobades siguin òptimes però el temps de càlcul és molt inferior al dels mètodes exactes. La rapidesa del procés és tan important com la qualitat de les solucions trobades. Aquests mètodes solen ser bones opcions a problemes difícils ja que són procediments simples, basats en el sentit comú, que proporcionen bones solucions (no necessàriament òptimes) de forma fàcil i ràpida. Díaz et al. [24] defineix els mètodes aproximats o no exactes com: “Un mètode aproximat és un procediment per a resoldre un problema d’optimització ben definit mitjançant una aproximació intuïtiva, en la qual la forma de l’estructura del problema s’utilitza de forma intel·ligent per a obtenir una bona solució”. Els mètodes no exactes solen ser bones opcions enfront als exactes quan és dona alguna de les següents circumstàncies:  No existeix cap mètode exacte per a la resolució del problema.  Existeix un mètode exacte però el seu ús és massa costós. A mesura que augmenten les dimensions dels exemplars a resoldre, els procediments de resolució tendeixen a resultar intractables, doncs el temps computacional creix de forma exponencial, excedint els recursos de què es disposa.  A la indústria normalment una bona aproximació ja és suficient i no cal invertir més recursos a trobar solucions exactes. A més a més, encara que les solucions aproximades poden ser dolentes en el pitjor dels casos, aquests molt rarament es presenten a la realitat.  Són més flexibles que els mètodes exactes. Moltes vegades s’utilitzen com a part d’un altre mètode. Per exemple, per tal de proporcionar la solució inicial de partida per a aplicar altres mètodes d’optimització. Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 33 Aquest és només un exemple de com efectuar l’intercanvi de tasques però òbviament hi hauran tantes veïnes com possibilitats d’intercanvi hi hagin. S’ha de tindre en compte que la seqüència obtinguda ha de complir les relacions de precedència en tot moment. Siguin a i b dues tasques que es volen intercanviar, si a es troba abans en la seqüència que b, es podran intercanviar si: - a no és una tasca predecessora de b. - Totes les precedents de b es troben abans en la seqüència que a. - Totes les successores de a es troben després en la seqüència que b. Aquestes són les condicions que s’han imposat per realitzar el codi per generar les solucions veïnes de la solució inicial. El codi detallat es troba a l’apartat D de l’Annex. 6.2.3. Selecció de la millor veïna Un cop s’han generat totes les seqüències veïnes, s’han d’avaluar. Per tal d’avaluar una seqüència veïna, es genera una nova solució col·locant les tasques en estacions tot seguint l’ordre de prioritats de la nova seqüència amb el canvi realitzat i emplenant al màxim cada estació sense sobrepassar el temps de cicle màxim del problema. Seguint amb l’exemple proposat, a partir de la seqüència veïna extreta a partir de l’intercanvi de tasques (Figura 6.4), s’ha distribuït les tasques a les estacions tal i com es pot veure a la Taula 6.5. Estació Tasca i ti sti avi pi Temps de cada estació 1 1 6 0 0 6 13 4 7 6 6 7 2 5 1 14 6 1,8 12,78 2 2 15,8 6 2,98 6 2 18,78 18,18 2 8 6 20,78 20,78 6 3 10 5 28 26,78 5,122 12,8342 3 5 33,122 6 7,7122 4 7 3 42 40,8342 3,11658 12,11658 9 5 45,11658 45,11658 5 11 4 50,11658 50,11658 4 Taula 6.5. Càlculs per a la nova distribució de tasques a les estacions al problema Jackson. [Font. Pròpia] Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 34 Com es pot observar, amb el canvi de les tasques 3 i 5 amb el qual s’ha generat una solució veïna de la solució inicial, s’ha pogut distribuir totes les tasques en 4 estacions en comptes de en 5 estacions com ho feia la solució inicial. A continuació, a la Figura 6.5, es pot veure la nova seqüència de tasques distribuïdes en estacions (cada color correspon a una estació). Figura 6.5. Nova distribució de tasques del problema Jackson amb TC=14 i b=0,1. [Font: Pròpia] Cal remarcar però que aquesta és només una veïna que ha millorat la solució inicial. De la mateixa manera, en aquesta etapa s’han pogut trobar altres veïnes que també millorin en la mateixa proporció la solució inicial, i per tant, també s’haurien d’estudiar. Potser també que hi hagi alguna altre veïna que millores encara més la solució inicial. En aquest cas, es continuaria la cerca local per aquesta i no per la trobada anteriorment. Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 35 7. Experiència computacional 7.1. Exemplars de testeig Per tal d’avaluar el funcionament del procediment de resolució proposat s’ha realitzat una experiència computacional a partir d’un conjunt d’exemplars de testatge. L’objectiu de l’experiment és estudiar el comportament del procediment a l’hora de resoldre exemplars de diferents mides. Per dur a terme l’experimentació, s’ha escollit utilitzar el conjunt de dades de Scholl [26] per a problemes d’equilibrat de línia de muntatge simple (SALBP). S’ha decidit utilitzar aquests exemplars ja que es troben recollits amb lliure accés a la pàgina www.assembly-line-balancing.de i perquè s’han utilitzat per provar i comparar procediments en molts estudis sobre l’equilibrat de línies, podent així comparar resultats si s’escau. A més a més, aquest conjunt de dades es caracteritzen per estar compostos per una gran varietat de línies diferents el qual permet poder provar la proposta de resolució en diversos casos. Degut a que aquestes dades estan orientades per a resoldre problemes SALBP i no existeix cap banc de dades específic per estudiar el problema de línies de muntatge on es té en compte l’efecte de la deterioració, s’ha hagut de triar i afegir la dada de la taxa creixement de la deterioració b. S’estudien 5 possibilitats diferents per analitzar la incidència que té la deterioració en l’equilibrat de la línia. S’analitzen cada un dels exemplars del SALBP amb les següents possibilitats de deterioració: - b=0,1 en totes les tasques. - b=0,2 en totes les tasques. - b=0, és a dir, efecte nul de la deterioració en aquelles tasques que no tenen predecessores. I b=0,1 a les demés tasques. - b=0, és a dir, efecte nul de la deterioració en aquelles tasques que no tenen predecessores. I b=0,2 a les demés tasques. - b=nombre aleatori en cada tasca comprés entre el 0 i el 0,2, ambdós inclosos. El motiu per el qual s’han triat els valor de b=0,1 i b=0,2 i no d’altres ha sigut perquè han estat utilitzats en la literatura i per tant, facilita el poder comparar els resultats amb altres estudis si s’escau. La raó per tal qual s’han considerat les variants en les quals aquelles tasques sense predecessores tenen deterioració nul·la és perquè aquestes tasques estan disponibles en l’instant inicial i normalment són de les primeres en processar-se. Per tant, al no tindre temps d’espera no tenen perquè tindre l’efecte de la deterioració. Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 36 Com que aquests exemplars estan pensats per a resoldre problemes de tipus SALBP (i UALBP) on les durades de les tasques són deterministes, al aplicar un problema on les tasques es deterioren, en alguns casos no s’ha trobat cap combinació possible d’adjudicació de tasques degut a aquest efecte. Això és degut fonamentalment a dos motius. En primer lloc, es pot donar el cas de que segons els criteris de prioritat que segueixen les heurístiques per a l’assignació de tasques a les diferents estacions, hi hagin tasques que augmentin tan el temps d’espera que el seu propi temps de processament sigui major que el màxim temps de cicle permés. Això provoca que no hi hagi cap combinació possible d’adjudicació de tasques degut a l’efecte deterioratiu. Per tant, en aquests casos, les heurístiques proposades no són vàlides per a resoldre aquests problemes. També es possible que per característiques del problema en si, no sigui possible aplicar-li el concepte de deterioració de tasques. Això passa en problemes on per exemple, els temps de cicles són molt baixos, o on els temps de procés constants de les tasques són elevats. A quest fet fa que per molt petita que sigui la taxa de deterioració, i per tant augmenti poc el temps d’espera, les durades d’algunes tasques puguin sobrepassar igualment el temps de cicle màxim. Això també pot succeir en problemes grans on hi ha una quantitat de tasques molt elevada, ja que hi poden haver temps d’espera molt grans. En el banc de dades utilitzat això succeeix en 4 problemes que han sigut prèviament descartats (Barthold 2, Mukherje, Scholl i Wee-Mag). A la Taula 7.1 es troben recollits tots els exemplars utilitzats. La tercera columna de la taula (tmin) fa referència a la part constant del temps de procés de tasca més petita que té l’exemplar. De la mateixa manera, la quarta columna (tmax) fa referència a la part constant del temps de procés més gran. La cinquena correspon a l’interval en el qual es troben els temps de cicle de cada variant de l’exemplar, ambdós inclosos. La sisena columna indica la quantitat d’exemplars que té cada problema, és a dir, la quantitat de variants amb un temps de cicle i una taxa de deterioració diferent cada un. I per últim, la setena columna, indica el percentatge de cada problema que s’ha trobat solució afegint el concepte de deterioració de les tasques. En total, hi ha 895 exemplars. Aquests exemplars, tal com ja s’ha indicat, s’han creat a partir dels 179 exemplars del SALBP combinats amb les 5 possibles taxes de deterioració. Per cada exemplar s’ha trobat una solució per cada una de les 12 heurístiques, amb les quals se li han aplicat l’optimització. Del total, s’han trobat solució factible de 670 exemplars. Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 37 Problema Número de Tasques tmin tmax Interval de TC Exemplars % d’exemplars amb solució Mertens 7 1 6 6-18 30 83,33 Bowman 8 3 17 20 5 100 Jaeschke 9 1 6 6-18 25 80 Mansoor 11 2 45 48-94 15 100 Jackson 11 1 7 7-21 30 83,33 Mitchell 21 1 13 14-39 30 100 Roszieg 25 1 13 14-32 30 100 Heskiaoff 28 1 108 138-342 30 100 Buxey 29 1 25 27-54 35 100 Sawyer 30 1 25 25-75 45 88,89 Lutz1 32 100 1400 1414-2828 30 100 Gunther 35 1 40 41-81 35 85,71 Kilbridge 45 3 55 56-184 50 80 Hahn 53 40 1775 2004-4676 25 100 Warnecke 58 7 53 54-111 80 31,25 Tonge 70 1 156 160-527 80 62,50 Arcus1 83 233 3691 3786-10816 80 100 Lutz3 89 1 74 75-150 60 75 Lutz2 89 1 10 11-21 55 36,36 Arcus2 111 10 5689 5755-17067 85 41,18 Barthold 148 3 383 403-805 40 87,50 Total d’exemplars: 895 Taula 7.1. Exemplars utilitzats per a la experiència computacional [Font. Pròpia] Per tal d’avaluar prèviament els algorismes utilitzats, s’ha resolt el problema sense l’efecte de la deterioració amb tots els exemplars de testeig del SALBP (excepte els 4 problemes que s’han destartat prèviament). Per tant, s’ha resolt un SALBP-1. Això pot donar una idea de l’efectivitat de cada heurística sense que es vegi afectada per el deteriorament. Per avaluar els resultats obtinguts, s’han utilitzat els valors òptims del nombre d’estacions de cada exemplar del problema del SALBP-1 provinents del banc de dades. Aquests valors s’han utilitzat com a fites per tal de comparar amb els resultats. Dels 2148 exemplars avaluats en aquesta simulació (179 problemes per les 12 heurístiques), s’han obtingut 1336 solucions òptimes, el que representa el 62,20% de tota la mostra. Els resultats es troben a l’apartat B de l’Annex. Els codis dels algorismes han estat programats en Python i han sigut executats amb un ordinador amb processador Intel Core i7 de 2.6GHz amb el sistema operatiu Ubuntu 16.04 LTS. Tots els codis utilitzats es poden trobar a l’apartat D de l’Annex. Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 38 Els temps d’execució per cada un dels algorismes es troben a l’apartat A de l’Annex, on el temps màxim ha estat d’uns 17 segons. 7.2. Anàlisis de resultats Com que per a la resolució d’aquest problema s’han fer servir procediments heurístics i per tant no es garanteixen trobar solucions òptimes, cal mesurar la qualitat d’aquests mètodes utilitzats per tal de determinar la seva validesa. Per avaluar el funcionament dels procediments dissenyats i per comparar-los entre ells s’utilitzen les següents mesures:  Comparació amb una fita. Com que es desconeixen els valors òptims d’aquest problema, el que es pot fer és comparar les solucions obtingudes de cada heurística amb fites. Les fites amb les quals s’han comparat provenen del banc de dades que s’ha utilitzat i corresponen al mínim d’estacions que es pot donar per cada exemplar. Cal destacar però, que aquestes fites corresponen al mínim d’estacions al qual es pot arribar en una distribució de tasques del problema convencional (SALBP-1), és a dir, sense tenir en compte l’efecte de la deterioració. En cap cas aquests valors han de ser els valors òptims en aquesta variants del problema ja que en alguns casos arribar a aquesta solució és inassolible degut a l’efecte deterioratiu. El que si que es pot assegurar es que aquells exemplars que tenen aquests valors, han arribat a la solució òptima, però no es pot assegurar que aquells valors que no hi han arribat no siguin òptims. A la Taula 7.2 s’observa el nombre de vegades que cada heurística aplicada per trobar la solució inicial assoleix el valor de la fita. Tot i que els valors obtinguts són baixos comparats amb la mostra de la qual es parteix no es pot afirmar que el mètode aplicat sigui poc efectiu per la raó anteriorment exposada. D’aquestes dades es poden treure conclusions sobre les regles de prioritat que sembla que ajustin millor el problema, la qual sembla ser l’heurística 5 que correspon a ordenar les tasques segons el mínim temps de procés de la tasca i de les seves predecessores ponderat pel temps de cicle. Tot i això, no hi ha una diferència gaire significativa entre les altres heurístiques. A la Taula 7.3 es troben el nombre de vegades que l’optimització assoleix el valor de fita. S’observa que les versions que més han millorat han sigut en aquelles en que la taxa de deterioració és b=0,2 i la combinació de b=0,2 i b=0, mentre que les altres versions no s’aprecien una diferència gaire notable. Cal destacar que les versions on s’ha donat una millora significativa són també les que es partien d’una solució pitjor. Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 39 H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 H12 b=0,1 3 8 3 7 11 3 4 8 8 3 8 2 b=0,2 1 2 2 3 4 1 2 3 3 1 2 1 b=0,1 i b=0 3 8 3 8 11 3 4 8 13 3 8 2 b=0,2 i b=0 1 3 2 2 6 1 2 3 6 1 3 1 b aleatòria 3 12 4 9 8 3 6 9 8 4 10 3 Taula 7.2: Nombre de vegades que cada heurística inicial arriba al valor de la fita. [Font: Pròpia] H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 H12 b=0,1 4 10 4 8 11 4 6 9 10 4 10 3 b=0,2 4 9 4 6 10 4 6 7 9 4 10 3 b=0,1 i b=0 4 10 4 9 11 4 6 9 15 4 10 3 b=0,2 i b=0 4 9 4 8 10 4 6 8 12 4 9 3 b aleatòria 4 14 4 9 8 4 6 9 8 5 11 4 Taula 7.3: Nombre de vegades que cada optimització arriba al valor de la fita. [Font: Pròpia]  Nombre de vegades que cada procediment ha obtingut la millor solució per cada variant del problema. A la Taula 7.4 es pot observar quantes vegades cada heurística utilitzada per obtenir les solucions inicials han obtingut la millor solució. Cal tindre en compte que la millor solució en cap cas vol dir que sigui la solució òptima. Es pot veure que la tendència es similars entre les variants amb taxa de deterioració b=0,1 i el que utilitza b=0 per les tasques sense precedents i b=0,1 per les demés. Es pot apreciar una lleugera millora per aquesta última variant, fet que resulta lògic ja que si no s’aplica deterioració en algunes tasques, el temps de procés total tendeix a disminuir. Aquesta mateixa tendència també es troba entre la variant amb taxa de deterioració b=0,2 i la de b=0 per les primeres tasques i b=0,2 per la resta de tasques, també amb una petita millora per aquesta última. També es pot observar que s’han obtingut resultats notablement millors amb la taxa de deterioració mes baix com ja s’esperava. En quant a la Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 40 variant de taxa b aleatòria s’han obtingut resultats millor que aquells amb b=0,2 però pitjors que amb b=0,1. A l’hora de comparar entre heurístiques, en el cas de les variant amb b=0,1 destaca per sobre de les demés l’H5. En quant a les variants amb b=0,2, es poden destacar en la mateixa mesura l’H2 i l’H9 corresponents respectivament a les regles de prioritat de màxim temps de procés de tasca i màxim temps de procés tasca i de les seves successores. A la Taula 7.5 es troben les vegades que l’optimització local ha trobat les millors solucions. Es pot observar, que no hi ha millores gaire notables respecte als resultats inicials recollits a la Taula 7.4. Les variants que més han millorat els resultats han sigut les de b=0,2. Tot i així, com que en aquests casos hi ha més marge de millora, segueixen obtenint millors resultats aquells amb taxa de deterioració més baix. A la Figura 7.1 es pot veure representat en un gràfic clarament on els màxims es troben en les heurístiques H2, H5, H9 i H11, fet que indica que aquestes heurístiques permeten trobar millors solucions. H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 H12 b=0,1 15 52 18 28 76 15 22 43 50 15 49 16 b=0,2 9 16 10 16 31 10 11 18 29 10 15 6 b=0,1 i b=0 16 57 16 28 72 16 21 41 57 15 51 17 b=0,2 i b=0 8 17 11 13 30 8 10 16 31 10 15 7 b aleatòria 14 54 14 27 45 15 20 38 47 17 45 9 Taula 7.4: Nombre de vegades que cada heurística inicial troba la millor solució. [Font: Pròpia] H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 H12 b=0.1 18 52 19 32 82 17 25 47 55 18 55 18 b=0.2 14 24 13 19 38 14 16 27 32 13 23 10 b=0 i b=0.1 16 56 16 28 74 16 20 39 58 16 56 16 b=0 i b=0.2 13 24 13 24 39 13 13 27 38 14 24 9 b aleatòria 16 57 14 27 47 17 20 38 47 18 46 10 Taula 7.5: Nombre de vegades que cada optimització troba la millor solució. [Font: Pròpia] Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 41 Figura 7.1: Gràfic representatiu del nombre de vegades que l’optimització assoleix la millor solució per cada heurística. [Font: Pròpia]  Millora de l’optimització local: Per estudiar més a fons l’efecte del procés de millora, s’han recollit a la Taula 7.6 el nombre d’exemplars que l’optimització local millora respecte a la solució inicial. Per tots els casos es por observar una clara superioritat de l’heurística 5 front les demés, seguida per les H2, H8, H9 i H11. H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 H12 b=0,1 8 10 6 9 26 8 11 12 10 5 13 6 b=0,2 9 17 9 13 30 9 11 26 26 9 18 9 b=0,1 i b=0 5 10 3 8 22 5 5 8 8 2 11 4 b=0,2 i b=0 9 19 9 19 34 9 9 23 26 9 17 8 b aleatòria 2 4 3 5 15 4 3 6 7 1 10 2 Taula 7.6: Nombre d’exemplars que l’optimització local millora. [Font: Pròpia] 0 10 20 30 40 50 60 70 80 90 H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 H12 b=0.1 b=0.2 b=0.1 i b=0 b=0.2 i b=0 b aleatori Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 42  Mitjana del nombre d’estacions. Es tracta de fer la mitjana del nombre d’estacions de les solucions obtingudes per cada procediment i per cada exemplars de testeig. Aquest mètode d’anàlisi permet comparar lo bones que poden ser les diferents heurístiques. Com que no totes les heurístiques donen solució a la mateixa quantitat d’exemplars ni als mateixos exemplars en alguns casos (a la Taula 7.1 de l’apartat anterior mostra el percentatge d’exemplars que les heurístiques han trobat solució), només s’ha calculat la mitjana d’estacions per a aquells exemplars que totes les heurístiques troben solució. D’aquesta manera, s’evita trobar resultats confusos ja que podria ser que l’heurística més bona trobes més quantitat de resultats per a exemplars amb nombres d’estacions elevats. A l’hora de fer la mitjana i comparar-la amb una heurística pitjor que només trobés solucions per a exemplars amb poques estacions, aquesta última tindria una mitjana inferior que l’heurística més bona, el que portaria a trobar conclusions errònies. Per aquesta mateixa raó també, en aquest cas només es comparen les heurístiques amb taxa de deterioració de b=0,1 i la convinació de b=0,1 i b=0, ja que la quantitat d’exemplars que la versió amb taxa de deterioració b=0,1 és molt més elevada a la que es troba amb b=0,2 i impossibilita fer una comparació entre elles. A la Taula 7.7 es troben les mitjanes del nombre d’estacions per cada heurística. Es pot observar que les mitjanes més baixes coincideixen amb les heurístiques que amb els previs mètodes d’avaluació efectuats han semblat ser les més efectives. Aquestes són, ordenades per major eficàcia, les H5, H8, H2, H11 i H9. En quant al procés d’optimització, els resultats obtinguts (recollits a la Taula 7.8) són equivalents als de les solucions inicials. Es pot observar una disminució de la mitjana del nombre d’estacions amb l’optimització local respecte les solucions inicials. Per últim es pot realitzar una comparació entre les mitjanes de les heurístiques amb la mitjana del nombre d’estacions de la fita. La mitjana dels valors òptims del nombre d’estacions dels exemplars considerats en aquest càlcul és de 4,889. Es pot observar que només hi ha una estació de diferència entre la mitjana dels valors òptims del problema del SALBP-1 i la mitjana de la millor heurística trobada, l’H5. H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 H12 b=0.1 6,806 5,972 6,583 6,056 5,833 6,806 6,500 5,972 6,028 6,750 6,000 6,722 b=0 i b=0.1 6,750 5,917 6,472 5,972 5,861 6,750 6,417 5,972 5,833 6,583 6,000 6,583 Taula 7.7: Mitjana del nombre d’estacions de les solucions inicials. [Font: Pròpia] Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 49 Annex B. Solucions inicials de l’experiència computacional Solucions incials per a b=0,1. Precedence graph c m* H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 H12 Arcus1 3786 21 28 Arcus1 3985 20 28 Arcus1 4206 19 25 27 Arcus1 4454 18 27 25 26 23 Arcus1 4732 17 26 23 23 21 Arcus1 5048 16 25 21 21 19 Arcus1 5408 15 22 19 19 17 Arcus1 5824 14 20 18 17 17 Arcus1 5853 14 20 17 17 17 Arcus1 6309 13 18 17 16 16 Arcus1 6842 12 18 17 15 15 14 Arcus1 6883 12 18 16 15 15 14 Arcus1 7571 11 14 15 13 14 12 15 Arcus1 8412 10 14 13 12 12 11 15 Arcus1 8898 9 14 13 11 11 11 14 Arcus1 10816 8 10 10 9 9 9 10 Arcus2 8847 18 27 Arcus2 9400 17 25 28 Arcus2 10027 16 23 Arcus2 10743 15 21 Arcus2 11378 14 19 25 Arcus2 11570 13 18 26 Arcus2 17067 9 20 13 17 Barthold 434 13 Barthold 470 12 Barthold 513 11 Barthold 564 10 Barthold 626 9 Barthold 705 8 Barthold 805 7 Bowman 20 5 5 5 5 5 5 5 5 5 5 5 5 6 Buxey 27 13 Buxey 30 12 16 Buxey 33 11 13 15 15 13 Buxey 36 10 12 13 13 12 Buxey 41 8 13 11 Buxey 47 7 12 9 10 12 12 9 9 Buxey 54 7 10 9 9 10 9 10 8 9 Gunther 44 12 18 18 Gunther 49 11 16 15 16 15 16 15 16 15 16 Gunther 54 9 15 15 15 15 15 13 14 13 15 15 15 Gunther 61 9 12 11 12 12 12 12 13 12 11 12 11 12 Gunther 69 8 11 11 11 10 10 11 10 10 11 11 11 11 Gunther 81 7 9 8 9 8 9 9 9 8 8 9 8 9 Hahn 2004 8 10 9 10 9 9 10 9 9 9 10 9 10 Hahn 2338 7 11 8 8 8 8 11 10 8 8 10 8 10 Hahn 2806 6 9 6 7 6 6 9 8 6 6 8 6 8 Hahn 3507 5 6 5 6 5 5 6 6 5 5 6 5 6 Hahn 4676 4 5 4 5 4 4 5 5 4 4 5 4 5 Heskiaoff 138 8 Heskiaoff 205 5 8 11 Heskiaoff 216 5 12 8 12 10 Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 50 Heskiaoff 256 4 12 11 7 12 11 7 12 Heskiaoff 324 4 12 11 7 5 12 12 7 6 11 12 Heskiaoff 342 3 12 9 11 7 5 12 11 7 6 12 9 12 Jackson 9 6 9 9 8 8 9 8 8 9 9 9 8 Jackson 10 5 7 7 6 6 6 7 7 6 7 7 7 7 Jackson 13 4 6 5 5 5 5 6 5 5 5 6 5 6 Jackson 14 4 5 5 5 5 5 5 5 5 5 5 5 5 Jackson 21 3 3 3 3 3 3 3 3 3 3 3 3 3 Jaeschke 7 7 8 8 8 8 8 8 8 8 8 8 8 8 Jaeschke 8 6 7 7 7 7 7 7 7 7 7 7 7 7 Jaeschke 10 4 5 5 5 5 5 5 5 5 5 5 5 5 Jaeschke 18 3 3 3 3 3 3 3 3 3 3 3 3 3 Kilbridge 56 10 Kilbridge 69 8 14 14 Kilbridge 79 7 13 Kilbridge 92 6 11 10 13 Kilbridge 110 6 10 9 8 9 10 Kilbridge 111 5 10 9 8 9 10 Kilbridge 138 4 8 10 6 8 9 8 Kilbridge 184 3 10 5 11 7 5 10 8 6 6 10 5 9 Lutz1 1414 11 14 13 14 Lutz1 1572 10 12 12 11 13 12 Lutz1 1768 9 10 11 11 11 11 10 Lutz1 2020 8 11 9 11 9 9 11 9 10 11 9 11 Lutz1 2357 7 9 8 8 8 8 9 8 8 9 9 8 8 Lutz1 2828 6 8 6 8 7 6 8 8 6 7 8 6 8 Lutz2 18 28 41 41 Lutz2 19 26 Lutz2 20 25 36 Lutz2 21 24 Lutz3 87 20 Lutz3 92 19 24 Lutz3 97 18 23 Lutz3 103 17 22 Lutz3 110 15 21 Lutz3 118 14 18 20 Lutz3 127 14 21 17 21 Lutz3 137 13 16 16 15 17 17 Lutz3 150 12 14 16 14 15 15 14 19 Mansoor 48 4 5 5 5 Mansoor 62 3 4 4 4 4 4 4 4 4 4 4 4 4 Mansoor 94 2 3 3 3 3 3 3 3 3 3 3 3 3 Mertens 7 5 6 6 6 6 6 6 6 6 6 Mertens 8 5 6 6 6 6 6 6 6 6 6 6 6 6 Mertens 10 3 5 4 5 5 5 5 4 4 4 5 4 5 Mertens 15 2 3 3 3 3 3 3 3 3 3 3 3 3 Mertens 18 2 3 2 3 3 2 3 2 3 2 3 2 3 Mitchell 14 8 10 10 10 11 10 Mitchell 15 8 10 10 10 10 11 10 10 10 Mitchell 21 5 7 6 7 7 7 7 8 7 7 7 6 7 Mitchell 26 5 6 6 6 5 5 6 6 5 5 6 6 6 Mitchell 35 3 4 4 4 4 4 4 4 4 4 4 4 4 Mitchell 39 3 4 4 4 4 3 4 4 4 4 4 4 4 Roszieg 14 10 14 13 14 13 14 14 13 14 14 14 13 Roszieg 16 8 11 12 11 12 11 11 Roszieg 18 8 10 9 10 9 9 10 10 10 10 10 10 10 Roszieg 21 6 9 8 9 8 8 9 8 8 9 9 8 9 Roszieg 25 6 8 7 7 7 6 8 7 7 7 7 7 8 Roszieg 32 4 5 5 5 5 5 5 5 5 5 5 5 5 Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 51 Sawyer 27 13 18 Sawyer 30 12 16 18 Sawyer 33 11 16 15 Sawyer 36 10 14 15 Sawyer 41 8 12 14 13 Sawyer 47 7 11 11 11 10 11 Sawyer 54 7 10 9 9 9 10 Sawyer 75 5 7 6 8 7 6 7 7 6 6 8 6 7 Tonge 176 21 31 31 Tonge 234 16 23 23 Tonge 251 14 23 23 Tonge 270 14 22 Tonge 293 13 19 19 19 Tonge 320 11 19 17 19 Tonge 364 10 15 14 15 Tonge 410 9 13 13 13 Tonge 468 8 11 12 15 11 Tonge 527 7 10 10 15 10 Warnecke 82 20 Warnecke 92 17 Warnecke 97 17 Warnecke 104 15 Warnecke 111 14 Solucions incials per a b=0,2. Precedence graph c m* H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 H12 Arcus1 3786 21 Arcus1 3985 20 Arcus1 4206 19 Arcus1 4454 18 Arcus1 4732 17 Arcus1 5048 16 Arcus1 5408 15 Arcus1 5824 14 21 27 Arcus1 5853 14 21 Arcus1 6309 13 21 23 17 Arcus1 6842 12 18 21 16 Arcus1 6883 12 18 21 16 Arcus1 7571 11 16 20 13 Arcus1 8412 10 15 16 13 Arcus1 8898 9 15 15 12 Arcus1 10816 8 11 13 10 Arcus2 8847 18 Arcus2 9400 17 Arcus2 10027 16 Arcus2 10743 15 Arcus2 11378 14 Arcus2 11570 13 Arcus2 17067 9 Barthold 434 13 Barthold 470 12 Barthold 513 11 Barthold 564 10 Barthold 626 9 Barthold 705 8 Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 52 Barthold 805 7 Bowman 20 5 6 6 6 6 5 6 6 6 6 6 6 6 Buxey 27 13 Buxey 30 12 Buxey 33 11 Buxey 36 10 Buxey 41 8 Buxey 47 7 Buxey 54 7 10 9 Gunther 44 12 Gunther 49 11 Gunther 54 9 Gunther 61 9 Gunther 69 8 13 Gunther 81 7 Hahn 2004 8 10 Hahn 2338 7 10 10 9 9 9 9 10 10 Hahn 2806 6 8 10 7 7 8 7 8 Hahn 3507 5 6 6 6 8 6 6 6 Hahn 4676 4 5 7 4 4 7 4 4 5 8 Heskiaoff 138 8 Heskiaoff 205 5 Heskiaoff 216 5 Heskiaoff 256 4 Heskiaoff 324 4 7 Heskiaoff 342 3 6 Jackson 9 6 10 Jackson 10 5 8 8 7 8 8 Jackson 13 4 6 6 6 6 6 6 6 6 6 Jackson 14 4 5 5 5 5 6 5 5 5 5 5 5 5 Jackson 21 3 4 3 3 3 3 4 3 3 3 4 3 4 Jaeschke 7 7 8 8 8 8 8 8 8 8 8 8 Jaeschke 8 6 7 7 7 7 7 7 7 7 7 7 Jaeschke 10 4 5 6 5 5 5 5 5 5 6 5 6 5 Jaeschke 18 3 3 3 3 3 3 3 3 3 3 3 3 3 Kilbridge 56 10 Kilbridge 69 8 Kilbridge 79 7 Kilbridge 92 6 Kilbridge 110 6 Kilbridge 111 5 Kilbridge 138 4 Kilbridge 184 3 7 Lutz1 1414 11 Lutz1 1572 10 Lutz1 1768 9 12 12 Lutz1 2020 8 11 10 Lutz1 2357 7 10 9 9 9 10 10 Lutz1 2828 6 7 7 7 8 8 7 Lutz2 18 28 Lutz2 19 26 Lutz2 20 25 Lutz2 21 24 Lutz3 87 20 Lutz3 92 19 Lutz3 97 18 Lutz3 103 17 Lutz3 110 15 Lutz3 118 14 Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 53 Lutz3 127 14 Lutz3 137 13 Lutz3 150 12 Mansoor 48 4 6 6 6 Mansoor 62 3 5 4 5 5 5 4 5 4 4 Mansoor 94 2 3 3 4 3 3 3 3 3 3 4 3 4 Mertens 7 5 Mertens 8 5 Mertens 10 3 5 5 5 4 5 5 Mertens 15 2 4 3 3 3 3 4 3 3 3 4 3 4 Mertens 18 2 3 3 3 3 3 3 3 3 3 3 3 3 Mitchell 14 8 12 13 12 Mitchell 15 8 Mitchell 21 5 8 8 9 9 Mitchell 26 5 8 6 6 8 Mitchell 35 3 5 5 5 5 4 5 6 5 5 5 5 6 Mitchell 39 3 4 4 4 5 4 4 4 5 4 4 4 4 Roszieg 14 10 Roszieg 16 8 13 Roszieg 18 8 10 11 Roszieg 21 6 10 9 9 10 9 10 Roszieg 25 6 9 8 9 7 9 8 8 8 9 9 Roszieg 32 4 7 5 7 7 6 7 7 7 6 7 7 7 Sawyer 27 13 Sawyer 30 12 Sawyer 33 11 Sawyer 36 10 Sawyer 41 8 Sawyer 47 7 Sawyer 54 7 Sawyer 75 5 9 9 Tonge 176 21 Tonge 234 16 Tonge 251 14 Tonge 270 14 Tonge 293 13 Tonge 320 11 Tonge 364 10 Tonge 410 9 Tonge 468 8 Tonge 527 7 Warnecke 82 20 Warnecke 92 17 Warnecke 97 17 Warnecke 104 15 Warnecke 111 14 Solucions incials per a b=0,1 i b=0. Precedence graph c m* H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 H12 Arcus1 3786 21 28 Arcus1 3985 20 28 Arcus1 4206 19 25 27 Arcus1 4454 18 27 25 26 23 Arcus1 4732 17 26 23 23 21 Arcus1 5048 16 25 21 21 19 Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 54 Arcus1 5408 15 22 19 19 17 Arcus1 5824 14 20 18 17 17 Arcus1 5853 14 20 17 17 17 Arcus1 6309 13 18 17 16 16 Arcus1 6842 12 18 17 15 15 14 Arcus1 6883 12 18 16 15 15 14 Arcus1 7571 11 14 15 13 14 12 15 Arcus1 8412 10 14 13 12 12 11 15 Arcus1 8898 9 14 13 11 11 11 14 Arcus1 10816 8 10 10 9 9 9 10 Arcus2 8847 18 27 Arcus2 9400 17 25 28 Arcus2 10027 16 23 Arcus2 10743 15 21 Arcus2 11378 14 19 25 Arcus2 11570 13 18 26 Arcus2 17067 9 20 13 17 Barthold 434 13 20 21 Barthold 470 12 18 18 Barthold 513 11 16 Barthold 564 10 15 16 Barthold 626 9 13 16 13 Barthold 705 8 12 16 16 11 Barthold 805 7 10 12 14 14 10 Bowman 20 5 5 5 5 5 5 5 5 5 5 5 5 6 Buxey 27 13 16 Buxey 30 12 16 Buxey 33 11 13 15 14 13 Buxey 36 10 13 Buxey 41 8 13 10 Buxey 47 7 11 10 9 11 Buxey 54 7 10 9 9 10 10 10 7 9 10 Gunther 44 12 18 18 Gunther 49 11 16 14 15 16 14 14 Gunther 54 9 14 14 14 15 14 13 14 13 14 14 13 Gunther 61 9 13 11 12 11 12 13 13 12 10 12 11 12 Gunther 69 8 12 10 11 10 10 12 10 10 10 11 10 11 Gunther 81 7 9 8 9 8 9 9 9 8 8 9 8 9 Hahn 2004 8 9 9 10 9 10 9 9 10 9 9 9 9 Hahn 2338 7 11 8 9 8 8 11 10 8 8 10 8 10 Hahn 2806 6 9 6 8 6 6 9 8 6 6 8 6 8 Hahn 3507 5 7 5 6 5 5 7 6 5 5 6 5 6 Hahn 4676 4 5 4 5 4 4 5 5 4 4 5 4 5 Heskiaoff 138 8 Heskiaoff 205 5 12 8 12 12 Heskiaoff 216 5 12 11 8 11 11 12 Heskiaoff 256 4 12 10 7 10 8 12 Heskiaoff 324 4 11 10 7 5 11 11 7 6 11 10 11 Heskiaoff 342 3 12 9 11 7 5 12 11 7 6 11 9 11 Jackson 9 6 9 9 8 8 9 8 8 9 9 9 8 Jackson 10 5 7 7 6 6 6 7 7 6 7 7 7 7 Jackson 13 4 6 5 5 5 5 6 5 5 5 6 5 6 Jackson 14 4 5 5 5 5 5 5 5 5 5 5 5 5 Jackson 21 3 3 3 3 3 3 3 3 3 3 3 3 3 Jaeschke 7 7 8 8 8 8 8 8 8 8 8 8 8 8 Jaeschke 8 6 7 7 7 7 7 7 7 7 7 7 7 7 Jaeschke 10 4 5 5 5 5 5 5 5 5 5 5 5 5 Jaeschke 18 3 3 3 3 3 3 3 3 3 3 3 3 3 Kilbridge 56 10 15 15 Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 55 Kilbridge 69 8 14 14 Kilbridge 79 7 12 12 12 Kilbridge 92 6 11 11 11 11 Kilbridge 110 6 9 9 8 9 9 9 Kilbridge 111 5 9 8 8 9 9 9 Kilbridge 138 4 11 7 9 6 11 9 8 7 7 11 Kilbridge 184 3 9 5 8 6 5 9 7 6 5 9 5 8 Lutz1 1414 11 13 14 14 14 14 13 Lutz1 1572 10 12 11 12 12 11 12 11 12 12 11 12 Lutz1 1768 9 12 10 11 11 11 12 11 11 10 11 10 11 Lutz1 2020 8 11 9 11 9 9 11 10 9 9 11 9 10 Lutz1 2357 7 8 8 8 8 8 8 8 8 9 9 8 8 Lutz1 2828 6 7 6 7 6 6 7 7 6 6 7 6 7 Lutz2 18 28 41 41 Lutz2 19 26 38 Lutz2 20 25 Lutz2 21 24 Lutz3 87 20 25 25 Lutz3 92 19 24 Lutz3 97 18 23 Lutz3 103 17 22 Lutz3 110 15 21 Lutz3 118 14 18 18 18 Lutz3 127 14 21 17 21 Lutz3 137 13 18 15 16 Lutz3 150 12 16 18 14 16 19 Mansoor 48 4 5 5 5 5 5 5 5 5 4 5 5 5 Mansoor 62 3 4 4 4 4 4 4 4 4 4 4 4 4 Mansoor 94 2 3 3 3 3 3 3 3 3 2 3 3 3 Mertens 7 5 6 6 6 6 6 6 6 6 6 Mertens 8 5 6 6 6 6 6 6 6 6 6 6 6 6 Mertens 10 3 5 4 5 5 5 5 4 4 4 5 4 5 Mertens 15 2 3 3 3 3 3 3 3 3 3 3 3 3 Mertens 18 2 3 2 3 3 2 3 2 3 2 3 2 3 Mitchell 14 8 10 10 10 11 10 Mitchell 15 8 10 10 10 10 11 10 10 10 Mitchell 21 5 7 6 7 7 7 7 8 7 7 7 6 7 Mitchell 26 5 6 6 6 5 5 6 6 5 5 6 6 6 Mitchell 35 3 4 4 4 4 4 4 4 4 4 4 4 4 Mitchell 39 3 4 4 4 4 3 4 4 4 4 4 4 4 Roszieg 14 10 14 13 14 13 14 14 13 14 14 14 13 Roszieg 16 8 11 10 11 12 10 11 11 11 11 11 12 11 Roszieg 18 8 10 9 10 9 9 10 10 10 10 10 10 10 Roszieg 21 6 8 7 8 8 8 8 8 7 8 8 9 8 Roszieg 25 6 8 7 7 7 6 8 7 7 7 7 7 8 Roszieg 32 4 5 5 5 5 5 5 5 5 5 5 5 5 Sawyer 27 13 17 Sawyer 30 12 16 17 Sawyer 33 11 15 15 13 Sawyer 36 10 14 15 11 Sawyer 41 8 12 12 11 Sawyer 47 7 11 11 10 9 11 Sawyer 54 7 9 9 8 8 8 9 Sawyer 75 5 7 6 7 7 6 7 6 6 5 7 6 7 Tonge 176 21 Tonge 234 16 Tonge 251 14 Tonge 270 14 20 Tonge 293 13 19 Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 56 Tonge 320 11 17 Tonge 364 10 14 Tonge 410 9 15 13 15 Tonge 468 8 10 11 10 Tonge 527 7 11 10 11 Warnecke 82 20 27 Warnecke 92 17 Warnecke 97 17 23 23 Warnecke 104 15 22 Warnecke 111 14 21 20 Solucions incials per a b=0,2 i b=0. Precedence graph c m* H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 H12 Arcus1 3786 21 Arcus1 3985 20 Arcus1 4206 19 Arcus1 4454 18 Arcus1 4732 17 Arcus1 5048 16 Arcus1 5408 15 Arcus1 5824 14 21 27 Arcus1 5853 14 21 Arcus1 6309 13 21 23 17 Arcus1 6842 12 18 21 16 Arcus1 6883 12 18 21 16 Arcus1 7571 11 16 20 13 Arcus1 8412 10 15 16 13 Arcus1 8898 9 15 15 12 Arcus1 10816 8 11 13 10 Arcus2 8847 18 Arcus2 9400 17 Arcus2 10027 16 Arcus2 10743 15 Arcus2 11378 14 Arcus2 11570 13 Arcus2 17067 9 Barthold 434 13 Barthold 470 12 Barthold 513 11 Barthold 564 10 Barthold 626 9 Barthold 705 8 Barthold 805 7 Bowman 20 5 6 6 6 6 5 6 6 6 6 6 6 6 Buxey 27 13 Buxey 30 12 Buxey 33 11 14 Buxey 36 10 Buxey 41 8 Buxey 47 7 11 Buxey 54 7 Gunther 44 12 Gunther 49 11 Gunther 54 9 Gunther 61 9 Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 57 Gunther 69 8 11 13 12 11 Gunther 81 7 10 Hahn 2004 8 11 10 10 11 Hahn 2338 7 9 10 9 9 8 8 9 Hahn 2806 6 8 7 8 8 8 8 Hahn 3507 5 6 10 6 5 8 6 5 6 Hahn 4676 4 4 7 5 4 7 4 4 4 8 Heskiaoff 138 8 Heskiaoff 205 5 Heskiaoff 216 5 Heskiaoff 256 4 Heskiaoff 324 4 6 Heskiaoff 342 3 6 Jackson 9 6 10 Jackson 10 5 8 8 7 8 8 Jackson 13 4 6 6 6 6 6 6 6 6 6 Jackson 14 4 5 5 5 5 6 5 5 5 5 5 5 5 Jackson 21 3 4 3 3 3 3 4 3 3 3 4 3 4 Jaeschke 7 7 8 8 8 8 8 8 8 8 8 8 Jaeschke 8 6 7 7 7 7 7 7 7 7 7 7 Jaeschke 10 4 5 6 5 5 5 5 5 5 6 5 6 5 Jaeschke 18 3 3 3 3 3 3 3 3 3 3 3 3 3 Kilbridge 56 10 Kilbridge 69 8 Kilbridge 79 7 Kilbridge 92 6 Kilbridge 110 6 Kilbridge 111 5 Kilbridge 138 4 9 Kilbridge 184 3 7 Lutz1 1414 11 16 15 15 Lutz1 1572 10 12 12 12 Lutz1 1768 9 11 12 12 12 11 Lutz1 2020 8 10 11 11 11 10 Lutz1 2357 7 9 9 9 8 9 Lutz1 2828 6 7 7 6 7 9 9 7 9 Lutz2 18 28 Lutz2 19 26 Lutz2 20 25 Lutz2 21 24 Lutz3 87 20 Lutz3 92 19 Lutz3 97 18 Lutz3 103 17 Lutz3 110 15 Lutz3 118 14 Lutz3 127 14 Lutz3 137 13 Lutz3 150 12 Mansoor 48 4 5 5 5 5 5 5 5 5 4 5 5 5 Mansoor 62 3 5 4 4 5 5 5 4 5 4 4 4 4 Mansoor 94 2 3 3 3 3 3 3 3 3 2 3 3 3 Mertens 7 5 Mertens 8 5 Mertens 10 3 5 5 5 4 5 5 Mertens 15 2 4 3 3 3 3 4 3 3 3 4 3 4 Mertens 18 2 3 3 3 3 3 3 3 3 3 3 3 3 Mitchell 14 8 12 13 12 Mitchell 15 8 Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 58 Mitchell 21 5 8 8 9 9 Mitchell 26 5 8 6 6 8 Mitchell 35 3 5 5 5 5 4 5 6 5 5 5 5 6 Mitchell 39 3 4 4 4 5 4 4 4 5 4 4 4 4 Roszieg 14 10 Roszieg 16 8 12 Roszieg 18 8 10 11 Roszieg 21 6 9 9 9 9 9 9 Roszieg 25 6 9 8 9 9 8 9 8 7 8 9 9 Roszieg 32 4 7 6 7 7 6 7 7 7 6 7 7 7 Sawyer 27 13 Sawyer 30 12 Sawyer 33 11 Sawyer 36 10 Sawyer 41 8 Sawyer 47 7 Sawyer 54 7 11 10 Sawyer 75 5 8 9 6 Tonge 176 21 Tonge 234 16 Tonge 251 14 Tonge 270 14 Tonge 293 13 Tonge 320 11 Tonge 364 10 Tonge 410 9 Tonge 468 8 Tonge 527 7 14 Warnecke 82 20 Warnecke 92 17 Warnecke 97 17 Warnecke 104 15 Warnecke 111 14 Solucions incials per a b aleatòria dins l’interval [0, 0,2]. Precedence graph c m* H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 H12 Arcus1 3786 21 28 Arcus1 3985 20 26 25 Arcus1 4206 19 24 Arcus1 4454 18 24 24 Arcus1 4732 17 22 24 19 Arcus1 5048 16 19 20 18 Arcus1 5408 15 19 20 19 Arcus1 5824 14 17 17 16 Arcus1 5853 14 17 18 16 Arcus1 6309 13 16 16 16 14 Arcus1 6842 12 14 15 15 15 14 Arcus1 6883 12 16 14 14 13 Arcus1 7571 11 15 13 14 12 Arcus1 8412 10 11 13 11 12 12 Arcus1 8898 9 13 12 12 12 Arcus1 10816 8 10 10 9 9 9 10 Arcus2 8847 18 Arcus2 9400 17 Arcus2 10027 16 23 Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 65 Warnecke 60 27 29 29 30 30 34 29 30 30 30 30 29 30 Warnecke 62 27 29 29 29 30 32 29 30 30 29 29 29 30 Warnecke 65 25 27 28 29 29 31 27 28 29 29 27 28 28 Warnecke 68 24 26 26 26 27 28 26 26 27 27 26 25 26 Warnecke 71 23 24 26 24 25 27 24 25 25 25 25 25 25 Warnecke 74 22 23 25 23 24 25 23 24 25 24 23 24 24 Warnecke 78 21 21 23 22 22 25 21 23 23 22 21 22 23 Warnecke 82 20 20 21 21 21 24 20 21 22 21 21 21 21 Warnecke 86 19 19 20 19 20 23 19 20 21 20 19 20 20 Warnecke 92 17 19 19 19 19 20 19 19 19 19 19 19 19 Warnecke 97 17 17 18 18 18 18 17 18 18 17 17 18 18 Warnecke 104 15 16 16 16 17 17 16 17 16 16 16 16 17 Warnecke 111 14 15 15 15 16 16 15 16 15 16 15 15 15 Wee-Mag 28 63 63 63 63 64 65 63 64 65 64 63 63 63 Wee-Mag 29 63 63 63 63 63 64 63 64 64 63 63 63 63 Wee-Mag 30 62 63 63 63 63 64 63 64 64 62 63 63 63 Wee-Mag 31 62 63 62 63 62 63 63 63 64 62 63 62 63 Wee-Mag 32 61 61 61 61 62 62 61 61 62 62 61 61 61 Wee-Mag 33 61 61 61 61 61 61 61 61 61 61 61 61 61 Wee-Mag 34 61 61 61 61 61 61 61 61 61 61 61 61 61 Wee-Mag 35 60 60 60 60 61 61 60 61 61 61 60 60 60 Wee-Mag 36 60 60 60 60 60 60 60 60 60 60 60 60 60 Wee-Mag 37 60 60 60 60 60 60 60 60 60 60 60 60 60 Wee-Mag 38 60 60 60 60 60 60 60 60 60 60 60 60 60 Wee-Mag 39 60 60 60 60 60 60 60 60 60 60 60 60 60 Wee-Mag 40 60 60 60 60 60 60 60 60 60 60 60 60 60 Wee-Mag 41 59 59 59 59 59 60 59 60 60 59 59 59 59 Wee-Mag 42 55 55 55 55 56 58 55 57 56 56 55 55 55 Wee-Mag 43 50 51 50 51 51 50 51 52 51 52 51 50 51 Wee-Mag 45 38 41 39 41 41 42 41 42 42 43 41 39 42 Wee-Mag 46 34 36 36 37 37 39 36 38 39 40 36 37 37 Wee-Mag 47 [32,33] 33 34 34 34 36 33 35 36 37 33 33 34 Wee-Mag 49 32 33 32 33 32 33 33 33 33 33 33 32 33 Wee-Mag 50 32 32 32 32 32 33 32 33 33 32 32 32 32 Wee-Mag 52 31 32 32 32 32 33 32 32 32 32 32 31 32 Wee-Mag 54 31 31 31 31 31 32 31 32 32 31 31 31 31 Wee-Mag 56 30 31 31 31 31 31 31 31 31 31 31 31 31 Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 66 Annex C. Solucions de l’optimització local a partir de l’exeperiència computacional Solucions de l’optimització local amb b=0,1. Precedence graph c m* H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 H12 Arcus1 3786 21 28 Arcus1 3985 20 28 Arcus1 4206 19 24 26 Arcus1 4454 18 27 23 26 23 Arcus1 4732 17 25 22 22 20 Arcus1 5048 16 23 20 21 19 Arcus1 5408 15 22 18 19 17 Arcus1 5824 14 20 17 17 17 Arcus1 5853 14 20 17 17 17 Arcus1 6309 13 18 15 16 15 Arcus1 6842 12 18 17 14 15 14 Arcus1 6883 12 18 16 15 15 14 Arcus1 7571 11 14 15 13 14 12 15 Arcus1 8412 10 12 13 12 12 11 13 Arcus1 8898 9 13 13 11 11 11 13 Arcus1 10816 8 10 10 9 9 9 10 Arcus2 8847 18 26 Arcus2 9400 17 24 28 Arcus2 10027 16 22 Arcus2 10743 15 21 Arcus2 11378 14 19 24 Arcus2 11570 13 18 25 Arcus2 17067 9 18 13 17 Barthold 434 13 Barthold 470 12 Barthold 513 11 Barthold 564 10 Barthold 626 9 Barthold 705 8 Barthold 805 7 Bowman 20 5 5 5 5 5 5 5 5 5 5 5 5 6 Buxey 27 13 Buxey 30 12 16 Buxey 33 11 13 14 15 13 Buxey 36 10 12 13 13 12 Buxey 41 8 11 11 Buxey 47 7 12 9 10 12 12 9 9 Buxey 54 7 10 9 9 10 8 10 8 9 Gunther 44 12 17 17 Gunther 49 11 16 15 16 15 16 15 16 15 16 Gunther 54 9 15 15 15 14 15 13 13 13 15 15 15 Gunther 61 9 12 11 12 12 11 12 12 12 11 12 11 12 Gunther 69 8 11 10 11 10 10 11 10 10 10 11 10 11 Gunther 81 7 9 8 9 8 9 9 9 8 8 9 8 9 Hahn 2004 8 10 9 10 9 9 10 9 9 9 10 9 10 Hahn 2338 7 10 8 8 8 8 10 10 8 8 10 8 10 Hahn 2806 6 8 6 7 6 6 8 7 6 6 8 6 8 Hahn 3507 5 6 5 6 5 5 6 6 5 5 6 5 6 Hahn 4676 4 5 4 5 4 4 5 5 4 4 5 4 5 Heskiaoff 138 8 Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 67 Heskiaoff 205 5 8 11 Heskiaoff 216 5 12 7 12 8 Heskiaoff 256 4 12 9 7 12 9 7 12 Heskiaoff 324 4 12 11 7 5 12 8 7 6 11 12 Heskiaoff 342 3 12 9 8 7 4 12 9 7 6 9 9 11 Jackson 9 6 9 9 8 8 9 8 8 9 9 9 8 Jackson 10 5 6 6 6 6 6 6 7 6 7 6 6 6 Jackson 13 4 6 4 5 5 5 6 4 5 4 6 4 6 Jackson 14 4 5 4 5 5 5 5 4 5 4 5 4 5 Jackson 21 3 3 3 3 3 3 3 3 3 3 3 3 3 Jaeschke 7 7 8 8 8 8 8 8 8 8 8 8 8 8 Jaeschke 8 6 7 7 7 7 7 7 7 7 7 7 7 7 Jaeschke 10 4 5 5 5 5 5 5 5 5 5 5 5 5 Jaeschke 18 3 3 3 3 3 3 3 3 3 3 3 3 3 Kilbridge 56 10 Kilbridge 69 8 14 14 Kilbridge 79 7 13 Kilbridge 92 6 11 10 13 Kilbridge 110 6 10 9 8 9 10 Kilbridge 111 5 10 9 8 9 10 Kilbridge 138 4 8 8 6 8 9 8 Kilbridge 184 3 10 5 10 7 5 10 7 6 6 10 5 9 Lutz1 1414 11 13 13 13 Lutz1 1572 10 12 11 11 13 12 Lutz1 1768 9 10 11 11 10 11 10 Lutz1 2020 8 11 9 11 9 9 11 9 10 11 9 11 Lutz1 2357 7 8 8 8 8 8 8 8 8 9 8 8 8 Lutz1 2828 6 7 6 7 7 6 7 7 6 7 7 6 7 Lutz2 18 28 41 41 Lutz2 19 26 Lutz2 20 25 35 Lutz2 21 24 Lutz3 87 20 Lutz3 92 19 24 Lutz3 97 18 23 Lutz3 103 17 21 Lutz3 110 15 19 Lutz3 118 14 18 19 Lutz3 127 14 21 17 21 Lutz3 137 13 16 16 15 16 16 Lutz3 150 12 14 16 14 15 15 14 19 Mansoor 48 4 5 5 5 Mansoor 62 3 4 4 4 4 4 4 4 4 4 4 4 4 Mansoor 94 2 3 3 3 3 3 3 3 3 3 3 3 3 Mertens 7 5 6 6 6 6 6 6 6 6 6 Mertens 8 5 6 6 6 6 6 6 6 6 6 6 6 6 Mertens 10 3 5 4 4 4 4 5 4 4 4 5 4 4 Mertens 15 2 3 3 3 3 3 3 3 3 3 3 3 3 Mertens 18 2 2 2 2 2 2 2 2 2 2 2 2 2 Mitchell 14 8 10 10 10 11 10 Mitchell 15 8 10 10 10 10 10 10 10 10 Mitchell 21 5 7 6 7 7 6 7 7 7 7 7 6 7 Mitchell 26 5 6 6 6 5 5 6 6 5 5 6 6 6 Mitchell 35 3 4 4 4 4 4 4 4 4 4 4 4 4 Mitchell 39 3 4 4 4 4 3 4 4 4 4 4 4 4 Roszieg 14 10 13 13 14 12 13 13 13 13 14 13 13 Roszieg 16 8 11 11 11 12 11 11 Roszieg 18 8 10 9 10 9 9 10 10 10 9 10 9 10 Roszieg 21 6 9 8 9 8 8 9 8 8 9 9 8 9 Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 68 Roszieg 25 6 7 7 7 7 6 7 7 7 7 7 7 7 Roszieg 32 4 5 5 5 5 5 5 5 5 5 5 5 5 Sawyer 27 13 18 Sawyer 30 12 16 18 Sawyer 33 11 16 15 Sawyer 36 10 14 14 Sawyer 41 8 12 12 12 Sawyer 47 7 11 11 11 10 11 Sawyer 54 7 9 8 9 9 9 Sawyer 75 5 7 6 7 7 6 7 7 6 6 8 6 7 Tonge 176 21 31 31 Tonge 234 16 23 23 Tonge 251 14 23 23 Tonge 270 14 21 Tonge 293 13 19 18 19 Tonge 320 11 18 17 18 Tonge 364 10 15 14 15 Tonge 410 9 13 13 13 Tonge 468 8 11 12 15 11 Tonge 527 7 10 10 15 10 Warnecke 82 20 Warnecke 92 17 Warnecke 97 17 Warnecke 104 15 Warnecke 111 14 Solucions de l’optimització local amb b=0,2. Precedence graph c m* H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 H12 Arcus1 3786 21 Arcus1 3985 20 Arcus1 4206 19 Arcus1 4454 18 Arcus1 4732 17 Arcus1 5048 16 Arcus1 5408 15 Arcus1 5824 14 17 19 Arcus1 5853 14 17 Arcus1 6309 13 16 16 15 Arcus1 6842 12 15 15 14 Arcus1 6883 12 15 15 14 Arcus1 7571 11 13 14 12 Arcus1 8412 10 12 12 12 Arcus1 8898 9 11 12 11 Arcus1 10816 8 9 9 9 Arcus2 8847 18 Arcus2 9400 17 Arcus2 10027 16 Arcus2 10743 15 Arcus2 11378 14 Arcus2 11570 13 Arcus2 17067 9 Barthold 434 13 Barthold 470 12 Barthold 513 11 Barthold 564 10 Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 69 Barthold 626 9 Barthold 705 8 Barthold 805 7 Bowman 20 5 5 5 5 5 5 5 5 5 5 5 5 6 Buxey 27 13 Buxey 30 12 Buxey 33 11 Buxey 36 10 Buxey 41 8 Buxey 47 7 Buxey 54 7 8 8 Gunther 44 12 Gunther 49 11 Gunther 54 9 Gunther 61 9 Gunther 69 8 11 Gunther 81 7 Hahn 2004 8 9 Hahn 2338 7 8 9 8 9 8 8 8 9 Hahn 2806 6 6 7 7 6 7 7 6 Hahn 3507 5 5 5 5 6 5 5 5 Hahn 4676 4 5 5 4 4 5 4 4 4 5 Heskiaoff 138 8 Heskiaoff 205 5 Heskiaoff 216 5 Heskiaoff 256 4 Heskiaoff 324 4 5 Heskiaoff 342 3 5 Jackson 9 6 9 Jackson 10 5 7 7 6 7 7 Jackson 13 4 6 4 4 6 4 4 6 4 6 Jackson 14 4 5 4 5 5 4 5 4 5 4 5 4 5 Jackson 21 3 3 3 3 3 3 3 3 3 3 3 3 3 Jaeschke 7 7 8 8 8 8 8 8 8 8 8 8 Jaeschke 8 6 7 7 7 7 7 7 7 7 7 7 Jaeschke 10 4 5 6 5 5 5 5 5 5 5 5 5 5 Jaeschke 18 3 3 3 3 3 3 3 3 3 3 3 3 3 Kilbridge 56 10 Kilbridge 69 8 Kilbridge 79 7 Kilbridge 92 6 Kilbridge 110 6 Kilbridge 111 5 Kilbridge 138 4 Kilbridge 184 3 4 Lutz1 1414 11 Lutz1 1572 10 Lutz1 1768 9 11 10 Lutz1 2020 8 9 9 Lutz1 2357 7 8 8 8 8 9 8 Lutz1 2828 6 6 7 7 6 7 6 Lutz2 18 28 Lutz2 19 26 Lutz2 20 25 Lutz2 21 24 Lutz3 87 20 Lutz3 92 19 Lutz3 97 18 Lutz3 103 17 Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 70 Lutz3 110 15 Lutz3 118 14 Lutz3 127 14 Lutz3 137 13 Lutz3 150 12 Mansoor 48 4 5 5 5 Mansoor 62 3 4 4 4 4 4 4 4 4 4 Mansoor 94 2 3 3 3 3 3 3 3 3 3 3 3 3 Mertens 7 5 Mertens 8 5 Mertens 10 3 4 4 4 4 4 4 Mertens 15 2 3 3 3 3 3 3 3 3 3 3 3 3 Mertens 18 2 2 2 2 2 2 2 2 2 2 2 2 2 Mitchell 14 8 10 10 10 Mitchell 15 8 Mitchell 21 5 7 7 6 7 Mitchell 26 5 6 5 5 6 Mitchell 35 3 4 4 4 4 4 4 4 4 4 4 4 4 Mitchell 39 3 4 4 4 4 4 4 4 4 4 4 4 4 Roszieg 14 10 Roszieg 16 8 11 Roszieg 18 8 9 10 Roszieg 21 6 8 8 8 9 9 8 Roszieg 25 6 7 7 7 7 7 7 7 7 7 7 Roszieg 32 4 5 5 5 5 5 5 5 5 5 5 5 5 Sawyer 27 13 Sawyer 30 12 Sawyer 33 11 Sawyer 36 10 Sawyer 41 8 Sawyer 47 7 Sawyer 54 7 Sawyer 75 5 6 6 Tonge 176 21 Tonge 234 16 Tonge 251 14 Tonge 270 14 Tonge 293 13 Tonge 320 11 Tonge 364 10 Tonge 410 9 Tonge 468 8 Tonge 527 7 Warnecke 82 20 Warnecke 92 17 Warnecke 97 17 Warnecke 104 15 Warnecke 111 14 Solucions de l’optimització local amb b=0,1 i b=0. Precedence graph c m* H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 H12 Arcus1 3786 21 28 Arcus1 3985 20 28 Arcus1 4206 19 24 26 Arcus1 4454 18 27 24 26 23 Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 71 Arcus1 4732 17 25 22 22 20 Arcus1 5048 16 24 20 21 19 Arcus1 5408 15 22 18 19 17 Arcus1 5824 14 20 17 17 17 Arcus1 5853 14 20 17 17 17 Arcus1 6309 13 18 16 16 15 Arcus1 6842 12 18 17 14 15 14 Arcus1 6883 12 18 16 14 15 14 Arcus1 7571 11 14 15 13 14 12 15 Arcus1 8412 10 13 13 12 12 11 13 Arcus1 8898 9 13 13 11 11 11 13 Arcus1 10816 8 10 10 9 9 9 10 Arcus2 8847 18 26 Arcus2 9400 17 24 28 Arcus2 10027 16 22 Arcus2 10743 15 21 Arcus2 11378 14 19 24 Arcus2 11570 13 18 25 Arcus2 17067 9 18 13 17 Barthold 434 13 20 21 Barthold 470 12 18 18 Barthold 513 11 16 Barthold 564 10 15 16 Barthold 626 9 13 16 13 Barthold 705 8 12 16 16 11 Barthold 805 7 10 12 14 14 10 Bowman 20 5 5 5 5 5 5 5 5 5 5 5 5 6 Buxey 27 13 16 Buxey 30 12 16 Buxey 33 11 13 15 14 13 Buxey 36 10 13 Buxey 41 8 12 10 Buxey 47 7 11 10 9 11 Buxey 54 7 10 9 9 10 10 10 7 9 10 Gunther 44 12 17 17 Gunther 49 11 16 14 15 16 14 14 Gunther 54 9 14 14 14 14 14 13 13 13 14 14 13 Gunther 61 9 13 11 12 11 11 13 12 12 10 12 11 12 Gunther 69 8 12 10 11 10 10 12 10 10 10 11 10 11 Gunther 81 7 9 8 9 8 9 9 9 8 8 9 8 9 Hahn 2004 8 9 9 9 9 9 9 9 9 9 9 9 9 Hahn 2338 7 10 8 9 8 8 10 10 8 8 10 8 10 Hahn 2806 6 9 6 8 6 6 9 8 6 6 8 6 8 Hahn 3507 5 7 5 6 5 5 7 6 5 5 6 5 6 Hahn 4676 4 5 4 5 4 4 5 5 4 4 5 4 5 Heskiaoff 138 8 Heskiaoff 205 5 12 8 12 12 Heskiaoff 216 5 12 11 8 11 10 12 Heskiaoff 256 4 12 9 7 9 8 12 Heskiaoff 324 4 11 10 7 5 11 11 7 6 11 10 11 Heskiaoff 342 3 12 8 11 7 4 12 11 7 6 11 8 11 Jackson 9 6 9 9 8 8 9 8 8 9 9 9 8 Jackson 10 5 6 6 6 6 6 6 7 6 7 6 6 6 Jackson 13 4 6 4 5 5 5 6 4 5 4 6 4 6 Jackson 14 4 5 4 5 5 5 5 4 5 4 5 4 5 Jackson 21 3 3 3 3 3 3 3 3 3 3 3 3 3 Jaeschke 7 7 8 8 8 8 8 8 8 8 8 8 8 8 Jaeschke 8 6 7 7 7 7 7 7 7 7 7 7 7 7 Jaeschke 10 4 5 5 5 5 5 5 5 5 5 5 5 5 Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 72 Jaeschke 18 3 3 3 3 3 3 3 3 3 3 3 3 3 Kilbridge 56 10 15 15 Kilbridge 69 8 14 14 Kilbridge 79 7 12 12 12 Kilbridge 92 6 11 11 11 11 Kilbridge 110 6 9 9 8 9 9 9 Kilbridge 111 5 9 8 8 9 9 9 Kilbridge 138 4 11 7 9 6 11 9 8 7 7 11 Kilbridge 184 3 9 5 8 6 5 9 7 6 5 9 5 8 Lutz1 1414 11 13 14 14 14 14 13 Lutz1 1572 10 12 11 12 11 11 12 11 12 12 11 12 Lutz1 1768 9 12 10 11 11 11 12 11 11 10 11 10 11 Lutz1 2020 8 11 9 11 9 9 11 10 9 9 11 9 10 Lutz1 2357 7 8 8 8 8 8 8 8 8 9 9 8 8 Lutz1 2828 6 7 6 7 6 6 7 7 6 6 7 6 7 Lutz2 18 28 41 41 Lutz2 19 26 38 Lutz2 20 25 Lutz2 21 24 Lutz3 87 20 25 25 Lutz3 92 19 24 Lutz3 97 18 23 Lutz3 103 17 21 Lutz3 110 15 19 Lutz3 118 14 18 18 18 Lutz3 127 14 21 17 21 Lutz3 137 13 18 15 16 Lutz3 150 12 16 18 14 16 19 Mansoor 48 4 5 5 5 5 5 5 5 5 4 5 5 5 Mansoor 62 3 4 4 4 4 4 4 4 4 4 4 4 4 Mansoor 94 2 3 3 3 3 3 3 3 3 2 3 3 3 Mertens 7 5 6 6 6 6 6 6 6 6 6 Mertens 8 5 6 6 6 6 6 6 6 6 6 6 6 6 Mertens 10 3 5 4 4 4 4 5 4 4 4 5 4 4 Mertens 15 2 3 3 3 3 3 3 3 3 3 3 3 3 Mertens 18 2 2 2 2 2 2 2 2 2 2 2 2 2 Mitchell 14 8 10 10 10 11 10 Mitchell 15 8 10 10 10 10 10 10 10 10 Mitchell 21 5 7 6 7 7 6 7 7 7 7 7 6 7 Mitchell 26 5 6 6 6 5 5 6 6 5 5 6 6 6 Mitchell 35 3 4 4 4 4 4 4 4 4 4 4 4 4 Mitchell 39 3 4 4 4 4 3 4 4 4 4 4 4 4 Roszieg 14 10 13 13 14 12 13 13 13 13 14 13 13 Roszieg 16 8 11 10 11 11 10 11 11 11 11 11 12 11 Roszieg 18 8 10 9 10 9 9 10 10 10 9 10 9 10 Roszieg 21 6 8 7 8 8 8 8 8 7 8 8 9 8 Roszieg 25 6 7 7 7 7 6 7 7 7 7 7 7 7 Roszieg 32 4 5 5 5 5 5 5 5 5 5 5 5 5 Sawyer 27 13 17 Sawyer 30 12 16 17 Sawyer 33 11 15 15 13 Sawyer 36 10 14 15 11 Sawyer 41 8 12 12 11 Sawyer 47 7 11 11 10 9 11 Sawyer 54 7 9 9 8 8 8 9 Sawyer 75 5 7 6 7 7 6 7 6 6 5 7 6 7 Tonge 176 21 Tonge 234 16 Tonge 251 14 Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 73 Tonge 270 14 20 Tonge 293 13 19 Tonge 320 11 17 Tonge 364 10 14 Tonge 410 9 15 13 15 Tonge 468 8 10 11 10 Tonge 527 7 11 10 11 Warnecke 82 20 27 Warnecke 92 17 23 23 Warnecke 97 17 22 Warnecke 104 15 21 20 Warnecke 111 14 18 18 Solucions de l’optimització local amb b=0,2 i b=0. Precedence graph c m* H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 H12 Arcus1 3786 21 Arcus1 3985 20 Arcus1 4206 19 Arcus1 4454 18 Arcus1 4732 17 Arcus1 5048 16 Arcus1 5408 15 Arcus1 5824 14 17 19 Arcus1 5853 14 17 Arcus1 6309 13 16 16 15 Arcus1 6842 12 15 15 14 Arcus1 6883 12 15 15 14 Arcus1 7571 11 13 14 12 Arcus1 8412 10 12 12 11 Arcus1 8898 9 11 11 11 Arcus1 10816 8 9 9 9 Arcus2 8847 18 Arcus2 9400 17 Arcus2 10027 16 Arcus2 10743 15 Arcus2 11378 14 Arcus2 11570 13 Arcus2 17067 9 Barthold 434 13 Barthold 470 12 Barthold 513 11 Barthold 564 10 Barthold 626 9 Barthold 705 8 Barthold 805 7 Bowman 20 5 5 5 5 5 5 5 5 5 5 5 5 6 Buxey 27 13 Buxey 30 12 Buxey 33 11 14 Buxey 36 10 Buxey 41 8 Buxey 47 7 9 Buxey 54 7 Gunther 44 12 Gunther 49 11 Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 74 Gunther 54 9 Gunther 61 9 Gunther 69 8 9 11 9 9 Gunther 81 7 9 Hahn 2004 8 9 9 9 9 Hahn 2338 7 8 9 8 8 8 8 8 Hahn 2806 6 6 6 6 6 6 6 Hahn 3507 5 5 6 5 5 6 5 5 5 Hahn 4676 4 4 5 4 4 5 4 4 4 5 Heskiaoff 138 8 Heskiaoff 205 5 Heskiaoff 216 5 Heskiaoff 256 4 Heskiaoff 324 4 5 Heskiaoff 342 3 5 Jackson 9 6 9 Jackson 10 5 7 7 6 7 7 Jackson 13 4 6 4 5 6 4 4 6 4 6 Jackson 14 4 5 4 5 5 4 5 4 5 4 5 4 5 Jackson 21 3 3 3 3 3 3 3 3 3 3 3 3 3 Jaeschke 7 7 8 8 8 8 8 8 8 8 8 8 Jaeschke 8 6 7 7 7 7 7 7 7 7 7 7 Jaeschke 10 4 5 5 5 5 5 5 5 5 5 5 6 5 Jaeschke 18 3 3 3 3 3 3 3 3 3 3 3 3 3 Kilbridge 56 10 Kilbridge 69 8 Kilbridge 79 7 Kilbridge 92 6 Kilbridge 110 6 Kilbridge 111 5 Kilbridge 138 4 6 Kilbridge 184 3 4 Lutz1 1414 11 14 15 15 Lutz1 1572 10 12 12 11 Lutz1 1768 9 10 11 11 11 10 Lutz1 2020 8 10 9 9 9 10 Lutz1 2357 7 8 8 8 8 8 Lutz1 2828 6 7 6 6 6 7 8 7 8 Lutz2 18 28 Lutz2 19 26 Lutz2 20 25 Lutz2 21 24 Lutz3 87 20 Lutz3 92 19 Lutz3 97 18 Lutz3 103 17 Lutz3 110 15 Lutz3 118 14 Lutz3 127 14 Lutz3 137 13 Lutz3 150 12 Mansoor 48 4 5 5 5 5 5 5 5 5 4 5 5 5 Mansoor 62 3 4 4 4 4 4 4 4 5 4 4 4 4 Mansoor 94 2 3 3 3 3 3 3 3 3 2 3 3 3 Mertens 7 5 Mertens 8 5 Mertens 10 3 4 4 5 4 4 4 Mertens 15 2 3 3 3 3 3 3 3 3 3 3 3 3 Mertens 18 2 2 2 2 2 2 2 2 2 2 2 2 2 Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 81 main('Gunther', 81) main('Hahn', 2004) main('Hahn', 2338) main('Hahn', 2806) main('Hahn', 3507) main('Hahn', 4676) main('Heskiaoff', 138) main('Heskiaoff', 205) main('Heskiaoff', 216) main('Heskiaoff', 256) main('Heskiaoff', 324) main('Heskiaoff', 342) main('Jackson', 7) main('Jackson', 9) main('Jackson', 10) main('Jackson', 13) main('Jackson', 14) main('Jackson', 21) main('Jaeschke', 6) main('Jaeschke', 7) main('Jaeschke', 8) main('Jaeschke', 10) main('Jaeschke', 18) main('Kilbridge', 56) main('Kilbridge', 57) main('Kilbridge', 62) main('Kilbridge', 69) main('Kilbridge', 79) main('Kilbridge', 92) main('Kilbridge', 110) main('Kilbridge', 111) main('Kilbridge', 138) main('Kilbridge', 184) main('Lutz1', 1414) main('Lutz1', 1572) main('Lutz1', 1768) main('Lutz1', 2020) main('Lutz1', 2357) main('Lutz1', 2828) main('Lutz2', 11) main('Lutz2', 12) main('Lutz2', 13) main('Lutz2', 14) main('Lutz2', 15) main('Lutz2', 16) main('Lutz2', 17) main('Lutz2', 18) main('Lutz2', 19) main('Lutz2', 20) main('Lutz2', 21) main('Lutz3', 75) main('Lutz3', 79) main('Lutz3', 83) main('Lutz3', 87) main('Lutz3', 92) main('Lutz3', 97) main('Lutz3', 103) main('Lutz3', 110) main('Lutz3', 118) main('Lutz3', 127) main('Lutz3', 137) main('Lutz3', 150) main('Mansoor', 48) main('Mansoor', 62) main('Mansoor', 94) main('Mertens', 6) main('Mertens', 7) main('Mertens', 8) main('Mertens', 10) main('Mertens', 15) main('Mertens', 18) main('Mitchell', 14) main('Mitchell', 15) main('Mitchell', 21) main('Mitchell', 26) main('Mitchell', 35) main('Mitchell', 39) main('Mukherje', 176) main('Mukherje', 183) main('Mukherje', 192) main('Mukherje', 201) main('Mukherje', 211) main('Mukherje', 222) main('Mukherje', 234) main('Mukherje', 248) main('Mukherje', 263) main('Mukherje', 281) Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 82 main('Mukherje', 301) main('Mukherje', 324) main('Mukherje', 351) main('Roszieg', 14) main('Roszieg', 16) main('Roszieg', 18) main('Roszieg', 21) main('Roszieg', 25) main('Roszieg', 32) main('Sawyer', 25) main('Sawyer', 27) main('Sawyer', 30) main('Sawyer', 33) main('Sawyer', 36) main('Sawyer', 41) main('Sawyer', 47) main('Sawyer', 54) main('Sawyer', 75) main('Scholl', 1394) main('Scholl', 1422) main('Scholl', 1452) main('Scholl', 1483) main('Scholl', 1515) main('Scholl', 1548) main('Scholl', 1584) main('Scholl', 1620) main('Scholl', 1659) main('Scholl', 1699) main('Scholl', 1742) main('Scholl', 1787) main('Scholl', 1834) main('Scholl', 1883) main('Scholl', 1935) main('Scholl', 1991) main('Scholl', 2049) main('Scholl', 2111) main('Scholl', 2177) main('Scholl', 2247) main('Scholl', 2322) main('Scholl', 2402) main('Scholl', 2488) main('Scholl', 2580) main('Scholl', 2680) main('Scholl', 2787) main('Tonge', 160) main('Tonge', 168) main('Tonge', 176) main('Tonge', 185) main('Tonge', 195) main('Tonge', 207) main('Tonge', 220) main('Tonge', 234) main('Tonge', 251) main('Tonge', 270) main('Tonge', 293) main('Tonge', 320) main('Tonge', 364) main('Tonge', 410) main('Tonge', 468) main('Tonge', 527) main('Warnecke', 54) main('Warnecke', 56) main('Warnecke', 58) main('Warnecke', 60) main('Warnecke', 62) main('Warnecke', 65) main('Warnecke', 68) main('Warnecke', 71) main('Warnecke', 74) main('Warnecke', 78) main('Warnecke', 82) main('Warnecke', 86) main('Warnecke', 92) main('Warnecke', 97) main('Warnecke', 104) main('Warnecke', 111) main('Wee-Mag', 28) main('Wee-Mag', 29) main('Wee-Mag', 30) main('Wee-Mag', 31) main('Wee-Mag', 32) main('Wee-Mag', 33) main('Wee-Mag', 34) main('Wee-Mag', 35) main('Wee-Mag', 36) main('Wee-Mag', 37) main('Wee-Mag', 38) Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 83 main('Wee-Mag', 39) main('Wee-Mag', 40) main('Wee-Mag', 41) main('Wee-Mag', 42) main('Wee-Mag', 43) main('Wee-Mag', 45) main('Wee-Mag', 46) main('Wee-Mag', 47) main('Wee-Mag', 49) main('Wee-Mag', 50) main('Wee-Mag', 52) main('Wee-Mag', 54) main('Wee-Mag', 56) CODI DE LES HEURÍSTIQUES D’ASSIGNACIÓ DE TASQUES HEURÍSTICA 1 def llista_prioritats_tasques(g): prioritats=[] successors=[] for i in g.nodes(): temps=g.node[i]['time'] dic=nx.dfs_successors(g,i) for key in dic: if len(dic[key])==1: element=dic[key][0] temps = temps + g.node[element]['time'] else: for element in dic[key]: temps = temps + g.node[element]['time'] successors.append((i,temps)) successors=sorted(successors, key=lambda tup: tup[1], reverse=True) for i in successors: prioritats.append(i[0]) return prioritats HEURÍSTICA 2 def llista_duracions_tasques(g): duracions=[] aux=[] for i in g.nodes(): aux.append((i,g.node[i]['time'])) aux=sorted(aux, key=lambda tup: tup[1], reverse=True) for i in aux: duracions.append(i[0]) return duracions HEURÍSTICA 3 def llista_duracions_tasques(g): duracions=[] aux=[] for i in g.nodes(): suc=0 dic=nx.dfs_successors(g,i) for key in dic: suc=suc+len(dic[key]) aux.append((i,suc)) aux=sorted(aux, key=lambda tup: tup[1], reverse=True) for i in aux: duracions.append(i[0]) return duracions HEURÍSTICA 4 def llista_prioritats_tasques(g): prioritats=[] successors = [] for i in g.nodes(): successors.append((i,len(g.successors(i)))) successors=sorted(successors, key=lambda tup: tup[1], reverse=True) for i in successors: prioritats.append(i[0]) Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 84 return prioritats HEURÍSTICA 5 def llista_prioritats_tasques(h,temps_cicle): prioritats=[] successors=[] for i in h.nodes(): temps=h.node[i]['time'] dic=nx.dfs_successors(h,i) for key in dic: if len(dic[key])==1: element=dic[key][0] temps = temps + h.node[element]['time'] else: for element in dic[key]: temps = temps + h.node[element]['time'] formula=float(temps)/float(temps_cicle) successors.append((i,formula)) successors=sorted(successors, key=lambda tup: tup[1]) for i in successors: prioritats.append(i[0]) return prioritats HEURÍSTICA 6 def llista_prioritats_tasques(g,temps_cicle): prioritats=[] successors=[] n=len(g.nodes())-1 for i in g.nodes(): temps=g.node[i]['time'] dic=nx.dfs_successors(g,i) for key in dic: if len(dic[key])==1: element=dic[key][0] temps = temps + g.node[element]['time'] else: for element in dic[key]: temps = temps + g.node[element]['time'] formula=n+1-(float(temps)/float(temps_cicle)) successors.append((i,formula)) successors=sorted(successors, key=lambda tup: tup[1]) for i in successors: prioritats.append(i[0]) return prioritats HEURÍSTICA 7 def llista_prioritats_tasques(g,h,temps_cicle): prioritats=[] successors=[] aux=[] n=len(g.nodes()) for i in g.nodes(): temps=g.node[i]['time'] dic=nx.dfs_successors(g,i) for key in dic: if len(dic[key])==1: element=dic[key][0] temps = temps + g.node[element]['time'] else: for element in dic[key]: temps = temps + g.node[element]['time'] formula=n+1-(float(temps)/float(temps_cicle)) successors.append([i,formula]) for i in h.nodes(): temps=h.node[i]['time'] dic=nx.dfs_successors(h,i) for key in dic: if len(dic[key])==1: element=dic[key][0] temps = temps + h.node[element]['time'] else: for element in dic[key]: temps = temps + h.node[element]['time'] formula=float(temps)/float(temps_cicle) Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 85 for j in successors: if j[0]==i: j.append(formula) break else: pass for llista in successors: aux.append((llista[0],llista[1]-llista[2])) aux=sorted(aux, key=lambda tup: tup[1]) for i in aux: prioritats.append(i[0]) return prioritats HEURÍSTICA 9 def llista_prioritats_tasques(g): prioritats=[] successors=[] for i in g.nodes(): suc=0 temps=g.node[i]['time'] dic=nx.dfs_successors(g,i) for key in dic: suc=suc+len(dic[key]) if len(dic[key])==1: element=dic[key][0] temps = temps + g.node[element]['time'] else: for element in dic[key]: temps = temps + g.node[element]['time'] formula=float(temps)/(float(suc+1)) successors.append((i,formula)) successors=sorted(successors, key=lambda tup: tup[1], reverse=True) for i in successors: prioritats.append(i[0]) return prioritats HEURÍSTICA 10 def llista_prioritats_tasques(g,temps_cicle): prioritats=[] successors=[] n=len(g.nodes())-1 for i in g.nodes(): suc=0 temps=g.node[i]['time'] dic=nx.dfs_successors(g,i) for key in dic: suc=suc+len(dic[key]) if len(dic[key])==1: element=dic[key][0] temps = temps + g.node[element]['time'] else: for element in dic[key]: temps = temps + g.node[element]['time'] formula=(n+1-(float(temps)/float(temps_cicle)))/float(suc+1) successors.append((i,formula)) successors=sorted(successors, key=lambda tup: tup[1]) for i in successors: prioritats.append(i[0]) return prioritats HEURÍSTICA 11 def llista_prioritats_tasques(g,temps_cicle): prioritats=[] successors=[] n=len(g.nodes())-1 for i in g.nodes(): temps=g.node[i]['time'] dic=nx.dfs_successors(g,i) for key in dic: if len(dic[key])==1: element=dic[key][0] temps = temps + g.node[element]['time'] else: Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 86 for element in dic[key]: temps = temps + g.node[element]['time'] formula=float(g.node[i]['time'])/(n+1- (float(temps)/float(temps_cicle))) successors.append((i,formula)) successors=sorted(successors, key=lambda tup: tup[1], reverse=True) for i in successors: prioritats.append(i[0]) return prioritats HEURÍSTICA 12 def llista_prioritats_tasques(g,h,temps_cicle): prioritats=[] successors=[] aux=[] n=len(g.nodes()) for i in g.nodes(): suc=0 temps=g.node[i]['time'] dic=nx.dfs_successors(g,i) for key in dic: suc=suc+len(dic[key]) if len(dic[key])==1: element=dic[key][0] temps = temps + g.node[element]['time'] else: for element in dic[key]: temps = temps + g.node[element]['time'] formula=n+1-(float(temps)/float(temps_cicle)) successors.append([i,formula,suc]) for i in h.nodes(): temps=h.node[i]['time'] dic=nx.dfs_successors(h,i) for key in dic: if len(dic[key])==1: element=dic[key][0] temps = temps + h.node[element]['time'] else: for element in dic[key]: temps = temps + h.node[element]['time'] formula=float(temps)/float(temps_cicle) for j in successors: if j[0]==i: j.append(formula) break else: pass for llista in successors: aux.append((llista[0],llista[2]/(llista[1]-llista[3]))) aux=sorted(aux, key=lambda tup: tup[1], reverse=True) for i in aux: prioritats.append(i[0]) return prioritats OPTIMITZACIÓ LOCAL import networkx as nx import time import codi1 def intercanvi(ordre, tasca, tasca_inter): copia=ordre[:] index=copia.index(tasca) index_inter=copia.index(tasca_inter) copia[index], copia[index_inter] = copia[index_inter], copia[index] return copia Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 87 def algorisme(ordre,g): llista = [] index_node=-1 for node in ordre: index_node=index_node+1 index_elem=index_node+1 descendants=list(nx.descendants(g,node)) for elem in ordre[index_elem:]: ancestres = list(nx.ancestors(g,elem)) llesca = ordre[index_node:index_elem] index_elem=index_elem+1 c=0 for i in llesca: if i in ancestres: break elif i in descendants: break else: c=c+1 if c==len(llesca): l=intercanvi(ordre,node,elem) llista.append(l) else: pass return llista def desfer_llista(estacions): ordre=[] for subllista in estacions: for i in subllista: ordre.append(i) return ordre def available_time(g,tasca): aval=0 if tasca == 0: return 0 else: for pre in g.predecessors(tasca): if aval <= g.node[pre]['temps_acaba']: aval = g.node[pre]['temps_acaba'] else: pass return aval def montar_estacions(sub_llista, g, temps_cicle): nova_organitzacio=[] aux=[] start_time=0 temps=temps_cicle c=1 for tasca in sub_llista: aval=available_time(g,tasca) if 0 in g.predecessors(tasca): b=0 else: b=0.1 if start_time>=aval: p=g.node[tasca]['time']+b*(start_time-aval) if p>temps_cicle: return 'Impossible' elif p<=temps and temps>0: aux.append(tasca) temps=temps-p start_time=start_time+p g.node[tasca]['temps_acaba']=start_time if tasca==sub_llista[len(sub_llista)-1]: nova_organitzacio.append(aux) else: start_time = temps_cicle*c c=c+1 nova_organitzacio.append(aux) temps=temps_cicle aux=[] p=g.node[tasca]['time']+b*(start_time-aval) if p<temps_cicle: g.node[tasca]['temps_acaba']=start_time+p Resolució del problema d’equilibrat de línia de muntatge amb tasques amb deterioració Pág. 88 aux.append(tasca) start_time = start_time+p temps=temps-p if tasca==sub_llista[len(sub_llista)-1]: nova_organitzacio.append(aux) else: return 'Impossible' else: start_time = temps_cicle*c c=c+1 nova_organitzacio.append(aux) temps=temps_cicle aux=[] p=g.node[tasca]['time']+b*(start_time-aval) if p<temps_cicle: g.node[tasca]['temps_acaba']=start_time+p aux.append(tasca) start_time= start_time+p temps=temps-p if tasca==sub_llista[len(sub_llista)-1]: nova_organitzacio.append(aux) else: return 'Impossible' return nova_organitzacio def canviar_atributs(g): for nodes in g.nodes(): g.node[nodes]['temps_acaba']=0 return g def main(nom_fitxer, temps_cicle): fitxer=open('optimitzacio_codi1', 'a') start=time.clock() estacions, g = codi1.main(nom_fitxer, temps_cicle) ordre = desfer_llista(estacions) llista = algorisme(ordre,g) for sub_llista in llista: g = canviar_atributs(g) nova_organitzacio=montar_estacions(sub_llista, g, temps_cicle) if nova_organitzacio == 'Impossible': pass elif len(nova_organitzacio)<len(estacions) and estacions!=[]: fitxer.write(nom_fitxer+'*'+str(temps_cicle)+'*'+str(len(n ova_organitzacio))+'*'+str(time.clock()- start)+'*'+str(nova_organitzacio)+'\n') else: pass fitxer.close() if __name__=='__main__': main('Arcus1', 3786) main('Arcus1', 3985) main('Arcus1', 4206) …