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

T eball de Fi de G au G au en Enginye ia en Tecnologies Indus ials Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació MEMÒRIA Au o : Lau a En ique Feliu Di ec o : Albe o Ga cía Villo ia Con oca ò ia: Se emb e 2017 Escola Tècnica Supe io d’Enginye ia Indus ial de Ba celona Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 2 1. Resum El p esen eball é la inali a de esold e el p oblema de l’equilib a de línia de mun a ge conside an l’e ec e de la de e io ació de les asques. De inin la de e io ació d’una asca com el e de que una asca p ocessada desp és d’un ce emps consumeix més emps de p ocessamen que si la ma eixa es p ocessada més a ia . To i que és un p oblema que es oba p esen en ce es línies de mun a ge eals, se’n oben pocs es udis a la li e a u a cien í ica. Amb al i, s’ha desen olupa un p ocedimen heu ís ic que, donades unes de e minades ca ac e ís iques de la línia de p oducció, conc e amen el nomb e de asques, els emps de p océs cons an s de cada asca, les se es elacions de p ecedència i el emps de cicle màxim de la línia, eali zi la se a dis ibució a les es acions de eball de la mane a més e icien possible i minimi zan el nomb e d’es acions u ili zades (el que es coneix com a ALBP-1). El p ocedimen p oposa es basa en una heu ís ica de millo a coneguda com a op imi zació local. Aques mè ode pa eix d’una solució inicial (en aques cas obada a pa i d’heu ísi iques cons uc i es g eedy) i u ili za com a idea onamen al l’explo ació del eïna ge pe oba solucions millo s. S’han c ea 12 a ian s basades en aques algo isme que esul en de can is en els mè odes pe ob eni la solució inicial, és a di , 12 heu ís iques amb egles de p io i a di e en s pe dis ibui les asques en les es acions. Pe al d’a alua el uncionamen del p ocedimen de esolució p oposa s’ha eali za una expe iència compu acional a pa i d’un conjun d’exempla s de es a ge. Pe du a e me l’expe imen ació, s’ha escolli u ili za un banc de dades di igi pe la esolució de p oblemes d’equilib a de línia de mun a ge simple al que se li ha a egi com a dada la axa de c eixemen de la de e io ació. En conc e s’han es udia 5 a ian s di e en s de axa de de e io ació pe al de pode anali za la incidència que é en l’equilib a de la línia. Finalmen s’ha e una compa a i a en e les di e en s heu ís iques aplicades pe eu e quina d’elles és la més e icaç pe esold e aques p oblema. Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 3 Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 4 2. Suma i 1. RESUM ____________________________________________________ 2 2. SUMARI ___________________________________________________ 4 3. INTRODUCCIÓ ______________________________________________ 7 3.1. Objec ius del p ojec e ..................................................................................... 7 3.2. Abas del p ojec e ........................................................................................... 7 4. ESTAT DE L’ART DEL PROBLEMA DE L’EQUILIBRAT DE LÍNIES DE MUNTATGE ______________________________________________ 9 4.1. Les línies de mun a ge ................................................................................... 9 4.1.1. In oducció ........................................................................................................ 9 4.1.2. Concep es p incipals ....................................................................................... 10 4.1.3. Classi icació de les línies de mun a ge ............................................................ 11 4.2. Tipus de p oblemes de línies de mun a ge .................................................. 15 4.2.1. Disseny de línies de mun a ge ........................................................................ 15 4.2.2. Equilib a de línies de mun a ge ...................................................................... 16 5. EQUILIBRAT DE LÍNEA DE MUNTATGE AMB TASQUES AMB DETERIORACIÓ __________________________________________ 19 5.1. Es a de l’a .................................................................................................. 19 5.2. De inició del p oblema .................................................................................. 20 5.3. Fo mali zació del p oblema .......................................................................... 23 6. PROPOSTA DE RESOLUCIÓ DEL PROBLEMA ________________ 26 6.1. Mè odes de esolució ................................................................................... 26 6.2. P ocedimen de esolució mi jançan op imi zació local ............................... 28 6.2.1. Gene ació de solucions inicials ....................................................................... 28 6.2.2. Gene ació de solucions eïnes ....................................................................... 32 6.2.3. Selecció de la millo eïna ............................................................................... 33 7. EXPERIÈNCIA COMPUTACIONAL ___________________________ 35 7.1. Exempla s de es eig .................................................................................... 35 7.2. Anàlisis de esul a s ...................................................................................... 38 CONCLUSIONS ______________________________________________ 44 BIBLIOGRAFIA ______________________________________________ 45 Re e ències bibliog à iques .................................................................................... 45 Bibliog a ia complemen à ia ................................................................................... 47 Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 5 ANNEX _____________________________________________________ 48 Annex A. Temps d’execució de l’expe iència compu acional ................................ 48 Annex B. Solucions inicials de l’expe iència compu acional .................................. 49 Annex C. Solucions de l’op imi zació local a pa i de l’exepe iència compu acional .............................................................................................. 66 Annex D. Algo ismes ............................................................................................. 78 Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 7 3. In oducció L’equilib a d’una línia de mun a ge és un p ocedimen en que les asques es dis ibueixen de mane a uni o me a cada es ació de eball. Pe al de que una es ació es igui ben equilib ada cal que o es les es acions inguin una cà ega i un cicle de eball el més semblan possible pe al de edui el emps d’inac i i a dins de la línia. Al món indus ial exis eixen mol s ipus de línies de mun a ge. Pe aques mo iu s’han eali za nomb osos es udis pe in es iga el seu compo amen ope a iu i oba no es mane es d’augmen a la se a e iciència. En aques con ex apa eix el p oblema d’equilib a de línies de mun a ge (ALBP) del qual en la li e a u a se n’acos uma a ac a la e sió simpli icada (SALBP). Aques a e sió, pe ò, no conside a ca ac e ís iques eals de les línies de mun a ge. D’aques a mane a i pe al de dona espos a a p oblemes eals, com a a a una ca ac e ís ica que es oba p esen en mul i ud de línies, el p esen p ojec e conside a l’e ec e de la de e io ació de les asques. 3.1. Objec ius del p ojec e L’objec iu d’aques p ojec e és esold e el p oblema de l’equilib a de línia de mun a ge conside an l’e ec e de la de e io ació de les asques. L’objec iu del p oblema consis eix en minimi za el nomb e d’es acions de eball dona un emps de cicle de e mina . Pe al de po a -ho a e me, es p esen a un conjun de p ocedimen s heu ís ics pe ob eni solucions ac ibles inicials del p oblema. A pa i d’aquí es p oposa un mè ode d’op imi zació local. Pe al d’a alua l’e iciència dels p ocedimen s de esolució p oposa , es p esen a una expe iència compu acional eali zada a pa i de l’a aluació d’exempla s, amb els quals s’a aluen els esul a s ob ingu s. 3.2. Abas del p ojec e En aques p ojec e es ac a la esolució del p oblema des d’una pe spec i a eò ica i d’in es igació. Conc e amen , la a ian es udiada é en comp e les següen s hipò esis i ca ac e ís iques:  Es coneix el emps de cicle de la línia.  Les asques són indi isibles i un cop iniciada la se a execució no es poden in e omp e. Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 8  Exis eixen elacions de p ecedència en e les asques, les quals ambé es coneixen.  La línia é una du ació de les asques dependen . El emps de p ocessamen d’una de e minada asca depèn del seu momen d’inici i del momen en el qual s’acaben de p ocessa les se es p edecesso es.  El concep e de la de e io ació de les asques es conside a lineal.  La línia de mun a ge és simple, se ial i sínc ona.  La línia no di e ència en e ope ado s manuals o obò ics.  La axa d’en ada de les peces a la línia és ixa.  Les es acions són del ma eix ipus. Això implica que es an equipades amb els ma eixos componen s i, conseqüen men , o a asca po se assignada a qualse ol es ació. Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 9 4. Es a de l’a del p oblema de l’equilib a de línies de mun a ge 4.1. Les línies de mun a ge 4.1.1. In oducció En la se a o ma bàsica, una línia de mun a ge consis eix en una seqüència d’es acions de eball, gene almen connec ades pe un mecanisme de anspo com a a una cin a anspo ado a, a a és de la qual lueixen les uni a s d’un p oduc e. Cada es ació de eball eali za epe idamen un conjun de asques pe p odui o ab ica un p oduc e especí ic. Les asques eque eixen un ce emps pe p ocessa -se i es an elacionades en e elles d'aco d amb les es iccions ecnològiques exis en s. Un dels exemples més amosos d'una línia de mun a ge és la plan a de p oducció de Hen y Fo d, ja que a se la p ime a en assen a les bases mode nes de la p oducció en cadena. Els componen s del model T de Fo d es an ab ica a la p ime a línia mòbil u ili zan les idees de di isió de eball pe seguin dos objec ius cla s: la disminució dels cos os i la p oducció en massa. Tanma eix, aques s ipus de con igu acions da en d'èpoques mol an e io s. L'A senal enecià (conside a la p ime a àb ica del món), a desen olupa mè odes de p oducció massi a de aixells de gue a que e en mol més àpids i eque ien menys us a. En el momen àlgid de la se a e icàcia a p incipis del segle XVI, l'A senal a pode p odui p op d'un aixell pe dia amb una línia de p oducció que no es a eu e de nou ins a la Re olució Indus ial. L’any 1799, Eli Whi ney a in odui el concep e d’es anda di zació en el sis ema de ab icació no d-ame icà a pa i de la c eació de pa s in e can iables en la ab icació d’a mamen , en ús dels concep es de di isió de eball i ole ància en l’àmbi de l’enginye ia, pe al de c ea acobla s de pa s d’una o ma epe i i a. Al 1901 Ransom Eli Olds, c eado de la ma ca au omobilís ica Oldsmobile, a in en a pa en a el p ime concep e de línia de mun a ge pe al de ab ica au omòbils en massa, pe ò no a se ins a 1913 quan Hen y Fo d a pe ecciona aques a idea i inalmen la a po a a e me. Enca a que les línies de mun a ge es oben mol so in a la indús ia de l'au omòbil, mol s al es sec o s ambé es an o gani za s d’aques a mane a. Aques és el cas de la majo ia de béns de la ida quo idiana, com, pe exemple, el mun a ge inal de p oduc es elèc ics com a a màquines de ca è, en ado es, e ige ado s, àdio, ele isió i o dinado s pe sonals, e c. Més ecen men , les línies de mun a ge han guanya impo ància en la p oducció en olum eduï de p oduc es pe sonali za s així com en els sis emes de se ei. Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 10 4.1.2. Concep es p incipals Una línia de mun a ge é com a objec iu c ea un de e mina p oduc e, ja sigui inal o in e medi, a egin conjun s de peces de mane a p ede inida. Pe eali za aques mun a ge, es disposa p incipalmen d’un nomb e d’es acions i unes de e minades asques, que es ca ac e i zen cada una d’elles pe la se a du ació i les elacions en e elles, ja siguin pe exemple, de p ecedència o d’incompa ibili a . A con inuació s’exposen els concep es més signi ica ius dels p oblemes d’equilib a de línies de mun a ge:  Tasca i: és una uni a de eball indi isible que é associa un emps de p océs ( i). El eball o al eque i pe ab ica un p oduc e en una línia de mun a ge es di ideix en un conjun de N asques.  Temps de p océs de la asca i ( i): emps necessa i pe eali za la asca i.  Es ació de eball j: són els componen s de la línia en els quals es p ocessen les asques, pe an , una es ació de eball es à o mada pe un conjun de asques a eali za . Poden implica un ope ado humà o obò ic, de e mina s equips i alguns mecanismes de p ocessamen especiali za s.  Cà ega de eball de l’es ació j: és el conjun de asques assignades a l’es ació de eball j.  Temps de eball de l’es ació j: és la suma dels emps de p océs de les asques assignades a l’es ació j.  Temps mo o ociós de l’es ació j: és la di e ència en e el emps de cicle i el emps de eball de l’es ació j.  Temps de cicle (TC): és el emps disponible a cada es ació de eball pe comple a les asques necessà ies pe p ocessa una uni a de p oduc e. En cas que no es igui especi ica , s’acos uma a conside a igual al emps de eball de l’es ació més ca egada. A la li e a u a, el emps de cicle ambé es de ineix com l’in e al de emps en e el p ocessamen de dues uni a s consecu i es.  Relacions de p ecedència: es de ineixen pe les es iccions de p io i a ecnològica que de e minen l’o d e en què es poden eali za les asques a la línia de mun a ge. No es po p ocessa una asca ins que no s’hagin p ocessa o es les se es p edecesso es immedia es. Les elacions de p ecedència no malmen es an ep esen ades pe un diag ama g a de p ecedències. Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 17  To es les asques es p ocessen de la ma eixa mane a, no hi ha al e na i es de p ocessamen .  Casa asca cons i ueix una uni a indi isible.  La línia é una a qui ec u a simple i se ial, sense línies d’alimen ació ni elemen s pa al·lels.  La línia és sinc ònica.  L’o d e en que es eali zen les asques ha de espec a unes es iccions de p ecedència.  La du ació de les asques és de e minis a.  La axa d’en ada de les peces de la línia és ixa.  Les es acions són del ma eix ipus. Això implica que es an equipades amb els ma eixos componen s i, conseqüen men , o a asca pod ia se assignada a qualse ol es ació. Pa in d’aques es ca ac e ís iques, es poden dis ingi qua e a ian s del SALBP en unció de l’objec iu que es ol assoli (Scholl [3]): SALBP-1: es busca minimi za el nomb e d'es acions necessà ies pe a eali za el p océs p oduc iu a pa i d'un emps de cicle màxim assigna (sense sob epassa la axa de p oducció especi icada). Aques ipus de p oblema és adequa quan es ol ins al·la un nou sis ema de mun a ge i la demanda ex e na és coneguda (o se’n po e una bona es imació). SALBP-2: en aques cas es pa eix d'un nomb e d'es acions ix i es busca minimi za el emps de cicle de la línia de mun a ge (és a di , maximi za la axa de p oducció). D’aques a mane a es ga an eixen emps mínims d’inac i i a . Aques p oblema s’acos uma a p esen a quan la línia de mun a ge ja exis eix. SALBP-E: es ol maximi za l'e iciència de la línia, o el que és el ma eix, minimi za el p oduc e de nomb e d'es acions de eball (M) pe el emps de cicle (TC). En aques cas, an el nomb e d’es acions com el emps de cicle són a iables del p oblema donades. SALBP-F: consis eix en oba una solució ac ible pe una combinació qualse ol de emps de cicle (TC) i nomb e d'es acions (M). Se eix pe aquells casos en els que es ol conèixe si la línia po ope a amb uns alo s de e mina s de M i TC. GALBP: P oblema gene al d’equilib a de línia de mun a ge. Els p oblemes ipus ALBP són o s aquells que no són el SALBP i que s’ap open més a p oblemes eals. Usualmen aques s p oblemes són mol di ícils de esold e òp imamen degu a la se a na u alesa combina ò ia i a la mul i ud de asques i condicions p esen s en les si uacions eals. Els ALBPs, a causa de la se a eno me elle ància en la indús ia i en els se eis, han es a àmpliamen es udia s des de les úl imes dècades com es e lec eix en els nomb osos eballs de Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 18 sín esi que han ana apa eixen . Una c í ica esmen ada eqüen men en aques s eballs és la impo an di e ència exis en en e els p oblemes habi ualmen in es iga s pe la comuni a cien í ica i els que es donen en la eali a indus ial. Un mo iu d'aques enomen és que s'ha endi a in es iga e sions simpli icades dels ma eixos pe edui la se a complexi a a un ni ell abo dable a les ècniques de la in es igació ope a i a. Així, aques s úl ims anys la comuni a cien í ica ha in ensi ica els seus es o ços a es udia ALBPs que inco po in ca ac e ís iques addicionals p esen s en sis emes eals. Pe exemple, en e d'al es: emps de les asques dependen s de la seqüència de mun a ge (Capacho e al. [6]), emps de les asques dependen s dels ope a is (Mo ei a e al. [7]), emps de p epa ació en e asques (Ma ino i Pas o [8]), ince esa en els emps de les asques (Saï e al. [9]), es iccions espacials (Bau is a i Pe ei a [10]), ecu sos limi a s (Co ominas e al. [11]), conside acions e gonòmiques (O o i Scholl [12]), línies en o ma d'U (A ikal e al. [13]) i línies amb dos cos a s (Pu nomo e al. [14]). Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 19 5. Equilib a de línea de mun a ge amb asques amb de e io ació En aques apa a es a la desc ipció del p oblema en conc e a ac a en aques eball. En p ime lloc es a una e isió de la li e a u a on s’ha ac a aques p oblema i a con inuació es comen en les ca ac e ís iques especí iques del p oblema. 5.1. Es a de l’a En el camp de l’es udi dels p oblemes d’equilib a , una g an quan i a d’in es igació s’han du a e me en di e sos ipus de línies i di e en s uncions objec iu. La majo ia dels es udis pe ò, han conside a el emps de p ocessamen de les asques com a un alo cons an . To i així, en algunes si uacions indus ials el emps de p ocessamen de les asques augmen a a mesu a que a den en comença en p ocessa -se; pe an , és una ca ac e ís ica impo an a eni en comp e. Aques eball ac a sob e els e ec es que compo a a egi el concep e de la de e io ació de asques al conegu p oblema d’equilib a de línies de p oducció (ALBP). De inin la de e io ació d’una asca com el e de que una asca p ocessada desp és d’un ce emps consumeix més emps de p ocessamen que si la ma eixa es p ocessada més a ia . Aques concep e a se p ime amen in oduï pe Gup a and Gup a [15] i B owne i Yechiali [16] anomenan -lo “Task De e io a ion” en p oblemes de p og amació. Van p oposa models ma emà ics on el emps de p ocessamen d’una asca és una unció lineal del seu emps d’inici. L’exemple mes popula que es po oba a la li e a u a on es po obse a aques enomen és la empe a u a d’un lingo , que men e espe a pe en a a la màquina de laminació, la se a empe a u a baixa ins a un de e mina ni ell que suposa à ha e de o na a escal a -lo abans d’en a a la màquina. La al a d’una p og amació e icien en aques ipus de asques en cadenes de p oducció po po a a un inc emen signi ica iu en el emps de cicle, especialmen en uni a s de manu ac u a de g ans dimensions. Aques concep e de la de e io ació ha sigu o ça es udia en p oblemes de p og amació com es po eu e en es udis de Ji e al. [17] o Wang e al. [18], pe ò no an a p oblemes d’equilib a de línies. Si em una e isió de la li e a u a podem oba a icles com a a el de Toksa i e al. [19] en el qual conside en simul àniamen l’e ec e de la de e io ació de les asques amb l’e ec e de l’ap enen a ge dels ope a is degu a la epe ició de les asques. P oposen ep esen a la de e io ació com una unció lineal c eixen del emps d’inici d’una asca jun amen amb la co ba d’ap enen a ge in oduïda pe Biskup [20], la qual, en la se a o ma més bàsica es bassa en que el emps necessa i pe eali za una ope ació disminueix p opo cionalmen pel nomb e de epe icions. L’objec iu del p oblema és minimi za el nomb e d’es acions pe el qual desen olupen un model de p og amació en e a mix a no lineal. U ili zen les ma eixes axes Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 20 d’ap enen a ge i de e io amen en o es les es acions. En aques a icle ambé es p o a l’adap ació de l’en ocamen COMSOAL (Compu e me hod o sequencing ope a ions o assembly lines) pe a aques p oblema d’equilib a de línia de mun a ge a g an escala. Els exempla s u ili za s son a is p oblemes ja conegu s a la li e a u a a egin -los les axes d’ap enen a ge i de e io amen . Un al e es udi a eni en comp e és el de Hamp a e al. [21] en el qual ambé es ac a l’equilib a de línia de mun a ge simple de ipus ALBP-2 (pe an es busca minimi za el emps de cicle pe un de e mina nomb e d’es acions de eball). En aques es udi es conside en els e ec es del de e io amen i l’ap enen a ge simul àniamen i es desen olupa un model ma emà ic. A més de l’equilib a de la línia de mun a ge, el model desen olupa p esen a la p og amació de l’execució de les asques assignades a cada es ació. A més a més, es p oposa un mè ode me aheu ís ic pe al de esold e el p oblema. I pe úl im podem des aca uns dos al es es udis mol simila s en e si, degu al plan ejamen i els esul a s ob ingu s. Són el de Noushabadi e al. [22] i el de Shahanaghi e al. [23]. En aques s dos a icles s’es udia solamen l’e ec e del de e io amen d’una asca al p oblema d’equilib a de línia de mun a ge simple. En el de Noushabadi e al. es busca una p og amació de asques pe a minimi za el nomb e d’es acions dona un emps de cicle de e mina (pe an , el que es coneix com a ALBP-1). A aques e ec e, es p oposa un model ma emà ic i pos e io men , degu a que es ac a d’un p oblema NP-ha d, es p oposa un algo isme genè ic. Resolen di e sos p oblemes conegu s a la li e a u a pe a es udia el endimen de l’en ocamen p oposa . En el cas del es udi de Shahanagui e al. el que busquen és p og ama les asques a les es acions de eball pe al de minimi za el emps de cicle, el que es coneix com a ALBP-2. En aques es udi ambé es p oposa un model ma emà ic i pos e io men un algo isme genè ic. De la ma eixa mane a es esolen di e sos exemples conegu s pe il·lus a l’en ocamen p oposa . A p io i aques s dos úl ims es udis es an selecciona pe a e una compa a i a amb els esul a ob ingu s en aques p ojec e. Això es a desca a una egada anali za bé els a icles ja que es a descob i una e ada en la p opos a de esolució. Tan en el eball de Noushabadi e al. com el de Shahanaghi e al. no es enen en comp e els emps ociosos de les es acions pe calcula el de e io amen , e que anul·la la alidesa dels esul a s. 5.2. De inició del p oblema El p oblema consis eix en que, dona un emps de cicle de e mina , hi ha N asques dependen s que s’han d’assigna i p og ama a les es acions de eball. Pe an es ac a d’un ALBP-1. Al conside a la de e io ació de les asques, aques es es de e io en men e espe en a se p ocessades. Aques concep e d’espe a es po de ini com el emps que ansco e en e el momen en que una asca es à disponible pe se p ocessada i el momen en que s’inicia aques p ocessamen . Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 21 Aques emps de p ocessamen no cons an ha sigu de ini a la li e a u a com la següen unció lineal: 𝑝𝑖=𝑡𝑖+𝑏𝑖×(𝑠𝑡𝑖−𝑎𝑣𝑖) (Eq. 1) on i és la pa cons an del emps de p ocessamen de la asca i, bi co espon a la axa de c eixemen de la de e io ació de la asca i, s i (s a ime) és el emps d’inici la asca i, quan es comença a p ocessa , i a i (a ailable ime) és el emps en que la asca i passa a es a disponible. D’aques a mane a, la di e ència en e el emps d’inici i el emps en que es à disponible equi al al emps de e a d de la asca. Cal ema ca que el emps disponible d’una asca és el momen en que aques a es po eali za . En les línies de mun a ge es po eali za una asca una egada que s’hagin comple a o es les se es asques p edecesso es. El momen en que s’acabi de p ocessa l’úl ima p edecesso a d’una de e minada asca, co espond à al seu emps disponible. Pe an , com es po obse a a l’Eq. 1, pi co espon al emps de p ocessamen de la asca i enin en comp e la de e io ació. Pe il·lus a bé aques concep e, a con inuació es mos a un pe i exemple. L’exempla que es esol és un p oblema mol conegu de mida pe i a anomena Me ens. La in o mació que es e sob e aques exempla és la següen : - El nomb e de asques que é, i la pa cons an del emps de p océs de cada asca ( ecolli s a la Taula 5.1) - El emps de cicle màxim del que disposen les es acions. En aques cas de 10 segons. - Les elacions de p ecedència di ec a que enen les asques. Les elacions de p ecedències es ep esen en, al com es a habi ualmen , en un g a (Figu a 5.1). Els nodes del g a simboli zen les asques, i les a es es simboli zen que la asca de la qual su la le xa és la asca p eceden immedia a de la asca a la qual a iba la le xa. Pe exemple, la asca 5 é com a asca p eceden immedia a la asca 2, com a p eceden s o als les asques 1 i 2, i com a successo a immedia a la asca 1. Com a axa de c eixemen de la de e io ació s’ha assigna 0,1. Tasca i i 1 1 2 5 3 4 4 3 5 5 6 6 7 5 Taula 5.1. Temps de p ocessamen de les asques del p oblema Me ens. [Fon : P òpia] Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 22 Figu a 5.1. G a de p ecedències del p oblema Me ens. [Fon : P òpia] A pa i de les dades de l’exempla es poden oba di e en s solucions ac ibles, una de les quals pod ia se la p oposada a la Taula 5.2. El c i e i pe col·loca les asques ha sigu dona p io i a a les asques que inguessin emps de p océs con an ( i) més ele a , i en cas d’empa , assigna abans les asques amb menys p eceden s o als. A la úl ima columna es oben els emps de eball de cada es ació. La di e ència en e el emps de cicle màxim i el emps de eball co espon al emps mo o ociós de cada es ació. Núme o d’es ació Tasca s i a i Temps de p océs pi Temps de eball de cada es ació 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ó p oposada pel p oblema Me ens. [Fon : P òpia] A con inuació es de allen les hipò esis i ca ac e ís iques de la línia de mun a ge que es conside a en aques eball:  Les asques són indi isibles i un cop iniciada la se a execució no es poden in e omp e.  Exis eixen elacions de p ecedència en e les asques.  La línia é una du ació de les asques dependen . El emps de p ocessamen d’una de e minada asca i depèn del seu momen d’inici i del momen en el qual s’acaben de p ocessa les se es p edecesso es, essen pi el emps de p océs de la asca i (i=1,...,N). Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 23  El concep e de la de e io ació de les asques es conside a lineal.  La línia de mun a ge és simple, se ial i sínc ona.  La línia no di e ència en e ope ado s manuals o obò ics.  La axa d’en ada de les peces a la línia és ixa.  Les es acions són del ma eix ipus. Això implica que es an equipades amb els ma eixos componen s i, conseqüen men , o a asca po se assignada a qualse ol es ació. 5.3. Fo mali zació del p oblema En aques apa a es o mali za el p oblema modeli zan -lo mi jançan el següen model ma emà ic. Dades N Nomb e de asques. M Fi a supe io del nomb e d’es acions. El seu alo es pod ia de e mina , pe exemple, amb el nomb e d’es acions d’una solució calculada heu ís icamen . TC Temps de cicle màxim a espec a . 𝑡𝑖 Temps de p océs cons an de la asca i ( 1i ,...,N ). 𝑏𝑖 Taxa del c eixemen de la de e io ació de la asca i ( 1i ,...,N ). i PR Conjun de les p edecesso es immedia es de la asca i ( 1i ,...,N ). i PRT Conjun de les p edecesso es o als de la asca i   1i ,...,N : i i i h h PR PRT PR PRT      . P Conjun de pa elles de asques al que no hi ha cap elació de p ecedència en e elles:     1 1 1 ih P h,i :h ,...,N ;i h ,...,N |h PRT i PRT        . Va iables   01 ij x, 1 si la asca i es assignada a la es ació j ; 0 en cas con a i ( 1i ,...,N ; 1j ,...,M )   01 j y, 1 si és necessà ia l’es ació j ; 0 en cas con a i ( 1j ,...,M ) i p Z Temps de p océs ( enin en comp e la de e io ació) de la asca i ( 1i ,...,N ) i s  Z Ins an en que comença a p ocessa -se la asca i ( 1i ,...,N ). Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 24   01 hi w, 1 si la asca h es p ocessa abans que la asca i ; 0 en cas con a i (   h,i P ) i a  Z Ins an en que la asca i es à disponible; és a di , l’ins an en que inali za de p ocessa -se o es les se es p eceden s ( 1i ,...,N ) Model   1 MIN M j j jy    (Eq. 2) 1 1 M ij j x    1i ,...,N (Eq. 3) h h i s p s  1i ,...,N ; i h PR (Eq. 4)     1 h h i hi s p s M TC w        h,i P (Eq. 5)   i i h hi s p s M TC w       h,i P (Eq. 6)   1 1 M i ij j s TC j x          1i ,...,N (Eq. 7) 1 M i i ij j s p TC j x          1i ,...,N (Eq. 8) ij j xy 1i ,...,N ; 1j ,...,M (Eq. 9)   i i h h h PR a max s p   1i ,...,N (Eq. 10) 𝑝𝑖=𝑡𝑖+𝑏𝑖×(𝑠𝑡𝑖−𝑎𝑣𝑖) 1i ,...,N (Eq. 11) L’objec iu del model (Eq. 2) consis eix en minimi za el nomb e d’es acions necessà ies dona un emps de cicle de e mina ; aques a equació, a més a més, enca sime ies en e solucions equi alen s. L’Eq. 3 assigna cada asca a una i només una es ació. Les asques es an subjec es a elacions de p ecedència les quals es an assegu ades amb l’Eq. 4. Les Eqs. 5 i 6 assegu en que dues asques no es eali zen simul àniamen a la ma eixa es ació (cal no a que aques es es iccions només són necessà ies imposa -les pe a aquelles pa elles de asques sense elacions de p ecedència). Les Eqs. 7 i 8 assegu en que cada asca comença Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 25 i inali za en l’es ació assignada espec an el emps de cicle màxim dona . L’Eq. 9 de e mina que una es ació és necessà ia si se l’assigna al menys una asca. L’Eq. 10 ixa l’ins an de disponibili a d’una asca a l’ins an en que acaba l’úl ima de les se es p edecesso es en p ocessa -se. Finalmen , l’Eq. 11 es ableix el emps de p océs d’una asca en unció del de e io amen que ha so e des de que es à disponible ins que comença a p ocessa -se. Eq. 10 és la única exp essió no lineal del model. Si es olgués p o a de esold e el model amb un sol e de p og amació lineal, aques a equació es po lineali za de la següen mane a: Va iables addicionals   01 hi , 1 si la asca h es la úl ima p edecesso a de la asca i en p ocessa -se; 0 en cas con a i ( 1i ,...,N ; i h PR ) Res iccions addicionals (que subs i ueixen l’Eq. 11) 1 i hi h PR    1i ,...,N (Eq. 12)       1 i h h hi a s p M TC       1i ,...,N ; i h PR (Eq. 13)   i h h a s p 1i ,...,N ; i h PR (Eq. 14) L’Eq. 12 imposa que una i només una de les p edecesso es de cada asca se à la úl ima en p ocessa -se. Les Eqs. 13 i 14 ixen l’ins an de disponibili a de cada asca a l’ins an en que acaba la úl ima de les se es p edecesso es en p ocessa -se. Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 26 6. P opos a de esolució del p oblema 6.1. Mè odes de esolució Pe al de oba la solució al p oblema plan eja exis eixen di e en s mè odes de esolució que es pod ien aplica . Pe aques mo iu, en aques capí ol es a una pe i a in oducció als dos ipus de mè odes que pod ien se adien s en la esolució d’aques p oblema en conc e ; els mè odes exac es i els mè odes ap oxima s (no exac es). Els mè odes exac es són p ocedimen s que ga an eixen oba la solució òp ima d’un p oblema en un emps ini , semp e i quan aques a exis eix. De egades pe ò, el emps in e i po a iba a se d’un o d e de magni ud mol supe io al dels mè odes ap oxima s, i pe an inaplicable en mol s casos. Els mè odes ap oxima s són p ocedimen s que no ga an eixen que les solucions obades siguin òp imes pe ò el emps de càlcul és mol in e io al dels mè odes exac es. La apidesa del p océs és an impo an com la quali a de les solucions obades. Aques s mè odes solen se bones opcions a p oblemes di ícils ja que són p ocedimen s simples, basa s en el sen i comú, que p opo cionen bones solucions (no necessà iamen òp imes) de o ma àcil i àpida. Díaz e al. [24] de ineix els mè odes ap oxima s o no exac es com: “Un mè ode ap oxima és un p ocedimen pe a esold e un p oblema d’op imi zació ben de ini mi jançan una ap oximació in uï i a, en la qual la o ma de l’es uc u a del p oblema s’u ili za de o ma in el·ligen pe a ob eni una bona solució”. Els mè odes no exac es solen se bones opcions en on als exac es quan és dona alguna de les següen s ci cums àncies:  No exis eix cap mè ode exac e pe a la esolució del p oblema.  Exis eix un mè ode exac e pe ò el seu ús és massa cos ós. A mesu a que augmen en les dimensions dels exempla s a esold e, els p ocedimen s de esolució endeixen a esul a in ac ables, doncs el emps compu acional c eix de o ma exponencial, excedin els ecu sos de què es disposa.  A la indús ia no malmen una bona ap oximació ja és su icien i no cal in e i més ecu sos a oba solucions exac es. A més a més, enca a que les solucions ap oximades poden se dolen es en el pi jo dels casos, aques s mol a amen es p esen en a la eali a .  Són més lexibles que els mè odes exac es. Mol es egades s’u ili zen com a pa d’un al e mè ode. Pe exemple, pe al de p opo ciona la solució inicial de pa ida pe a aplica al es mè odes d’op imi zació. Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 33 Aques és només un exemple de com e ec ua l’in e can i de asques pe ò òb iamen hi hau an an es eïnes com possibili a s d’in e can i hi hagin. S’ha de ind e en comp e que la seqüència ob inguda ha de compli les elacions de p ecedència en o momen . Siguin a i b dues asques que es olen in e can ia , si a es oba abans en la seqüència que b, es pod an in e can ia si: - a no és una asca p edecesso a de b. - To es les p eceden s de b es oben abans en la seqüència que a. - To es les successo es de a es oben desp és en la seqüència que b. Aques es són les condicions que s’han imposa pe eali za el codi pe gene a les solucions eïnes de la solució inicial. El codi de alla es oba a l’apa a D de l’Annex. 6.2.3. Selecció de la millo eïna Un cop s’han gene a o es les seqüències eïnes, s’han d’a alua . Pe al d’a alua una seqüència eïna, es gene a una no a solució col·locan les asques en es acions o seguin l’o d e de p io i a s de la no a seqüència amb el can i eali za i emplenan al màxim cada es ació sense sob epassa el emps de cicle màxim del p oblema. Seguin amb l’exemple p oposa , a pa i de la seqüència eïna ex e a a pa i de l’in e can i de asques (Figu a 6.4), s’ha dis ibuï les asques a les es acions al i com es po eu e a la Taula 6.5. Es ació Tasca i i s i a i pi Temps de cada es ació 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 pe a la no a dis ibució de asques a les es acions al p oblema Jackson. [Fon . P òpia] Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 34 Com es po obse a , amb el can i de les asques 3 i 5 amb el qual s’ha gene a una solució eïna de la solució inicial, s’ha pogu dis ibui o es les asques en 4 es acions en comp es de en 5 es acions com ho eia la solució inicial. A con inuació, a la Figu a 6.5, es po eu e la no a seqüència de asques dis ibuïdes en es acions (cada colo co espon a una es ació). Figu a 6.5. No a dis ibució de asques del p oblema Jackson amb TC=14 i b=0,1. [Fon : P òpia] Cal ema ca pe ò que aques a és només una eïna que ha millo a la solució inicial. De la ma eixa mane a, en aques a e apa s’han pogu oba al es eïnes que ambé millo in en la ma eixa p opo ció la solució inicial, i pe an , ambé s’hau ien d’es udia . Po se ambé que hi hagi alguna al e eïna que millo es enca a més la solució inicial. En aques cas, es con inua ia la ce ca local pe aques a i no pe la obada an e io men . Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 35 7. Expe iència compu acional 7.1. Exempla s de es eig Pe al d’a alua el uncionamen del p ocedimen de esolució p oposa s’ha eali za una expe iència compu acional a pa i d’un conjun d’exempla s de es a ge. L’objec iu de l’expe imen és es udia el compo amen del p ocedimen a l’ho a de esold e exempla s de di e en s mides. Pe du a e me l’expe imen ació, s’ha escolli u ili za el conjun de dades de Scholl [26] pe a p oblemes d’equilib a de línia de mun a ge simple (SALBP). S’ha decidi u ili za aques s exempla s ja que es oben ecolli s amb lliu e accés a la pàgina www.assembly-line-balancing.de i pe què s’han u ili za pe p o a i compa a p ocedimen s en mol s es udis sob e l’equilib a de línies, poden així compa a esul a s si s’escau. A més a més, aques conjun de dades es ca ac e i zen pe es a compos os pe una g an a ie a de línies di e en s el qual pe me pode p o a la p opos a de esolució en di e sos casos. Degu a que aques es dades es an o ien ades pe a esold e p oblemes SALBP i no exis eix cap banc de dades especí ic pe es udia el p oblema de línies de mun a ge on es é en comp e l’e ec e de la de e io ació, s’ha hagu de ia i a egi la dada de la axa c eixemen de la de e io ació b. S’es udien 5 possibili a s di e en s pe anali za la incidència que é la de e io ació en l’equilib a de la línia. S’anali zen cada un dels exempla s del SALBP amb les següen s possibili a s de de e io ació: - b=0,1 en o es les asques. - b=0,2 en o es les asques. - b=0, és a di , e ec e nul de la de e io ació en aquelles asques que no enen p edecesso es. I b=0,1 a les demés asques. - b=0, és a di , e ec e nul de la de e io ació en aquelles asques que no enen p edecesso es. I b=0,2 a les demés asques. - b=nomb e alea o i en cada asca comp és en e el 0 i el 0,2, ambdós inclosos. El mo iu pe el qual s’han ia els alo de b=0,1 i b=0,2 i no d’al es ha sigu pe què han es a u ili za s en la li e a u a i pe an , acili a el pode compa a els esul a s amb al es es udis si s’escau. La aó pe al qual s’han conside a les a ian s en les quals aquelles asques sense p edecesso es enen de e io ació nul·la és pe què aques es asques es an disponibles en l’ins an inicial i no malmen són de les p ime es en p ocessa -se. Pe an , al no ind e emps d’espe a no enen pe què ind e l’e ec e de la de e io ació. Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 36 Com que aques s exempla s es an pensa s pe a esold e p oblemes de ipus SALBP (i UALBP) on les du ades de les asques són de e minis es, al aplica un p oblema on les asques es de e io en, en alguns casos no s’ha oba cap combinació possible d’adjudicació de asques degu a aques e ec e. Això és degu onamen almen a dos mo ius. En p ime lloc, es po dona el cas de que segons els c i e is de p io i a que segueixen les heu ís iques pe a l’assignació de asques a les di e en s es acions, hi hagin asques que augmen in an el emps d’espe a que el seu p opi emps de p ocessamen sigui majo que el màxim emps de cicle pe més. Això p o oca que no hi hagi cap combinació possible d’adjudicació de asques degu a l’e ec e de e io a iu. Pe an , en aques s casos, les heu ís iques p oposades no són àlides pe a esold e aques s p oblemes. També es possible que pe ca ac e ís iques del p oblema en si, no sigui possible aplica -li el concep e de de e io ació de asques. Això passa en p oblemes on pe exemple, els emps de cicles són mol baixos, o on els emps de p océs cons an s de les asques són ele a s. A ques e a que pe mol pe i a que sigui la axa de de e io ació, i pe an augmen i poc el emps d’espe a, les du ades d’algunes asques puguin sob epassa igualmen el emps de cicle màxim. Això ambé po succei en p oblemes g ans on hi ha una quan i a de asques mol ele ada, ja que hi poden ha e emps d’espe a mol g ans. En el banc de dades u ili za això succeeix en 4 p oblemes que han sigu p è iamen desca a s (Ba hold 2, Mukhe je, Scholl i Wee-Mag). A la Taula 7.1 es oben ecolli s o s els exempla s u ili za s. La e ce a columna de la aula ( min) a e e ència a la pa cons an del emps de p océs de asca més pe i a que é l’exempla . De la ma eixa mane a, la qua a columna ( max) a e e ència a la pa cons an del emps de p océs més g an. La cinquena co espon a l’in e al en el qual es oben els emps de cicle de cada a ian de l’exempla , ambdós inclosos. La sisena columna indica la quan i a d’exempla s que é cada p oblema, és a di , la quan i a de a ian s amb un emps de cicle i una axa de de e io ació di e en cada un. I pe úl im, la se ena columna, indica el pe cen a ge de cada p oblema que s’ha oba solució a egin el concep e de de e io ació de les asques. En o al, hi ha 895 exempla s. Aques s exempla s, al com ja s’ha indica , s’han c ea a pa i dels 179 exempla s del SALBP combina s amb les 5 possibles axes de de e io ació. Pe cada exempla s’ha oba una solució pe cada una de les 12 heu ís iques, amb les quals se li han aplica l’op imi zació. Del o al, s’han oba solució ac ible de 670 exempla s. Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 37 P oblema Núme o de Tasques min max In e al de TC Exempla s % d’exempla s amb solució Me ens 7 1 6 6-18 30 83,33 Bowman 8 3 17 20 5 100 Jaeschke 9 1 6 6-18 25 80 Mansoo 11 2 45 48-94 15 100 Jackson 11 1 7 7-21 30 83,33 Mi chell 21 1 13 14-39 30 100 Roszieg 25 1 13 14-32 30 100 Heskiao 28 1 108 138-342 30 100 Buxey 29 1 25 27-54 35 100 Sawye 30 1 25 25-75 45 88,89 Lu z1 32 100 1400 1414-2828 30 100 Gun he 35 1 40 41-81 35 85,71 Kilb idge 45 3 55 56-184 50 80 Hahn 53 40 1775 2004-4676 25 100 Wa necke 58 7 53 54-111 80 31,25 Tonge 70 1 156 160-527 80 62,50 A cus1 83 233 3691 3786-10816 80 100 Lu z3 89 1 74 75-150 60 75 Lu z2 89 1 10 11-21 55 36,36 A cus2 111 10 5689 5755-17067 85 41,18 Ba hold 148 3 383 403-805 40 87,50 To al d’exempla s: 895 Taula 7.1. Exempla s u ili za s pe a la expe iència compu acional [Fon . P òpia] Pe al d’a alua p è iamen els algo ismes u ili za s, s’ha esol el p oblema sense l’e ec e de la de e io ació amb o s els exempla s de es eig del SALBP (excep e els 4 p oblemes que s’han des a a p è iamen ). Pe an , s’ha esol un SALBP-1. Això po dona una idea de l’e ec i i a de cada heu ís ica sense que es egi a ec ada pe el de e io amen . Pe a alua els esul a s ob ingu s, s’han u ili za els alo s òp ims del nomb e d’es acions de cada exempla del p oblema del SALBP-1 p o inen s del banc de dades. Aques s alo s s’han u ili za com a i es pe al de compa a amb els esul a s. Dels 2148 exempla s a alua s en aques a simulació (179 p oblemes pe les 12 heu ís iques), s’han ob ingu 1336 solucions òp imes, el que ep esen a el 62,20% de o a la mos a. Els esul a s es oben a l’apa a B de l’Annex. Els codis dels algo ismes han es a p og ama s en Py hon i han sigu execu a s amb un o dinado amb p ocessado In el Co e i7 de 2.6GHz amb el sis ema ope a iu Ubun u 16.04 LTS. To s els codis u ili za s es poden oba a l’apa a D de l’Annex. Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 38 Els emps d’execució pe cada un dels algo ismes es oben a l’apa a A de l’Annex, on el emps màxim ha es a d’uns 17 segons. 7.2. Anàlisis de esul a s Com que pe a la esolució d’aques p oblema s’han e se i p ocedimen s heu ís ics i pe an no es ga an eixen oba solucions òp imes, cal mesu a la quali a d’aques s mè odes u ili za s pe al de de e mina la se a alidesa. Pe a alua el uncionamen dels p ocedimen s dissenya s i pe compa a -los en e ells s’u ili zen les següen s mesu es:  Compa ació amb una i a. Com que es desconeixen els alo s òp ims d’aques p oblema, el que es po e és compa a les solucions ob ingudes de cada heu ís ica amb i es. Les i es amb les quals s’han compa a p o enen del banc de dades que s’ha u ili za i co esponen al mínim d’es acions que es po dona pe cada exempla . Cal des aca pe ò, que aques es i es co esponen al mínim d’es acions al qual es po a iba en una dis ibució de asques del p oblema con encional (SALBP-1), és a di , sense eni en comp e l’e ec e de la de e io ació. En cap cas aques s alo s han de se els alo s òp ims en aques a a ian s del p oblema ja que en alguns casos a iba a aques a solució és inassolible degu a l’e ec e de e io a iu. El que si que es po assegu a es que aquells exempla s que enen aques s alo s, han a iba a la solució òp ima, pe ò no es po assegu a que aquells alo s que no hi han a iba no siguin òp ims. A la Taula 7.2 s’obse a el nomb e de egades que cada heu ís ica aplicada pe oba la solució inicial assoleix el alo de la i a. To i que els alo s ob ingu s són baixos compa a s amb la mos a de la qual es pa eix no es po a i ma que el mè ode aplica sigui poc e ec iu pe la aó an e io men exposada. D’aques es dades es poden eu e conclusions sob e les egles de p io i a que sembla que ajus in millo el p oblema, la qual sembla se l’heu ís ica 5 que co espon a o dena les asques segons el mínim emps de p océs de la asca i de les se es p edecesso es ponde a pel emps de cicle. To i això, no hi ha una di e ència gai e signi ica i a en e les al es heu ís iques. A la Taula 7.3 es oben el nomb e de egades que l’op imi zació assoleix el alo de i a. S’obse a que les e sions que més han millo a han sigu en aquelles en que la axa de de e io ació és b=0,2 i la combinació de b=0,2 i b=0, men e que les al es e sions no s’ap ecien una di e ència gai e no able. Cal des aca que les e sions on s’ha dona una millo a signi ica i a són ambé les que es pa ien d’una solució pi jo . Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació 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 alea ò ia 3 12 4 9 8 3 6 9 8 4 10 3 Taula 7.2: Nomb e de egades que cada heu ís ica inicial a iba al alo de la i a. [Fon : P ò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 alea ò ia 4 14 4 9 8 4 6 9 8 5 11 4 Taula 7.3: Nomb e de egades que cada op imi zació a iba al alo de la i a. [Fon : P òpia]  Nomb e de egades que cada p ocedimen ha ob ingu la millo solució pe cada a ian del p oblema. A la Taula 7.4 es po obse a quan es egades cada heu ís ica u ili zada pe ob eni les solucions inicials han ob ingu la millo solució. Cal ind e en comp e que la millo solució en cap cas ol di que sigui la solució òp ima. Es po eu e que la endència es simila s en e les a ian s amb axa de de e io ació b=0,1 i el que u ili za b=0 pe les asques sense p eceden s i b=0,1 pe les demés. Es po ap ecia una lleuge a millo a pe aques a úl ima a ian , e que esul a lògic ja que si no s’aplica de e io ació en algunes asques, el emps de p océs o al endeix a disminui . Aques a ma eixa endència ambé es oba en e la a ian amb axa de de e io ació b=0,2 i la de b=0 pe les p ime es asques i b=0,2 pe la es a de asques, ambé amb una pe i a millo a pe aques a úl ima. També es po obse a que s’han ob ingu esul a s no ablemen millo s amb la axa de de e io ació mes baix com ja s’espe a a. En quan a la Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 40 a ian de axa b alea ò ia s’han ob ingu esul a s millo que aquells amb b=0,2 pe ò pi jo s que amb b=0,1. A l’ho a de compa a en e heu ís iques, en el cas de les a ian amb b=0,1 des aca pe sob e de les demés l’H5. En quan a les a ian s amb b=0,2, es poden des aca en la ma eixa mesu a l’H2 i l’H9 co esponen s espec i amen a les egles de p io i a de màxim emps de p océs de asca i màxim emps de p océs asca i de les se es successo es. A la Taula 7.5 es oben les egades que l’op imi zació local ha oba les millo s solucions. Es po obse a , que no hi ha millo es gai e no ables espec e als esul a s inicials ecolli s a la Taula 7.4. Les a ian s que més han millo a els esul a s han sigu les de b=0,2. To i així, com que en aques s casos hi ha més ma ge de millo a, segueixen ob enin millo s esul a s aquells amb axa de de e io ació més baix. A la Figu a 7.1 es po eu e ep esen a en un g à ic cla amen on els màxims es oben en les heu ís iques H2, H5, H9 i H11, e que indica que aques es heu ís iques pe me en oba millo s 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 alea ò ia 14 54 14 27 45 15 20 38 47 17 45 9 Taula 7.4: Nomb e de egades que cada heu ís ica inicial oba la millo solució. [Fon : P ò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 alea ò ia 16 57 14 27 47 17 20 38 47 18 46 10 Taula 7.5: Nomb e de egades que cada op imi zació oba la millo solució. [Fon : P òpia] Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 41 Figu a 7.1: G à ic ep esen a iu del nomb e de egades que l’op imi zació assoleix la millo solució pe cada heu ís ica. [Fon : P òpia]  Millo a de l’op imi zació local: Pe es udia més a ons l’e ec e del p océs de millo a, s’han ecolli a la Taula 7.6 el nomb e d’exempla s que l’op imi zació local millo a espec e a la solució inicial. Pe o s els casos es po obse a una cla a supe io i a de l’heu ís ica 5 on les demés, seguida pe 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 alea ò ia 2 4 3 5 15 4 3 6 7 1 10 2 Taula 7.6: Nomb e d’exempla s que l’op imi zació local millo a. [Fon : P ò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 alea o i Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 42  Mi jana del nomb e d’es acions. Es ac a de e la mi jana del nomb e d’es acions de les solucions ob ingudes pe cada p ocedimen i pe cada exempla s de es eig. Aques mè ode d’anàlisi pe me compa a lo bones que poden se les di e en s heu ís iques. Com que no o es les heu ís iques donen solució a la ma eixa quan i a d’exempla s ni als ma eixos exempla s en alguns casos (a la Taula 7.1 de l’apa a an e io mos a el pe cen a ge d’exempla s que les heu ís iques han oba solució), només s’ha calcula la mi jana d’es acions pe a aquells exempla s que o es les heu ís iques oben solució. D’aques a mane a, s’e i a oba esul a s con usos ja que pod ia se que l’heu ís ica més bona obes més quan i a de esul a s pe a exempla s amb nomb es d’es acions ele a s. A l’ho a de e la mi jana i compa a -la amb una heu ís ica pi jo que només obés solucions pe a exempla s amb poques es acions, aques a úl ima ind ia una mi jana in e io que l’heu ís ica més bona, el que po a ia a oba conclusions e ònies. Pe aques a ma eixa aó ambé, en aques cas només es compa en les heu ís iques amb axa de de e io ació de b=0,1 i la con inació de b=0,1 i b=0, ja que la quan i a d’exempla s que la e sió amb axa de de e io ació b=0,1 és mol més ele ada a la que es oba amb b=0,2 i impossibili a e una compa ació en e elles. A la Taula 7.7 es oben les mi janes del nomb e d’es acions pe cada heu ís ica. Es po obse a que les mi janes més baixes coincideixen amb les heu ís iques que amb els p e is mè odes d’a aluació e ec ua s han sembla se les més e ec i es. Aques es són, o denades pe majo e icàcia, les H5, H8, H2, H11 i H9. En quan al p océs d’op imi zació, els esul a s ob ingu s ( ecolli s a la Taula 7.8) són equi alen s als de les solucions inicials. Es po obse a una disminució de la mi jana del nomb e d’es acions amb l’op imi zació local espec e les solucions inicials. Pe úl im es po eali za una compa ació en e les mi janes de les heu ís iques amb la mi jana del nomb e d’es acions de la i a. La mi jana dels alo s òp ims del nomb e d’es acions dels exempla s conside a s en aques càlcul és de 4,889. Es po obse a que només hi ha una es ació de di e ència en e la mi jana dels alo s òp ims del p oblema del SALBP-1 i la mi jana de la millo heu ís ica obada, 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: Mi jana del nomb e d’es acions de les solucions inicials. [Fon : P òpia] Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 49 Annex B. Solucions inicials de l’expe iència compu acional Solucions incials pe a b=0,1. P ecedence g aph c m* H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 H12 A cus1 3786 21 28 A cus1 3985 20 28 A cus1 4206 19 25 27 A cus1 4454 18 27 25 26 23 A cus1 4732 17 26 23 23 21 A cus1 5048 16 25 21 21 19 A cus1 5408 15 22 19 19 17 A cus1 5824 14 20 18 17 17 A cus1 5853 14 20 17 17 17 A cus1 6309 13 18 17 16 16 A cus1 6842 12 18 17 15 15 14 A cus1 6883 12 18 16 15 15 14 A cus1 7571 11 14 15 13 14 12 15 A cus1 8412 10 14 13 12 12 11 15 A cus1 8898 9 14 13 11 11 11 14 A cus1 10816 8 10 10 9 9 9 10 A cus2 8847 18 27 A cus2 9400 17 25 28 A cus2 10027 16 23 A cus2 10743 15 21 A cus2 11378 14 19 25 A cus2 11570 13 18 26 A cus2 17067 9 20 13 17 Ba hold 434 13 Ba hold 470 12 Ba hold 513 11 Ba hold 564 10 Ba hold 626 9 Ba hold 705 8 Ba hold 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 Gun he 44 12 18 18 Gun he 49 11 16 15 16 15 16 15 16 15 16 Gun he 54 9 15 15 15 15 15 13 14 13 15 15 15 Gun he 61 9 12 11 12 12 12 12 13 12 11 12 11 12 Gun he 69 8 11 11 11 10 10 11 10 10 11 11 11 11 Gun he 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 Heskiao 138 8 Heskiao 205 5 8 11 Heskiao 216 5 12 8 12 10 Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 50 Heskiao 256 4 12 11 7 12 11 7 12 Heskiao 324 4 12 11 7 5 12 12 7 6 11 12 Heskiao 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 Kilb idge 56 10 Kilb idge 69 8 14 14 Kilb idge 79 7 13 Kilb idge 92 6 11 10 13 Kilb idge 110 6 10 9 8 9 10 Kilb idge 111 5 10 9 8 9 10 Kilb idge 138 4 8 10 6 8 9 8 Kilb idge 184 3 10 5 11 7 5 10 8 6 6 10 5 9 Lu z1 1414 11 14 13 14 Lu z1 1572 10 12 12 11 13 12 Lu z1 1768 9 10 11 11 11 11 10 Lu z1 2020 8 11 9 11 9 9 11 9 10 11 9 11 Lu z1 2357 7 9 8 8 8 8 9 8 8 9 9 8 8 Lu z1 2828 6 8 6 8 7 6 8 8 6 7 8 6 8 Lu z2 18 28 41 41 Lu z2 19 26 Lu z2 20 25 36 Lu z2 21 24 Lu z3 87 20 Lu z3 92 19 24 Lu z3 97 18 23 Lu z3 103 17 22 Lu z3 110 15 21 Lu z3 118 14 18 20 Lu z3 127 14 21 17 21 Lu z3 137 13 16 16 15 17 17 Lu z3 150 12 14 16 14 15 15 14 19 Mansoo 48 4 5 5 5 Mansoo 62 3 4 4 4 4 4 4 4 4 4 4 4 4 Mansoo 94 2 3 3 3 3 3 3 3 3 3 3 3 3 Me ens 7 5 6 6 6 6 6 6 6 6 6 Me ens 8 5 6 6 6 6 6 6 6 6 6 6 6 6 Me ens 10 3 5 4 5 5 5 5 4 4 4 5 4 5 Me ens 15 2 3 3 3 3 3 3 3 3 3 3 3 3 Me ens 18 2 3 2 3 3 2 3 2 3 2 3 2 3 Mi chell 14 8 10 10 10 11 10 Mi chell 15 8 10 10 10 10 11 10 10 10 Mi chell 21 5 7 6 7 7 7 7 8 7 7 7 6 7 Mi chell 26 5 6 6 6 5 5 6 6 5 5 6 6 6 Mi chell 35 3 4 4 4 4 4 4 4 4 4 4 4 4 Mi chell 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 p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 51 Sawye 27 13 18 Sawye 30 12 16 18 Sawye 33 11 16 15 Sawye 36 10 14 15 Sawye 41 8 12 14 13 Sawye 47 7 11 11 11 10 11 Sawye 54 7 10 9 9 9 10 Sawye 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 Wa necke 82 20 Wa necke 92 17 Wa necke 97 17 Wa necke 104 15 Wa necke 111 14 Solucions incials pe a b=0,2. P ecedence g aph c m* H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 H12 A cus1 3786 21 A cus1 3985 20 A cus1 4206 19 A cus1 4454 18 A cus1 4732 17 A cus1 5048 16 A cus1 5408 15 A cus1 5824 14 21 27 A cus1 5853 14 21 A cus1 6309 13 21 23 17 A cus1 6842 12 18 21 16 A cus1 6883 12 18 21 16 A cus1 7571 11 16 20 13 A cus1 8412 10 15 16 13 A cus1 8898 9 15 15 12 A cus1 10816 8 11 13 10 A cus2 8847 18 A cus2 9400 17 A cus2 10027 16 A cus2 10743 15 A cus2 11378 14 A cus2 11570 13 A cus2 17067 9 Ba hold 434 13 Ba hold 470 12 Ba hold 513 11 Ba hold 564 10 Ba hold 626 9 Ba hold 705 8 Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 52 Ba hold 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 Gun he 44 12 Gun he 49 11 Gun he 54 9 Gun he 61 9 Gun he 69 8 13 Gun he 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 Heskiao 138 8 Heskiao 205 5 Heskiao 216 5 Heskiao 256 4 Heskiao 324 4 7 Heskiao 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 Kilb idge 56 10 Kilb idge 69 8 Kilb idge 79 7 Kilb idge 92 6 Kilb idge 110 6 Kilb idge 111 5 Kilb idge 138 4 Kilb idge 184 3 7 Lu z1 1414 11 Lu z1 1572 10 Lu z1 1768 9 12 12 Lu z1 2020 8 11 10 Lu z1 2357 7 10 9 9 9 10 10 Lu z1 2828 6 7 7 7 8 8 7 Lu z2 18 28 Lu z2 19 26 Lu z2 20 25 Lu z2 21 24 Lu z3 87 20 Lu z3 92 19 Lu z3 97 18 Lu z3 103 17 Lu z3 110 15 Lu z3 118 14 Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 53 Lu z3 127 14 Lu z3 137 13 Lu z3 150 12 Mansoo 48 4 6 6 6 Mansoo 62 3 5 4 5 5 5 4 5 4 4 Mansoo 94 2 3 3 4 3 3 3 3 3 3 4 3 4 Me ens 7 5 Me ens 8 5 Me ens 10 3 5 5 5 4 5 5 Me ens 15 2 4 3 3 3 3 4 3 3 3 4 3 4 Me ens 18 2 3 3 3 3 3 3 3 3 3 3 3 3 Mi chell 14 8 12 13 12 Mi chell 15 8 Mi chell 21 5 8 8 9 9 Mi chell 26 5 8 6 6 8 Mi chell 35 3 5 5 5 5 4 5 6 5 5 5 5 6 Mi chell 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 Sawye 27 13 Sawye 30 12 Sawye 33 11 Sawye 36 10 Sawye 41 8 Sawye 47 7 Sawye 54 7 Sawye 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 Wa necke 82 20 Wa necke 92 17 Wa necke 97 17 Wa necke 104 15 Wa necke 111 14 Solucions incials pe a b=0,1 i b=0. P ecedence g aph c m* H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 H12 A cus1 3786 21 28 A cus1 3985 20 28 A cus1 4206 19 25 27 A cus1 4454 18 27 25 26 23 A cus1 4732 17 26 23 23 21 A cus1 5048 16 25 21 21 19 Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 54 A cus1 5408 15 22 19 19 17 A cus1 5824 14 20 18 17 17 A cus1 5853 14 20 17 17 17 A cus1 6309 13 18 17 16 16 A cus1 6842 12 18 17 15 15 14 A cus1 6883 12 18 16 15 15 14 A cus1 7571 11 14 15 13 14 12 15 A cus1 8412 10 14 13 12 12 11 15 A cus1 8898 9 14 13 11 11 11 14 A cus1 10816 8 10 10 9 9 9 10 A cus2 8847 18 27 A cus2 9400 17 25 28 A cus2 10027 16 23 A cus2 10743 15 21 A cus2 11378 14 19 25 A cus2 11570 13 18 26 A cus2 17067 9 20 13 17 Ba hold 434 13 20 21 Ba hold 470 12 18 18 Ba hold 513 11 16 Ba hold 564 10 15 16 Ba hold 626 9 13 16 13 Ba hold 705 8 12 16 16 11 Ba hold 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 Gun he 44 12 18 18 Gun he 49 11 16 14 15 16 14 14 Gun he 54 9 14 14 14 15 14 13 14 13 14 14 13 Gun he 61 9 13 11 12 11 12 13 13 12 10 12 11 12 Gun he 69 8 12 10 11 10 10 12 10 10 10 11 10 11 Gun he 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 Heskiao 138 8 Heskiao 205 5 12 8 12 12 Heskiao 216 5 12 11 8 11 11 12 Heskiao 256 4 12 10 7 10 8 12 Heskiao 324 4 11 10 7 5 11 11 7 6 11 10 11 Heskiao 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 Kilb idge 56 10 15 15 Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 55 Kilb idge 69 8 14 14 Kilb idge 79 7 12 12 12 Kilb idge 92 6 11 11 11 11 Kilb idge 110 6 9 9 8 9 9 9 Kilb idge 111 5 9 8 8 9 9 9 Kilb idge 138 4 11 7 9 6 11 9 8 7 7 11 Kilb idge 184 3 9 5 8 6 5 9 7 6 5 9 5 8 Lu z1 1414 11 13 14 14 14 14 13 Lu z1 1572 10 12 11 12 12 11 12 11 12 12 11 12 Lu z1 1768 9 12 10 11 11 11 12 11 11 10 11 10 11 Lu z1 2020 8 11 9 11 9 9 11 10 9 9 11 9 10 Lu z1 2357 7 8 8 8 8 8 8 8 8 9 9 8 8 Lu z1 2828 6 7 6 7 6 6 7 7 6 6 7 6 7 Lu z2 18 28 41 41 Lu z2 19 26 38 Lu z2 20 25 Lu z2 21 24 Lu z3 87 20 25 25 Lu z3 92 19 24 Lu z3 97 18 23 Lu z3 103 17 22 Lu z3 110 15 21 Lu z3 118 14 18 18 18 Lu z3 127 14 21 17 21 Lu z3 137 13 18 15 16 Lu z3 150 12 16 18 14 16 19 Mansoo 48 4 5 5 5 5 5 5 5 5 4 5 5 5 Mansoo 62 3 4 4 4 4 4 4 4 4 4 4 4 4 Mansoo 94 2 3 3 3 3 3 3 3 3 2 3 3 3 Me ens 7 5 6 6 6 6 6 6 6 6 6 Me ens 8 5 6 6 6 6 6 6 6 6 6 6 6 6 Me ens 10 3 5 4 5 5 5 5 4 4 4 5 4 5 Me ens 15 2 3 3 3 3 3 3 3 3 3 3 3 3 Me ens 18 2 3 2 3 3 2 3 2 3 2 3 2 3 Mi chell 14 8 10 10 10 11 10 Mi chell 15 8 10 10 10 10 11 10 10 10 Mi chell 21 5 7 6 7 7 7 7 8 7 7 7 6 7 Mi chell 26 5 6 6 6 5 5 6 6 5 5 6 6 6 Mi chell 35 3 4 4 4 4 4 4 4 4 4 4 4 4 Mi chell 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 Sawye 27 13 17 Sawye 30 12 16 17 Sawye 33 11 15 15 13 Sawye 36 10 14 15 11 Sawye 41 8 12 12 11 Sawye 47 7 11 11 10 9 11 Sawye 54 7 9 9 8 8 8 9 Sawye 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 p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació 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 Wa necke 82 20 27 Wa necke 92 17 Wa necke 97 17 23 23 Wa necke 104 15 22 Wa necke 111 14 21 20 Solucions incials pe a b=0,2 i b=0. P ecedence g aph c m* H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 H12 A cus1 3786 21 A cus1 3985 20 A cus1 4206 19 A cus1 4454 18 A cus1 4732 17 A cus1 5048 16 A cus1 5408 15 A cus1 5824 14 21 27 A cus1 5853 14 21 A cus1 6309 13 21 23 17 A cus1 6842 12 18 21 16 A cus1 6883 12 18 21 16 A cus1 7571 11 16 20 13 A cus1 8412 10 15 16 13 A cus1 8898 9 15 15 12 A cus1 10816 8 11 13 10 A cus2 8847 18 A cus2 9400 17 A cus2 10027 16 A cus2 10743 15 A cus2 11378 14 A cus2 11570 13 A cus2 17067 9 Ba hold 434 13 Ba hold 470 12 Ba hold 513 11 Ba hold 564 10 Ba hold 626 9 Ba hold 705 8 Ba hold 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 Gun he 44 12 Gun he 49 11 Gun he 54 9 Gun he 61 9 Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 57 Gun he 69 8 11 13 12 11 Gun he 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 Heskiao 138 8 Heskiao 205 5 Heskiao 216 5 Heskiao 256 4 Heskiao 324 4 6 Heskiao 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 Kilb idge 56 10 Kilb idge 69 8 Kilb idge 79 7 Kilb idge 92 6 Kilb idge 110 6 Kilb idge 111 5 Kilb idge 138 4 9 Kilb idge 184 3 7 Lu z1 1414 11 16 15 15 Lu z1 1572 10 12 12 12 Lu z1 1768 9 11 12 12 12 11 Lu z1 2020 8 10 11 11 11 10 Lu z1 2357 7 9 9 9 8 9 Lu z1 2828 6 7 7 6 7 9 9 7 9 Lu z2 18 28 Lu z2 19 26 Lu z2 20 25 Lu z2 21 24 Lu z3 87 20 Lu z3 92 19 Lu z3 97 18 Lu z3 103 17 Lu z3 110 15 Lu z3 118 14 Lu z3 127 14 Lu z3 137 13 Lu z3 150 12 Mansoo 48 4 5 5 5 5 5 5 5 5 4 5 5 5 Mansoo 62 3 5 4 4 5 5 5 4 5 4 4 4 4 Mansoo 94 2 3 3 3 3 3 3 3 3 2 3 3 3 Me ens 7 5 Me ens 8 5 Me ens 10 3 5 5 5 4 5 5 Me ens 15 2 4 3 3 3 3 4 3 3 3 4 3 4 Me ens 18 2 3 3 3 3 3 3 3 3 3 3 3 3 Mi chell 14 8 12 13 12 Mi chell 15 8 Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 58 Mi chell 21 5 8 8 9 9 Mi chell 26 5 8 6 6 8 Mi chell 35 3 5 5 5 5 4 5 6 5 5 5 5 6 Mi chell 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 Sawye 27 13 Sawye 30 12 Sawye 33 11 Sawye 36 10 Sawye 41 8 Sawye 47 7 Sawye 54 7 11 10 Sawye 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 Wa necke 82 20 Wa necke 92 17 Wa necke 97 17 Wa necke 104 15 Wa necke 111 14 Solucions incials pe a b alea ò ia dins l’in e al [0, 0,2]. P ecedence g aph c m* H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 H12 A cus1 3786 21 28 A cus1 3985 20 26 25 A cus1 4206 19 24 A cus1 4454 18 24 24 A cus1 4732 17 22 24 19 A cus1 5048 16 19 20 18 A cus1 5408 15 19 20 19 A cus1 5824 14 17 17 16 A cus1 5853 14 17 18 16 A cus1 6309 13 16 16 16 14 A cus1 6842 12 14 15 15 15 14 A cus1 6883 12 16 14 14 13 A cus1 7571 11 15 13 14 12 A cus1 8412 10 11 13 11 12 12 A cus1 8898 9 13 12 12 12 A cus1 10816 8 10 10 9 9 9 10 A cus2 8847 18 A cus2 9400 17 A cus2 10027 16 23 Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 65 Wa necke 60 27 29 29 30 30 34 29 30 30 30 30 29 30 Wa necke 62 27 29 29 29 30 32 29 30 30 29 29 29 30 Wa necke 65 25 27 28 29 29 31 27 28 29 29 27 28 28 Wa necke 68 24 26 26 26 27 28 26 26 27 27 26 25 26 Wa necke 71 23 24 26 24 25 27 24 25 25 25 25 25 25 Wa necke 74 22 23 25 23 24 25 23 24 25 24 23 24 24 Wa necke 78 21 21 23 22 22 25 21 23 23 22 21 22 23 Wa necke 82 20 20 21 21 21 24 20 21 22 21 21 21 21 Wa necke 86 19 19 20 19 20 23 19 20 21 20 19 20 20 Wa necke 92 17 19 19 19 19 20 19 19 19 19 19 19 19 Wa necke 97 17 17 18 18 18 18 17 18 18 17 17 18 18 Wa necke 104 15 16 16 16 17 17 16 17 16 16 16 16 17 Wa necke 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 p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 66 Annex C. Solucions de l’op imi zació local a pa i de l’exepe iència compu acional Solucions de l’op imi zació local amb b=0,1. P ecedence g aph c m* H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 H12 A cus1 3786 21 28 A cus1 3985 20 28 A cus1 4206 19 24 26 A cus1 4454 18 27 23 26 23 A cus1 4732 17 25 22 22 20 A cus1 5048 16 23 20 21 19 A cus1 5408 15 22 18 19 17 A cus1 5824 14 20 17 17 17 A cus1 5853 14 20 17 17 17 A cus1 6309 13 18 15 16 15 A cus1 6842 12 18 17 14 15 14 A cus1 6883 12 18 16 15 15 14 A cus1 7571 11 14 15 13 14 12 15 A cus1 8412 10 12 13 12 12 11 13 A cus1 8898 9 13 13 11 11 11 13 A cus1 10816 8 10 10 9 9 9 10 A cus2 8847 18 26 A cus2 9400 17 24 28 A cus2 10027 16 22 A cus2 10743 15 21 A cus2 11378 14 19 24 A cus2 11570 13 18 25 A cus2 17067 9 18 13 17 Ba hold 434 13 Ba hold 470 12 Ba hold 513 11 Ba hold 564 10 Ba hold 626 9 Ba hold 705 8 Ba hold 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 Gun he 44 12 17 17 Gun he 49 11 16 15 16 15 16 15 16 15 16 Gun he 54 9 15 15 15 14 15 13 13 13 15 15 15 Gun he 61 9 12 11 12 12 11 12 12 12 11 12 11 12 Gun he 69 8 11 10 11 10 10 11 10 10 10 11 10 11 Gun he 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 Heskiao 138 8 Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 67 Heskiao 205 5 8 11 Heskiao 216 5 12 7 12 8 Heskiao 256 4 12 9 7 12 9 7 12 Heskiao 324 4 12 11 7 5 12 8 7 6 11 12 Heskiao 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 Kilb idge 56 10 Kilb idge 69 8 14 14 Kilb idge 79 7 13 Kilb idge 92 6 11 10 13 Kilb idge 110 6 10 9 8 9 10 Kilb idge 111 5 10 9 8 9 10 Kilb idge 138 4 8 8 6 8 9 8 Kilb idge 184 3 10 5 10 7 5 10 7 6 6 10 5 9 Lu z1 1414 11 13 13 13 Lu z1 1572 10 12 11 11 13 12 Lu z1 1768 9 10 11 11 10 11 10 Lu z1 2020 8 11 9 11 9 9 11 9 10 11 9 11 Lu z1 2357 7 8 8 8 8 8 8 8 8 9 8 8 8 Lu z1 2828 6 7 6 7 7 6 7 7 6 7 7 6 7 Lu z2 18 28 41 41 Lu z2 19 26 Lu z2 20 25 35 Lu z2 21 24 Lu z3 87 20 Lu z3 92 19 24 Lu z3 97 18 23 Lu z3 103 17 21 Lu z3 110 15 19 Lu z3 118 14 18 19 Lu z3 127 14 21 17 21 Lu z3 137 13 16 16 15 16 16 Lu z3 150 12 14 16 14 15 15 14 19 Mansoo 48 4 5 5 5 Mansoo 62 3 4 4 4 4 4 4 4 4 4 4 4 4 Mansoo 94 2 3 3 3 3 3 3 3 3 3 3 3 3 Me ens 7 5 6 6 6 6 6 6 6 6 6 Me ens 8 5 6 6 6 6 6 6 6 6 6 6 6 6 Me ens 10 3 5 4 4 4 4 5 4 4 4 5 4 4 Me ens 15 2 3 3 3 3 3 3 3 3 3 3 3 3 Me ens 18 2 2 2 2 2 2 2 2 2 2 2 2 2 Mi chell 14 8 10 10 10 11 10 Mi chell 15 8 10 10 10 10 10 10 10 10 Mi chell 21 5 7 6 7 7 6 7 7 7 7 7 6 7 Mi chell 26 5 6 6 6 5 5 6 6 5 5 6 6 6 Mi chell 35 3 4 4 4 4 4 4 4 4 4 4 4 4 Mi chell 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 p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació 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 Sawye 27 13 18 Sawye 30 12 16 18 Sawye 33 11 16 15 Sawye 36 10 14 14 Sawye 41 8 12 12 12 Sawye 47 7 11 11 11 10 11 Sawye 54 7 9 8 9 9 9 Sawye 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 Wa necke 82 20 Wa necke 92 17 Wa necke 97 17 Wa necke 104 15 Wa necke 111 14 Solucions de l’op imi zació local amb b=0,2. P ecedence g aph c m* H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 H12 A cus1 3786 21 A cus1 3985 20 A cus1 4206 19 A cus1 4454 18 A cus1 4732 17 A cus1 5048 16 A cus1 5408 15 A cus1 5824 14 17 19 A cus1 5853 14 17 A cus1 6309 13 16 16 15 A cus1 6842 12 15 15 14 A cus1 6883 12 15 15 14 A cus1 7571 11 13 14 12 A cus1 8412 10 12 12 12 A cus1 8898 9 11 12 11 A cus1 10816 8 9 9 9 A cus2 8847 18 A cus2 9400 17 A cus2 10027 16 A cus2 10743 15 A cus2 11378 14 A cus2 11570 13 A cus2 17067 9 Ba hold 434 13 Ba hold 470 12 Ba hold 513 11 Ba hold 564 10 Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 69 Ba hold 626 9 Ba hold 705 8 Ba hold 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 Gun he 44 12 Gun he 49 11 Gun he 54 9 Gun he 61 9 Gun he 69 8 11 Gun he 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 Heskiao 138 8 Heskiao 205 5 Heskiao 216 5 Heskiao 256 4 Heskiao 324 4 5 Heskiao 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 Kilb idge 56 10 Kilb idge 69 8 Kilb idge 79 7 Kilb idge 92 6 Kilb idge 110 6 Kilb idge 111 5 Kilb idge 138 4 Kilb idge 184 3 4 Lu z1 1414 11 Lu z1 1572 10 Lu z1 1768 9 11 10 Lu z1 2020 8 9 9 Lu z1 2357 7 8 8 8 8 9 8 Lu z1 2828 6 6 7 7 6 7 6 Lu z2 18 28 Lu z2 19 26 Lu z2 20 25 Lu z2 21 24 Lu z3 87 20 Lu z3 92 19 Lu z3 97 18 Lu z3 103 17 Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 70 Lu z3 110 15 Lu z3 118 14 Lu z3 127 14 Lu z3 137 13 Lu z3 150 12 Mansoo 48 4 5 5 5 Mansoo 62 3 4 4 4 4 4 4 4 4 4 Mansoo 94 2 3 3 3 3 3 3 3 3 3 3 3 3 Me ens 7 5 Me ens 8 5 Me ens 10 3 4 4 4 4 4 4 Me ens 15 2 3 3 3 3 3 3 3 3 3 3 3 3 Me ens 18 2 2 2 2 2 2 2 2 2 2 2 2 2 Mi chell 14 8 10 10 10 Mi chell 15 8 Mi chell 21 5 7 7 6 7 Mi chell 26 5 6 5 5 6 Mi chell 35 3 4 4 4 4 4 4 4 4 4 4 4 4 Mi chell 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 Sawye 27 13 Sawye 30 12 Sawye 33 11 Sawye 36 10 Sawye 41 8 Sawye 47 7 Sawye 54 7 Sawye 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 Wa necke 82 20 Wa necke 92 17 Wa necke 97 17 Wa necke 104 15 Wa necke 111 14 Solucions de l’op imi zació local amb b=0,1 i b=0. P ecedence g aph c m* H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 H12 A cus1 3786 21 28 A cus1 3985 20 28 A cus1 4206 19 24 26 A cus1 4454 18 27 24 26 23 Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 71 A cus1 4732 17 25 22 22 20 A cus1 5048 16 24 20 21 19 A cus1 5408 15 22 18 19 17 A cus1 5824 14 20 17 17 17 A cus1 5853 14 20 17 17 17 A cus1 6309 13 18 16 16 15 A cus1 6842 12 18 17 14 15 14 A cus1 6883 12 18 16 14 15 14 A cus1 7571 11 14 15 13 14 12 15 A cus1 8412 10 13 13 12 12 11 13 A cus1 8898 9 13 13 11 11 11 13 A cus1 10816 8 10 10 9 9 9 10 A cus2 8847 18 26 A cus2 9400 17 24 28 A cus2 10027 16 22 A cus2 10743 15 21 A cus2 11378 14 19 24 A cus2 11570 13 18 25 A cus2 17067 9 18 13 17 Ba hold 434 13 20 21 Ba hold 470 12 18 18 Ba hold 513 11 16 Ba hold 564 10 15 16 Ba hold 626 9 13 16 13 Ba hold 705 8 12 16 16 11 Ba hold 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 Gun he 44 12 17 17 Gun he 49 11 16 14 15 16 14 14 Gun he 54 9 14 14 14 14 14 13 13 13 14 14 13 Gun he 61 9 13 11 12 11 11 13 12 12 10 12 11 12 Gun he 69 8 12 10 11 10 10 12 10 10 10 11 10 11 Gun he 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 Heskiao 138 8 Heskiao 205 5 12 8 12 12 Heskiao 216 5 12 11 8 11 10 12 Heskiao 256 4 12 9 7 9 8 12 Heskiao 324 4 11 10 7 5 11 11 7 6 11 10 11 Heskiao 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 p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 72 Jaeschke 18 3 3 3 3 3 3 3 3 3 3 3 3 3 Kilb idge 56 10 15 15 Kilb idge 69 8 14 14 Kilb idge 79 7 12 12 12 Kilb idge 92 6 11 11 11 11 Kilb idge 110 6 9 9 8 9 9 9 Kilb idge 111 5 9 8 8 9 9 9 Kilb idge 138 4 11 7 9 6 11 9 8 7 7 11 Kilb idge 184 3 9 5 8 6 5 9 7 6 5 9 5 8 Lu z1 1414 11 13 14 14 14 14 13 Lu z1 1572 10 12 11 12 11 11 12 11 12 12 11 12 Lu z1 1768 9 12 10 11 11 11 12 11 11 10 11 10 11 Lu z1 2020 8 11 9 11 9 9 11 10 9 9 11 9 10 Lu z1 2357 7 8 8 8 8 8 8 8 8 9 9 8 8 Lu z1 2828 6 7 6 7 6 6 7 7 6 6 7 6 7 Lu z2 18 28 41 41 Lu z2 19 26 38 Lu z2 20 25 Lu z2 21 24 Lu z3 87 20 25 25 Lu z3 92 19 24 Lu z3 97 18 23 Lu z3 103 17 21 Lu z3 110 15 19 Lu z3 118 14 18 18 18 Lu z3 127 14 21 17 21 Lu z3 137 13 18 15 16 Lu z3 150 12 16 18 14 16 19 Mansoo 48 4 5 5 5 5 5 5 5 5 4 5 5 5 Mansoo 62 3 4 4 4 4 4 4 4 4 4 4 4 4 Mansoo 94 2 3 3 3 3 3 3 3 3 2 3 3 3 Me ens 7 5 6 6 6 6 6 6 6 6 6 Me ens 8 5 6 6 6 6 6 6 6 6 6 6 6 6 Me ens 10 3 5 4 4 4 4 5 4 4 4 5 4 4 Me ens 15 2 3 3 3 3 3 3 3 3 3 3 3 3 Me ens 18 2 2 2 2 2 2 2 2 2 2 2 2 2 Mi chell 14 8 10 10 10 11 10 Mi chell 15 8 10 10 10 10 10 10 10 10 Mi chell 21 5 7 6 7 7 6 7 7 7 7 7 6 7 Mi chell 26 5 6 6 6 5 5 6 6 5 5 6 6 6 Mi chell 35 3 4 4 4 4 4 4 4 4 4 4 4 4 Mi chell 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 Sawye 27 13 17 Sawye 30 12 16 17 Sawye 33 11 15 15 13 Sawye 36 10 14 15 11 Sawye 41 8 12 12 11 Sawye 47 7 11 11 10 9 11 Sawye 54 7 9 9 8 8 8 9 Sawye 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 p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació 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 Wa necke 82 20 27 Wa necke 92 17 23 23 Wa necke 97 17 22 Wa necke 104 15 21 20 Wa necke 111 14 18 18 Solucions de l’op imi zació local amb b=0,2 i b=0. P ecedence g aph c m* H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 H12 A cus1 3786 21 A cus1 3985 20 A cus1 4206 19 A cus1 4454 18 A cus1 4732 17 A cus1 5048 16 A cus1 5408 15 A cus1 5824 14 17 19 A cus1 5853 14 17 A cus1 6309 13 16 16 15 A cus1 6842 12 15 15 14 A cus1 6883 12 15 15 14 A cus1 7571 11 13 14 12 A cus1 8412 10 12 12 11 A cus1 8898 9 11 11 11 A cus1 10816 8 9 9 9 A cus2 8847 18 A cus2 9400 17 A cus2 10027 16 A cus2 10743 15 A cus2 11378 14 A cus2 11570 13 A cus2 17067 9 Ba hold 434 13 Ba hold 470 12 Ba hold 513 11 Ba hold 564 10 Ba hold 626 9 Ba hold 705 8 Ba hold 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 Gun he 44 12 Gun he 49 11 Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 74 Gun he 54 9 Gun he 61 9 Gun he 69 8 9 11 9 9 Gun he 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 Heskiao 138 8 Heskiao 205 5 Heskiao 216 5 Heskiao 256 4 Heskiao 324 4 5 Heskiao 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 Kilb idge 56 10 Kilb idge 69 8 Kilb idge 79 7 Kilb idge 92 6 Kilb idge 110 6 Kilb idge 111 5 Kilb idge 138 4 6 Kilb idge 184 3 4 Lu z1 1414 11 14 15 15 Lu z1 1572 10 12 12 11 Lu z1 1768 9 10 11 11 11 10 Lu z1 2020 8 10 9 9 9 10 Lu z1 2357 7 8 8 8 8 8 Lu z1 2828 6 7 6 6 6 7 8 7 8 Lu z2 18 28 Lu z2 19 26 Lu z2 20 25 Lu z2 21 24 Lu z3 87 20 Lu z3 92 19 Lu z3 97 18 Lu z3 103 17 Lu z3 110 15 Lu z3 118 14 Lu z3 127 14 Lu z3 137 13 Lu z3 150 12 Mansoo 48 4 5 5 5 5 5 5 5 5 4 5 5 5 Mansoo 62 3 4 4 4 4 4 4 4 5 4 4 4 4 Mansoo 94 2 3 3 3 3 3 3 3 3 2 3 3 3 Me ens 7 5 Me ens 8 5 Me ens 10 3 4 4 5 4 4 4 Me ens 15 2 3 3 3 3 3 3 3 3 3 3 3 3 Me ens 18 2 2 2 2 2 2 2 2 2 2 2 2 2 Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 81 main('Gun he ', 81) main('Hahn', 2004) main('Hahn', 2338) main('Hahn', 2806) main('Hahn', 3507) main('Hahn', 4676) main('Heskiao ', 138) main('Heskiao ', 205) main('Heskiao ', 216) main('Heskiao ', 256) main('Heskiao ', 324) main('Heskiao ', 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('Kilb idge', 56) main('Kilb idge', 57) main('Kilb idge', 62) main('Kilb idge', 69) main('Kilb idge', 79) main('Kilb idge', 92) main('Kilb idge', 110) main('Kilb idge', 111) main('Kilb idge', 138) main('Kilb idge', 184) main('Lu z1', 1414) main('Lu z1', 1572) main('Lu z1', 1768) main('Lu z1', 2020) main('Lu z1', 2357) main('Lu z1', 2828) main('Lu z2', 11) main('Lu z2', 12) main('Lu z2', 13) main('Lu z2', 14) main('Lu z2', 15) main('Lu z2', 16) main('Lu z2', 17) main('Lu z2', 18) main('Lu z2', 19) main('Lu z2', 20) main('Lu z2', 21) main('Lu z3', 75) main('Lu z3', 79) main('Lu z3', 83) main('Lu z3', 87) main('Lu z3', 92) main('Lu z3', 97) main('Lu z3', 103) main('Lu z3', 110) main('Lu z3', 118) main('Lu z3', 127) main('Lu z3', 137) main('Lu z3', 150) main('Mansoo ', 48) main('Mansoo ', 62) main('Mansoo ', 94) main('Me ens', 6) main('Me ens', 7) main('Me ens', 8) main('Me ens', 10) main('Me ens', 15) main('Me ens', 18) main('Mi chell', 14) main('Mi chell', 15) main('Mi chell', 21) main('Mi chell', 26) main('Mi chell', 35) main('Mi chell', 39) main('Mukhe je', 176) main('Mukhe je', 183) main('Mukhe je', 192) main('Mukhe je', 201) main('Mukhe je', 211) main('Mukhe je', 222) main('Mukhe je', 234) main('Mukhe je', 248) main('Mukhe je', 263) main('Mukhe je', 281) Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 82 main('Mukhe je', 301) main('Mukhe je', 324) main('Mukhe je', 351) main('Roszieg', 14) main('Roszieg', 16) main('Roszieg', 18) main('Roszieg', 21) main('Roszieg', 25) main('Roszieg', 32) main('Sawye ', 25) main('Sawye ', 27) main('Sawye ', 30) main('Sawye ', 33) main('Sawye ', 36) main('Sawye ', 41) main('Sawye ', 47) main('Sawye ', 54) main('Sawye ', 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('Wa necke', 54) main('Wa necke', 56) main('Wa necke', 58) main('Wa necke', 60) main('Wa necke', 62) main('Wa necke', 65) main('Wa necke', 68) main('Wa necke', 71) main('Wa necke', 74) main('Wa necke', 78) main('Wa necke', 82) main('Wa necke', 86) main('Wa necke', 92) main('Wa necke', 97) main('Wa necke', 104) main('Wa necke', 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 p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació 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 de llis a_p io i a s_ asques(g): p io i a s=[] successo s=[] o i in g.nodes(): emps=g.node[i][' ime'] dic=nx.d s_successo s(g,i) o key in dic: i len(dic[key])==1: elemen =dic[key][0] emps = emps + g.node[elemen ][' ime'] else: o elemen in dic[key]: emps = emps + g.node[elemen ][' ime'] successo s.append((i, emps)) successo s=so ed(successo s, key=lambda up: up[1], e e se=T ue) o i in successo s: p io i a s.append(i[0]) e u n p io i a s HEURÍSTICA 2 de llis a_du acions_ asques(g): du acions=[] aux=[] o i in g.nodes(): aux.append((i,g.node[i][' ime'])) aux=so ed(aux, key=lambda up: up[1], e e se=T ue) o i in aux: du acions.append(i[0]) e u n du acions HEURÍSTICA 3 de llis a_du acions_ asques(g): du acions=[] aux=[] o i in g.nodes(): suc=0 dic=nx.d s_successo s(g,i) o key in dic: suc=suc+len(dic[key]) aux.append((i,suc)) aux=so ed(aux, key=lambda up: up[1], e e se=T ue) o i in aux: du acions.append(i[0]) e u n du acions HEURÍSTICA 4 de llis a_p io i a s_ asques(g): p io i a s=[] successo s = [] o i in g.nodes(): successo s.append((i,len(g.successo s(i)))) successo s=so ed(successo s, key=lambda up: up[1], e e se=T ue) o i in successo s: p io i a s.append(i[0]) Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 84 e u n p io i a s HEURÍSTICA 5 de llis a_p io i a s_ asques(h, emps_cicle): p io i a s=[] successo s=[] o i in h.nodes(): emps=h.node[i][' ime'] dic=nx.d s_successo s(h,i) o key in dic: i len(dic[key])==1: elemen =dic[key][0] emps = emps + h.node[elemen ][' ime'] else: o elemen in dic[key]: emps = emps + h.node[elemen ][' ime'] o mula= loa ( emps)/ loa ( emps_cicle) successo s.append((i, o mula)) successo s=so ed(successo s, key=lambda up: up[1]) o i in successo s: p io i a s.append(i[0]) e u n p io i a s HEURÍSTICA 6 de llis a_p io i a s_ asques(g, emps_cicle): p io i a s=[] successo s=[] n=len(g.nodes())-1 o i in g.nodes(): emps=g.node[i][' ime'] dic=nx.d s_successo s(g,i) o key in dic: i len(dic[key])==1: elemen =dic[key][0] emps = emps + g.node[elemen ][' ime'] else: o elemen in dic[key]: emps = emps + g.node[elemen ][' ime'] o mula=n+1-( loa ( emps)/ loa ( emps_cicle)) successo s.append((i, o mula)) successo s=so ed(successo s, key=lambda up: up[1]) o i in successo s: p io i a s.append(i[0]) e u n p io i a s HEURÍSTICA 7 de llis a_p io i a s_ asques(g,h, emps_cicle): p io i a s=[] successo s=[] aux=[] n=len(g.nodes()) o i in g.nodes(): emps=g.node[i][' ime'] dic=nx.d s_successo s(g,i) o key in dic: i len(dic[key])==1: elemen =dic[key][0] emps = emps + g.node[elemen ][' ime'] else: o elemen in dic[key]: emps = emps + g.node[elemen ][' ime'] o mula=n+1-( loa ( emps)/ loa ( emps_cicle)) successo s.append([i, o mula]) o i in h.nodes(): emps=h.node[i][' ime'] dic=nx.d s_successo s(h,i) o key in dic: i len(dic[key])==1: elemen =dic[key][0] emps = emps + h.node[elemen ][' ime'] else: o elemen in dic[key]: emps = emps + h.node[elemen ][' ime'] o mula= loa ( emps)/ loa ( emps_cicle) Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 85 o j in successo s: i j[0]==i: j.append( o mula) b eak else: pass o llis a in successo s: aux.append((llis a[0],llis a[1]-llis a[2])) aux=so ed(aux, key=lambda up: up[1]) o i in aux: p io i a s.append(i[0]) e u n p io i a s HEURÍSTICA 9 de llis a_p io i a s_ asques(g): p io i a s=[] successo s=[] o i in g.nodes(): suc=0 emps=g.node[i][' ime'] dic=nx.d s_successo s(g,i) o key in dic: suc=suc+len(dic[key]) i len(dic[key])==1: elemen =dic[key][0] emps = emps + g.node[elemen ][' ime'] else: o elemen in dic[key]: emps = emps + g.node[elemen ][' ime'] o mula= loa ( emps)/( loa (suc+1)) successo s.append((i, o mula)) successo s=so ed(successo s, key=lambda up: up[1], e e se=T ue) o i in successo s: p io i a s.append(i[0]) e u n p io i a s HEURÍSTICA 10 de llis a_p io i a s_ asques(g, emps_cicle): p io i a s=[] successo s=[] n=len(g.nodes())-1 o i in g.nodes(): suc=0 emps=g.node[i][' ime'] dic=nx.d s_successo s(g,i) o key in dic: suc=suc+len(dic[key]) i len(dic[key])==1: elemen =dic[key][0] emps = emps + g.node[elemen ][' ime'] else: o elemen in dic[key]: emps = emps + g.node[elemen ][' ime'] o mula=(n+1-( loa ( emps)/ loa ( emps_cicle)))/ loa (suc+1) successo s.append((i, o mula)) successo s=so ed(successo s, key=lambda up: up[1]) o i in successo s: p io i a s.append(i[0]) e u n p io i a s HEURÍSTICA 11 de llis a_p io i a s_ asques(g, emps_cicle): p io i a s=[] successo s=[] n=len(g.nodes())-1 o i in g.nodes(): emps=g.node[i][' ime'] dic=nx.d s_successo s(g,i) o key in dic: i len(dic[key])==1: elemen =dic[key][0] emps = emps + g.node[elemen ][' ime'] else: Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 86 o elemen in dic[key]: emps = emps + g.node[elemen ][' ime'] o mula= loa (g.node[i][' ime'])/(n+1- ( loa ( emps)/ loa ( emps_cicle))) successo s.append((i, o mula)) successo s=so ed(successo s, key=lambda up: up[1], e e se=T ue) o i in successo s: p io i a s.append(i[0]) e u n p io i a s HEURÍSTICA 12 de llis a_p io i a s_ asques(g,h, emps_cicle): p io i a s=[] successo s=[] aux=[] n=len(g.nodes()) o i in g.nodes(): suc=0 emps=g.node[i][' ime'] dic=nx.d s_successo s(g,i) o key in dic: suc=suc+len(dic[key]) i len(dic[key])==1: elemen =dic[key][0] emps = emps + g.node[elemen ][' ime'] else: o elemen in dic[key]: emps = emps + g.node[elemen ][' ime'] o mula=n+1-( loa ( emps)/ loa ( emps_cicle)) successo s.append([i, o mula,suc]) o i in h.nodes(): emps=h.node[i][' ime'] dic=nx.d s_successo s(h,i) o key in dic: i len(dic[key])==1: elemen =dic[key][0] emps = emps + h.node[elemen ][' ime'] else: o elemen in dic[key]: emps = emps + h.node[elemen ][' ime'] o mula= loa ( emps)/ loa ( emps_cicle) o j in successo s: i j[0]==i: j.append( o mula) b eak else: pass o llis a in successo s: aux.append((llis a[0],llis a[2]/(llis a[1]-llis a[3]))) aux=so ed(aux, key=lambda up: up[1], e e se=T ue) o i in aux: p io i a s.append(i[0]) e u n p io i a s OPTIMITZACIÓ LOCAL impo ne wo kx as nx impo ime impo codi1 de in e can i(o d e, asca, asca_in e ): copia=o d e[:] index=copia.index( asca) index_in e =copia.index( asca_in e ) copia[index], copia[index_in e ] = copia[index_in e ], copia[index] e u n copia Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 87 de algo isme(o d e,g): llis a = [] index_node=-1 o node in o d e: index_node=index_node+1 index_elem=index_node+1 descendan s=lis (nx.descendan s(g,node)) o elem in o d e[index_elem:]: ances es = lis (nx.ances o s(g,elem)) llesca = o d e[index_node:index_elem] index_elem=index_elem+1 c=0 o i in llesca: i i in ances es: b eak eli i in descendan s: b eak else: c=c+1 i c==len(llesca): l=in e can i(o d e,node,elem) llis a.append(l) else: pass e u n llis a de des e _llis a(es acions): o d e=[] o subllis a in es acions: o i in subllis a: o d e.append(i) e u n o d e de a ailable_ ime(g, asca): a al=0 i asca == 0: e u n 0 else: o p e in g.p edecesso s( asca): i a al <= g.node[p e][' emps_acaba']: a al = g.node[p e][' emps_acaba'] else: pass e u n a al de mon a _es acions(sub_llis a, g, emps_cicle): no a_o gani zacio=[] aux=[] s a _ ime=0 emps= emps_cicle c=1 o asca in sub_llis a: a al=a ailable_ ime(g, asca) i 0 in g.p edecesso s( asca): b=0 else: b=0.1 i s a _ ime>=a al: p=g.node[ asca][' ime']+b*(s a _ ime-a al) i p> emps_cicle: e u n 'Impossible' eli p<= emps and emps>0: aux.append( asca) emps= emps-p s a _ ime=s a _ ime+p g.node[ asca][' emps_acaba']=s a _ ime i asca==sub_llis a[len(sub_llis a)-1]: no a_o gani zacio.append(aux) else: s a _ ime = emps_cicle*c c=c+1 no a_o gani zacio.append(aux) emps= emps_cicle aux=[] p=g.node[ asca][' ime']+b*(s a _ ime-a al) i p< emps_cicle: g.node[ asca][' emps_acaba']=s a _ ime+p Resolució del p oblema d’equilib a de línia de mun a ge amb asques amb de e io ació Pág. 88 aux.append( asca) s a _ ime = s a _ ime+p emps= emps-p i asca==sub_llis a[len(sub_llis a)-1]: no a_o gani zacio.append(aux) else: e u n 'Impossible' else: s a _ ime = emps_cicle*c c=c+1 no a_o gani zacio.append(aux) emps= emps_cicle aux=[] p=g.node[ asca][' ime']+b*(s a _ ime-a al) i p< emps_cicle: g.node[ asca][' emps_acaba']=s a _ ime+p aux.append( asca) s a _ ime= s a _ ime+p emps= emps-p i asca==sub_llis a[len(sub_llis a)-1]: no a_o gani zacio.append(aux) else: e u n 'Impossible' e u n no a_o gani zacio de can ia _a ibu s(g): o nodes in g.nodes(): g.node[nodes][' emps_acaba']=0 e u n g de main(nom_ i xe , emps_cicle): i xe =open('op imi zacio_codi1', 'a') s a = ime.clock() es acions, g = codi1.main(nom_ i xe , emps_cicle) o d e = des e _llis a(es acions) llis a = algo isme(o d e,g) o sub_llis a in llis a: g = can ia _a ibu s(g) no a_o gani zacio=mon a _es acions(sub_llis a, g, emps_cicle) i no a_o gani zacio == 'Impossible': pass eli len(no a_o gani zacio)<len(es acions) and es acions!=[]: i xe .w i e(nom_ i xe +'*'+s ( emps_cicle)+'*'+s (len(n o a_o gani zacio))+'*'+s ( ime.clock()- s a )+'*'+s (no a_o gani zacio)+' n') else: pass i xe .close() i __name__=='__main__': main('A cus1', 3786) main('A cus1', 3985) main('A cus1', 4206) …