Minimización de los tiempos ociosos de las máquinas en el taller de flujo de permutación

P oyec o Fin de Ca e a
Ingenie ía de Telecomunicación
Fo ma o de Publicación de la Escuela Técnica
Supe io de Ingenie ía
Au o : F. Ja ie Payán Some
Tu o : Juan José Mu illo Fuen es
Dep. Teo ía de la Señal y Comunicaciones
Escuela Técnica Supe io de Ingenie ía
Uni e sidad de Se illa
Se illa, 2013
T abajo de Fin de G ado
G ado en Ingenie ía de las Tecnologías Indus iales
Minimización de los iempos ociosos de las
máquinas en el alle de lujo de pe mu ación
Au o : Juan Raúl Cas año Hue as
Tu o : Paz Pé ez González
Dp o. de O ganización Indus ial y Ges ión de
Emp esas
Escuela Técnica Supe io de Ingenie ía
Uni e sidad de Se illa
Se illa, 2020
T abajo de Fin de G ado
G ado en Ingenie ía de las Tecnologías Indus iales
Minimización de los iempos ociosos de las
máquinas en el alle de lujo de pe mu ación
Au o :
Juan Raúl Cas año Hue as
Tu o :
Paz Pé ez González
P o eso Ti ula
Dp o. de O ganización Indus ial y Ges ión de Emp esas
Escuela Técnica Supe io de Ingenie ía
Uni e sidad de Se illa
Se illa, 2020
T abajo de Fin de G ado:
Minimización de los iempos ociosos de las máquinas en el alle
de lujo de pe mu ación
Au o : Juan Raúl Cas año Hue as
Tu o : Paz Pé ez González
El ibunal nomb ado pa a juzga el abajo a iba indicado, compues o po los siguien es p o eso es:
P esiden e:
Vocal/es:
Sec e a io:
acue dan o o ga le la cali icación de:
El Sec e a io del T ibunal
Fecha:

Ag adecimien os
A mi abuelo, po es a conmigo du an e odo el camino.
Juan Raúl Cas año Hue as
Se illa, 2020
I
Resumen
En
es e T abajo de Fin de G ado se abo da el p oblema de la p og amación de ope aciones
en un en o no de alle de lujo egula con pe mu ación (pe mu a ion lowshop scheduling)
p oponiendo un mé odo de esolución en el caso de la minimización de iempo ocioso de las
máquinas. Pa a ello, se ha á una e isión de los concep os undamen ales que in oluc a el p oblema,
así como de algunos de los mé odos u ilizados pa a esol e lo pa a o os obje i os. Finalmen e, se
adap an algunos de los mé odos ya exis en es y se desa ollan nue as p opues as, analizando an o
la calidad de las soluciones ob enidas como los iempos de ejecución de los algo i mos u ilizados.
III
XÍndice de Figu as
5.11 Tiempos de ejecución acumulados de cada mé odo implemen ado con la PRC34
5.12 ARPD del mé odo NEHLJP implemen ado con la PRCen unción de la
dimensión de los p oblemas 36
5.13 ARPD del mé odo NEHLJP implemen ado con la PRCen unción de los
pesos de los p oblemas 37
5.14 Tiempos de ejecución del mé odo NEHLJP implemen ado con la PRC37
5.15 Tiempos de ejecución acumulados del mé odo NEHLJP implemen ado
con la PRC38
5.16 ARPD del mé odo NEHLJP o iginal s el NEHLJP implemen ado con la PRC38
5.17 ARPD de cada p io i y ule implemen ada con la TBCen unción de la
dimensión de los p oblemas 40
5.18 ARPD de cada p io i y ule implemen ada con la TBCen unción de los
pesos de los p oblemas 41
5.19 Tiempos de ejecución de cada p io i y ule implemen ada con la TBC41
5.20 Tiempos de ejecución acumulados de cada p io i y ule implemen ada
con la TBC42

Índice de Tablas
2.1 No ación u ilizada en el documen o 12
4.1 G upos de p oblemas según su amaño 23
5.1 ARPD de cada p io i y ule en unción de la dimensión de los p oblemas 26
5.2 ARPD de cada p io i y ule en unción de los pesos de los p oblemas 26
5.3 Tiempos de ejecución de cada p io i y ule 26
5.4 ARPD de cada mé odo en unción de la dimensión de los p oblemas 28
5.5 ARPD de cada mé odo en unción de los pesos de los p oblemas 29
5.6 Tiempos de ejecución de cada mé odo 29
5.7 ARPD de cada ie b eaking ule implemen ada con la PRCen unción de
la dimensión de los p oblemas 32
5.8 ARPD de cada ie b eaking ule implemen ada con la PRCen unción de
los pesos de los p oblemas 32
5.9 Tiempos de ejecución de cada ie b eaking ule implemen ada con la PRC33
5.10 ARPD del mé odo NEHLJP implemen ado con la PRCen unción de la
dimensión de los p oblemas 35
5.11 ARPD del mé odo NEHLJP implemen ado con la PRCen unción de los
pesos de los p oblemas 35
5.12 Tiempos de ejecución del mé odo NEHLJP implemen ado con la PRC36
5.13 Di e encia en e la calidad de los esul ados del NEHLJP o iginal y el
NEHLJP implemen ado con la PRC38
5.14 ARPD de cada p io i y ule implemen ada con la TBCen unción de la
dimensión de los p oblemas 39
5.15 ARPD de cada p io i y ule implemen ada con la TBCen unción de los
pesos de los p oblemas 39
5.16 Tiempos de ejecución de cada p io i y ule implemen ada con la TBC40
1 ARPD de cada p io i y ule en unción de las ca ac e ís icas de los p oblemas 73
2 ARPD de cada mé odo en unción de las ca ac e ís icas de los p oblemas 77
3 ARPD de cada ie b eaking ule implemen ada con la PRCen unción de
las ca ac e ís icas de los p oblemas 80
4 ARPD del mé odo NEHLJP implemen ado con la PRCen unción de las
ca ac e ís icas de los p oblemas 83
5 ARPD de cada p io i y ule implemen ada con la TBCen unción de las
ca ac e ís icas de los p oblemas 86
XI
1 In oducción y obje i os
En
es e capí ulo se p e ende in oduci al lec o a la emá ica de la p og amación de ope aciones,
así como pone le en con ex o en cuan o al obje i o del p oblema que se p e ende esol e y
su jus i icación. También se explican an o la es uc u a que sigue el p opio documen o como el
con enido en cada una de sus pa es.
Asimismo, a medida que se a ance en la lec u a, se i á in oduciendo e minología en inglés, siendo
es a iden i icada po apa ece en cu si a, y que se á explicada a medida que aya apa eciendo. Po
úl imo, se ha á uso de siglas, pe enecien es a sus espec i as exp esiones en inglés, habiendo sido
odas y cada una de ellas de inidas con an e io idad.
La p og amación de ope aciones (ope a ion scheduling) ocupa un papel muy impo an e en la
indus ia, ya que puede supone impo an es mejo as en el desempeño de una emp esa, sea cual
sea su campo de p oducción (sec o au omo ilís ico, p oduc os ecnológicos, e c.). Aumen os en el
endimien o, ales como el aumen o de la p oduc i idad a a és de la disminución de los iempos de
p oceso o ales, la disminución de los iempos ociosos de las máquinas en e abajos o de los e asos
en los abajos son algunas de las en ajas que se pueden log a con una e icien e p og amación de
las ope aciones de una emp esa.
Po o a pa e, el en o no de alle de lujo uni o me ( lowshop), es uno de los ipos de p oble-
ma más ex endidos en la ac ualidad, debido a que es el que más se asemeja a la con igu ación eal
de la mayo pa e de los sis emas p oduc i os de la indus ia.
1.1 Obje i os del p oyec o
En es e abajo se iene como p incipal obje i o analiza la e iciencia de dis in os algo i mos, cuyo
p opósi o es minimiza la suma ponde ada en e el máximo iempo de e minación de una se ie
de abajos en lujo uni o me con pe mu ación (pe mu a ion lowshop scheduling) y la suma de
los iempos ociosos de las máquinas en e abajos (co e idle ime). Pa a ello, se p opone un nue o
algo i mo, que se á compa ado con algunos de los mejo es algo i mos p esen es en la ac ualidad: el
p opues o po Víc o Fe nández – Viagas y José Manuel F amiñán (Fe nández – Viagas, F amiñán,
2014), Weibo Liu, Yan Jin y Ma k P ice (Weibo Liu, Yan Jin, Ma k P ice, 2016) y el algo i mo en
que ambos mé odos es án basados, p opues o po Muhammad Nawaz, E. Emo y Ensco e e Inyong
Ham (Nawaz, Ensco e, Ham, 1983).
1
2Capí ulo 1. In oducción y obje i os
Figu a 1.1 Diag ama de lujo de in o mación en un sis ema de ab icación.
Pa a comp oba la e iciencia de los mé odos an e io men e mencionados se compa a án la ca-
lidad de las soluciones ob enidas median e la des iación po cen ual ela i a p omedio (A e age
ela i e pe cen age de ia ion) o ARPD, así como los iempos de ejecución de cada uno de ellos.
1.2 Jus i icación
Median e la co ec a p og amación de ope aciones se puede log a una disminución signi ica i a en
el iempo o al de p oceso, lo que se aduce en un aho o de cos es pa a la emp esa. Además, a en-
diendo al c i e io de la disminución de los iempos ociosos de las máquinas, se consigue aumen a
la e iciencia de cada una de las máquinas po sepa ado.
El es udio de es e ipo de p oblemas a iende a la necesidad de disminui el iempo y los ecu sos
necesa ios pa a esol e los de o ma óp ima, ya que muchos de los p oblemas de ipo lowshop
pe enecen a la clasi icación de no polinomiales o NP-ha d, que como se á explicado pos e io men e,
necesi an de una bas a can idad de iempo y ecu sos pa a encon a una solución óp ima al p oblema
a a a . Es po eso po lo que se hace uso de algo i mos que pe mi an encon a una solución lo
su icien emen e p óxima a la solución óp ima del p oblema en una can idad de iempo azonable.
1.3 Es uc u a del documen o 3
1.3 Es uc u a del documen o
El p esen e documen o es á es uc u ado en 6 capí ulos, a lo la go de los cuales se desa olla án los
siguien es pun os:
En el p ime capí ulo se hace una b e e in oducción del p oblema a a a en es e abajo y los obje-
i os que se p e enden, pasando po la jus i icación del mismo. Po úl imo, se explica la es uc u a
que sigue el documen o.
En el capí ulo segundo se desc ibe el p oblema, a ando aspec os ales como la no ación, el
en o no, las es icciones a los que es á suje o y el obje i o a op imiza . P e iamen e a la p esen-
ación de dichas pa icula idades se ha á una in oducción a la p og amación de la p oducción,
con el in de ayuda al lec o a en ende de una mejo mane a el con ex o en el que se si úa el p oblema.
En el e ce capí ulo se ealiza una desc ipción de los algo i mos que han sido pues os en p ác ica
pa a la compa ación de las dis in as soluciones al p oblema, explicando los pasos que sigue cada
uno de ellos.
En el cua o capí ulo se in oduce Ma lab, el so wa e u ilizado pa a implemen a los 4 algo-
i mos u ilizados pa a los expe imen os, calcula y compa a las soluciones ob enidas. También
se desc iben las ins ancias u ilizadas pa a compa a dichos algo i mos, así como los indicado es
usados pa a e alua las soluciones.
En el capí ulo quin o se mues an y analizan los esul ados ob enidos.
Po úl imo, en el sex o capí ulo se exponen las conclusiones ex aídas de los esul ados mos ados
en el capí ulo 5.

2 Desc ipción del p oblema
En
es e capí ulo se desc ibi á el p oblema obje i o de es e abajo. Tal y como se ha mencionado
en el capí ulo 1, se ealiza á una in oducción p e ia a la p og amación de la p oducción, pa a
pos e io men e abo da las dis in as pa icula idades del p oblema.
2.1 P og amación de la p oducción
La p og amación de la p oducción (manu ac u ing scheduling) es la ama de la o ganización de la
p oducción (p oduc ion managemen ) que se enca ga de asigna una se ie de abajos o ecu sos en
el iempo con el in de hace dicho p oceso de p oducción más e icien e, ya sea disminuyendo los
iempos o ales de p oceso, la u ilización de ecu sos o los cos es pa a la emp esa.
Dicha asignación da luga a un p og ama (p oduc ion schedule), que iden i ica cada abajo (job)
e indica cuándo debe se p ocesado en cada máquina (machine). Una de las he amien as más
u ilizadas pa a ep esen a dichos p og amas de o ma g á ica es el diag ama de Gan , desa ollado
po Hen y Lau ence Gan en e 1910 y 1915, donde se ep esen an las máquinas o las ope aciones
que componen un abajo ( e ical) en e al iempo (ho izon al). A pa i de es e diag ama pueden
iden i ica se an o las echas de comienzo y in de cada abajo como su du ación.
Figu a 2.1 Diag ama de Gan [4].
5
6Capí ulo 2. Desc ipción del p oblema
Figu a 2.2 Diag ama de Gan de dos secuencias di e en es [5].
La p og amación de la p oducción es ca alogada como un p oceso de oma de decisiones, y
es ampliamen e u ilizado en el ámbi o indus ial, an o en p oducción y ensamblaje como en la
plani icación de p oyec os. Su come ido es el de encon a al menos un p og ama admisible ( easible
schedule) que log e op imiza cie o obje i o, a endiendo al mismo iempo a las es icciones que
en uel en al p oblema en cues ión.
En el caso de que se hubie an encon ado más de un p og ama admisible, se debe á elegi aquel
cuya solución mejo sa is aga el obje i o del p oblema.
2.2 Algo i mos
El mé odo u ilizado pa a ob ene un p og ama admisible ecibe el nomb e de algo i mo. Un algo i -
mo es una sucesión ini a de ope aciones o denadas que iene como obje i o la ob ención de una
solución a un p oblema. Dicha solución puede se exac a o ap oximada.
Se en iende como solución exac a aquella que p opo ciona un esul ado óp imo a un p oblema,
mien as que una solución ap oximada o ece á un esul ado que, aun a pesa de no se el óp imo,
se le ace ca de una o ma (más o menos) azonable. Los algo i mos de ap oximación esul an
especialmen e in e esan es en aquellos casos en los que calcula la solución óp ima de un p oblema
equie e una g an can idad de ecu sos. Es el caso del p oblema de lowshop a ado en el p esen e
abajo, del que se habla á en la sección 2.3 de es e capí ulo.
2.3 Concep os básicos
A con inuación, se de inen algunos de los elemen os básicos que componen un p oblema de p og a-
mación de la p oducción, jun o con la no ación que se a a usa pa a designa las en es e abajo:
•
Máquina (machine): “Recu so p oduc i o con capacidad pa a ealiza ope aciones de ans o -
mación/ anspo e de ma e ial” [
4
]. Hay un o al de mmáquinas, designadas po el subíndice
i.
•
T abajo (job): “P oduc o que es obje o de una ope ación en alguna de las máquinas de la
áb ica” [4]. Hay un o al de n abajos, designados po el subíndice j.
•
Ru a ( ou e): La u a indica el o den que debe segui un abajo a la ho a de p ocesa se. Es un
ec o de mcomponen es, que con iene los núme os asociados a cada una de las mmáquinas.
Exis en un o al de n u as, una po cada abajo, designadas median e la no ación Rj.
De es e modo, omando como ejemplo la u a
R2
=(3,1,2), el abajo 2 debe á p ocesa se
p ime o en la máquina 3, después en la 1 y po úl imo en la 2.
•
Secuencia (sequence): Es un ec o o mado po ncomponen es. Con iene los núme os
asociados a cada uno de los n abajos que, po o den, deben p ocesa se en cada máquina.
2.3 Concep os básicos 7
Puede habe un o al de mmáquinas o únicamen e una, en caso de que odos los abajos sean
p ocesados en el mismo o den. La secuencia se designa median e la no ación Si.
•
Tiempo de p oceso (p ocessing ime): El iempo de p oceso
pi j
indica el iempo que el abajo
j a da en p ocesa se en la máquina i.
Figu a 2.3
Ejemplo de di e en es iempos de p oceso pa a cada abajo en las dis in as máquinas
[4].
•
Fecha de llegada ( elease da e): Ins an e de iempo en el cual el abajo jpasa a es a disponible
pa a p ocesa se, ep esen ado po j.
•
Fecha de en ega (due da e): La echa de en ega
dj
es el ins an e de iempo en el que, como
máximo, un abajo debe acaba de p ocesa se.
•
Peso (weigh ): Si e como mé odo de ponde ación pa a indica la impo ancia de un abajo.
Se designa median e la no ación wj.
•
Tiempo de e minación (comple ion ime): Ins an e de iempo en el que el abajo j e mina
de p ocesa se en la úl ima máquina. Rep esen ado po Cj.
•
Tiempo de lujo ( low ime): Tiempo o al que el abajo pe manece en el en o no, desde
que es á disponible has a que e mina de p ocesa se en la úl ima máquina. Se de ine como
Fj=Cj− j.
•Re aso (la eness): Re aso del abajo j, de inido como Lj=Cj−dj.
14 Capí ulo 3. Desc ipción de los algo i mos
Figu a 3.1 Pseudocódigo del algo i mo NEH [4].
Figu a 3.2
Ejemplo del mé odo de inse ción, en el que un abajo es in e cambiado de la posición j
a la posición kde una secuencia [4].
3.2 NEHFF
El algo i mo NEH
FF
es una a ian e del NEH desa ollada en 2014 po Víc o Fe nández – Viagas
y José M. F amiñán (Fe nández – Viagas, F amiñán, 2014) que, median e la implemen ación de
la egla de desempa e TB
FF
, se ha consolidado como uno de los mejo es algo i mos usados pa a
esol e p oblemas del ipo Fm|p mu|Cmax has a la echa.
Las eglas de desempa e, o ie-b eaking ules, son he amien as de decisión que si en pa a esol e
los desempa es que pueden da se a la ho a de elegi una secuencia pa cial óp ima du an e la ase de
inse ción. La TB
FF
es á basada en la disminución de los idle- ime, esol iendo los desempa es a
a o de la secuencia pa cial cuya suma en e el on delay y el co e idle- ime sea la de meno alo .
El cálculo de es a suma se ealiza de la siguien e mane a:
•
P ime o se calculan los co e idle- ime de cada máquina:
CIT i=∑n
j=2max(Ci j −pi j −Ci,j−1,0)
•
En segundo luga se calculan los on delay de cada máquina, a los que se les asigna á la
no ación de FIT ( on idle- ime): FIT i=∑i−1
k=1pi−k,1, siendo FIT1=0.
•
A con inuación, se suman los CIT y los FIT pa a ob ene los idle- ime de cada máquina:
IT i=∑m
i=1FIT i+CIT i
•
Po úl imo, se suman odos los
ITi
(
∑m
i=1IT i
), dando como esul ado el idle- ime o al de la
secuencia.
Una ez in oducida la egla de desempa e, se pasa a enume a los pasos que ha de segui el algo i mo:
En p ime luga , se ejecu a la p io i y ule del algo i mo NEH:
•P ime o: Se calculan los Pjde odos los abajos.
•Segundo: Se o denan los abajos de mayo a meno según sus Pj.

3.3 NEHLJP 15
Una ez se iene la secuencia inicial, es ho a de pasa a la inse ción. Pa a ello, se pa i á de la
secuencia pa cial o mada po los 2 p ime os abajos, en la que se i án inse ando el es o de
abajos siguiendo la ie-b eaking ule TBFF :
•
Te ce o: Se seleccionan los dos p ime os abajos y se de e mina la secuencia pa cial óp ima.
•
Cua o: Pa a el es o de los abajos (de
j=3
a
j=n
), se inse a el j-ésimo abajo en odas
las posiciones posibles y se e iene aquella secuencia cuya unción obje i o sea la de meno
alo . En caso de que haya más de una secuencia con el mismo alo de la unción obje i o,
se aplica á el mé odo TB
FF
, siendo seleccionada aquella secuencia cuyo IT asociado sea el
de meno alo .
•Quin o: Repe i el cua o paso has a que odos los abajos hayan sido inse ados (j=n).
3.3 NEHLJP
C eado en 2016 po Weibo Liu, Yan Jin y Ma k P ice (Weibo Liu, Yan Jin y Ma k P ice, 2016), el
NEH
LJP
es uno de los algo i mos más ecien es que, basándose en la heu ís ica del NEH, ha sido
diseñado pa a esol e el p oblema de pe mu a ion lowshop con los obje i os de makespan yco e
idle- ime (
Fm|p mu|Cmax,∑CITi
). Pa a ello, sus au o es p oponen una nue a egla de p io idad,
basada en indicado es es adís icos, así como una egla de desempa e.
3.3.1 PRLJP
La p io i y ule que se p opone en es e algo i mo consis e en o dena de mayo a meno los abajos
en unción de: AVGj+MADj+abs(SKE j)1
3+1
KURj
1
4!
A con inuación se de inen cada uno de los é minos de la exp esión an e io :
•
AVG: El a e age p ocessing ime se co esponde con la media de los p ocessing ime del
abajo jen odas las máquinas: AVGj=1
m∑m
i=1pi j
•
MAD: Es e é mino hace e e encia a la des iación absolu a media (mean absolu e de ia ion)
de los p ocessing ime del abajo j:MADj=1
m∑m
i=1|pi j −AVGj|
La des iación absolu a se u iliza como una medida de la dispe sión, lo que pe mi e conoce
cómo se dis ibuyen los alo es de una población con espec o a la media. En la igu a 3.3
se puede obse a cómo dos poblaciones, a pesa de compa i la misma media, p esen an
dis ibuciones muy di e en es. Po ello, es udia la dispe sión esul a de g an in e és a la ho a
de abaja con conjun os de da os.
16 Capí ulo 3. Desc ipción de los algo i mos
Figu a 3.3 Di e encia en e dos poblaciones de igual media y di e en e dispe sión.
•
SKE: La asime ía, o skewness, es un indicado es adís ico que si e pa a conoce la endencia
de una población a des ia se de la media. Se de ine de la siguien e mane a:
SKE j=
1
m∑m
i=1(pi j −AVGj)3
q1
m∑m
i=1(pi j −AVGj)23
Figu a 3.4 E ec o del skewness en una unción [1].
3.3 NEHLJP 17
•
KUR: La cu osis (en inglés ku osis) indica la concen ación de los alo es de una población
con espec o a la media. Su exp esión ma emá ica se puede esc ibi como:
KURj=
1
m∑m
i=1(pi j −AVGj)4
q1
m∑m
i=1(pi j −AVGj)22
Figu a 3.5 E ec o de la cu osis en una unción [1].
3.3.2 TBLJP
La egla de desempa e del algo i mo NEH
LJP
es á basada en los iempos de lujo dinámicos o
dynamic low imes, pa iendo de la idea de que “minimiza los iempos de lujo conduce a una
disminución del makespan, así como a un aumen o de los iempos ociosos de las máquinas, y
ice e sa” [11].
Se en iende po dynamic low ime la can idad de iempo anscu ido en e el ins an e en que
un abajo comienza a p ocesa se en la p ime a máquina y el ins an e en que e mina de p ocesa se
en la úl ima (no con undi es e concep o con el low ime, explicado en la sección 4.2. Se exp esa de
la siguien e o ma:
¯
j=Cm j −C1,j−1
, siendo
Ci j
el ins an e de iempo en que el abajo j e mina
de p ocesa se en la máquina i.
A endiendo a lo explicado an e io men e, la TB
LJP
consis e en elegi aquella secuencia que p opo -
cione el mayo alo pa a la exp esión dada po :
¯
−q1
n−1∑n
j j−¯
2
Cmax
donde ¯
=1
n∑n
j=1 j ep esen a la media de los dynamic low ime de cada abajo.
3.3.3 Algo i mo NEHLJP
A endiendo a odo lo expues o an e io men e, el algo i mo NEH
LJP
se ejecu a siguiendo los siguien-
es pasos:
•P ime o: Se calcula el alo de AV Gj+MADj+abs(SKE j)1
3+1
KURj
1
4pa a cada uno.
18 Capí ulo 3. Desc ipción de los algo i mos
•
Segundo: Se o denan los abajos de mayo a meno en unción de los alo es calculados en
el paso p ime o.
•
Te ce o: Se seleccionan los dos p ime os abajos y se de e mina la secuencia pa cial óp ima.
•
Cua o: Pa a el es o de los abajos (de
j=3
a
j=n
), se inse a el j-ésimo abajo en odas
las posiciones posibles y se e iene aquella secuencia cuya unción obje i o sea la de meno
alo . En caso de que haya más de una secuencia con el mismo alo de la unción obje i o,
se selecciona á aquella que p opo cione el mayo alo de ¯
−q1
n−1∑n
j( j−¯
)2
Cmax !
•Quin o: Repe i el cua o paso has a que odos los abajos hayan sido inse ados (j=n).
3.4 Algo i mo p opues o: NEHC
El algo i mo que se p opone en es e abajo consis e en una a ian e del algo i mo NEH o iginal,
diseñada pa a disminui los co e idle- ime de las máquinas y así cumpli con los dos obje i os del
p oblema que se plan ea (min w∗Cmax + (1−w)∗∑m
i=1CIT i).
Pa a ello, se in oduce una egla de p io idad basada en la PR del NEH, así como una nue a
egla de desempa e, undamen ada en el concep o de la u ilización de las máquinas, que se á
explicado en la sección 4.2.
3.4.1 PRC
La p io i y ule, designada como PR
C
, consis e en o dena los abajos de mayo a meno en unción
de: m
∑
i=1
pi j+
m
∑
i=1pi j −¯p+Rj!
donde
Rj
ep esen a el ango de los p ocessing imes del abajo j, es deci , la di e encia en e el
alo máximo y el mínimo de los
pi j
, que se calcula como:
Rj=max(pi j)−min(pi j),i∈(1,2, ...m)
.
Como se ha explicado en la sección 3.3.1, la des iación absolu a, co espondien e al segundo
é mino de la exp esión de la PR
C
, si e pa a cuan i ica la dispe sión de los p ocessing imes de
cada abajo. Conoce in o mación ela i a a la dispe sión de los alo es de una población pe mi e
asigna una mayo p io idad a aquellas a eas que p esen en una mayo a iabilidad en sus iempos
de p oceso, y así a enua los e ec os nega i os que pueda ene sob e la solución inal.
Pa a complemen a la in o mación p opo cionada po la des iación absolu a se incluye ambién
el ango, que pe mi e aco a los in e alos en e los que se mue en los iempos de p oceso. Un
ango meno implica alo es de dispe sión meno es, y po consiguien e, iempos de p oceso más
uni o mes. De es e modo, aquellos abajos cuyo ango sea mayo debe án se p ocesados an es que
el es o.
3.4.2 TBC
La egla de desempa e que se p opone, como se ha mencionado an e io men e, es á basada en el
concep o de u ilización, que hace e e encia al g ado en que una máquina es ap o echada, o dicho
de o a o ma, qué po cen aje del iempo se es á p ocesando un abajo con espec o al iempo o al
en el que una máquina pe manece en uncionamien o.
La u ilización de una máquina i se puede de ini de la siguien e mane a:
Ui=∑n
j=1pi j
∑n
j=1pi j +CITi
3.4 Algo i mo p opues o: NEHC19
Pa a un p oblema de m máquinas se u iliza la media de los ac o es de u ilización:
U=1
m
m
∑
i=1
∑n
j=1pi j
∑n
j=1pi j +CITi
Es ácil comp oba que, a medida que la u ilización de una máquina aumen a, su co e idle- ime
disminuye. Po lo an o, la ie-b eaking ule del algo i mo NEH
C
esol e á los desempa es a a o
de la secuencia que enga una mayo u ilización media.
Figu a 3.6 U ilización media de un conjun o de máquinas [11].
3.4.3 Algo i mo NEHC
Basado en las eglas de p io idad y desempa e desc i as en las secciones 3.4.1 y 3.4.2 se p opone el
algo i mo NEHC, cuya ejecución se lle a a cabo siguiendo los pasos enume ados a con inuación:
•
P ime o: Se calcula el alo de
∑m
i=1pi j+∑m
i=1pi j −¯p+Rj
pa a cada uno de los abajos.
•
Segundo: Se o denan los abajos de mayo a meno en unción de los alo es calculados en
el paso p ime o.
•
Te ce o: Se seleccionan los dos p ime os abajos y se de e mina la secuencia pa cial óp ima
•
Cua o: Pa a el es o de los abajos (de
j=3
a
j=n
), se inse a el j-ésimo abajo en odas
las posiciones posibles y se e iene aquella secuencia cuya unción obje i o sea la de meno
alo . En caso de que haya más de una secuencia con el mismo alo de la unción obje i o,
se esol e á el empa e a a o de la secuencia con el mayo alo de
U=1
m∑m
i=1
∑n
j=1pi j
∑n
j=1pi j+CITi
•Quin o: Repe i el cua o paso has a que odos los abajos hayan sido inse ados (j=n).

4 Desa ollo de los mé odos
En
es e capí ulo se expone el so wa e u ilizado pa a la implemen ación de los algo i mos
desc i os en el capí ulo 3, la esolución de los p oblemas y el pos e io análisis de los esul ados
ob enidos. También se p esen an los p oblemas elegidos pa a e ec ua las p uebas an e io men e
mencionadas, así como los dis in os pa áme os u ilizados pa a ello. Finalmen e, se desc iben los
indicado es con los que se ealiza á la compa ación de los algo i mos.
4.1 P og amación de los algo i mos
El p og ama elegido pa a la esolución de los p oblemas, Ma lab, es un so wa e lanzado po
la compañía Ma hWo ks en 1984. Ma lab posee su p opio lenguaje de p og amación, llamado
“lenguaje M”, en el cual se han implemen ado los algo i mos. Una de las p incipales en ajas con
espec o a o os en o nos de p og amación es la acilidad pa a la c eación y manejo de unciones, lo
cual ha esul ado de especial u ilidad debido al ca ác e i e a i o de los algo i mos. La posibilidad
de examina la in o mación almacenada en las a iables di ec amen e desde el wo kspace es o a de
las i udes de es e so wa e, ya que al dispone los alo es en celdas pe mi e que su expo ación a
Excel se pueda lle a a cabo de o ma ápida y sencilla sin necesidad de cambia su o ma o.
Figu a 4.1 Wo kspace de Ma lab.
21
22 Capí ulo 4. Desa ollo de los mé odos
Figu a 4.2 Fo ma o de los da os almacenados en una ma iz.
Po o a pa e, el p og ama que se ha elegido pa a el análisis y compa ación de los esul ados es
Mic oso Excel, debido a la amplia a iedad que p esen a en cuan o a ablas y g á icos con los que
pode ep esen a y compa a in o mación.
Figu a 4.3 Análisis de soluciones en Mic oso Excel.
Finalmen e, se deben conside a las siguien es condiciones expe imen ales:
•
Se u iliza á el mismo o denado du an e odo el expe imen o. En es e caso se a a de un
equipo pe sonal con p ocesado INTEL CORE i7-6500U CPU, 2.50GHz y 12GB de memo ia
RAM.
•
Se u iliza á el mismo leguaje (lenguaje M), p og ama (Ma lab R2020b,Mic oso Excel) y
sis ema ope a i o (Mic oso Windows 10 Home). Además, se ha á uso de las mismas lib e ías
y unciones.
•
Se u iliza án las mismas ins ancias pa a las compa aciones. De es o se habla á con más de alle
en la siguien e sección.
4.2 Gene ación de las ins ancias 23
4.2 Gene ación de las ins ancias
Pa a compa a la e icacia de los algo i mos se han escogido las ins ancias de Tailla d (É ic Tailla d,
1993), en las que se p oponen 120 ins ancias, di ididas en 12 g upos de 10 p oblemas cada uno,
cuyos iempos de p oceso han sido gene ados a pa i de una dis ibución uni o me, omando alo es
de en e 1 y 99. Dichos g upos han sido di ididos en unción del núme o de máquinas y abajos
que los componen, expues os en la abla 4.1. Dado que el alo de la unción obje i o depende de la
ponde ación que se le asigne a cada obje i o, se es udia á cada p oblema a iando el pa áme o w
en e 0 y 1 en in e alos de 0.1, lo que o igina á un o al de 1320 p oblemas.
Tabla 4.1 G upos de p oblemas según su amaño.
Máquinas T abajos
5 20
10 20
20 20
5 50
10 50
20 50
5 100
10 100
20 100
10 200
20 200
20 500
Figu a 4.4
Ins ancias de Tailla d: disposición de los p oblemas [Fuen e: h p://mis ic.heig-
d.ch/ ailla d/p oblemes.di /o donnancemen .di /o donnancemen .h ml].
30 Capí ulo 5. Resul ados y análisis
Figu a 5.4 ARPD de cada mé odo en unción de la dimensión de los p oblemas.
Figu a 5.5 ARPD de cada mé odo en unción de los pesos de los p oblemas.
Con espec o a los iempos de ejecución, el NEH se es ablece como el algo i mo de meno iempo
de ejecución medio con un o al de 7.12 segundos, mien as que el iempo medio de ejecución
del algo i mo NEH
C
es de 8.45 segundos. La di e encia de iempo (1.33 segundos) se jus i ica
debido a la complejidad de ambas heu ís icas y al núme o de ope aciones implíci as en cada una de
ellas, pudiéndose ap ecia que la di e encia de los iempos de ejecución de ambos mé odos iende
a aumen a más cuan o mayo es la dimensión de los p oblemas. No obs an e, dicha di e encia es
azonable y no in luye sob emane a en la elección de un mé odo u o o.

5.3 PRC+ TB 31
Figu a 5.6 Tiempos de ejecución de cada mé odo.
Figu a 5.7 Tiempos de ejecución acumulados de cada mé odo.
5.3 PRC+ TB
Después de analiza los esul ados ob enidos median e los mé odos NEH, NEH
FF
, NEH
LJP
y
NEH
C
, se pasa a es udia la e icacia de la PR
C
y la TB
C
po sepa ado. En es e p ime ensayo se
ha implemen ado la PR
C
en odos los mé odos, con el in de a e igua si és a es capaz de ob ene
mejo es esul ados en combinación con la ie b eaking ule de los demás mé odos que las o iginales:
32 Capí ulo 5. Resul ados y análisis
Tabla 5.7
ARPD de cada ie b eaking ule implemen ada con la PR
C
en unción de la dimensión de
los p oblemas.
m n PRC+ TBNEH PRC+ TBFF PRC+ TBLJP PRC+ TBC
5 20 1,06 1,30 0,54 1,08
10 20 0,37 0,32 0,33 0,26
20 20 0,16 0,13 0,22 0,15
5 50 0,25 0,23 0,55 0,65
10 50 1,44 1,36 1,21 1,19
20 50 0,42 0,38 0,27 0,40
5 100 0,18 0,17 0,49 0,21
10 100 1,00 0,90 0,58 0,74
20 100 1,44 1,42 1,15 1,34
10 200 0,81 0,86 0,94 0,84
20 200 1,49 1,48 0,87 1,30
20 500 1,32 1,23 1,05 1,26
Tabla 5.8
ARPD de cada ie b eaking ule implemen ada con la PR
C
en unción de los pesos de los
p oblemas.
w PRC+ TBNEH PRC+ TBFF PRC+ TBLJP PRC+ TBC
0 2,26 2,51 1,97 2,15
0,1 1,53 1,49 1,05 1,38
0,2 1,19 1,14 0,78 1,14
0,3 0,84 0,84 0,58 0,91
0,4 0,76 0,76 0,50 0,77
0,5 0,71 0,62 0,60 0,55
0,6 0,50 0,53 0,59 0,48
0,7 0,35 0,37 0,37 0,38
0,8 0,31 0,33 0,31 0,33
0,9 0,19 0,19 0,26 0,18
1 0,46 0,18 0,50 0,34
5.3 PRC+ TB 33
Tabla 5.9 Tiempos de ejecución de cada ie b eaking ule implemen ada con la PRC.
m n PRC+ TBNEH PRC+ TBFF PRC+ TBLJP PRC+ TBC
5 20 0,0115 0,0094 0,0087 0,0098
10 20 0,0041 0,0061 0,0060 0,0061
20 20 0,0060 0,0065 0,0068 0,0074
5 50 0,0601 0,0729 0,0717 0,0732
10 50 0,0570 0,0768 0,0838 0,0791
20 50 0,0719 0,0847 0,0913 0,0942
5 100 0,4574 0,5463 0,5658 0,5974
10 100 0,5517 0,6023 0,5939 0,6111
20 100 0,7720 0,6751 0,6964 0,7483
10 200 6,6557 5,0391 5,1135 5,2466
20 200 7,7572 5,6445 5,6540 6,0368
20 500 108,9591 102,4835 103,2376 109,2045
P omedio 10,4470 9,6039 9,6775 10,2262
Los esul ados as implemen a la PR
C
en odos los algo i mos jun o con sus eglas de desempa e
o iginales mues an que la ie b eaking ule que mejo desempeño log a jun o con es a egla de
p io idad es la TB
LJP
, con un ARPD p omedio in e io a la TB
NEH
, TB
FF
y TB
C
en un 17.37%,
16.25% y 12.92% espec i amen e.
Figu a 5.8
ARPD de cada ie b eaking ule implemen ada con la PR
C
en unción de la dimensión
de los p oblemas.
34 Capí ulo 5. Resul ados y análisis
Figu a 5.9
ARPD de cada ie b eaking ule implemen ada con la PR
C
en unción de los pesos de
los p oblemas.
Figu a 5.10 Tiempos de ejecución de cada mé odo implemen ado con la PRC.
Figu a 5.11 Tiempos de ejecución acumulados de cada mé odo implemen ado con la PRC.
5.3 PRC+ TB 35
A con inuación, se ha implemen ado la TB
C
en el algo i mo NEH
LJP
y se ha compa ado con
los mé odos o iginales (NEH, NEH
FF
y NEH
C
). Los esul ados de las ablas 5.10 y 5.11 mues an
que la nue a e sión del algo i mo NEH
LJP
es supe io al es o, con un ARPD p omedio in e io al
NEH
C
en un 4.99%, des acando en los p oblemas de dimensión 5x20, 20x50, 10x100, 20x200 y
20x500 (Figu a 5.12), así como pa a las ponde aciones de alo 0, 0.1, 0.2, 0.3, 0.4 y 0.7 (Figu a
5.13).
Tabla 5.10
ARPD del mé odo NEH
LJP
implemen ado con la PR
C
en unción de la dimensión de los
p oblemas.
m n NEH NEHFF PRc+ TBLJP NEHC
5 20 12,14 12,10 2,27 2,76
10 20 2,52 2,44 2,32 2,26
20 20 2,17 2,16 1,82 1,74
5 50 0,73 0,69 2,53 2,64
10 50 3,38 3,35 3,58 3,51
20 50 2,63 2,60 1,21 1,34
5 100 0,96 0,95 1,10 0,83
10 100 2,25 2,23 1,00 1,16
20 100 1,57 1,50 2,12 2,31
10 200 1,50 1,54 1,78 1,69
20 200 2,44 2,38 1,10 1,53
20 500 2,09 2,03 1,04 1,25
Tabla 5.11
ARPD del mé odo NEH
LJP
implemen ado con la PR
C
en unción de los pesos de los
p oblemas.
w NEH NEHFF PRc+ TBLJP NEHC
0 14,39 14,39 4,93 5,04
0,1 4,42 4,43 3,10 3,44
0,2 2,67 2,66 2,47 2,84
0,3 2,16 2,06 2,06 2,40
0,4 1,92 1,96 1,37 1,64
0,5 1,53 1,51 1,56 1,52
0,6 1,31 1,34 1,51 1,39
0,7 0,98 0,96 0,93 0,93
0,8 0,85 0,82 0,89 0,91
0,9 0,62 0,61 0,61 0,54
1 0,67 0,41 0,62 0,46

36 Capí ulo 5. Resul ados y análisis
Tabla 5.12 Tiempos de ejecución del mé odo NEHLJP implemen ado con la PRC.
m n NEH NEHFF PRc+ TBLJP NEHC
5 20 0,0260 0,0163 0,0176 0,0116
10 20 0,0175 0,0047 0,0065 0,0050
20 20 0,0043 0,0054 0,0057 0,0063
5 50 0,0582 0,0580 0,0631 0,0594
10 50 0,0591 0,0615 0,0635 0,0661
20 50 0,0602 0,0717 0,0724 0,0797
5 100 0,4426 0,4530 0,4565 0,4652
10 100 0,4980 0,4991 0,4817 0,5067
20 100 0,5259 0,5518 0,5605 0,6004
10 200 3,9429 4,1290 4,1874 4,3793
20 200 4,1973 4,6374 4,8859 5,0065
20 500 77,3044 84,6991 86,2719 90,4058
P omedio 7,2614 7,9323 8,0894 8,4660
Figu a 5.12
ARPD del mé odo NEH
LJP
implemen ado con la PR
C
en unción de la dimensión de
los p oblemas.
5.3 PRC+ TB 37
Figu a 5.13
ARPD del mé odo NEH
LJP
implemen ado con la PR
C
en unción de los pesos de los
p oblemas.
Figu a 5.14 Tiempos de ejecución del mé odo NEHLJP implemen ado con la PRC.
38 Capí ulo 5. Resul ados y análisis
Figu a 5.15 Tiempos de ejecución acumulados del mé odo NEHLJP implemen ado con la PRC.
Uno de los e ec os que se log a con la implemen ación de la PR
C
es “sua iza ” la unción de
los ARPD eliminando los “picos” p o ocados po los alo es a ípicos que apa ecen en aquellos
p oblemas en los que la ponde ación es igual a 0, es deci , el obje i o es únicamen e minimiza
los co e idle- ime. Es o ocu e g acias a que se p oduce una mejo dis ibución en los abajos,
disminuyendo conside ablemen e los CIT y con ello el alo de la unción obje i o. Además, no se
p oducen cambios signi ica i os en la calidad de los esul ados, como se puede obse a en la abla
5.13:
Figu a 5.16 ARPD del mé odo NEHLJP o iginal s el NEHLJP implemen ado con la PRC.
Tabla 5.13
Di e encia en e la calidad de los esul ados del NEH
LJP
o iginal y el NEH
LJP
imple-
men ado con la PRC.
NEHLJP PRC+ TBLJP Va iación
o 5727,89 5730,53 -0,0005%
Cmax 7045,52 7043,58 0,0275%
∑CITi4770,15 4774,93 -0,1002%
5.4 PR + TBC39
5.4 PR + TBC
Po úl imo, se ha implemen ado la TB
C
en odos los algo i mos jun o con sus p io i y ules o iginales,
con el in de a e igua si és a es capaz de ob ene mejo es esul ados en combinación con la p io i y
ule de los demás mé odos que las o iginales. Los esul ados señalan de nue o al NEH
C
como el
mé odo que p esen a una mayo calidad en sus soluciones, con un ARPD p omedio un 30.21%
in e io al de la PRLJP y un 25% in e io al de la PRNEH.
Tabla 5.14
ARPD de cada p io i y ule implemen ada con la TB
C
en unción de la dimensión de los
p oblemas.
m n PRNEH + TBCPRFF + TBCPRLJP + TBCPRC+ TBC
5 20 8,48 8,48 15,82 2,42
10 20 3,35 3,35 4,20 3,12
20 20 3,18 3,18 1,64 2,73
5 50 0,97 0,97 2,02 2,79
10 50 4,09 4,09 2,30 4,34
20 50 3,16 3,16 1,88 1,91
5 100 2,45 2,45 2,97 0,97
10 100 2,00 2,00 1,19 1,32
20 100 1,65 1,65 2,48 2,57
10 200 1,72 1,72 1,32 1,82
20 200 2,29 2,29 1,20 1,32
20 500 2,03 2,03 0,98 1,23
Tabla 5.15
ARPD de cada p io i y ule implemen ada con la TB
C
en unción de los pesos de los
p oblemas.
w PRNEH + TBCPRFF + TBCPRLJP + TBCPRC+ TBC
0 13,08 13,08 16,96 5,16
0,1 4,73 4,73 4,56 4,04
0,2 2,96 2,96 3,25 3,36
0,3 2,58 2,58 2,37 2,85
0,4 2,33 2,33 1,77 2,10
0,5 1,84 1,84 1,66 1,88
0,6 1,55 1,55 1,24 1,58
0,7 1,14 1,14 1,01 1,10
0,8 0,96 0,96 0,89 1,06
0,9 0,76 0,76 0,67 0,67
1 0,50 0,50 0,46 0,51
46 Capí ulo 6. Anexo: Códigos de Ma lab
PRLJP
unc ion [seqinic]=seqinicialnehljp(seq,pij,m,n)
%C eo dos ec o es, uno que almacene los índices de los abajos
%y o o con sus alo es a o dena asociados:
seqaux=[1:n];
seqini=[1:n];
%Relleno el ec o con los alo es a o dena :
o j=1:n
seqaux(j)=(sumapj(j,seq,pij,m)/m)+(des iacionabsolu apj(j,seq,pij,m)/m)+
(skepj(j,seq,pij,m)^(1/3))+(1/(ku pj(j,seq,pij,m)^(1/4)));
end
%Y aho a lo o deno:
seqinic=o denamam(seqini,seqaux,n);
end
PRC
unc ion [seqinic]=seqinicialnehc(seq,pij,m,n)
%C eo dos ec o es, uno que almacene los índices de los abajos
%y o o con sus alo es a o dena asociados:
seqaux=[1:n];
seqini=[1:n];
%Relleno el ec o con los alo es a o dena :
o j=1:n
seqaux(j)=sumapj(j,seq,pij,m)+des iacionabsolu apj(j,seq,pij,m)+ angopj(j,seq,pij,m);
end
%Y aho a lo o deno:
seqinic=o denamam(seqini,seqaux,n);

47
end
TB
TBNEH
seq =[seqi(1),seqi(2)];
%P ime o comp uebo que la subsecuencia sea la mejo de las dos posibles:
seq al =[seqi(2),seqi(1)];
%E alúo la unción obje i o de ambas subsecuencias:
[c,ci ]=implemen a(seq ,pij,m,2);
cmax=makespan(c,2);
sumaci =sumci (ci ,m);
o1= uncionobje i o(w,cmax,sumaci );
[c,ci ]=implemen a(seq al ,pij,m,2);
cmax=makespan(c,2);
sumaci =sumci (ci ,m);
o2= uncionobje i o(w,cmax,sumaci );
%Y compa o:
i o2< o1
seq =seq al ;
end
%Una ez engo la subsecuencia óp ima inse o el es o de abajos:
o i=3:n
%Hago la inse ción del siguien e abajo
seq (i)=seqi(i);
%Aho a saco odas las posibles combinaciones:
combi=combinaciones(seq ,i);
48 Capí ulo 6. Anexo: Códigos de Ma lab
%Busco el meno alo de la FO:
%Empiezo po da le el meno a la p ime a combinacion:
[c,ci ]=implemen a(combi(1,1:i),pij,m,i);
cmax=makespan(c,i);
sumaci =sumci (ci ,m);
min o= uncionobje i o(w,cmax,sumaci );
%Aho a busco una FO meno :
o j=2:i
[c,ci ]=implemen a(combi(j,1:i),pij,m,i);
cmax=makespan(c,i);
sumaci =sumci (ci ,m);
oaux= uncionobje i o(w,cmax,sumaci );
i oaux<min o
seq =combi(j,1:i);
min o= oaux;
end
end
end
TBFF
seq =[seqi(1),seqi(2)];
%P ime o comp uebo que la subsecuencia sea la mejo de las dos posibles:
seq al =[seqi(2),seqi(1)];
%E alúo la unción obje i o de ambas subsecuencias:
%Gua do el alo del IT po si ue a necesa io esol e un desempa e
[c,ci ]=implemen a(seq ,pij,m,2);
cmax=makespan(c,2);
49
sumaci =sumci (ci ,m);
o1= uncionobje i o(w,cmax,sumaci );
i 1= b neh (seq ,pij,m,sumaci );
[c,ci ]=implemen a(seq al ,pij,m,2);
cmax=makespan(c,2);
sumaci =sumci (ci ,m);
o2= uncionobje i o(w,cmax,sumaci );
i 2= b neh (seq al ,pij,m,sumaci );
%Y compa o:
i o2< o1
seq =seq al ;
end
i o2== o1 && i 2< i 1
seq =seq al ;
end
%Una ez engo la subsecuencia óp ima inse o el es o de abajos:
o i=3:n
%Hago la inse ción del siguien e abajo
seq (i)=seqi(i);
%Aho a saco odas las posibles combinaciones
combi=combinaciones(seq ,i);
%Busco el meno alo de la FO:
%Empiezo po da le el meno a la p ime a combinacion:
[c,ci ]=implemen a(combi(1,1:i),pij,m,i);
cmax=makespan(c,i);
50 Capí ulo 6. Anexo: Códigos de Ma lab
sumaci =sumci (ci ,m);
min o= uncionobje i o(w,cmax,sumaci );
%Aho a busco una FO meno :
o j=2:i
[c,ci ]=implemen a(combi(j,1:i),pij,m,i);
cmax=makespan(c,i);
sumaci =sumci (ci ,m);
oaux= uncionobje i o(w,cmax,sumaci );
i oaux<min o
min o= oaux;
end
end
%aho a que engo la meno uncion obje i o elijo de en e odas la
%que mejo sa is aga la condición de la TB:
meno i =in ;
o j=1:i
[c,ci ]=implemen a(combi(j,1:i),pij,m,i);
cmax=makespan(c,i);
sumaci =sumci (ci ,m);
oaux= uncionobje i o(w,cmax,sumaci );
i aux= b neh (combi(j,1:i),pij,m,sumaci );
i oaux==min o && i aux<meno i
seq =combi(j,1:i);
meno i = i aux;
end
51
end
end
unc ion [ i ]= b neh (seq,pij,m,sumaci )
%P ime o calculo los on idle- ime:
i =ze os(1,m);
i (1)=0;
o j=2:m
i (j)= i (j-1)+pij(j-1,seq(1));
end
%Aho a la suma:
sum i =0;
o j=1:m
sum i =sum i + i (j);
end
%Y la suma del i con el ci :
i =sum i +sumaci ;
end
TBLJP
seq =[seqi(1),seqi(2)];
%P ime o comp uebo que la subsecuencia sea la mejo de las dos posibles:
seq al =[seqi(2),seqi(1)];
%E alúo la unción obje i o de ambas subsecuencias:
%Gua do el alo de "p" po si ue a necesa io esol e un desempa e:
[c,ci ]=implemen a(seq ,pij,m,2);

52 Capí ulo 6. Anexo: Códigos de Ma lab
cmax=makespan(c,2);
sumaci =sumci (ci ,m);
o1= uncionobje i o(w,cmax,sumaci );
p1= b nehljp(seq ,pij,2,c,cmax);
[c,ci ]=implemen a(seq al ,pij,m,2);
cmax=makespan(c,2);
sumaci =sumci (ci ,m);
o2= uncionobje i o(w,cmax,sumaci );
p2= b nehljp(seq al ,pij,2,c,cmax);
%Y compa o:
i o2< o1
seq =seq al ;
end
i o2== o1 && p2>p1
seq =seq al ;
end
%Una ez engo la subsecuencia óp ima inse o el es o de abajos:
o i=3:n
%Hago la inse ción del siguien e abajo
seq (i)=seqi(i);
%Aho a saco odas las posibles combinaciones
combi=combinaciones(seq ,i);
%Busco el meno alo de la FO:
%Empiezo po da le el meno a la p ime a combinacion:
[c,ci ]=implemen a(combi(1,1:i),pij,m,i);
53
cmax=makespan(c,i);
sumaci =sumci (ci ,m);
min o= uncionobje i o(w,cmax,sumaci );
%Aho a busco una FO meno :
o j=2:i
[c,ci ]=implemen a(combi(j,1:i),pij,m,i);
cmax=makespan(c,i);
sumaci =sumci (ci ,m);
oaux= uncionobje i o(w,cmax,sumaci );
i oaux<min o
min o= oaux;
end
end
%aho a que engo la meno uncion obje i o elijo de en e odas la
%que mejo sa is aga la condición de la TB:
mayo p=0;
o j=1:i
[c,ci ]=implemen a(combi(j,1:i),pij,m,i);
cmax=makespan(c,i);
sumaci =sumci (ci ,m);
oaux= uncionobje i o(w,cmax,sumaci );
paux= b nehljp(combi(j,1:i),pij,i,c,cmax);
i oaux==min o && paux>mayo p
seq =combi(j,1:i);
mayo p=paux;
54 Capí ulo 6. Anexo: Códigos de Ma lab
end
end
end
unc ion [p]= b nehljp(seq,pij,i,c,cmax)
%P ime o calculo los comple ion imes en la p ime a máquina:
cm1=ze os(1,i);
cm1(1)=pij(1,seq(1));
o j=2:i
cm1(j)=cm1(j-1)+pij(1,seq(j));
end
%A con inuación calculo los low imes:
=ze os(1,i);
(1)=c(1);
o j=2:i
(j)=c(j)-cm1(j-1);
end
%Calculo la media de los low imes:
media =0;
o j=1:i
media =media + (j);
end
media =media /i;
%Po úl imo calculo el é mino del suma o io:
e minosum=0;
o j=1:i
55
e minosum= e minosum+( (j)-media )^2;
end
%Lo mul iplico po 1/n-1, así luego es más cómodo al hace la aíz:
e minosum= e minosum*(1/(i-1));
p=(media -sq ( e minosum))/cmax;
TBC
seq =[seqi(1),seqi(2)];
%P ime o comp uebo que la subsecuencia sea la mejo de las dos posibles:
seq al =[seqi(2),seqi(1)];
%E alúo la unción obje i o de ambas subsecuencias:
%Gua do el alo de "u" po si ue a necesa io esol e
un desempa e
[c,ci ]=implemen a(seq ,pij,m,2);
cmax=makespan(c,2);
sumaci =sumci (ci ,m);
o1= uncionobje i o(w,cmax,sumaci );
u1= b nehc(seq ,pij,m,2,ci );
[c,ci ]=implemen a(seq al ,pij,m,2);
cmax=makespan(c,2);
sumaci =sumci (ci ,m);
o2= uncionobje i o(w,cmax,sumaci );
u2= b nehc(seq al ,pij,m,2,ci );
%Y compa o:
i o2< o1
seq =seq al ;
end
62 Capí ulo 6. Anexo: Códigos de Ma lab
mcpu (1,1)=mcpu (1,1)+mcpu(i,3);
mcpu (1,2)=mcpu (1,2)+mcpu(i,4);
mcpu (1,3)=mcpu (1,3)+mcpu(i,5);
mcpu (1,4)=mcpu (1,4)+mcpu(i,6);
end
mcpu (1,1)=mcpu (1,1)/12;
mcpu (1,2)=mcpu (1,2)/12;
mcpu (1,3)=mcpu (1,3)/12;
mcpu (1,4)=mcpu (1,4)/12;

63
Funciones auxilia es
Valo de la unción obje i o
unc ion [ o]= uncionobje i o(w,cmax,sumaci )
o=(w*cmax)+((1-w)*sumaci );
end
Iden i icación de la mejo solución
unc ion [b o]=bes o(neh,neh ,nehljp,nehc)
soluciones=[neh,neh ,nehljp,nehc];
b o=min(soluciones);
end
In e cambio de posiciones en ec o es
unc ion [ ]=cambio( ,i,j)
aux=[1,2];
aux(1)= (i);
aux(2)= (j);
(i)= aux(2);
(j)= aux(1);
end
Combinaciones pa a una secuencia de nelemen os
unc ion [combi]=combinaciones(seq ,i)
combi=ze os(i,i);
%Copio seq :
o j=1:i
o k=1:i
combi(j,k)=seq (k);
end
64 Capí ulo 6. Anexo: Códigos de Ma lab
end
%Aho a c eo las i combinaciones:
lag=1;
o j=2:i
o k= lag:i-1
combi(j,1:i)=cambio(combi(j,1:i),k,i);
end
lag= lag+1;
end
end
Des iación absolu a
unc ion[des abs]=des iacionabsolu apj(j,seq,pij,m)
des abs=0;
o i=1:m
des abs=des abs+abs(pij(i,seq(j))-mediapj(j,seq,pij,m));
end
Comple ion imes y CIT de una secuencia
unc ion [c,ci ]=implemen a(seq,pij,m,n)
%C eo un ec o pa a el makespan y o o pa a el CIT:
c=[1:n];
ci =[1:m];
o j=1:n
c(j)=0;
end
o i=1:m
ci (i)=0;
65
end
%P ime o p epa o el abajo 1 ue a del bucle po que no iene
%an eceso es y después me o el es o de abajos en el bucle:
o i=1:m
c(1)=c(1)+pij(i,seq(1));
o j=2:n
i c(j-1)<c(j)
%Si el abajo an e io acabó an es que el nue o, es e debe
%espe a a acaba y hab á que añadi el CIT:
ci (i)=ci (i)+(c(j)-c(j-1));
c(j)=c(j)+pij(i,seq(j));
end
i c(j-1)==c(j)
%Si coinciden simplemen e se suma el iempo de p oceso:
c(j)=c(j-1)+pij(i,seq(j));
end
i c(j-1)>c(j)
%Si el c del abajo an e io supe a al nue o, en onces el
%nue o abajo a inmedia amen e después de es e:
c(j)=c(j-1)+pij(i,seq(j));
end
end
end
end
66 Capí ulo 6. Anexo: Códigos de Ma lab
Makespan
unc ion [cmax]=makespan(c,n)
cmax=0;
o j=1:n
i c(j)>cmax
cmax=c(j);
end
end
end
Suma de los CIT de odas las máquinas
unc ion [sumaci ]=sumci (ci ,m)
sumaci =0;
o i=1:m
sumaci =sumaci +ci (i);
end
end
Ku osis
unc ion [ku ]=ku pj(j,seq,pij,m)
nume ado =0;
o i=1:m
nume ado =nume ado +(pij(i,seq(j))-(mediapj(j,seq,pij,m)))^4;
end
nume ado =nume ado /m;
denominado =0;
o i=1:m
denominado =denominado +(pij(i,seq(j))-(mediapj(j,seq,pij,m)))^2;
67
end
denominado =denominado /m;
denominado =denominado ^;
ku =nume ado /denominado ;
end
Skewness
unc ion[ske]=skepj(j,seq,pij,m)
nume ado =0;
o i=1:m
nume ado =nume ado +(pij(i,seq(j))-(mediapj(j,seq,pij,m)))^3;
end
nume ado =nume ado /m;
denominado =0;
o i=1:m
denominado =denominado +(pij(i,seq(j))-(mediapj(j,seq,pij,m)))^2;
end
denominado =denominado /m;
denominado =sq (denominado );
denominado =denominado ^3;
ske=nume ado /denominado ;
end
Media de los pi j de un abajo
unc ion [mediapj]=mediapj(j,seq,pij,m)
aux=sumapj(j,seq,pij,m);
mediapj=aux/m;
end

68 Capí ulo 6. Anexo: Códigos de Ma lab
Suma de los pi j de un abajo
unc ion [sumpj]=sumapj(j,seq,pij,m)
sumpj=0;
o i=1:m
sumpj=sumpj+pij(i,seq(j));
end
end
O dena una secuencia de mayo a meno en unción de sus ppi j
unc ion [seqo den]=o denamam(seq,seqaux,n)
%copio el ec o de la secuencia y de los pij
seqo den=[1:n];
seqaux2=[1:n];
o i=1:n
seqo den(i)=seq(i);
end
o i=1:n
seqaux2(i)=seqaux(i);
end
%aho a epaso el ec o de pij pa a o dena los
o i=1:n
o j=1:n
i seqaux2(i)>seqaux2(j)
seqaux2=cambio(seqaux2,i,j);
seqo den=cambio(seqo den,i,j);
end
end
69
end
end
Rango de los pi j de un abajo
unc ion [ ango]= angopj(j,seq,pij,m)
%Pongo como alo de e e encia el p ime componen e pa a pode compa a :
max=pij(1,seq(j));
min=pij(1,seq(j));
o i=1:m
i pij(i,seq(j))>max
max=pij(i,seq(j));
end
i pij(i,seq(j))<min
min=pij(i,seq(j));
end
ango=max-min;
end
70 Capí ulo 6. Anexo: Códigos de Ma lab
Ejemplo de implemen ación del algo i mo NEHC
%Ca go las ins ancias:
a=impo da a(' ailla dbenchma k. x ');
%Inicio el lag pa a eco e las posiciones de las ins ancias:
lag=0;
%C eo la ma iz de las soluciones:
msolnehc=ze os(1320,7);
%Inicio un segundo lag pa a ellena la ma iz de soluciones:
lag2=1;
%Reco o cada uno de los 120 p oblemas:
o s=1:120
%Inicio el con ado del iempo de CPU:
inicio1=cpu ime;
%Incluyo los da os del p oblema (Es necesa io adap a el o ma o
%de los iempos de p oceso)
n= a(1+ lag);
m= a(2+ lag);
dim=2+ lag+(m*n);
pij= a(3+ lag:dim);
pij= eshape(pij,n,m);
pij= anspose(pij);
seq=[1:n];
%Se ejecu a la p io i y ule:
seqi=seqinicialnehc(seq,pij,m,n);
% inicio1 es el iempo que se a da en esol e la secuencia inicial:
inicio1=cpu ime- inicio1;
71
%Aho a elleno la abla con las combinaciones de w po cada
%p oblema:
o k=0:10
% inicio2 es el iempo que se a da en calcula la o:
inicio2=cpu ime;
msolnehc( lag2,1)=m;
msolnehc( lag2,2)=n;
w=0.1*k;
msolnehc( lag2,3)=w;
%Se aplica la TB:
ieb eakingnehc;
%Se implemen a la secuencia inal:
[c,ci ]=implemen a(seq ,pij,m,n);
%Se calcula el makespan y el CIT:
cmax=makespan(c,n);
sumaci =sumci (ci ,m);
%Se almacenan los esul ados en la abla:
msolnehc( lag2,4)= uncionobje i o(w,cmax,sumaci );
msolnehc( lag2,5)=cmax;
msolnehc( lag2,6)=sumaci ;
%El iempo de ejecución es la suma en e ambos iempos:
msolnehc( lag2,7)=cpu ime- inicio2+ inicio1;
lag2= lag2+1;
end
lag=dim;
end
78 Capí ulo 6. Anexo: ARPD en unción de las ca ac e ís icas del p oblema
m n w NEH NEHFF NEHLJP NEHC
5 50 0,9 1,54 1,54 2,38 3,68
5 50 1,0 1,53 1,53 2,00 2,82
10 50 0,0 4,51 4,51 2,43 7,34
10 50 0,1 4,24 4,24 2,20 6,67
10 50 0,2 3,98 3,98 1,97 6,00
10 50 0,3 3,72 3,72 1,75 5,33
10 50 0,4 3,48 3,48 1,54 4,69
10 50 0,5 3,26 3,26 1,34 4,05
10 50 0,6 3,03 3,03 1,14 3,42
10 50 0,7 2,82 2,82 0,94 2,80
10 50 0,8 2,64 2,64 0,77 2,20
10 50 0,9 2,53 2,53 0,68 1,67
10 50 1,0 2,53 2,53 0,68 1,25
20 50 0,0 3,34 3,34 6,61 5,84
20 50 0,1 3,25 3,25 6,40 5,62
20 50 0,2 3,15 3,15 6,14 5,37
20 50 0,3 3,04 3,04 5,85 5,08
20 50 0,4 2,90 2,90 5,51 4,75
20 50 0,5 2,73 2,73 5,11 4,34
20 50 0,6 2,53 2,53 4,61 3,86
20 50 0,7 2,28 2,28 4,00 3,25
20 50 0,8 1,96 1,96 3,24 2,49
20 50 0,9 1,58 1,58 2,27 1,54
20 50 1,0 1,33 1,33 1,24 0,52
5 100 0,0 0,97 0,97 10,47 13,06
5 100 0,1 0,79 0,79 7,44 9,30
5 100 0,2 0,68 0,68 5,66 7,00
5 100 0,3 0,62 0,62 4,47 5,44
5 100 0,4 0,57 0,57 3,61 4,31
5 100 0,5 0,53 0,53 2,96 3,45
5 100 0,6 0,51 0,51 2,46 2,78
5 100 0,7 0,52 0,52 2,08 2,27
5 100 0,8 0,53 0,53 1,77 1,85
5 100 0,9 0,56 0,56 1,54 1,51
5 100 1,0 0,64 0,64 1,40 1,29
10 100 0,0 4,32 4,32 12,75 14,11
10 100 0,1 3,88 3,88 11,33 12,53
10 100 0,2 3,47 3,47 9,98 11,03
10 100 0,3 3,07 3,07 8,68 9,60
10 100 0,4 2,70 2,70 7,44 8,22
10 100 0,5 2,34 2,34 6,24 6,89
10 100 0,6 2,00 2,00 5,09 5,61
10 100 0,7 1,68 1,68 3,98 4,38
10 100 0,8 1,36 1,36 2,91 3,19

79
m n w NEH NEHFF NEHLJP NEHC
10 100 0,9 1,08 1,08 1,89 2,06
10 100 1,0 1,23 1,23 1,32 1,37
20 100 0,0 0,76 0,76 11,05 8,85
20 100 0,1 0,73 0,73 10,63 8,52
20 100 0,2 0,70 0,70 10,16 8,15
20 100 0,3 0,67 0,67 9,61 7,72
20 100 0,4 0,63 0,63 8,97 7,22
20 100 0,5 0,60 0,60 8,23 6,66
20 100 0,6 0,57 0,57 7,36 5,98
20 100 0,7 0,53 0,53 6,29 5,15
20 100 0,8 0,48 0,48 4,97 4,12
20 100 0,9 0,42 0,42 3,27 2,81
20 100 1,0 0,75 0,75 1,42 1,46
10 200 0,0 9,09 9,09 5,22 6,01
10 200 0,1 8,15 8,15 4,68 5,37
10 200 0,2 7,25 7,25 4,16 4,75
10 200 0,3 6,39 6,39 3,65 4,16
10 200 0,4 5,57 5,57 3,17 3,59
10 200 0,5 4,78 4,78 2,71 3,05
10 200 0,6 4,01 4,01 2,26 2,52
10 200 0,7 3,28 3,28 1,83 2,02
10 200 0,8 2,57 2,57 1,43 1,54
10 200 0,9 1,98 1,98 1,11 1,16
10 200 1,0 1,53 1,53 0,95 0,92
20 200 0,0 0,43 0,43 7,20 7,82
20 200 0,1 0,41 0,41 6,89 7,49
20 200 0,2 0,39 0,39 6,54 7,12
20 200 0,3 0,36 0,36 6,15 6,70
20 200 0,4 0,33 0,33 5,70 6,22
20 200 0,5 0,29 0,29 5,18 5,66
20 200 0,6 0,25 0,25 4,57 5,01
20 200 0,7 0,20 0,20 3,86 4,25
20 200 0,8 0,14 0,14 3,00 3,33
20 200 0,9 0,10 0,10 1,98 2,23
20 200 1,0 0,29 0,29 0,95 1,10
20 500 0,0 4,80 4,80 3,82 3,36
20 500 0,1 4,55 4,55 3,63 3,18
20 500 0,2 4,27 4,27 3,41 2,99
20 500 0,3 3,97 3,97 3,17 2,77
20 500 0,4 3,63 3,63 2,91 2,54
20 500 0,5 3,25 3,25 2,62 2,27
20 500 0,6 2,82 2,82 2,29 1,98
20 500 0,7 2,34 2,34 1,93 1,65
20 500 0,8 1,80 1,80 1,52 1,28
20 500 0,9 1,20 1,20 1,08 0,87
20 500 1,0 0,67 0,67 0,75 0,58
P omedio 2,856 2,856 5,348 6,949
80 Capí ulo 6. Anexo: ARPD en unción de las ca ac e ís icas del p oblema
ARPD de cada ie b eaking ule implemen ada con la PRCen unción de las
ca ac e ís icas de los p oblemas
Tabla 3
ARPD de cada ie b eaking ule implemen ada con la PR
C
en unción de las ca ac e ís icas
de los p oblemas.
m n w PRC+ TBNEH PRC+ TBFF PRC+ TBLJP PRC+ TBC
5 20 0,0 4,88 7,83 4,52 4,88
5 20 0,1 2,11 2,11 0,00 2,11
5 20 0,2 2,38 2,38 0,00 2,38
5 20 0,3 0,56 0,56 0,14 0,56
5 20 0,4 0,28 0,28 0,09 0,28
5 20 0,5 0,21 0,21 0,10 0,21
5 20 0,6 0,21 0,21 0,00 0,21
5 20 0,7 0,10 0,10 0,23 0,10
5 20 0,8 0,07 0,02 0,14 0,02
5 20 0,9 0,03 0,03 0,49 0,03
5 20 1,0 0,86 0,63 0,26 1,07
10 20 0,0 0,58 0,58 0,00 0,58
10 20 0,1 0,53 0,47 0,06 0,47
10 20 0,2 0,35 0,35 0,00 0,35
10 20 0,3 0,29 0,29 0,00 0,29
10 20 0,4 0,23 0,23 0,00 0,23
10 20 0,5 1,54 0,00 1,29 0,00
10 20 0,6 0,07 0,91 1,02 0,00
10 20 0,7 0,20 0,20 0,17 0,01
10 20 0,8 0,05 0,05 0,20 0,05
10 20 0,9 0,02 0,02 0,11 0,04
10 20 1,0 0,21 0,41 0,73 0,81
20 20 0,0 0,87 0,87 0,20 0,27
20 20 0,1 0,00 0,00 0,20 0,00
20 20 0,2 0,13 0,13 0,19 0,13
20 20 0,3 0,12 0,12 0,15 0,12
20 20 0,4 0,00 0,29 0,44 0,29
20 20 0,5 0,00 0,00 0,14 0,00
20 20 0,6 0,17 0,00 0,17 0,25
20 20 0,7 0,00 0,00 0,30 0,19
20 20 0,8 0,00 0,00 0,00 0,00
20 20 0,9 0,04 0,00 0,04 0,00
20 20 1,0 0,40 0,00 0,61 0,35
5 50 0,0 0,63 0,63 1,55 1,89
5 50 0,1 0,18 0,18 1,18 1,36
5 50 0,2 0,08 0,08 0,98 1,00
5 50 0,3 0,14 0,14 0,75 0,94
5 50 0,4 0,00 0,00 0,41 0,25
5 50 0,5 0,41 0,52 0,01 0,51
5 50 0,6 0,51 0,37 0,36 0,37
81
m n w PRC+ TBNEH PRC+ TBFF PRC+ TBLJP PRC+ TBC
5 50 0,7 0,24 0,16 0,13 0,24
5 50 0,8 0,11 0,14 0,26 0,15
5 50 0,9 0,25 0,17 0,13 0,25
5 50 1,0 0,16 0,17 0,27 0,20
10 50 0,0 3,61 3,61 3,45 3,28
10 50 0,1 3,71 3,71 1,16 3,36
10 50 0,2 1,14 1,14 2,14 0,87
10 50 0,3 1,82 1,82 1,26 1,34
10 50 0,4 1,63 1,28 1,56 0,95
10 50 0,5 0,59 1,06 0,70 0,78
10 50 0,6 0,55 0,55 1,25 0,70
10 50 0,7 0,87 0,87 0,11 0,87
10 50 0,8 0,34 0,39 0,60 0,39
10 50 0,9 0,42 0,48 0,24 0,34
10 50 1,0 1,12 0,05 0,84 0,18
20 50 0,0 0,57 0,57 0,11 0,57
20 50 0,1 0,48 0,48 0,10 0,48
20 50 0,2 0,45 0,45 0,03 0,45
20 50 0,3 0,18 0,18 0,16 0,18
20 50 0,4 0,43 0,43 0,37 0,43
20 50 0,5 0,20 0,20 0,31 0,00
20 50 0,6 0,17 0,17 0,36 0,17
20 50 0,7 0,54 0,75 0,39 0,98
20 50 0,8 0,60 0,60 0,02 0,53
20 50 0,9 0,17 0,17 0,24 0,17
20 50 1,0 0,84 0,22 0,87 0,45
5 100 0,0 0,60 0,60 2,95 1,14
5 100 0,1 0,11 0,11 0,60 0,11
5 100 0,2 0,03 0,03 0,37 0,03
5 100 0,3 0,19 0,19 0,04 0,19
5 100 0,4 0,07 0,07 0,21 0,06
5 100 0,5 0,10 0,10 0,04 0,13
5 100 0,6 0,20 0,17 0,04 0,17
5 100 0,7 0,15 0,15 0,41 0,15
5 100 0,8 0,22 0,31 0,27 0,22
5 100 0,9 0,01 0,01 0,13 0,01
5 100 1,0 0,28 0,08 0,26 0,09
10 100 0,0 3,62 3,62 1,00 2,09
10 100 0,1 2,51 2,51 1,42 1,81
10 100 0,2 1,08 0,81 0,82 0,74
10 100 0,3 0,57 0,57 0,60 0,92
10 100 0,4 0,77 0,66 0,31 0,66
10 100 0,5 0,46 0,03 0,95 0,03
10 100 0,6 0,48 0,48 0,30 0,52
82 Capí ulo 6. Anexo: ARPD en unción de las ca ac e ís icas del p oblema
m n w PRC+ TBNEH PRC+ TBFF PRC+ TBLJP PRC+ TBC
10 100 0,7 0,31 0,31 0,19 0,42
10 100 0,8 0,59 0,52 0,22 0,43
10 100 0,9 0,21 0,21 0,15 0,21
10 100 1,0 0,39 0,23 0,38 0,27
20 100 0,0 3,63 3,63 2,74 2,49
20 100 0,1 1,04 1,04 2,50 1,10
20 100 0,2 2,41 2,08 1,94 2,15
20 100 0,3 2,19 2,19 0,47 2,43
20 100 0,4 2,02 2,23 0,16 2,12
20 100 0,5 0,89 1,17 1,14 1,08
20 100 0,6 1,24 0,98 1,06 0,98
20 100 0,7 0,75 0,75 0,72 0,71
20 100 0,8 0,74 1,07 0,86 1,07
20 100 0,9 0,30 0,28 0,39 0,36
20 100 1,0 0,59 0,17 0,70 0,29
10 200 0,0 3,61 3,61 4,42 4,34
10 200 0,1 2,04 2,04 1,49 1,80
10 200 0,2 1,13 1,15 0,48 1,00
10 200 0,3 0,27 0,66 1,34 0,08
10 200 0,4 0,56 0,56 0,61 0,49
10 200 0,5 0,46 0,70 0,36 0,78
10 200 0,6 0,26 0,32 0,24 0,27
10 200 0,7 0,16 0,16 0,50 0,12
10 200 0,8 0,15 0,06 0,25 0,18
10 200 0,9 0,08 0,07 0,30 0,10
10 200 1,0 0,17 0,13 0,33 0,12
20 200 0,0 2,89 2,89 1,38 1,94
20 200 0,1 2,55 2,55 1,82 1,66
20 200 0,2 2,21 2,21 1,07 2,12
20 200 0,3 1,98 1,74 0,47 2,33
20 200 0,4 1,89 1,97 0,53 2,30
20 200 0,5 2,11 2,27 0,76 1,71
20 200 0,6 1,01 1,08 1,28 0,89
20 200 0,7 0,38 0,38 0,73 0,29
20 200 0,8 0,49 0,53 0,47 0,50
20 200 0,9 0,48 0,61 0,59 0,43
20 200 1,0 0,36 0,04 0,52 0,16
20 500 0,0 1,66 1,66 1,27 2,39
20 500 0,1 3,05 2,68 2,11 2,29
20 500 0,2 2,86 2,91 1,34 2,49
20 500 0,3 1,75 1,58 1,60 1,57
20 500 0,4 1,19 1,14 1,28 1,16
20 500 0,5 1,49 1,21 1,34 1,42
20 500 0,6 1,05 1,13 1,03 1,23
20 500 0,7 0,56 0,64 0,61 0,44
20 500 0,8 0,44 0,31 0,39 0,47
20 500 0,9 0,25 0,28 0,29 0,26
20 500 1,0 0,18 0,03 0,28 0,12
P omedio 0,83 0,82 0,68 0,78
83
ARPD del mé odo NEHLJP implemen ado con la PRCen unción de las ca ac-
e ís icas de los p oblemas
Tabla 4 ARPD del mé odo NEHLJP implemen ado con la PRCen unción de las ca ac e ís icas de
los p oblemas.
m n w NEH NEHFF PRc+ TBLJP NEHC
5 20 0,0 108,33 108,33 11,30 10,84
5 20 0,1 11,16 11,16 3,24 5,61
5 20 0,2 2,92 2,92 1,54 4,05
5 20 0,3 4,00 4,00 0,29 0,71
5 20 0,4 2,25 2,25 0,40 0,59
5 20 0,5 1,37 1,37 0,60 0,70
5 20 0,6 0,79 0,79 1,55 1,77
5 20 0,7 0,50 0,50 1,17 1,04
5 20 0,8 0,28 0,27 2,65 2,52
5 20 0,9 0,93 0,93 1,63 1,17
5 20 1,0 1,04 0,61 0,59 1,40
10 20 0,0 4,82 4,82 2,90 3,50
10 20 0,1 5,70 5,70 4,44 4,84
10 20 0,2 4,06 4,06 2,41 2,76
10 20 0,3 3,37 3,31 2,19 2,48
10 20 0,4 1,78 1,91 1,52 1,75
10 20 0,5 1,95 1,95 3,87 2,58
10 20 0,6 2,11 2,11 3,47 2,45
10 20 0,7 0,94 0,94 1,18 1,02
10 20 0,8 0,71 0,71 1,91 1,77
10 20 0,9 0,89 0,89 0,91 0,84
10 20 1,0 1,40 0,48 0,75 0,83
20 20 0,0 3,17 3,17 2,56 2,63
20 20 0,1 2,89 2,89 2,20 2,00
20 20 0,2 1,38 1,38 2,78 2,71
20 20 0,3 3,11 3,11 3,41 3,37
20 20 0,4 2,99 2,99 2,11 1,95
20 20 0,5 2,56 2,56 2,44 2,30
20 20 0,6 2,91 2,91 1,10 1,17
20 20 0,7 1,59 1,59 1,53 1,42
20 20 0,8 1,23 1,23 0,63 0,63
20 20 0,9 1,23 1,23 0,49 0,45
20 20 1,0 0,78 0,76 0,76 0,50
5 50 0,0 2,43 2,43 11,11 11,56
5 50 0,1 1,17 1,17 5,29 5,49
5 50 0,2 0,64 0,64 3,52 3,53
5 50 0,3 0,89 0,45 2,53 2,72
5 50 0,4 0,45 0,45 0,69 0,53
5 50 0,5 0,65 0,65 0,35 0,86
5 50 0,6 0,34 0,34 1,87 1,87
5 50 0,7 0,10 0,10 1,06 1,16
5 50 0,8 0,77 0,77 0,61 0,49
5 50 0,9 0,35 0,35 0,28 0,40
5 50 1,0 0,25 0,25 0,52 0,45

84 Capí ulo 6. Anexo: ARPD en unción de las ca ac e ís icas del p oblema
m n w NEH NEHFF PRc+ TBLJP NEHC
10 50 0,0 12,06 12,06 10,22 9,66
10 50 0,1 6,05 6,05 6,26 8,33
10 50 0,2 4,86 4,86 6,67 5,32
10 50 0,3 2,72 2,72 3,62 3,77
10 50 0,4 3,62 3,62 3,68 3,06
10 50 0,5 1,82 1,82 2,25 2,32
10 50 0,6 2,09 2,09 2,83 2,27
10 50 0,7 1,64 1,38 1,12 1,88
10 50 0,8 0,65 0,69 0,96 0,75
10 50 0,9 0,81 0,81 0,84 0,96
10 50 1,0 0,92 0,77 0,96 0,30
20 50 0,0 7,81 7,81 1,04 1,49
20 50 0,1 5,21 5,21 0,83 1,20
20 50 0,2 2,73 2,73 2,06 2,49
20 50 0,3 1,79 1,79 2,02 2,04
20 50 0,4 2,65 2,65 1,48 1,53
20 50 0,5 1,53 1,53 1,39 1,07
20 50 0,6 1,11 1,11 1,35 1,17
20 50 0,7 2,37 2,37 0,52 1,11
20 50 0,8 2,11 2,11 1,03 1,54
20 50 0,9 0,62 0,69 0,58 0,50
20 50 1,0 0,99 0,56 1,08 0,66
5 100 0,0 5,55 5,55 6,75 4,97
5 100 0,1 1,28 1,28 1,78 1,29
5 100 0,2 1,00 1,00 0,59 0,25
5 100 0,3 0,51 0,51 0,71 0,87
5 100 0,4 0,35 0,35 0,56 0,42
5 100 0,5 0,33 0,33 0,21 0,30
5 100 0,6 0,84 0,81 0,08 0,20
5 100 0,7 0,38 0,38 0,54 0,29
5 100 0,8 0,04 0,04 0,35 0,29
5 100 0,9 0,08 0,06 0,22 0,09
5 100 1,0 0,19 0,10 0,32 0,14
10 100 0,0 8,23 8,23 1,91 3,00
10 100 0,1 5,36 5,36 1,88 2,28
10 100 0,2 3,54 3,54 1,68 1,61
10 100 0,3 1,98 1,98 1,06 1,38
10 100 0,4 1,67 1,67 0,76 1,11
10 100 0,5 0,99 1,12 1,31 0,39
10 100 0,6 0,71 0,78 0,53 0,74
10 100 0,7 0,68 0,68 0,51 0,74
10 100 0,8 0,55 0,57 0,51 0,72
10 100 0,9 0,36 0,36 0,31 0,37
10 100 1,0 0,66 0,26 0,54 0,44
20 100 0,0 2,80 2,80 3,19 2,94
20 100 0,1 2,16 2,16 3,07 1,66
20 100 0,2 1,89 1,89 3,14 3,39
20 100 0,3 1,83 1,83 3,71 5,70
20 100 0,4 1,65 1,65 1,08 3,04
20 100 0,5 1,46 1,47 2,80 2,75
20 100 0,6 0,88 0,88 2,75 2,66
85
m n w NEH NEHFF PRc+ TBLJP NEHC
20 100 0,7 1,42 1,42 1,37 1,36
20 100 0,8 1,50 1,35 0,86 1,06
20 100 0,9 0,69 0,66 0,56 0,53
20 100 1,0 0,96 0,44 0,74 0,33
10 200 0,0 6,13 6,13 5,37 5,39
10 200 0,1 2,05 2,25 4,73 5,00
10 200 0,2 2,33 2,33 2,52 3,03
10 200 0,3 1,73 1,73 2,55 1,27
10 200 0,4 1,26 1,26 1,31 1,19
10 200 0,5 0,38 0,74 0,94 1,36
10 200 0,6 0,93 0,89 0,42 0,46
10 200 0,7 0,51 0,51 0,64 0,26
10 200 0,8 0,67 0,67 0,25 0,19
10 200 0,9 0,21 0,20 0,41 0,21
10 200 1,0 0,35 0,25 0,44 0,23
20 200 0,0 5,89 5,89 1,34 1,89
20 200 0,1 5,43 5,43 1,94 1,78
20 200 0,2 3,89 3,66 1,38 2,43
20 200 0,3 1,41 1,41 0,77 2,65
20 200 0,4 2,75 3,08 1,36 3,14
20 200 0,5 2,61 2,01 1,17 2,11
20 200 0,6 1,67 1,86 1,38 0,99
20 200 0,7 0,83 0,83 0,93 0,48
20 200 0,8 1,12 0,88 0,53 0,55
20 200 0,9 0,84 0,89 0,82 0,65
20 200 1,0 0,38 0,20 0,49 0,12
20 500 0,0 5,41 5,41 1,46 2,60
20 500 0,1 4,52 4,52 1,57 1,75
20 500 0,2 2,84 2,88 1,35 2,50
20 500 0,3 2,60 1,89 1,86 1,83
20 500 0,4 1,67 1,69 1,47 1,34
20 500 0,5 2,65 2,60 1,41 1,50
20 500 0,6 1,36 1,54 0,76 0,96
20 500 0,7 0,83 0,82 0,60 0,43
20 500 0,8 0,53 0,51 0,36 0,44
20 500 0,9 0,42 0,25 0,31 0,28
20 500 1,0 0,17 0,23 0,29 0,13
P omedio 2,87 2,83 1,82 1,92
86 Capí ulo 6. Anexo: ARPD en unción de las ca ac e ís icas del p oblema
ARPD de cada p io i y ule implemen ada con la TBCen unción de las ca ac-
e ís icas de los p oblemas
Tabla 5
ARPD de cada p io i y ule implemen ada con la TB
C
en unción de las ca ac e ís icas de
los p oblemas.
m n w PRNEH + TBCPRFF + TBCPRLJP + TBCPRC+ TBC
5 20 0,0 72,12 72,12 129,02 7,21
5 20 0,1 8,60 8,60 18,52 5,01
5 20 0,2 1,61 1,61 9,24 3,46
5 20 0,3 3,24 3,24 5,75 0,42
5 20 0,4 2,17 2,17 2,49 0,81
5 20 0,5 1,62 1,62 1,93 0,96
5 20 0,6 1,04 1,04 1,18 2,02
5 20 0,7 0,51 0,51 1,35 1,05
5 20 0,8 0,56 0,56 1,74 2,80
5 20 0,9 1,27 1,27 1,14 1,50
5 20 1,0 0,60 0,60 1,69 1,35
10 20 0,0 7,94 7,94 8,56 6,61
10 20 0,1 7,45 7,45 9,55 6,59
10 20 0,2 5,48 5,48 6,32 4,20
10 20 0,3 3,94 3,94 4,51 3,16
10 20 0,4 3,21 3,21 4,26 2,97
10 20 0,5 2,45 2,45 3,53 3,02
10 20 0,6 2,20 2,20 3,29 2,54
10 20 0,7 1,00 1,00 1,96 1,08
10 20 0,8 0,91 0,91 2,49 1,96
10 20 0,9 1,08 1,08 1,27 1,03
10 20 1,0 1,17 1,17 0,44 1,11
20 20 0,0 5,11 5,11 2,78 4,50
20 20 0,1 4,93 4,93 2,03 3,97
20 20 0,2 3,99 3,99 1,85 5,28
20 20 0,3 3,84 3,84 3,88 4,12
20 20 0,4 3,84 3,84 2,58 2,83
20 20 0,5 3,65 3,65 2,02 3,36
20 20 0,6 3,50 3,50 0,59 1,75
20 20 0,7 1,94 1,94 0,82 1,75
20 20 0,8 1,51 1,51 0,78 0,90
20 20 0,9 1,74 1,74 0,39 0,90
20 20 1,0 0,88 0,88 0,27 0,63
5 50 0,0 3,70 3,70 8,85 11,71
5 50 0,1 1,20 1,20 4,26 5,53
5 50 0,2 0,98 0,98 2,93 3,90
5 50 0,3 0,78 0,78 2,05 3,07
5 50 0,4 0,80 0,80 0,82 0,87
5 50 0,5 0,62 0,62 0,48 0,83
5 50 0,6 0,50 0,50 1,24 2,03
87
m n w PRNEH + TBCPRFF + TBCPRLJP + TBCPRC+ TBC
5 50 0,7 0,40 0,40 0,44 1,47
5 50 0,8 0,82 0,82 0,47 0,55
5 50 0,9 0,58 0,58 0,25 0,30
5 50 1,0 0,24 0,24 0,40 0,47
10 50 0,0 13,01 13,01 5,09 10,43
10 50 0,1 7,95 7,95 4,06 10,20
10 50 0,2 6,17 6,17 2,95 7,71
10 50 0,3 3,84 3,84 3,22 4,85
10 50 0,4 3,96 3,96 2,50 3,57
10 50 0,5 3,01 3,01 1,74 3,67
10 50 0,6 2,53 2,53 2,12 2,49
10 50 0,7 2,03 2,03 0,60 2,48
10 50 0,8 0,84 0,84 1,21 0,90
10 50 0,9 0,77 0,77 1,48 0,92
10 50 1,0 0,91 0,91 0,34 0,55
20 50 0,0 7,62 7,62 3,10 1,32
20 50 0,1 5,45 5,45 3,50 1,43
20 50 0,2 3,87 3,87 3,48 3,60
20 50 0,3 3,31 3,31 2,42 3,56
20 50 0,4 4,24 4,24 2,15 3,06
20 50 0,5 2,66 2,66 1,74 2,13
20 50 0,6 1,59 1,59 0,74 1,64
20 50 0,7 2,50 2,50 1,73 1,24
20 50 0,8 2,09 2,09 0,41 1,52
20 50 0,9 1,05 1,05 0,65 0,86
20 50 1,0 0,40 0,40 0,76 0,60
5 100 0,0 21,13 21,13 26,59 5,74
5 100 0,1 1,80 1,80 1,36 1,79
5 100 0,2 1,14 1,14 1,22 0,38
5 100 0,3 0,55 0,55 0,68 0,90
5 100 0,4 0,36 0,36 0,64 0,43
5 100 0,5 0,41 0,41 0,42 0,37
5 100 0,6 0,71 0,71 0,61 0,11
5 100 0,7 0,32 0,32 0,68 0,23
5 100 0,8 0,31 0,31 0,24 0,42
5 100 0,9 0,10 0,10 0,13 0,13
5 100 1,0 0,08 0,08 0,09 0,16
10 100 0,0 6,82 6,82 2,92 3,06
10 100 0,1 4,00 4,00 2,03 2,27
10 100 0,2 2,45 2,45 1,95 2,10
10 100 0,3 2,62 2,62 1,16 1,63
10 100 0,4 1,97 1,97 0,74 1,40
10 100 0,5 1,17 1,17 1,64 0,55
10 100 0,6 0,80 0,80 0,69 0,74