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)
…