28
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 Fin de G ado
G ado en Ingenie ía de Tecnologías Indus iales
Análisis de la aplicación de heu ís icas y me a-
heu ís icas aplicadas al p oblema Dis ibu ed
Flowshop pa a minimiza el o al a diness
Au o : Alejand o Sil a Ca e o
Tu o : Paz Pé ez González
Dp o. O ganización Indus ial y Ges ión de Emp esas I
Escuela Técnica Supe io de Ingenie ía
Uni e sidad de Se illa
Se illa, 2025
T abajo Fin de G ado
G ado en Ingenie ía de Tecnologías Indus iales
Análisis de la aplicación de heu ís icas y
me aheu ís icas aplicadas al p oblema
Dis ibu ed Flowshop pa a minimiza el o al
a diness
Au o :
Alejand o Sil a Ca e o
Tu o :
Paz Pé ez González
Ca ed á ico de Uni e sidad
Dp o. O ganización Indus ial y Ges ión de Emp esas I
Escuela Técnica Supe io de Ingenie ía
Uni e sidad de Se illa
Se illa, 2025
T abajo Fin de G ado:
Análisis de la aplicación de heu ís icas y me aheu ís icas aplicadas al
p oblema Dis ibu ed Flowshop pa a minimiza el o al a diness
Au o : Alejand o Sil a Ca e o
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 mis pad es,
An onio y Ma ibel,
po apoya me en odas mis decisiones.
A mis he manos,
Albe o, An onio y Gema,
po la unión que enemos.
A mi pa eja,
Ana,
po es a siemp e a mi lado.
I
Resumen
El en o no se ca ac e iza po in oluc a dos decisiones: la asignación de los abajos a las áb icas, y la
secuenciación de los mismos en cada una de ellas.
Es e abajo abo da la op imización de un p oblema de p og amación de la p oducción en un en o no de
Dis ibu ed Flowshop, que se ca ac e iza po in oluc a dos decisiones: la asignación de los abajos
a las áb icas exis en es, y la secuenciación de los mismos en cada una de ellas. El obje i o p incipal es
minimiza la a danza o al de los abajos asignados a cada áb ica, es deci , la suma de la des iación de los
iempos de e minación con espec o a las echas de en ega, cuando los abajos an a de.
En p ime luga se han in oducido los concep os undamen ales de la p og amación de ope aciones, los
cuales pe mi en ca ac e iza adecuadamen e el p oblema y sus es icciones. Se han implemen ado di e sos
mé odos de esolución, en e ellos eglas de despacho adicionales, algo i mos heu ís icos y me aheu ís icos,
los cuales ue on explicados en de alle pa a una mejo comp ensión de su uncionamien o y aplicabilidad.
El abajo ealiza un análisis compa a i o del desempeño de cada algo i mo, e aluando su e icacia en
é minos de educción de a danza y e iciencia compu acional. La expe imen ación incluye un es udio
exhaus i o de los pa áme os que de inen el p oblema, como el núme o de áb icas, la can idad de abajos y
el núme o de máquinas in oluc adas en cada áb ica. Adicionalmen e, se ha lle ado a cabo un seguimien o
del iempo de compu ación pa a cada algo i mo, lo que pe mi e una e aluación p ecisa de su iabilidad en
escena ios de p oducción eal.
Es e p oyec o concluye con una e aluación de los esul ados ob enidos, analizando la e ec i idad de los
algo i mos aplicados pa a minimiza el iempo de a danza o al en en o nos de p oducción dis ibuidos.
III
1 In oducción
E
lDis ibu ed Pe mu a ion Flowshop Scheduling P oblem (DPFSP) es una a ian e a anzada del p oblema
clásico de p og amación de p oducción conocido como Flowshop. En un en o no DPFSP, exis e un
núme o de e minado de áb icas o almen e idén icas. En cada una de ellas, hay un conjun o de máquinas po
las que deben se p ocesados los abajos asignados. Además, debido a la es icción de pe mu ación, den o
de cada áb ica, la secuencia de abajos en cada máquina se á la misma. Es e modelo e leja la c ecien e
complejidad de los sis emas de p oducción mode nos, donde las máquinas y ecu sos no es án cen alizados
en una única áb ica, sino dis ibuidos geog á icamen e, lo que añade una capa adicional de plani icación y
coo dinación (Olhage & Feldmann, 2018).
En el DPFSP, la p incipal a ea es asigna y secuencia los abajos en el conjun o de áb icas de mane a
que se op imice un obje i o especí ico, como pueden se la minimización del iempo o al de inalización
de los abajos (makespan), la educción de los e asos ( a diness), o la maximización de la u ilización
de los ecu sos. Es e p oblema es de g an ele ancia en la indus ia manu ac u e a y de se icios, ya que
una p og amación e icien e puede esul a en una educción de cos es y iempos signi ica i a, mejo ando la
compe i i idad (Fe nandez-Viagas & F aminan, 2015).
1.1 Obje i o
El obje i o en es e documen o es esol e y analiza el p oblema de DPFS, median e la aplicación de di e sas
eglas de despacho, heu ís icas y me aheu ís icas. La es icción p opues a es la de pe mu ación y el obje i o
a op imiza es el o al a diness, ambos concep os se de inen en el capí ulo 2.
Pa a ello, una ez ob enidos los esul ados de cada uno de los mé odos, se ealiza una compa a i a pa a
e alua los, con el in de es ablece una conclusión sob e el desempeño que o ece cada algo i mo.
1.2 He amien as empleadas
En es e p oyec o, se ha empleado Py hon como he amien a p incipal pa a el desa ollo e implemen ación
de los mé odos pa a esol e el DPFSP. Py hon es un lenguaje de p og amación ampliamen e u ilizado
en el ámbi o académico e indus ial debido a su simplicidad, e sa ilidad y la ex ensa disponibilidad de
biblio ecas especializadas (Oliphan , 2007). Pa a abo da la complejidad del DPFSP y aplica las heu ís icas y
me aheu ís icas, se ha u ilizado la lib e ía schep k (F aminan, 2023), diseñada especí icamen e pa a p oblemas
de p og amación de la p oducción.
Adicionalmen e, pa a el análisis de los esul ados se han elabo ado ablas y g á icas empleando el p og ama
Mic oso Excel, po su g an u ilidad en es e aspec o.
1.3 Es uc u a
En es a p ime a sección se in oduce de o ma b e e el p oblema con el que se abaja a lo la go del documen o,
así como el obje i o del abajo, las he amien as u ilizadas y el con enido de cada uno de los apa ados.
La sección dos a a sob e concep os básicos de p og amación de ope aciones, necesa ios pa a en ende
cualquie p oblema desde la base, la a iedad de p oblemas posibles y la ca ac e ización del p oblema a
esol e .
1
2Capí ulo 1. In oducción
En la e ce a sección se p esen an los mé odos de esolución empleados, de allando el uncionamien o de
cada una de las eglas de despacho, heu ís icas y me aheu ís icas.
Luego, en la cua a sección, se p esen an las ins ancias que se han u ilizado pa a esol e el p oblema y se
ealiza una compa a i a y análisis de los esul ados ob enidos.
Po úl imo, en la sección núme o cinco, se es ablecen las conclusiones a las que se han llegado as el
análisis.
2 Desc ipción del p oblema
E
n es e apa ado se a a a a de in oduci los concep os básicos elacionados con la p og amación de
ope aciones, con el obje i o de ca ac e iza el p oblema plan eado en es e documen o.
2.1 Concep os básicos
La de inición de dichos concep os así como la no ación usada son los siguien es (Pe ez-Gonzalez e al.,
2022):
•
Máquina: Recu so p oduc i o con capacidad pa a ealiza ope aciones de ans o mación o anspo e
de ma e ial. El conjun o de máquinas iene de inido po M=1,...,m, siendo el índice empleado i
∈
M.
•
T abajo: P oduc o que es obje o de una ope ación en alguna de las máquinas de la áb ica. El conjun o
de abajos iene de inido po N=1,...,n, siendo el índice empleado j∈N.
•
Tiempo de p oceso: Es el iempo en el que la máquina i
∈
Mes á ocupada en p ocesa el abajo j
∈
N.
Se deno a como pi j.
•
Fecha de en ega: Ins an e de iempo en el que el abajo j
∈
Ndebe de es a e minado, se deno a
como dj. La úl ima ope ación de cada abajo debe comple a se an es de dj.
•
Ru a de p oceso: Vec o en el que se indica el o den en el que el abajo j a a se p ocesado. Se deno a
como Rj.
O o concep o impo an e es el de p og ama o schedule, que consis e en la asignación en la escala empo al
conc e a de las máquinas de una emp esa pa a la ab icación de un conjun o de abajos. Un p og ama
de e mina el comienzo y el inal de cada ope ación a ealiza en cada ecu so p oduc i o. Pa a que un
p og ama sea admisible debe cumpli con odas las es icciones y ca ac e ís icas del p oceso p oduc i o, el
obje i o de la p og amación de la p oducción es encon a dicho p og ama admisible, en la Figu a 2.1 se
mues a un ejemplo. Sin emba go pa a que un p og ama sea semi-ac i o se iene que cumpli que no pueda
adelan a se ninguna ope ación sin cambia el o den en que alguna máquina p ocesa los abajos, localmen e,
en cada máquina, cada abajo se encuen a lo más a la izquie da posible pa a un o den dado, como se obse a
en la Figu a 2.2.
Figu a 2.1 Ejemplo de p og ama admisible [Fuen e: Pe ez-Gonzalez e al., 2022].
3
4Capí ulo 2. Desc ipción del p oblema
Figu a 2.2 Ejemplo de p og ama semi-ac i o [Fuen e: Pe ez-Gonzalez e al., 2022].
Po úl imo, se de ine secuencia como el o den en que cada abajo comienza a p ocesa se en cada máquina.
Es a se puede ep esen a como un ec o pa a cada máquina o en caso de que la asignación sea la misma
pa a odas las máquinas, como un ec o único.
2.2 Modelos de p og amación de la p oducción
La impo ancia de es e pun o ecae en la necesidad de clasi ica el p oblema pa a así lle a a cabo su esolución.
Po ello G aham e al. (1979) p opusie on una no ación en base a es á eas: en o no, es icciones y obje i os.
Rep esen ado como α|β|γ, se p esen a en la Figu a 2.3.
Figu a 2.3
Clasi icación de los modelos de p og amación de la p oducción [Fuen e: F aminan e al., 2014].
•
En o no (
α
): Es e p ime campo consis e en especi ica el en o no de las máquinas, es deci , el núme o
de máquinas en la áb ica y la disposición de cada una de ellas. Los layou s exis en es se pueden
simpli ica en los siguien es seis ipos, máquina indi idual, máquinas pa alelas, alle de lujo egula o
lowshop, alle de abajos o jobshop, alle abie o o openshop e híb idos. No obs an e, exis en más
en o nos, como el Dis ibu ed Flowshop que se p esen a en es e documen o.
•
Res icciones (
β
): Aquí se de inen las ca ac e ís icas de los abajos, son es icciones que se deben
cumpli pa a que el p og ama sea admisible. Algunas de las es icciones p incipales son las siguien es
(Pe ez-Gonzalez e al., 2022):
◦
In e upción o p eemp ion: Los abajos pueden in e umpi se una ez que han empezado a
p ocesa se.
◦Fecha de llegada: Ins an e de iempo en el que el abajo es á disponible.
◦
Fecha de en ega: Únicamen e cuando es obliga o ia (deadline). Es el ins an e de iempo lími e
en el que un abajo debe se en egado.
◦
Tiempos de se up: Es el iempo de p epa ación de la máquina pa a p ocesa el abajo co espon-
dien e.
◦Lo es: Se puede p ocesa a la ez una can idad de e minada de abajos en una única máquina.
2.3 Ca ac e ización del p oblema 5
◦
P ecedencia: Un abajo no puede empeza a p ocesa se has a que no acaben los abajos que lo
p eceden.
Como es icciones de los en o nos ipo alle podemos encon a (Pe ez-Gonzalez e al., 2022):
◦Pe mu ación: Misma secuencia pa a odas las máquinas.
◦
Tiempos ociosos no pe mi idos o no-idle: Una ez la máquina empieza a p ocesa el p ime
abajo de su p og ama, no puede pa a .
◦
Los abajos no pueden espe a en e máquinas: Una ez comienza a p ocesa se el abajo en la
p ime a máquina, las acciones ealizadas sob e es e no pueden de ene se has a que haya pasado
po odas las máquinas, no-wai .
◦
Almacén de una máquina o bu e : Es el espacio donde espe an los abajos pa a se p ocesados
en la siguien e máquina, se limi a la can idad de abajos en dicha zona de espe a.
Cuando las es icciones no es án p esen es, es necesa io ene en cuen a las siguien es suposiciones
gene ales (Pe ez-Gonzalez e al., 2022):
◦Los abajos se encuen an disponibles al p incipio del ho izon e de p og amación.
◦Los abajos no se pueden in e umpi .
◦Las máquinas es án siemp e disponibles.
◦Cada máquina puede hace un abajo, y un abajo puede se ealizado solo en una máquina.
◦El bu e en e máquinas se supone in ini o.
◦El iempo de anspo e es desp eciable.
•
Obje i os (
γ
): En es e e ce y úl imo campo se escoge un c i e io de op imización, la unción obje i o
(FO) del p oblema. A con inuación, se p esen an algunos de los obje i os que se pueden elegi (Pe ez-
Gonzalez e al., 2022).
◦
Tiempo de e minación del abajo jocomple ion ime (
Cj
): Es el ins an e en el que el abajo
acaba, no iene elación con la echa de en ega. Hay dos FO posibles, la p ime a es el makespan
(
Cmax
), es el mayo iempo de e minación de los abajos; la segunda, el o al comple ion ime
(∑Cj), pa a el que se suma el iempo de inalización de cada abajo.
◦
Ta danza del abajo j o a diness (
Tj
): Si el abajo e mina an es de su echa de en ega no pasa
nada, solo mide los abajos que e minan después del due da e. Al igual que en el caso an e io
hay dos ipos de FO, maximum a diness (
Tmax
), es el abajo con mayo a danza; y o al a diness
(∑Tj), se ob iene sumando la a danza de odos los abajos.
◦
Re aso del abajo jola eness (
Lj
): Es e obje i o al igual que el an e io depende de la echa
de en ega, pe o en caso de que se p ocese el abajo an es de cumpli dicha echa, el esul ado,
oma ía un alo nega i o. Del mismo modo exis en dos FO posibles, maximum la eness (
Lmax
) y
o al la eness (∑Lj).
◦
Adelan o del abajo joea liness (
Ej
): Es el caso opues o al a diness, si el abajo e mina después
de su echa de en ega, no pasa nada. Puede se maximum ea liness (
Emax
) o o al ea liness (
∑Ej
).
◦
Tiempo de lujo del abajo jo low ime (
Fj
): Es el iempo que el abajo es á en el en o no
mien as se p ocesa o espe a pa a se p ocesado. No iene elación con la echa de en ega, igual
que el comple ion ime. La FO puede se maximum low ime (Fmax) o o al low ime (∑Fj).
◦
Núme o de abajos a de (
Uj
): Si un abajo llega a de oma á el alo 1 y en caso con a io
ce o, ob eniendo así el núme o de abajos a de (∑Uj).
Como esumen, de iniendo cada uno de los es campos explicados, se puede ca ac e iza cualquie ipo de
p oblema, es e se á el obje i o del siguien e subapa ado.
2.3 Ca ac e ización del p oblema
En p ime luga , aplicando la no ación p esen ada en la sección 2.2, el p oblema a esol e en es e documen o
es el siguien e, DF|p mu|
∑Tj
. A con inuación, se de alla la opción seleccionada en cada uno de los es
campos.
6Capí ulo 2. Desc ipción del p oblema
•
En o no: Se ha seleccionado un Dis ibu ed Flowshop (
α
=DF), a ian e del p oblema de lowshop,
una pa icula idad de es e es que la u a de p oceso es la misma pa a odos los abajos, que empiezan
a p ocesa se en la máquina 1 y acaban en la máquina m, sin al e a el o den. En el lowshop odos los
p ocesos de ab icación ocu en en una única áb ica, algo cada ez menos común en la economía
global de hoy en día, po ello su ge el modelo de Dis ibu ed Flowshop, que consis e en un núme o F
de áb icas idén icas y cada una con mmáquinas disponibles. Así, en el p oceso de p og amación se á
cla e la asignación de los dis in os abajos a cada áb ica y la secuenciación de dichos abajos den o
de cada una de es as (Nade i & Ruiz, 2010). Además, algunas de las suposiciones necesa ias son las
siguien es, el núme o de áb icas idén icas debe se supe io a uno y deben p ocesa los n abajos
exis en es, odas las áb icas disponen del mismo conjun o de mmáquinas, odas las máquinas y abajos
es án disponibles en el ins an e empo al ce o, y po úl imo, cada máquina puede p ocesa un único
abajo a la ez y cada abajo se puede p ocesa en una máquina a la ez y el iempo de p oceso de un
abajo en una máquina especí ica es el mismo en cada una de las áb icas. En la Figu a 2.4, median e
un diag ama de Gan , se puede obse a un ejemplo de p og ama pa a un Dis ibu ed Flowshop, en el
que se conside a que hay dos áb icas con dos máquinas en cada una de ellas (m=2) y cinco abajos
(n=5) que deben se p og amados.
Figu a 2.4 Ejemplo de Dis ibu ed Flowshop [Fuen e: Kha e y Ag awal, 2021].
•
Res icciones: La única es icción p esen e en es e campo es la de pe mu ación (
β
=p mu), como se
ió en la sección 2.2, implica que, den o de cada una de las áb icas, la secuencia es idén ica pa a
odas las máquinas. De ese modo se educe el núme o de posibles p og amas semiac i os den o de
cada áb ica, pasando de (n!)man! p og amas.
•
Obje i o: Se ha p opues o minimiza el o al a diness (
∑Tj
), po lo cual, odos aquellos abajos
cuyo ins an e empo al de salida en la úl ima máquina sea supe io a la echa de en ega, epe cu i án
nega i amen e a la unción obje i o, aumen ando el alo o al. A modo de ejemplo se puede ap ecia
en la Figu a 2.4 la echa de en ega de cada uno de los abajos (
dj
) y el alo del a diness (
Tj
) de cada
uno, a excepción del abajo 3 ya que su due da e es supe io a su iempo de e minación. El esul ado
del obje i o consis i ía en suma cada uno de los iempos de a danza, los cuales son
T1
=16,
T2
=17,
T3=0, T4=5 y T5=9, siendo el alo de la FO de 47 unidades.
3 Mé odos de esolución
P
a a esol e el p oblema p esen ado en la sección 2.3, es necesa io ene en cuen a los aspec os que se
exponen a con inuación:
•
La p ime a pa e del p oceso de p og amación de un Dis ibu ed Flowshop consis e en la asignación
de abajos a las di e en es áb icas. Se ha escogido como egla de asignación únicamen e la egla ECT
(ea lies comple ion ime), que consis e en asigna cada abajo a la áb ica en la que end ía un meno
iempo de e minación. La decisión se debe a que Nade i y Ruiz (2010) demos a on que la egla ECT
da un mejo esul ado con un cos e compu acional muy pequeño, de ahí la elección de dicha egla.
•
La segunda pa e se basa en secuencia los abajos en cada una de las áb icas. Pa a ello se aplica án
di e sos mé odos p opues os po Kha e y Ag awal (2021), en su es udio a an de minimiza la
a danza o al pa a el p oblema de DPFS, con la es icción de pe mu ación, quedando ca ac e izado el
p oblema como el que se ha plan eado en es e es udio: DF|p mu|
∑Tj
. Así su ge el in e és de p oba
los mismos mé odos, conc e amen e, es eglas de despacho, dos heu ís icas y dos me aheu ís icas,
que se desa olla án en los siguien es subapa ados.
El p oblema es conocido po se NP-ha d, po lo que se p oponen mé odos ap oximados de esolución, al
no pode ga an iza la op imalidad.
3.1 Reglas de despacho
Las eglas de despacho o dispa ching ules son mé odos clásicos y po an o no pueden a ibui se a un único
au o . Es as consis en en lle a a cabo un cálculo simple pa a luego secuencia las a eas ( abajos en es e
caso) con un o den de p io idad (F aminan e al., 2014). Las es eglas de despacho empleadas son: ea lies
due da e (EDD), smalles o e all slack ime (OSL) y smalles slack ime on he las machine (LSL).
3.1.1 EDD
Es a egla iene en cuen a únicamen e la echa de en ega (
dj
) de los abajos, que son o denados de meno a
mayo alo . Gene ando así una secuencia de n abajos del ipo
π
=
π1
,
π2
,
π3
,...,
πn
, con
dπ(j)≤dπ(j+1)
pa a
j= 1, 2,..., n−1. En caso de empa e se escoge el abajo con meno índice.
3.1.2 OSL
Consis e en clasi ica los abajos en o den no dec ecien e del o e all slack ime, es deci , pa a cada abajo,
la di e encia de iempo en e la echa de en ega (
dj
) y la suma de los iempos de p oceso de dicho abajo
en odas las máquinas. El cálculo es el siguien e:
dπ(j)−∑m
i=1pi,π(j)≤dπ(j+1)−∑m
i=1pi,π(j+1)
. Igual que en el
EDD, el desempa e se ealiza escogiendo el abajo con el índice más pequeño.
3.1.3 LSL
La úl ima egla de despacho es smalles slack ime on he las machine, pa ecida a la egla OSL pe o en es e
caso no se iene en cuen a el slack ime gene al sino el de la úl ima máquina (m). De esa o ma, el cálculo
que se aplica se ía: dπ(j)−pm,π(j)≤dπ(j+1)−pm,π(j+1). Mismo desempa e que las eglas EDD y OSL.
7
8Capí ulo 3. Mé odos de esolución
3.2 Heu ís icas
Las heu ís icas, al igual que las me aheu ís icas (sección 3.3), son algo i mos de esolución ap oximados. La
necesidad de aplica es os mé odos adica en la complejidad compu acional inhe en e a los mé odos exac os,
donde la mayo ía de los modelos de p og amación equie en un iempo de compu ación excesi amen e
ele ado (F aminan e al., 2014).
Como ca ac e ís ica gene al, las heu ís icas son especí icamen e diseñadas pa a un modelo en pa icula ,
po lo que dependen en g an medida del p oblema (F aminan e al., 2014). Se a an de p ocedimien os
sencillos, basados en el sen ido común y en el conocimien o del p oblema, que o ecen buenas soluciones
de o ma ápida. Las heu ís icas empleadas en es a sección son dos, la p ime a se llama NEHD
edd
, la cual
es una ex ensión de la heu ís ica NEH
edd
(Kim, 1993) conside ando la exis encia de a ias áb icas, es a
heu ís ica es una de las más conocidas y ci adas pa a los p oblemas de lowshop, siendo econocida po su
buen desempeño y e iciencia; la segunda se llama smalles slack ime on e e y machine (ESL).
3.2.1 NEHDedd
En es a heu ís ica, lo p ime o es clasi ica los abajos en o den no dec ecien e según las echas de en ega.
Luego, se selecciona cada abajo en el o den es ablecido y se asigna a la áb ica con el meno alo de
a diness, as habe comp obado odas las posiciones posibles en odas las áb icas. El pseudocódigo del
algo i mo se p esen a en la Figu a 3.1.
Figu a 3.1 Pseudocódigo del algo i mo NEHDedd [Fuen e: Kha e y Ag awal, 2021].
3.2.2 ESL
Es a segunda heu ís ica se inspi a en la egla de despacho LSL, en es e caso, en luga de ene en cuen a
únicamen e el slack ime de la úl ima máquina, se con emplan odas las máquinas. De es a o ma, pa a
cada máquina se disponen los abajos en o den no dec ecien e según el slack ime, ob eniendo en o al m
secuencias. La secuencia escogida se á la que o ezca el meno alo de la unción obje i o, es deci , el
mínimo o al a diness. En la Figu a 3.2 se obse a el pseudocódigo pa a es a heu ís ica.
3.3 Me aheu ís icas 9
Figu a 3.2 Pseudocódigo del algo i mo ESL [Fuen e: Kha e y Ag awal, 2021].
3.3 Me aheu ís icas
Lo p ime o es comen a las ca ac e ís icas p incipales de las me aheu ís icas, pa a luego de alla aquellas
que se han empleado en es e documen o.
Las me aheu ís icas se de inen como algo i mos gene ales que pueden aplica se a di e sos p oblemas
median e pequeñas modi icaciones pa a adap a los. Suelen se más obus as y lexibles que las p opias heu ís-
icas y capaces de encon a soluciones mucho más e inadas. Sin emba go, conlle an un cos e compu acional
supe io (F aminan e al., 2014).
En las secciones 3.3.1 y 3.3.2 se de alla cada uno de los algo i mos, p ime o el Hyb id Disc e e Ha is
Hawks Op imisa ion (HDHHO) y en segundo luga el I e a ed G eedy (IG).
3.3.1 Hyb id Disc e e Ha is Hawks Op imisa ion
El algo i mo HDHHO (Kha e & Ag awal, 2021) es una e sión mejo ada del HHO (Heida i e al., 2019), que
consis e en una me aheu ís ica basada en la población e inspi ada en la na u aleza según el compo amien o
de caza de las águilas de Ha is. El pa ón de caza de las águilas se di ide en es ases: explo ación, ansición
de explo ación a explo ación y explo ación.
Fase de explo ación
Se a a de de ec a la posición de la p esa (mejo solución), las águilas (soluciones candida as) espe an y
obse an según dos es a egias. En la p ime a, cada águila decide su posición en unción de la ubicación
de la p esa y de o as águilas; en la segunda, se ubican en posiciones alea o ias. La o mulación de dichas
es a egias es la siguien e:
X( +1) =
X and ( )− 1×|X and( )−2 2X( )|si q ≥0.5
(Xp ey( )−Xm( ))− 3×(LB + 4×(UB −LB)) si q <0.5
El ec o de posición de cada águila en la siguien e i e ación es
X( +1)
, el ec o de posición
X and ( )
se
escoge alea o iamen e en e las águilas de la población ac ual,
X( )
es el ec o de posición de la i e ación
ac ual, el ec o de posición
Xp ey
ep esen a la mejo solución ob enida has a el momen o y
Xm( )
es la
posición media en e odas las águilas, se ob iene aplicando el siguien e cálculo:
Xm( ) = ∑N
i=1Xi( )
N
16 Capí ulo 3. Mé odos de esolución
Algo i mo
Finalmen e, aplicando cada uno de los pasos an e io es, se elabo a el pseudocódigo pa a el algo i mo I e a ed
G eedy, como se obse a en la Figu a 3.9.
Figu a 3.9 Pseudocódigo del algo i mo I e a ed G eedy [Fuen e: Kha e y Ag awal, 2021].
4 Resul ados y análisis
E
l obje i o de es a sección es esol e el p oblema plan eado con cada uno de los algo i mos p opues os,
pa a es ablece una compa a i a en e dichos algo i mos y así de e mina cual se adap a mejo al
p oblema.
Lo p ime o de odo se á de alla las di e sas ins ancias usadas en el p oblema, sección 4.1. Así, pos e io -
men e en la sección 4.2, se ealiza la ob ención y compa a i a de esul ados.
4.1 Ins ancias
Es a sección se di ide en dos subsecciones. En la p ime a, se de inen las ins ancias empleadas pa a el
calib ado de las me aheu ís icas HDHHO e I e a ed G eedy; mien as que en la segunda, se especi ican las
ins ancias seleccionadas pa a e alua los algo i mos de ini i os.
4.1.1 Ins ancias de calib ado
Se u ilizan únicamen e pa a las me aheu ís icas, dado que es as cuen an con una se ie de pa áme os a iables
que hay que ija . Pa a ello, Kha e y Ag awal (2021) p oponen un conjun o de 54 ins ancias únicas con las
que ealiza el calib ado. Las ca ac e ís icas son las siguien es:
•Núme o de abajos: n=20, 50, 100
•Núme o de máquina: m=5, 10, 20
•Núme o de áb icas: =2, 3, 4, 5, 6, 7
•
El iempo de p oceso de cada abajo en cada máquina se gene a alea o iamen e, alo en e 1 y 99,
ambos incluidos.
•
Las echas de en ega se calculan con el mé odo de Hasija y Rajend an (2004). P ime o se calcula el
iempo de p oceso o al de cada abajo en odas las máquinas,
Pj=∑m
i=1pi j
con
j=1,2,...,n
, y luego
se ob iene el alo de la echa de en ega con la ecuación
dj=Pj×(1+ and ×(1/ )×α)
, siendo el
alo de and un núme o alea o io en e 0 y 1, ambos incluidos, y
α=0.5
(Kha e & Ag awal, 2021).
4.1.2 Ins ancias pa a compa a los algo i mos
Una ez calib ados los pa áme os de las me aheu ís icas, se emplean nue as ins ancias pa a compa a odos
los algo i mos. Se a a usa el banco de p uebas de Nade i y Ruiz (2010), el cual se compone de dos conjun os
de ins ancias.
El p ime conjun o es de ins ancias pequeñas, donde el núme o de abajos n
∈
4, 6, 8, 10, 12, 14, 16, de
máquinas m
∈
2, 3, 4, 5 y de áb icas
∈
2, 3, 4, además pa a cada combinación se gene an cinco ins ancias
di e en es, así, hay un o al de 420 ins ancias.
El segundo conjun o es á o mado po ins ancias g andes, basado en las ins ancias de Tailla d (1993),
donde, n
×
m
∈
20
×
5, 20
×
10, 20
×
20, 50
×
5, 50
×
10, 50
×
20, 100
×
5, 100
×
10, 100
×
20, 200
×
10, 200
×
20, 500
×
20 son las combinaciones posibles, con diez ins ancias di e en es pa a cada opción y
pa a cada ∈2, 3, 4, 5, 6, 7, o mando un o al de 720 ins ancias.
17
18 Capí ulo 4. Resul ados y análisis
4.2 Expe imen ación
En es e apa ado se de alla como se han ob enido los esul ados pa a cada uno de los mé odos p opues os, los
c i e ios empleados pa a la compa a i a y un análisis del desempeño de los algo i mos.
El indicado empleado pa a de e mina la elección de los pa áme os en el calib ado y ealiza la compa a i a
en e odos los algo i mos es el ARPD (A e age Rela i e Pe cen age De ia ion). El ARPD es la media de los
esul ados del RPD, que se ob iene con la siguien e ó mula:
RPD =Algsol −Bes sol
Bes sol
×100
Donde
Algsol
es el iempo de a danza o al pa a una con igu ación/algo i mo conc e o y
Bes sol
es el
meno iempo de a danza en la ins ancia. Po an o, mues a la a iación del o al a diness en e cada
con igu ación/algo i mo y la mejo solución, pa a cada ins ancia. El ARPD se calcula aplicando la siguien e
exp esión:
ARPD =∑q
i=1RPDi
q
4.2.1 Resul ados del calib ado
Como se ha comen ado en la sección 4.1.1, es e calib ado se ealiza únicamen e pa a las me aheu ís icas. Po
ello, las con igu aciones analizadas y los esul ados ob enidos pa a cada algo i mo se de allan a con inuación.
Hyb id Disc e e Ha is Hawks Op imisa ion
Pa a el HDHHO los pa áme os de en ada necesa ios son el amaño de la población y el núme o máximo de
i e aciones a ealiza . Pa a el p ime o, se p opone es ni eles posibles: 10, 20 y 30 águilas. De igual o ma,
el segundo pa áme o cuen a con la misma can idad de ni eles, pe o con los siguien es alo es: 50, 100 y 200
i e aciones como máximo.
Exis en 9 con igu aciones en o al, que son e aluadas en cada una de las 54 ins ancias, ob eniéndose un
alo RPD pa a cada con igu ación en cada ins ancia. La can idad de i e aciones máximas es el c i e io de
pa ada es ablecido. Po úl imo, se aplica el ARPD, cuya solución apa ece en la Tabla 4.1, además, se ma ca
en neg i a el mejo esul ado pa a cada pa áme o, es os son los elegidos pa a la compa ación inal.
Tabla 4.1 Valo es ARPD pa a pa áme os de en ada en HDHHO.
Valo es ARPD pa áme os de en ada HDHHO
10 1,4623
Tamaño de la población 20 1,5215
30 1,3170
50 1,5431
I e aciones máximas (N) 100 1,5427
200 1,2149
De o ma g á ica, en la Figu a 4.1, se mues a la espues a del ARPD pa a cada a iable. Aquellos
pa áme os con el alo más ce cano a ce o son los que p opo cionan un mejo desempeño, y po an o, los
ganado es en el p oceso de calib ado.
La con igu ación po la que se ha op ado pa a el HDHHO es: población de 30 águilas y 200 i e aciones
como máximo.
4.2 Expe imen ación 19
Figu a 4.1 Resul ado ARPD de cada pa áme o del HDHHO [Fuen e: Elabo ación p opia].
I e a ed G eedy
Los pa áme os a calib a y los alo es que se han conside ado son los siguien es:
•
Po cen aje de abajos a elimina , d
=
0.2, 0.3, 0.5. Cuan o más ele ado sea el po cen aje mayo se á la
di e si icación.
•
Tempe a u a de e e encia,
T0=
0.1, 0.4, 1, 10. Cuan o mayo sea el alo de la empe a u a, la
acep ación de peo es soluciones se á meno .
•Mé odo de inicialización, heu ís ica NEHDedd o ESL.
•Búsqueda local, RSLS o RPLS.
Es ableciendo odas las combinaciones posibles el núme o o al de con igu aciones es de 48 (
3×4×2×2
).
Se aplica el algo i mo pa a cada con igu ación en cada una de las 54 ins ancias. El c i e io de e minación
escogido es po iempo (segundos), siendo el cálculo
n×m×0.025
. Aplicando el indicado p opues o, se
ob ienen los esul ados de odos los pa áme os, como se mues a en la Tabla 4.2, en neg i a apa ecen los
mejo es esul ados de cada pa áme o, son los escogidos pa a la compa ación inal.
Tabla 4.2 Valo es ARPD pa a pa áme os de en ada en IG.
Valo es ARPD pa áme os de en ada IG
0.2 1,8676
%de abajos a elimina (d) 0.3 2,3578
0.5 3,3201
0.1 2,2624
Tempe a u a e e encia (T0) 0.4 2,2559
12,1867
10 3,3557
Mé odo de inicialización ESL 2,5499
NEHDedd 2,4804
Búsqueda local RSLS 2,4768
RPLS 2,5536
20 Capí ulo 4. Resul ados y análisis
Figu a 4.2 Resul ado ARPD de cada pa áme o del IG [Fuen e: Elabo ación p opia].
En la Figu a 4.2 se p esen an los mismos esul ados pe o g á icamen e, acili ando su comp ensión.
La con igu ación escogida pa a el I e a ed G eedy es: d
=
20
%
,
T0=
1, inicialización con heu ís ica
NEHDedd y búsqueda local con RSLS.
4.2.2 Resul ados de los algo i mos empleando ins ancias pequeñas
Una ez calib adas ambas me aheu ís icas se p ocede a e alua cada uno de los algo i mos plan eados usando
las ins ancias pequeñas in oducidas en la sección 4.1.2. Con el obje i o de es ablece una compa a i a
gene al y una alo ación del desempeño.
Las me aheu ís icas son los únicos algo i mos que equie en un c i e io de e minación. Pa a lle a a cabo
una compa a i a exhaus i a se ha decidido que el iempo de ejecución en cada ins ancia sea igual pa a ambos
mé odos. Se man iene el c i e io de e minación en el HDHHO, que consis e en ealiza i e aciones has a
llega al núme o de i e aciones máximas. De ese modo, el c i e io de e minación escogido pa a el I e a ed
G eedy en cada ins ancia es el iempo de ejecución empleado en el HDHHO pa a esa misma ins ancia.
A con inuación, se mues a en la Tabla 4.3 los esul ados ob enidos al aplica el ARPD pa a cada uno
de los algo i mos. Se puede obse a como el I e a ed G eedy es el que o ece el mejo desempeño con
di e encia, ma cado en neg i a, casi en la o alidad de las ins ancias es la mejo solución o coincide con es a.
Po o o lado, la des iación del HDHHO espec o a la mejo solución se encuen a ce cana al 4
%
de media.
Además, la mejo a de las me aheu ís icas espec o de las heu ís icas y de las eglas de despacho es cla a,
como se mues a en la Tabla 4.3 y se ap ecia con mayo acilidad en la Figu a 4.3.
Es in e esan e analiza más a ondo el compo amien o de los algo i mos una ez aplicados al p oblema. Los
pa áme os que de inen dicho p oblema son las áb icas, los abajos y las máquinas, como ya se explicó en
la sección 2. Po ello, se analiza como a ec a sob e los algo i mos la a iación de cada uno de los pa áme os.
Se e alúan únicamen e las me aheu ís icas y las heu ís icas, al se los que p esen aban mejo es esul ados en
la compa a i a gene al.
En p ime luga , como se mues a en la Tabla 4.4, se ha calculado el ARPD de cada algo i mo pa a
2, 3 y 4 áb icas. Con esos esul ados, ep esen ados en la Figu a 4.4, se deduce que la me aheu ís ica
HDHHO empeo a cuan as más áb icas en an en juego, mien as que el IG p esen a un g an endimien o sin
impo a la can idad de áb icas, iene los mejo es esul ados, ma cados en neg i a. La heu ís ica ESL iene
un compo amien o p ác icamen e cons an e, a di e encia de la NEHDedd la cual es muy i egula .
4.2 Expe imen ación 21
Tabla 4.3 Valo es ARPD po algo i mos pa a ins ancias pequeñas.
Valo es ARPD
EDD 30,1573
LSL 15,3584
OSL 80,9338
Algo i mos ESL 12,0856
NEHDedd 20,5280
IG 0,0072
HDHHO 4,1458
Figu a 4.3 Resul ado ARPD de cada algo i mo pa a ins ancias pequeñas [Fuen e: Elabo ación p opia].
Tabla 4.4 Valo es ARPD po áb icas pa a las heu ís icas y me aheu ís icas en ins ancias pequeñas.
ARPD Fáb icas ARPD
2 3 4 Medio
ESL 13,3896 11,3939 11,4733 12,0856
Algo i mos NEHDedd 9,5986 33,4609 18,5243 20,5280
IG 0,0215 0 0 0,0072
HDHHO 3,2494 4,5240 4,6640 4,1458
Luego, se ha lle ado a cabo la e aluación según el núme o de abajos, siendo las opciones las siguien es:
n={4,6,8,10,12,14,16}
, Tabla 4.5. Al igual que an es, el IG p esen a los mejo es esul ados pa a odas
las opciones posibles, sal o pa a la con igu ación con cua o abajos y el HDHHO uel e a empeo a ,
en es e caso, con o me aumen a el núme o de abajos, Figu a 4.5. La heu ís ica NEHD
edd
sí mues a un
compo amien o de mejo a con el aumen o de los abajos, y la ESL unciona peo con es e aumen o. En
neg i a se mues an los mejo es esul ados.
22 Capí ulo 4. Resul ados y análisis
Figu a 4.4 Resul ado ARPD po áb icas pa a ins ancias pequeñas [Fuen e: Elabo ación p opia].
Tabla 4.5 Valo es ARPD po abajos pa a las heu ís icas y me aheu ís icas en ins ancias pequeñas.
ARPD T abajos ARPD
4 6 8 10 12 14 16 Medio
ESL 3,377 6,205 13,827 14,931 13,535 15,490 17,234 12,086
Algo i mos NEHDedd 51,036 19,546 16,239 17,851 13,384 13,410 12,230 20,528
IG 0,050 0 0 0 0 0 0 0,007
HDHHO 00,829 1,932 4,382 6,381 7,505 7,992 4,146
Figu a 4.5 Resul ado ARPD po abajos pa a ins ancias pequeñas [Fuen e: Elabo ación p opia].
Po úl imo, se calcula el ARPD según el núme o de máquinas,
m={2,3,4,5}
. Una ez más, los esul ados
pa a la me aheu ís ica HDHHO se alejan de la mejo solución en elación al inc emen o de máquinas. El
I e a ed G eedy con inúa o eciendo el mejo endimien o pa a odas las con igu aciones, esul ados en
neg i a. Con es e pa áme o la heu ís ica ESL se compo a mejo que la NEHD
edd
en odas las opciones. Es e
análisis se puede ex ae de la Tabla 4.6, y de la Figu a 4.6.
Un aspec o cla e a la ho a de compa a algo i mos es ene en cuen a el iempo de cómpu o. Po ello, en la
4.2 Expe imen ación 23
Tabla 4.6 Valo es ARPD po máquinas pa a las heu ís icas y me aheu ís icas en ins ancias pequeñas.
ARPD Máquinas ARPD
2 3 4 5 Medio
ESL 8,7269 13,5922 12,9154 13,1079 12,0856
Algo i mos NEHDedd 10,4172 15,8606 38,4292 17,4049 20,5280
IG 0,0286 0 0 0 0,0072
HDHHO 2,2121 3,8160 5,1526 5,4024 4,1458
Figu a 4.6 Resul ado ARPD po máquinas pa a ins ancias pequeñas [Fuen e: Elabo ación p opia].
Tabla 4.7, se ha calculado el iempo medio empleado pa a odas las ins ancias po cada uno de los mé odos.
Se puede obse a como los iempos pa a las eglas de despacho y las heu ís icas son desp eciables, mien as
que pa a las me aheu ís icas equie en de media poco más de un minu o. Esa di e encia de iempo en e unos
mé odos y o os puede jus i ica se al log a mejo es esul ados de la unción obje i o.
Tabla 4.7 Tiempo medio de compu ación po algo i mo pa a ins ancias pequeñas.
Tiempo medio po ins ancia (s)
EDD 0,001
LSL 0,001
OSL 0,001
Algo i mos ESL 0,004
NEHDedd 0,003
IG 73,353
HDHHO 73,349
Adicionalmen e, en la Figu a 4.7 y en la Figu a 4.8, se puede obse a un ejemplo de como e oluciona el
alo de la FO en cada una de las me aheu ís icas espec o del núme o de i e aciones.
4.2.3 Resul ados de los algo i mos empleando ins ancias g andes
Inicialmen e, como en el apa ado an e io , se ealiza una compa a i a gene al en e los algo i mos, pe o
en es e caso usando las ins ancias g andes del banco de p uebas. Los c i e ios de e minación pa a las
24 Capí ulo 4. Resul ados y análisis
Figu a 4.7 E olución de la FO en el IG pa a ins ancias pequeñas [Fuen e: Elabo ación p opia].
Figu a 4.8 E olución de la FO en el HDHHO pa a ins ancias pequeñas [Fuen e: Elabo ación p opia].
me aheu ís icas son los mismos que los de la sección 4.2.2.
En la Tabla 4.8 se e leja la media del RPD pa a cada uno de los mé odos empleados en es e abajo. Los
esul ados ob enidos se p oyec an ambién en la Figu a 4.9. Al igual que pa a las ins ancias pequeñas, el
I e a ed G eedy, o ece un desempeño sob esalien e, llegando siemp e a la mejo solución o coincidiendo
con es a, ma cado en neg i a. En cuan o al HDHHO, se p oduce un inc emen o del ARPD en elación a las
ins ancias pequeñas, supe ando el 20
%
de des iación espec o a la mejo solución. Las heu ís icas y eglas
de despacho ambién se en pe judicadas, siendo la ESL la que empeo a de o ma más no able.
4.2 Expe imen ación 25
Tabla 4.8 Valo es ARPD po algo i mos pa a ins ancias g andes.
Valo es ARPD
EDD 67,8893
LSL 66,9362
OSL 109,4472
Algo i mos ESL 56,0614
NEHDedd 26,9495
IG 0
HDHHO 24,2003
Figu a 4.9 Resul ado ARPD de cada algo i mo pa a ins ancias g andes [Fuen e: Elabo ación p opia].
A con inuación, se epi e el análisis po pa áme os del p oblema, empezando po el núme o de áb icas,
donde
={2,3,4,5,6,7}
, Tabla 4.9. El ARPD pa a el HDHHO inc emen a con el aumen o de áb icas y es
le emen e in e io al NEHDedd, que p esen a un uncionamien o muy supe io al ESL, como se ap ecia en
la Figu a 4.10.
Tabla 4.9 Valo es ARPD po áb icas pa a las heu ís icas y me aheu ís icas en ins ancias g andes.
ARPD Fáb icas ARPD
2 3 4 5 6 7 Medio
ESL 63,1011 59,5642 56,8367 57,9869 49,4813 49,3981 56,0614
Algo i mos NEHDedd 20,4043 23,3693 28,1868 32,2264 26,8433 30,6669 26,9495
IG 0000000
HDHHO 19,2898 22,0515 24,9495 28,1252 23,5781 27,2079 24,2003
32 Capí ulo 4. Resul ados y análisis
Figu a 4.18
Compa a i a ARPD po áb icas pa a el NEHD
edd
en ins ancias pequeñas [Fuen e: Elabo ación
p opia].
Figu a 4.19
Compa a i a ARPD po abajos pa a el NEHD
edd
en ins ancias pequeñas [Fuen e: Elabo ación
p opia].
Tabla 4.17
Compa a i a ARPD po áb icas pa a el IG en ins ancias pequeñas, según pa áme os Tabla 4.13.
Compa a i a ARPD Fáb icas ARPD
2 3 4 Medio
Algo i mos IG Kha e y Ag awal 0,055 0,091 0,100 0,082
IG del es udio 0,022 0 0 0,007
4.3 Análisis y compa ación de esul ados 33
Tabla 4.18
Compa a i a ARPD po abajos pa a el IG en ins ancias pequeñas, según pa áme os Tabla 4.13.
Compa a i a ARPD T abajos ARPD
4 6 8 10 12 14 16 Medio
Algo i mos IG Kha e y Ag awal 0 0 0,007 0,019 0,060 0,144 0,344 0,082
IG del es udio 0,050 0 0 0 0 0 0 0,007
Figu a 4.20
Compa a i a ARPD po áb icas pa a el HDHHO en ins ancias pequeñas, según pa áme os
Tabla 4.13 [Fuen e: Elabo ación p opia].
Figu a 4.21
Compa a i a ARPD po abajos pa a el HDHHO en ins ancias pequeñas, según pa áme os
Tabla 4.13 [Fuen e: Elabo ación p opia].
34 Capí ulo 4. Resul ados y análisis
4.3.3 Ins ancias g andes
Al emplea las ins ancias g andes Kha e y Ag awal (2021) in oducen o as sie e me aheu ís icas con as adas,
pa a así e alua la e ec i idad del IG y del HDHHO. En es e caso se compa an únicamen e las me aheu ís icas,
en la Tabla 4.19 apa ece el esul ado del ARPD pa a cada algo i mo en cada es udio, as e alua las 720
ins ancias. Pa a Kha e y Ag awal aumen a conside ablemen e el ARPD del IG espec o a las ins ancias
pequeñas, debido a la exis encia de nue as me aheu ís icas, mien as que el IG de es e es udio man iene el
desempeño mos ado. Po o o lado, el HDHHO su e un empeo amien o menos acen uado con las ins ancias
g andes pa a Kha e y Ag awal, en el caso de es e abajo el compo amien o del HDHHO se e muy a ec ado
al emplea ins ancias g andes, como se explicó en el subapa ado 4.2.3.
Tabla 4.19
Compa a i a ARPD de cada me aheu ís ica con Kha e y Ag awal (2021) en ins ancias g andes,
según pa áme os Tabla 4.13.
Compa a i a ARPD
Resul ado del es udio Kha e y Ag awal
Algo i mos IG 01,76
HDHHO 24,20 5,27
5 Conclusiones
F
inalmen e en es e apa ado se p esen an las conclusiones del es udio ealizado. El p oblema que se ha
analizado ha sido el Dis ibu ed Flowshop con es icción de pe mu ación y con el obje i o de minimiza
el iempo o al de a danza de los abajos. Pa a ello se han aplicado di e sas heu ís icas y me aheu ís icas
plan eadas po Kha e y Ag awal (2021), desa olladas en la sección 3. Pos e io men e, en la sección 4, se ha
ealizado la expe imen ación, llegando a las siguien es conclusiones:
•
En e las dos me aheu ís icas es udiadas, I e a ed G eedy y HDHHO, ha sido el IG, en odas las
si uaciones analizadas, la que ha mos ado los mejo es esul ados y un mejo endimien o pa a el
p oblema de inido, an o en es e es udio como en el de Kha e y Ag awal (2021).
•
Una posible causa de la peo adap ación del algo i mo HDHHO al p oblema, espec o al IG, puede
se que es e se p opuso o iginalmen e po Heida i e al. (2019) pa a esol e p oblemas en un en o no
Flowshop. Cabe des aca que en el es udio de Kha e y Ag awal (2021) es e mé odo log a un mejo
esul ado espec o al de es e abajo, uno de los mo i os p incipales es la di e encia en e el pa áme o
de i e aciones elegido.
•
El IG, en las ins ancias g andes, ealiza un núme o educido de i e aciones espec o a las ins ancias
pequeñas. La causa p incipal es el iempo que emplea en ealiza la búsqueda local cuando ope a con
un g an núme o de abajos, una posible solución se ía limi a la can idad de ecinos que se analizan
en dicha búsqueda local.
•
En e los pa áme os candida os, se han seleccionado aquellos que pueden o ece un mayo desempeño
en las me aheu ís icas.
•La egla de despacho LSL p esen a mejo es esul ados que la EDD y la OSL.
•
En cuan o a las heu ís icas, el algo i mo ESL unciona mejo en ins ancias pequeñas y el NEHDedd en
ins ancias g andes.
35
Bibliog a ía
Fe nandez-Viagas, V., & F aminan, J. (2015). A bounded-sea ch i e a ed g eedy algo i hm o he dis ibu ed
pe mu a ion lowshop scheduling p oblem. In e na ional Jou nal o P oduc ion Resea ch,53,
1111-1123. h ps://doi.o g/10.1080/00207543.2014.948578
F aminan, J. (2023). schep k (SCHEduling Py hon ToolKi ) [Ve sion 0.1.3]. h ps://gi hub.com/ aminan/
schep k
F aminan, J., Leis en, R., & Ga cía, R. (2014). Manu ac u ing scheduling sys ems: An in eg a ed iew on
models, me hods and ools (Vol. 9781447162). h ps://doi.o g/10.1007/978-1-4471-6272-8
G aham, R., Lawle , E., Lens a, J., & Kan, A. (1979). Op imiza ion and app oxima ion in de e minis ic
sequencing and scheduling: A su ey (Vol. 5). h ps://doi.o g/10.1016/S0167-5060(08)70356-X
Hasija, S., & Rajend an, C. (2004). Scheduling in lowshops o minimize o al a diness o jobs. In e na ional
Jou nal o P oduc ion Resea ch,42, 2289
-
2301. h ps://doi.o g/10.1080/00207540310001657595
Heida i, A., Mi jalili, S., Fa is, H., Alja ah, I., Ma a ja, M., & Chen, H. (2019). Ha is hawks op imiza ion:
Algo i hm and applica ions. Fu u e Gene a ion Compu e Sys ems,97, 849
-
872. h ps://doi.o g/10.
1016/j. u u e.2019.02.028
Kha e, A., & Ag awal, S. (2021). E ec i e heu is ics and me aheu is ics o minimise o al a diness o
he dis ibu ed pe mu a ion lowshop scheduling p oblem. In e na ional Jou nal o P oduc ion
Resea ch,59, 7266-7282. h ps://doi.o g/10.1080/00207543.2020.1837982
Kim, Y.
-
D. (1993). Heu is ics o lowshop scheduling p oblems minimizing mean a diness. Jou nal o he
Ope a ional Resea ch Socie y,44, 19-28. h ps://doi.o g/10.1057/jo s.1993.3
Nade i, B., & Ruiz, R. (2010). The dis ibu ed pe mu a ion lowshop scheduling p oblem. Compu e s and
Ope a ions Resea ch,37. h ps://doi.o g/10.1016/j.co .2009.06.019
Olhage , J., & Feldmann, A. (2018). Dis ibu ion o manu ac u ing s a egy decision-making in mul i-plan
ne wo ks. In e na ional Jou nal o P oduc ion Resea ch,56, 692
-
708. h ps://doi.o g/10.1080/
00207543.2017.1401749
Oliphan , T. (2007). Py hon o scien i ic compu ing. Compu ing in Science and Enginee ing,9, 10
-
20.
h ps://doi.o g/10.1109/MCSE.2007.58
Pe ez-Gonzalez, P., F aminan, J., & Na a o-Ga cia, B. (2022). P og amación de Ope aciones. Escuela
Técnica Supe io de Ingenie ía, Uni e sidad de Se illa, Iden i icado : 1043.
Ruiz, R., & S ü zle, T. (2007). A simple and e ec i e i e a ed g eedy algo i hm o he pe mu a ion lowshop
scheduling p oblem. Eu opean Jou nal o Ope a ional Resea ch,177, 2033
-
2049. h ps://doi.o g/
10.1016/j.ejo .2005.12.009
Tailla d, E. (1993). Benchma ks o basic scheduling p oblems. Eu opean Jou nal o Ope a ional Resea ch,
64, 278-285. h ps://doi.o g/10.1016/0377-2217(93)90182-M
Tasge i en, M., Liang, Y.
-
C., Se kli, M., & Gencyilmaz, G. (2007). A pa icle swa m op imiza ion algo i hm
o makespan and o al low ime minimiza ion in he pe mu a ion lowshop sequencing p oblem.
Eu opean Jou nal o Ope a ional Resea ch,177, 1930
-
1947. h ps://doi.o g/10.1016/j.ejo .2005.12.
024
Yang, X.
-
S. (2010, julio). Na u e-Inspi ed Me aheu is ic Algo i hms. Luni e P ess. h ps://www. esea chga e.
ne /publica ion/235979455_Na u e-Inspi ed_Me aheu is ic_Algo i hms
37
Anexo: Código de p og amación en Py hon
""""""""""""""""""""""""
##### heu is icas_ 8 #####
""""""""""""""""""""""""
impo copy, andom, ma h
om schep k.u il impo so ed_index_asc, ead_ ag
om schep k.schep k impo FlowShop
om ime impo ime
om sympy impo *
om sympy.abc impo x
impo ma plo lib.pyplo as pl
impo numpy as np
""" FUNCIÓN OBJETIVO """
de objec i e_ unc ion(ins ancia,secuencia,a chi o):
o al_ a diness = 0
o in ange( ead_ ag(a chi o, "FACTORIES")):
i secuencia[ ] != []:
o al_ a diness += ins ancia.SumTj(secuencia[ ])
e u n o al_ a diness
""""""
""""""
### FUNCIÓN PARA ASIGNAR CADA TRABAJO EVALUADO A LA FÁBRICA EN LA QUE TENDRÍA
MENOR COMPLETION TIME (ECT) ###
### Lo uso en las unciones EDD, OSL, LSL y ESL. (Regla de asignacion ECT)
de FACTORY_LEAST_CT(ins ancia,sec,a chi o): #EN PRINCIPIO SEC_ACTUAL ELIMINAR
Y DEJAR SEC Y YA, NO LA TOCO NUNCA, SOLO LA RECORRO.
ac o ies= ead_ ag(a chi o, "FACTORIES")
sec_ ac o ies=[[] o in ange( ac o ies)] #Vec o pa a gua da la
secuencia escogida en cada áb ica.
sec_ac ual=copy.deepcopy(sec) #O den de los abajos que hay que asigna a
las áb icas.
39
40 Anexo: Código de p og amación en Py hon
o j in ange(ins ancia.jobs):
CT_aux=[] #Vec o auxilia pa a gua da el cálculo del CT que end ía
un mismo abajo en cada una de las áb icas.
o in ange( ac o ies):
sec_ ac o ies[ ].append(sec_ac ual[j]) #Asigno el abajo j a la á
b ica .
compl_ ime=max(ins ancia.Cj(sec_ ac o ies[ ])) #Calculo el CT de
dicho abajo en la áb ica asignada en la línea an e io .
CT_aux.append(compl_ ime)
sec_ ac o ies[ ].pop() #Elimino el abajo asignado inicialmen e a
la áb ica .
ac o y_CT_min=CT_aux.index(min(CT_aux)) #Gua do el núme o de la á
b ica en la que se ha ob enido el meno CT del abajo e aluado.
sec_ ac o ies[ ac o y_CT_min].append(sec_ac ual[j]) #Asigno el abajo
e aluado a la áb con el CT más pequeño pa a ese abajo.
e u n sec_ ac o ies
""""""
""""""""""""""""""""""""
##### REGLAS DE DESPACHO #####
""""""""""""""""""""""""
""" EDD """
de EDD (ins ancia,a chi o):
sec_edd=so ed_index_asc(ins ancia.dd) #O deno la secuencia según los due-
da es de meno a mayo .
#Aplico egla de asignación ECT.
sec=copy.deepcopy(FACTORY_LEAST_CT(ins ancia, sec_edd,a chi o))
e u n sec
""""""
""" OSL """
de OSL (ins ancia, a chi o):
suma_p =[0 o j in ange (ins ancia.jobs)] #Vec o pa a gua da el PT
o al de cada abajo (suma p de un mismo abajo en cada máquina).
osl=[0 o j in ange (ins ancia.jobs)] #Vec o pa a gua da el O e all
Slack Time de cada abajo.
o j in ange (ins ancia.jobs):
o i in ange (ins ancia.machines):
suma_p [j]=suma_p [j] + ins ancia.p [i][j] #P oceso pa a ob ene el
PT o al de cada abajo.
osl[j]=ins ancia.dd[j] - suma_p [j] #P oceso pa a ob ene el OSL de
cada abajo.
sec_osl=so ed_index_asc(osl) #O deno la secuencia según el OSL de meno a
mayo .
Anexo: Código de p og amación en Py hon 41
#Aplico egla de asignación ECT.
sec=copy.deepcopy(FACTORY_LEAST_CT(ins ancia, sec_osl, a chi o))
e u n sec
""""""
""" LSL """
de LSL (ins ancia, a chi o):
lsl=[0 o j in ange (ins ancia.jobs)] #Vec o pa a gua da el Las Slack
Time de cada abajo.
o j in ange(ins ancia.jobs):
lsl[j]=ins ancia.dd[j] - ins ancia.p [ins ancia.machines-1][j] #P oceso
pa a ob ene el LSL de cada abajo.
sec_lsl=so ed_index_asc(lsl) #O deno la secuencia según el LSL de meno a
mayo .
#Aplico egla de asignación ECT.
sec=copy.deepcopy(FACTORY_LEAST_CT(ins ancia, sec_lsl, a chi o))
e u n sec
""""""
""""""""""""""""""""""""
##### HEURÍSTICAS #####
""""""""""""""""""""""""
""" ESL """
de ESL (ins ancia, a chi o):
slack=[[0 o j in ange(ins ancia.jobs)] o j in ange(ins ancia.machines
)] #Vec o pa a gua da el Slack Time de cada abajo en cada máquina.
sec_esl=[0 o i in ange(ins ancia.machines)] #Vec o pa a gua da la
secuencia esul an e en cada máquina. (m secuencias)
o i in ange(ins ancia.machines):
o j in ange(ins ancia.jobs):
slack[i][j]=ins ancia.dd[j] - ins ancia.p [i][j] #P oceso de cálculo
del slack ime de cada abajo en cada máquina.
TT=[] #Vec o pa a gua da el TT ob enido pa a cada una de las m secuencias
a analiza .
o i in ange(ins ancia.machines):
sec_esl[i]=so ed_index_asc(slack[i]) #O deno la secuencia según el ESL
de meno a mayo . (en cada máquina)
sec=copy.deepcopy(FACTORY_LEAST_CT(ins ancia,sec_esl[i],a chi o)) #
Ob engo la secuencia de cada áb ica.
TT_aux=[] #Vec o auxilia pa a gua da el cálculo del TT en cada á
b ica.
o in ange( ead_ ag(a chi o, "FACTORIES")):
TT_aux.append(sum(ins ancia.Tj(sec[ ]))) #Añado en el ec o
auxilia el alo del TT en cada áb ica.
48 Anexo: Código de p og amación en Py hon
sec_aux[ ].pop(0)
b eak
e u n secuencia_desag egada
de c ea _ ec o _posicion_po _solucion(secuencia_desag egada):
posiciones_alea o ias = [ andom.uni o m(0, 1) o i in ange(len(secuencia_
desag egada))]
posiciones_alea o ias.so ()
e u n posiciones_alea o ias
de gene a _solucion_alea o ia(ins ancia, a chi o):
solucion_alea o ia = [j o j in ange(ins ancia.jobs)]
andom.shu le(solucion_alea o ia)
sol_alea o ia_asignada = copy.deepcopy(FACTORY_LEAST_CT(ins ancia, solucion
_alea o ia, a chi o))
e u n sol_alea o ia_asignada
""""""
""" FUNCIÓN EXPLORATION PHASE """
de explo a ion_phase(secuencias_ alo es_con inuos, i ness_ odas_soluciones,
indice_solucion_ac ual):
# De inición pa áme os
1= andom. andom()
2= andom. andom()
3= andom. andom()
4= andom. andom()
q= andom. andom()
UB=max( 1, 2, 3, 4, q)
LB=min( 1, 2, 3, 4, q)
X and= andom.choice(secuencias_ alo es_con inuos) #Vec o posición de una
solución (águila) escogida ale o iamen e
Xac ual=secuencias_ alo es_con inuos[indice_solucion_ac ual] #Vec o posici
ón de la solución (águila) de la i e ación ac ual
pos_Xp ey=secuencias_ alo es_con inuos[ i ness_ odas_soluciones.index(min(
i ness_ odas_soluciones))] #Vec o pos. Xp ey
# Cálculo de Xm
suma=[0 o k in ange(len(secuencias_ alo es_con inuos[0]))]
o i in ange(len(secuencias_ alo es_con inuos)):
o j in ange(len(secuencias_ alo es_con inuos[i])):
suma[j]=suma[j]+secuencias_ alo es_con inuos[i][j]
Xm=[x / len(secuencias_ alo es_con inuos) o x in suma]
# Ecuación según alo de q
i q>=0.5:
# x1 pa a p ime a mul iplicacion, x2 pa a la segunda. e1,e2,e3,e4 pa a
es a lis as.
ec o _pos_nex _i = [e1-e2 o e1,e2 in zip(X and,[x1 * 1 o x1 in [
abs(ele) o ele in [e3-e4 o e3,e4 in zip(X and,[x2 * (2* 2) o x
2 in Xac ual])]]])]
secuencias_ alo es_con inuos[indice_solucion_ac ual]=copy.deepcopy(
ec o _pos_nex _i )
Anexo: Código de p og amación en Py hon 49
eli q<0.5:
pa e_alea o ia= 3*(LB+ 4*(UB-LB))
# Pa a Xp ey engo que usa su ec o posición, la posición del ec o _
pos_aguilas con el min i ness.
ec o _pos_nex _i =[x - pa e_alea o ia o x in [e1-e2 o e1,e2 in
zip(secuencias_ alo es_con inuos[ i ness_ odas_soluciones.index(min(
i ness_ odas_soluciones))],Xm)]]
secuencias_ alo es_con inuos[indice_solucion_ac ual]=copy.deepcopy(
ec o _pos_nex _i )
e u n secuencias_ alo es_con inuos
""""""
""" GRÁFICA HDHHO Y EVOLUCIÓN PARÁMETRO E """
de g a ica_HDHHO( alo es_ o, , jj, ii, kk):
ig, ax = pl .subplo s()
ins an es_ iempo = [j o j in ange(len( alo es_ o))]
# Rep esen ación de la solución con una línea
ax.plo (ins an es_ iempo, alo es_ o, lines yle=’-’, linewid h=2, ma ke =’x
’, ma ke size=0, colo =’b’, alpha=0.7)
# Rep esen ación de la solución óp ima
ax.plo (ins an es_ iempo[ alo es_ o.index(min( alo es_ o))], alo es_ o[
alo es_ o.index(min( alo es_ o))], lines yle=’ ’, linewid h=0, ma ke =’
o’, ma ke size=10, colo =’ ’, alpha=1, label=’Op imo Local’)
ax.se _ylabel(’Valo de la F.O.’)
ax.se _xlabel(’I e aciones’)
ax.legend()
# Gua da la g á ica
pl .sa e ig("RESULTADOS/small_ins ances/g a icas_HDHHO/HDHHO_I_" + s ( )
+ "_" + s (jj) + "_" + s (ii) + "_" + s (kk) + ".png")
# Mos a la g á ica
pl .show()
de g a ica_HDHHO_ins _la ge( alo es_ o, , jj, ii, kk):
ig, ax = pl .subplo s()
ins an es_ iempo = [j o j in ange(len( alo es_ o))]
# Rep esen ación de la solución con una línea
ax.plo (ins an es_ iempo, alo es_ o, lines yle=’-’, linewid h=2, ma ke =’x
’, ma ke size=0, colo =’b’, alpha=0.7)
# Rep esen ación de la solución óp ima
ax.plo (ins an es_ iempo[ alo es_ o.index(min( alo es_ o))], alo es_ o[
alo es_ o.index(min( alo es_ o))], lines yle=’ ’, linewid h=0, ma ke =’
o’, ma ke size=10, colo =’ ’, alpha=1, label=’Op imo Local’)
ax.se _ylabel(’Valo de la F.O.’)
ax.se _xlabel(’I e aciones’)
ax.legend()
# Gua da la g á ica
pl .sa e ig("RESULTADOS/la ge_ins ances/g a icas_HDHHO/HDHHO_Ta" + s ( )
+ s (jj) + s (ii) + "_" + s (kk) + ".png")
50 Anexo: Código de p og amación en Py hon
# Mos a la g á ica
pl .show()
de g a ica_plo _E( alo es_ o):
ig, ax = pl .subplo s()
ins an es_ iempo = [j o j in ange(len( alo es_ o))]
# Rep esen ación de la solución con una línea
ax.plo (ins an es_ iempo, alo es_ o, lines yle=’-’, linewid h=2, ma ke =’x
’, ma ke size=0, colo =’b’, alpha=0.7)
""""""
""" HDHHO """
de HDHHO(ins ancia, T, am_pob, a chi o):
# Inicializa soluciones (águilas) EDD, LSL, OSL, ESL, NEHDedd y el es o
has a N alea o ias.
popula ion = [EDD(ins ancia, a chi o), LSL(ins ancia, a chi o), OSL(
ins ancia, a chi o), ESL(ins ancia, a chi o), NEHDedd(ins ancia,
a chi o)] # Vec o pa a gua da cada una de las soluciones exis en es
en la población.
o i in ange( am_pob-5):
popula ion.append(gene a _solucion_alea o ia(ins ancia, a chi o))
sec_desag = [] # Vec o pa a gua da cada secuencia desag egada (como
ec o único, sin asigna a áb icas)
sec_ al_con = [] # Vec o pa a gua da los alo es de posición de cada
secuencia.
o i in ange(len(popula ion)):
sec_desag.append(desag ega _asignacion_po _ ab ica(popula ion[i],
ins ancia))
sec_ al_con .append(c ea _ ec o _posicion_po _solucion(sec_desag[i]))
sp = copy.deepcopy(sec_desag)
soluciones_con_asignacion_ as_sp = [0 o j in ange(len(popula ion))]
i ness_soluciones = [objec i e_ unc ion(ins ancia, popula ion[j], a chi o)
o j in ange(len(popula ion))]
bes _Xp ey = copy.deepcopy(popula ion[ i ness_soluciones.index(min( i ness_
soluciones))])
bes _ i ness = min( i ness_soluciones)
# Pa a plo ea g á ica
alo es_ o_g a ica = []
plo _E = []
# Du ación de cada ins ancia
1 = ime()
2 = ime()
# Con c i e io de e minación po i e aciones.
=0
while < T:
# Emplea SPV pa a con e i alo es con inuos en pe mu ación de
abajos.
Anexo: Código de p og amación en Py hon 51
o i in ange(len(popula ion)):
sp [i] = SPV(sec_ al_con [i],sp [i])
# Calcula i ness de cada solución (águila), como engo un ec o
desag egado, 1o
¯asigno a áb icas, 2o
¯calculo i ness.
o i in ange(len(sp )):
soluciones_con_asignacion_ as_sp [i] = FACTORY_LEAST_CT(ins ancia,
sp [i], a chi o)
i ness_soluciones[i] = objec i e_ unc ion(ins ancia, soluciones_con
_asignacion_ as_sp [i], a chi o)
# Escoge Xp ey y Xwo s como las soluciones con meno y mayo i ness
espec i amen e.
Xp ey = copy.deepcopy(soluciones_con_asignacion_ as_sp [ i ness_
soluciones.index(min( i ness_soluciones))])
Xwo s = copy.deepcopy(soluciones_con_asignacion_ as_sp [ i ness_
soluciones.index(max( i ness_soluciones))])
# Gene a núme o alea o io en e 0 y 1.
= andom.uni o m(0,1)
# Calcula X’ aplicando Pa h- elinking con Xwo s , Xp ey y .
X_p ima,TT_X_p ima=PATH_RELINKING(Xwo s , Xp ey, , ins ancia, a chi o)
i X_p ima!=0:
i TT_X_p ima < min( i ness_soluciones):
Xp ey=copy.deepcopy(X_p ima)
# Como engo una nue a Xp ey, end é un nue o ec o de posición
pa a Xp ey, sec_desag pa a SPV y i ness.
sp [ i ness_soluciones.index(min( i ness_soluciones))] =
desag ega _asignacion_po _ ab ica(Xp ey, ins ancia)
sec_ al_con [ i ness_soluciones.index(min( i ness_soluciones))]
= c ea _ ec o _posicion_po _solucion(sp [ i ness_soluciones.
index(min( i ness_soluciones))])
i ness_soluciones[ i ness_soluciones.index(min( i ness_
soluciones))] = TT_X_p ima
eli TT_X_p ima < max( i ness_soluciones):
Xwo s =copy.deepcopy(X_p ima)
# Como engo una nue a Xwo s , end é un nue o ec o de posició
n pa a Xwo s , sec_desag pa a SPV y i ness.
sp [ i ness_soluciones.index(max( i ness_soluciones))] =
desag ega _asignacion_po _ ab ica(Xwo s , ins ancia)
sec_ al_con [ i ness_soluciones.index(max( i ness_soluciones))]
= c ea _ ec o _posicion_po _solucion(sp [ i ness_soluciones.
index(max( i ness_soluciones))])
i ness_soluciones[ i ness_soluciones.index(max( i ness_
soluciones))] = TT_X_p ima
i TT_X_p ima < bes _ i ness:
bes _Xp ey = copy.deepcopy(X_p ima)
bes _ i ness = TT_X_p ima
# Pa a plo ea g á ica
alo es_ o_g a ica.append(min( i ness_soluciones))
52 Anexo: Código de p og amación en Py hon
# COMIENZA BUCLE FOR PARA CADA SOLUCIÓN (ÁGUILA)
# Ac ualiza E usando la ecuación 15.
E_0=2* andom. andom()-1 #Cambia alea o iamen e en el in e alo (-1,1)
en cada i e ación, ES DECIR, an es bucle EXPLOT. Y EXPLOR.
E=2*E_0*(1-( /T)) # es la i e ación ac ual y T es el o al de
i e aciones
plo _E.append(E)
o i in ange(len(popula ion)):
# Pa a |E|>=1 --> EXPLORATION PHASE
i abs(E)>=1:
# Ac ualiza el ec o de posición ( alo es con inuos) usando
ecuación 13.
sec_ al_con = copy.deepcopy(explo a ion_phase(sec_ al_con ,
i ness_soluciones, i))
# Pa a |E|<1 --> EXPLOITATION PHASE
eli abs(E)<1:
= andom.uni o m(0, 1)
# So besiege, ac ualiza ec o posición usando ecuación 16.
i >=0.5 and abs(E)>=0.5:
sec_ al_con = copy.deepcopy(so _besiege(i, sec_ al_con ,
i ness_soluciones, E))
# Ha d besiege, ac ualiza ec o posición usando ecuación 18.
eli >=0.5 and abs(E)<0.5:
sec_ al_con = copy.deepcopy(ha d_besiege(i, sec_ al_con ,
i ness_soluciones, E))
# So besiege wi h p og essi e apid di es, ac ualiza ec o
posición usando ecuación 19.
eli <0.5 and abs(E)>=0.5:
sec_ al_con = copy.deepcopy(so _besiege_wi h_p og essi e_
apid_di es(i, sec_ al_con , i ness_soluciones,
popula ion, E, ins ancia, a chi o))
# Ha d besiege wi h p og essi e apid di es, ac ualiza ec o
posición usando ecuación 22.
eli <0.5 and abs(E)<0.5:
sec_ al_con = copy.deepcopy(ha d_besiege_wi h_p og essi e_
apid_di es(i, sec_ al_con , i ness_soluciones,
popula ion, E, ins ancia, a chi o))
2 = ime()
+= 1
p in ("Tiempo empleado:", 2 - 1)
e u n bes _Xp ey, bes _ i ness, alo es_ o_g a ica, plo _E
""""""
""" LOCAL SEARCH - IG """
""" Inse Ope a ion pa a RSLS_s """
Anexo: Código de p og amación en Py hon 53
de INSERT_OPERATION(sec_ ac o y_eleg, sec_local_sea ch, selec ed_ ac o y):
#Elijo subsecuencia
pun o_inicio_subsec= andom. andin (0, len(sec_ ac o y_eleg)-1) #Es ablezco
el pun o de inicio de la subsecuencia.
i pun o_inicio_subsec==0 and len(sec_ ac o y_eleg)>1:
pun o_ in_subsec= andom. andin (pun o_inicio_subsec, len(sec_ ac o y_
eleg)-2) #Pun o in pa a e i a sec comple a. (-2)
else:
pun o_ in_subsec= andom. andin (pun o_inicio_subsec, len(sec_ ac o y_
eleg)-1) #Es ablezco pun o de in.
long_subsec=pun o_ in_subsec-pun o_inicio_subsec+1 #Calculo la longi ud de
la subsecuencia. (+1 po si los p os coinciden)
subsec=[]
o j in ange(long_subsec):
subsec.append(sec_ ac o y_eleg[pun o_inicio_subsec+j]) #Cons uyo la
subsecuencia elegida.
#Selecciono el pun o de inse ción de o ma alea o ia.
inse _op =[] #Elabo o una lis a con las posiciones posibles pa a ealiza
el inse .
o j in ange(pun o_inicio_subsec):
inse _op .append(j)
o j in ange((pun o_ in_subsec+1),len(sec_ ac o y_eleg)):
inse _op .append(j)
i inse _op !=[]:
inse _poin = andom.choice(inse _op ) #Escojo una de las opciones.
else:
inse _poin =0 #Si uacion áb ica con un solo elemen o que se ía una
subsecuencia (queda igual), sec_ ac o y acia.
#Inse o la subsecuencia as el pun o de inse ción escogido.
o j in ange(pun o_inicio_subsec,pun o_ in_subsec+1):
sec_ ac o y_eleg.pop(pun o_inicio_subsec) #Elimino los abajos de la
subsecuencia en la secuencia comple a de la áb ica.
i pun o_inicio_subsec==(inse _poin +1): #Pa a e i a ob ene la misma
secuencia epe ida.
o j in ange(long_subsec):
sec_ ac o y_eleg.inse (inse _poin +j, subsec[j]) #Inse o la
subsec. pa a no epe i o iginal.
eli inse _op !=[]: #En caso de secuencia ab ica unico elemen o, no hay
opciones como al y da ia e o .
o j in ange(long_subsec):
sec_ ac o y_eleg.inse (inse _op .index(inse _poin )+1+j, subsec[j
]) #Inse o la subsecuencia en el pun o escogido.
eli inse _op ==[]: #Unica posibilidad si solo hay un elemen o en la
secuencia de la ab ica, lo inse o al cual y ya.
sec_ ac o y_eleg.inse (inse _poin , subsec[0])
54 Anexo: Código de p og amación en Py hon
#AñADO LA SUBSECUENCIA FINAL ACTUALIZADA A UNA COPIA DE LA SECUENCIA
ORIGINAL.
sec_local_sea ch[selec ed_ ac o y]=copy.deepcopy(sec_ ac o y_eleg)
e u n sec_local_sea ch
""""""
""" Re e se Ope a ion pa a RSLS_s """
de REVERSE_OPERATION(sec_ ac o y_eleg, sec_local_sea ch, selec ed_ ac o y):
#Elegi subsecuencia ( epe ido de la opción an e io ).
pun o_inicio_subsec= andom. andin (0, len(sec_ ac o y_eleg)-1) #Es ablezco
el pun o de inicio de la subsecuencia.
i pun o_inicio_subsec==0 and len(sec_ ac o y_eleg)>1:
pun o_ in_subsec= andom. andin (pun o_inicio_subsec, len(sec_ ac o y_
eleg)-2) #Pun o in pa a e i a sec comple a. (-2)
else:
pun o_ in_subsec= andom. andin (pun o_inicio_subsec, len(sec_ ac o y_
eleg)-1) #Es ablezco pun o de in.
long_subsec=pun o_ in_subsec-pun o_inicio_subsec+1 #Calculo la longi ud de
la subsecuencia. (+1 po si los p os coinciden)
subsec=[]
o j in ange(long_subsec):
subsec.append(sec_ ac o y_eleg[pun o_inicio_subsec+j]) #Cons uyo la
subsecuencia elegida.
#In e i la subsecuencia den o de la secuencia. (1o
¯Elimino subsec de la
sec. |2o
¯Inse o la subsec en la sec in i iendola)
o j in ange(pun o_inicio_subsec,pun o_ in_subsec+1):
sec_ ac o y_eleg.pop(pun o_inicio_subsec) #Elimino los abajos de la
subsecuencia en la secuencia comple a de la áb ica.
o j in ange(long_subsec):
sec_ ac o y_eleg.inse (pun o_inicio_subsec+j, subsec[long_subsec-1-j])
#Inse o alo es subsec de a ás hacia delan e.
#AñADO LA SUBSECUENCIA FINAL ACTUALIZADA A UNA COPIA DE LA SECUENCIA
ORIGINAL.
sec_local_sea ch[selec ed_ ac o y]=copy.deepcopy(sec_ ac o y_eleg)
e u n sec_local_sea ch
""""""
""" Inicialización RSLS_m """
de INITIALIZATION_RSLS_m(sec, a chi o):
#Elegi 2 áb icas de o ma alea o ia.
o al_ ac o ies=[]
o in ange( ead_ ag(a chi o, "FACTORIES")):
o al_ ac o ies.append( )
ac o y_A= andom.choice( o al_ ac o ies)
o al_ ac o ies.pop( ac o y_A)
Anexo: Código de p og amación en Py hon 55
ac o y_B= andom.choice( o al_ ac o ies)
#Escojo la áb ica con la secuencia más co a, elijo una subsecuencia en
es a (que se á álida pa a la o a áb ica ambién).
i len(sec[ ac o y_A])<=len(sec[ ac o y_B]):
selec ed_ ac o y= ac o y_A
ac o y_al e na i a= ac o y_B
si uacion=0
else:
selec ed_ ac o y= ac o y_B
ac o y_al e na i a= ac o y_A
si uacion=1
sec_ ac o y_eleg=copy.deepcopy(sec[selec ed_ ac o y]) #Fáb ica con la
secuencia de meno longi ud.
sec_ ac o y_al e na i a=copy.deepcopy(sec[ ac o y_al e na i a]) #Fab ica
con la secuencia de mayo longi ud.
#Elegi subsecuencia DE LA FÁBRICA CON SECUENCIA CORTA ( epe ido de la opci
ón an e io ).
pun o_inicio_subsec= andom. andin (0, len(sec_ ac o y_eleg)-1) #Es ablezco
el pun o de inicio de la subsecuencia.
i pun o_inicio_subsec==0 and len(sec_ ac o y_eleg)>1:
pun o_ in_subsec= andom. andin (pun o_inicio_subsec, len(sec_ ac o y_
eleg)-2) #Pun o in pa a e i a sec comple a. (-2)
else:
pun o_ in_subsec= andom. andin (pun o_inicio_subsec, len(sec_ ac o y_
eleg)-1) #Es ablezco pun o de in.
long_subsec=pun o_ in_subsec-pun o_inicio_subsec+1 #Calculo la longi ud de
la subsecuencia (g). (+1 po si los p os coinciden)
#Elegi PUNTO DE INICIO en la FÁBRICA CON SECUENCIA LARGA (no iene po que
coincidi con el de la o a ab ica).
pun o_inicio_subsec_la ga= andom. andin (0, len(sec_ ac o y_al e na i a)-
long_subsec)
subsec_A=[]
subsec_B=[]
i si uacion==0:
o j in ange(long_subsec):
subsec_A.append(sec_ ac o y_eleg[pun o_inicio_subsec+j]) #Cons uyo
la subsecuencia de la áb ica A.
subsec_B.append(sec_ ac o y_al e na i a[pun o_inicio_subsec_la ga+j
])
eli si uacion==1:
o j in ange(long_subsec):
subsec_B.append(sec_ ac o y_eleg[pun o_inicio_subsec+j]) #Cons uyo
la subsecuencia de la áb ica A.
subsec_A.append(sec_ ac o y_al e na i a[pun o_inicio_subsec_la ga+j
])
e u n subsec_A, subsec_B, pun o_inicio_subsec, pun o_ in_subsec, si uacion
, long_subsec, pun o_inicio_subsec_la ga, sec_ ac o y_al e na i a,
ac o y_A, ac o y_B, sec_ ac o y_eleg
56 Anexo: Código de p og amación en Py hon
""""""
""" Swap Ope a ion pa a RSLS_m """
de SWAP_OPERATION(pun o_inicio_subsec, pun o_ in_subsec, sec_ ac o y_eleg,
si uacion, long_subsec, subsec_A, subsec_B, pun o_inicio_subsec_la ga, sec_
ac o y_al e na i a, sec_local_sea ch, ac o y_A, ac o y_B):
#TENGO: sec_ ac o y_eleg, sec_ ac o y_al e na i a (secuencia de cada ab) y
subsec_A, subsec_B (in e cambia en sec o ig).
#Inse o la subsecuencia de sec_ ac o y_al e na i a en sec_ ac o y_eleg.
o j in ange(pun o_inicio_subsec,pun o_ in_subsec+1):
sec_ ac o y_eleg.pop(pun o_inicio_subsec) #Elimino los abajos de la
subsecuencia en la secuencia comple a de la áb ica.
i si uacion==0:
o j in ange(long_subsec):
sec_ ac o y_eleg.inse (pun o_inicio_subsec+j, subsec_B[j]) #Inse o
la subsecuencia en el pun o escogido.
eli si uacion==1:
o j in ange(long_subsec):
sec_ ac o y_eleg.inse (pun o_inicio_subsec+j, subsec_A[j]) #Inse o
la subsecuencia en el pun o escogido.
#Inse o la subsecuencia de sec_ ac o y_eleg en sec_ ac o y_al e na i a.
o j in ange(pun o_inicio_subsec_la ga,pun o_inicio_subsec_la ga+long_
subsec):
sec_ ac o y_al e na i a.pop(pun o_inicio_subsec_la ga) #Elimino los
abajos de la subsec en la sec comple a de la áb ica.
i si uacion==0:
o j in ange(long_subsec):
sec_ ac o y_al e na i a.inse (pun o_inicio_subsec_la ga+j, subsec_A
[j]) #Inse o la subsecuencia en el pun o escogido.
eli si uacion==1:
o j in ange(long_subsec):
sec_ ac o y_al e na i a.inse (pun o_inicio_subsec_la ga+j, subsec_B
[j]) #Inse o la subsecuencia en el pun o escogido.
#SOBREESCRIBIR ESAS NUEVAS SECUENCIAS SWAPEADAS EN LA SECUENCIA ORIGINAL.
i si uacion==0:
sec_local_sea ch[ ac o y_A]=copy.deepcopy(sec_ ac o y_eleg)
sec_local_sea ch[ ac o y_B]=copy.deepcopy(sec_ ac o y_al e na i a)
eli si uacion==1:
sec_local_sea ch[ ac o y_A]=copy.deepcopy(sec_ ac o y_al e na i a)
sec_local_sea ch[ ac o y_B]=copy.deepcopy(sec_ ac o y_eleg)
e u n sec_local_sea ch
""""""
Anexo: Código de p og amación en Py hon 57
""" Swap + Re e se Ope a ion pa a RSLS_m """
de SWAP_AND_REVERSE_OPERATION(pun o_inicio_subsec, pun o_ in_subsec, sec_
ac o y_eleg, si uacion, long_subsec, subsec_A, subsec_B, pun o_inicio_
subsec_la ga, sec_ ac o y_al e na i a, sec_local_sea ch, ac o y_A, ac o y
_B):
#Inse o la subsecuencia de sec_ ac o y_al e na i a en sec_ ac o y_eleg.
o j in ange(pun o_inicio_subsec,pun o_ in_subsec+1):
sec_ ac o y_eleg.pop(pun o_inicio_subsec) #Elimino los abajos de la
subsecuencia en la secuencia comple a de la áb ica.
i si uacion==0:
o j in ange(long_subsec):
sec_ ac o y_eleg.inse (pun o_inicio_subsec, subsec_B[j]) #Inse o
la subsecuencia en el pun o escogido.
eli si uacion==1:
o j in ange(long_subsec):
sec_ ac o y_eleg.inse (pun o_inicio_subsec, subsec_A[j]) #Inse o
la subsecuencia en el pun o escogido.
#Inse o la subsecuencia de sec_ ac o y_eleg en sec_ ac o y_al e na i a.
o j in ange(pun o_inicio_subsec_la ga,pun o_inicio_subsec_la ga+long_
subsec):
sec_ ac o y_al e na i a.pop(pun o_inicio_subsec_la ga) #Elimino los
abajos de la subsec en la sec comple a de la áb ica.
i si uacion==0:
o j in ange(long_subsec):
sec_ ac o y_al e na i a.inse (pun o_inicio_subsec_la ga, subsec_A[j
]) #Inse o la subsecuencia en el pun o escogido.
eli si uacion==1:
o j in ange(long_subsec):
sec_ ac o y_al e na i a.inse (pun o_inicio_subsec_la ga, subsec_B[j
]) #Inse o la subsecuencia en el pun o escogido.
#SOBREESCRIBIR ESAS NUEVAS SECUENCIAS SWAPEADAS EN LA SECUENCIA ORIGINAL.
i si uacion==0:
sec_local_sea ch[ ac o y_A]=copy.deepcopy(sec_ ac o y_eleg)
sec_local_sea ch[ ac o y_B]=copy.deepcopy(sec_ ac o y_al e na i a)
eli si uacion==1:
sec_local_sea ch[ ac o y_A]=copy.deepcopy(sec_ ac o y_al e na i a)
sec_local_sea ch[ ac o y_B]=copy.deepcopy(sec_ ac o y_eleg)
e u n sec_local_sea ch
""""""
""" RSLS """
de RSLS(sec, ins ancia, a chi o):
lag=T ue
64 Anexo: Código de p og amación en Py hon
ax.plo (ins an es_ iempo[ alo es_ o.index(min( alo es_ o))], alo es_ o[
alo es_ o.index(min( alo es_ o))], lines yle=’ ’, linewid h=0, ma ke =’
o’, ma ke size=10, colo =’ ’, alpha=1, label=’Op imo Local’)
ax.se _ylabel(’Valo de la F.O.’)
ax.se _xlabel(’I e aciones’)
ax.legend()
# Gua da la g á ica
pl .sa e ig("RESULTADOS/small_ins ances/g a icas_IG/IG_I_" + s ( ) + "_"
+ s (jj) + "_" + s (ii) + "_" + s (kk) + ".png")
# Mos a la g á ica
pl .show()
de g a ica_IG_ins _la ge( alo es_ o, , jj, ii, kk):
ig, ax = pl .subplo s()
ins an es_ iempo = [j o j in ange(len( alo es_ o))]
# Rep esen ación de la solución con una línea
ax.plo (ins an es_ iempo, alo es_ o, lines yle=’-’, linewid h=2, ma ke =’x
’, ma ke size=0, colo =’b’, alpha=0.7)
# Rep esen ación de la solución óp ima
ax.plo (ins an es_ iempo[ alo es_ o.index(min( alo es_ o))], alo es_ o[
alo es_ o.index(min( alo es_ o))], lines yle=’ ’, linewid h=0, ma ke =’
o’, ma ke size=10, colo =’ ’, alpha=1, label=’Op imo Local’)
ax.se _ylabel(’Valo de la F.O.’)
ax.se _xlabel(’I e aciones’)
ax.legend()
# Gua da la g á ica
pl .sa e ig("RESULTADOS/la ge_ins ances/g a icas_IG/IG_Ta" + s ( ) + s (
jj) + s (ii) + "_" + s (kk) + ".png")
# Mos a la g á ica
pl .show()
""""""""""""""""""""""""
##### RESULTADOS EDD INSTANCIAS PEQUEñAS #####
""""""""""""""""""""""""
om heu is icas_ 8 impo *
impo openpyxl
impo os
""" EDD PARA TODOS LOS ARCHIVOS (AUTOMATIZADO) """
# C eo a chi o pa a esul ados
wi h open(’EDD_INST_SMALL. x ’,’w’) as a chi o_ esul ados_ins _small:
a chi o_ esul ados_ins _small.w i e("")
# Esc ibo i ulo en x
wi h open("EDD_INST_SMALL. x ","a") as RESULTADOS:
RESULTADOS.w i e("RESULTADOS EDD: Ins ancia, Valo FO, Secuencias, Tiempo
de ejecución n")
Anexo: Código de p og amación en Py hon 65
# C ea un nue o lib o de abajo y selecciona la hoja ac i a
wb = openpyxl.Wo kbook()
ws = wb.ac i e
ila = 1
ws.cell( ow = ila, column = 1, alue = "Ins ancia")
ws.cell( ow = ila, column = 2, alue = "Valo FO")
ws.cell( ow = ila, column = 3, alue = "Secuencias")
ws.cell( ow = ila, column = 4, alue = "Tiempo ejecución")
o in ange(2,5):
o jj in ange(4,18,2):
o ii in ange(2,6):
o kk in ange(1,6):
# Ins ancias au oma izadas
a chi o=’DPFSP_DD/I_’ + s ( ) + ’_’ + s (jj) + ’_’ + s (ii)
+ ’_’ + s (kk) + ’. x ’
ins ancia=FlowShop(a chi o)
# Resul ados de cada ins ancia
ila += 1
ws.cell( ow = ila, column = 1, alue = "I_" + s ( ) + "_" +
s (jj) + "_" + s (ii) + "_" + s (kk) + ". x ")
1 = ime()
secuencias = EDD(ins ancia, a chi o)
2 = ime()
alo _ o = objec i e_ unc ion(ins ancia, secuencias, a chi o)
p in ("Valo FO:", alo _ o)
wi h open("EDD_INST_SMALL. x ","a") as RESULTADOS:
RESULTADOS.w i e(" nI_" + s ( ) + "_" + s (jj) + "_" + s
(ii) + "_" + s (kk) + ". x | " + "FO=" + s ( alo _ o)
+ " | secs=" + s (secuencias) + " | ime ex=" + s ( 2-
1) + " n")
# Esc ibi alo es en las celdas
ws.cell( ow = ila, column = 2, alue = alo _ o)
ws.cell( ow = ila, column = 3, alue = s (secuencias))
ws.cell( ow = ila, column = 4, alue = ( 2- 1))
# Ob ene la u a a la ca pe a deseada
ca pe a = os.pa h.join(os.pa h.expanduse (’~’), ’Desk op TFG’)
# De ini el nomb e del a chi o
a chi o_nomb e = ’EDD_ins _small.xlsx’
# C ea la u a comple a al a chi o
a chi o_ u a = os.pa h.join(ca pe a, a chi o_nomb e)
# Gua da el a chi o
wb.sa e(a chi o_ u a)
""""""
66 Anexo: Código de p og amación en Py hon
""""""""""""""""""""""""
##### RESULTADOS EDD INSTANCIAS GRANDES #####
""""""""""""""""""""""""
om heu is icas_ 8 impo *
impo openpyxl
impo os
""" EDD PARA TODOS LOS ARCHIVOS (AUTOMATIZADO) """
# C eo a chi o pa a esul ados
wi h open(’EDD_INST_LARGE. x ’,’w’) as a chi o_ esul ados_ins _la ge:
a chi o_ esul ados_ins _la ge.w i e("")
# Esc ibo i ulo en x
wi h open("EDD_INST_LARGE. x ","a") as RESULTADOS:
RESULTADOS.w i e("RESULTADOS EDD: Ins ancia, Valo FO, Secuencias, Tiempo
de ejecución n")
# C ea un nue o lib o de abajo y selecciona la hoja ac i a
wb = openpyxl.Wo kbook()
ws = wb.ac i e
ila = 1
ws.cell( ow = ila, column = 1, alue = "Ins ancia")
ws.cell( ow = ila, column = 2, alue = "Valo FO")
ws.cell( ow = ila, column = 3, alue = "Secuencias")
ws.cell( ow = ila, column = 4, alue = "Tiempo ejecución")
ws.cell( ow = ila, column = 5, alue = "La ge Ins ances")
o pp in ange(2):
o qq in ange(10):
o in ange(10):
o in ange(2,8):
i (pp==0 and qq==0 and ==0):
b eak
else:
# Ins ancias au oma izadas
a chi o = ’DPFSP_DD/Ta’ + s (pp) + s (qq) + s ( ) + ’_’ +
s ( ) + ’. x ’
ins ancia=FlowShop(a chi o)
# Resul ados de cada ins ancia
ila += 1
ws.cell( ow = ila, column = 1, alue = "Ta" + s (pp) + s (
qq) + s ( ) + "_" + s ( ) + ". x ")
1 = ime()
secuencias = EDD(ins ancia, a chi o)
2 = ime()
Anexo: Código de p og amación en Py hon 67
alo _ o = objec i e_ unc ion(ins ancia, secuencias, a chi o)
p in ("Valo FO:", alo _ o)
wi h open("EDD_INST_LARGE. x ","a") as RESULTADOS:
RESULTADOS.w i e(" nTa" + s (pp) + s (qq) + s ( ) +
"_" + s ( ) + ". x | " + "FO=" + s ( alo _ o) + "
| secs=" + s (secuencias) + " | ime ex=" + s ( 2-
1) + " n")
# Esc ibi alo es en las celdas
ws.cell( ow = ila, column = 2, alue = alo _ o)
ws.cell( ow = ila, column = 3, alue = s (secuencias))
ws.cell( ow = ila, column = 4, alue = ( 2- 1))
# Ob ene la u a a la ca pe a deseada
ca pe a = os.pa h.join(os.pa h.expanduse (’~’), ’Desk op TFG
’)
# De ini el nomb e del a chi o
a chi o_nomb e = ’EDD_ins _la ge.xlsx’
# C ea la u a comple a al a chi o
a chi o_ u a = os.pa h.join(ca pe a, a chi o_nomb e)
# Gua da el a chi o
wb.sa e(a chi o_ u a)
""""""
""""""""""""""""""""""""
##### RESULTADOS OSL INSTANCIAS PEQUEñAS #####
""""""""""""""""""""""""
om heu is icas_ 8 impo *
impo openpyxl
impo os
""" OSL PARA TODOS LOS ARCHIVOS (AUTOMATIZADO) """
# C eo a chi o pa a esul ados
wi h open(’OSL_INST_SMALL. x ’,’w’) as a chi o_ esul ados_ins _small:
a chi o_ esul ados_ins _small.w i e("")
# Esc ibo i ulo en x
wi h open("OSL_INST_SMALL. x ","a") as RESULTADOS:
RESULTADOS.w i e("RESULTADOS OSL: Ins ancia, Valo FO, Secuencias, Tiempo
de ejecución n")
# C ea un nue o lib o de abajo y selecciona la hoja ac i a
wb = openpyxl.Wo kbook()
ws = wb.ac i e
ila = 1
ws.cell( ow = ila, column = 1, alue = "Ins ancia")
ws.cell( ow = ila, column = 2, alue = "Valo FO")
ws.cell( ow = ila, column = 3, alue = "Secuencias")
68 Anexo: Código de p og amación en Py hon
ws.cell( ow = ila, column = 4, alue = "Tiempo ejecución")
o in ange(2,5):
o jj in ange(4,18,2):
o ii in ange(2,6):
o kk in ange(1,6):
# Ins ancias au oma izadas
a chi o=’DPFSP_DD/I_’ + s ( ) + ’_’ + s (jj) + ’_’ + s (ii)
+ ’_’ + s (kk) + ’. x ’
ins ancia=FlowShop(a chi o)
# Resul ados de cada ins ancia
ila += 1
ws.cell( ow = ila, column = 1, alue = "I_" + s ( ) + "_" +
s (jj) + "_" + s (ii) + "_" + s (kk) + ". x ")
1 = ime()
secuencias = OSL(ins ancia, a chi o)
2 = ime()
alo _ o = objec i e_ unc ion(ins ancia, secuencias, a chi o)
p in ("Valo FO:", alo _ o)
wi h open("OSL_INST_SMALL. x ","a") as RESULTADOS:
RESULTADOS.w i e(" nI_" + s ( ) + "_" + s (jj) + "_" + s
(ii) + "_" + s (kk) + ". x | " + "FO=" + s ( alo _ o)
+ " | secs=" + s (secuencias) + " | ime ex=" + s ( 2-
1) + " n")
# Esc ibi alo es en las celdas
ws.cell( ow = ila, column = 2, alue = alo _ o)
ws.cell( ow = ila, column = 3, alue = s (secuencias))
ws.cell( ow = ila, column = 4, alue = ( 2- 1))
# Ob ene la u a a la ca pe a deseada
ca pe a = os.pa h.join(os.pa h.expanduse (’~’), ’Desk op TFG’)
# De ini el nomb e del a chi o
a chi o_nomb e = ’OSL_ins _small.xlsx’
# C ea la u a comple a al a chi o
a chi o_ u a = os.pa h.join(ca pe a, a chi o_nomb e)
# Gua da el a chi o
wb.sa e(a chi o_ u a)
""""""
""""""""""""""""""""""""
##### RESULTADOS OSL INSTANCIAS GRANDES #####
""""""""""""""""""""""""
om heu is icas_ 8 impo *
impo openpyxl
Anexo: Código de p og amación en Py hon 69
impo os
""" OSL PARA TODOS LOS ARCHIVOS (AUTOMATIZADO) """
# C eo a chi o pa a esul ados
wi h open(’OSL_INST_LARGE. x ’,’w’) as a chi o_ esul ados_ins _la ge:
a chi o_ esul ados_ins _la ge.w i e("")
# Esc ibo i ulo en x
wi h open("OSL_INST_LARGE. x ","a") as RESULTADOS:
RESULTADOS.w i e("RESULTADOS OSL: Ins ancia, Valo FO, Secuencias, Tiempo
de ejecución n")
# C ea un nue o lib o de abajo y selecciona la hoja ac i a
wb = openpyxl.Wo kbook()
ws = wb.ac i e
ila = 1
ws.cell( ow = ila, column = 1, alue = "Ins ancia")
ws.cell( ow = ila, column = 2, alue = "Valo FO")
ws.cell( ow = ila, column = 3, alue = "Secuencias")
ws.cell( ow = ila, column = 4, alue = "Tiempo ejecución")
ws.cell( ow = ila, column = 5, alue = "La ge Ins ances")
o pp in ange(2):
o qq in ange(10):
o in ange(10):
o in ange(2,8):
i (pp==0 and qq==0 and ==0):
b eak
else:
# Ins ancias au oma izadas
a chi o = ’DPFSP_DD/Ta’ + s (pp) + s (qq) + s ( ) + ’_’ +
s ( ) + ’. x ’
ins ancia=FlowShop(a chi o)
# Resul ados de cada ins ancia
ila += 1
ws.cell( ow = ila, column = 1, alue = "Ta" + s (pp) + s (
qq) + s ( ) + "_" + s ( ) + ". x ")
1 = ime()
secuencias = OSL(ins ancia, a chi o)
2 = ime()
alo _ o = objec i e_ unc ion(ins ancia, secuencias, a chi o)
p in ("Valo FO:", alo _ o)
wi h open("OSL_INST_LARGE. x ","a") as RESULTADOS:
RESULTADOS.w i e(" nTa" + s (pp) + s (qq) + s ( ) +
"_" + s ( ) + ". x | " + "FO=" + s ( alo _ o) + "
70 Anexo: Código de p og amación en Py hon
| secs=" + s (secuencias) + " | ime ex=" + s ( 2-
1) + " n")
# Esc ibi alo es en las celdas
ws.cell( ow = ila, column = 2, alue = alo _ o)
ws.cell( ow = ila, column = 3, alue = s (secuencias))
ws.cell( ow = ila, column = 4, alue = ( 2- 1))
# Ob ene la u a a la ca pe a deseada
ca pe a = os.pa h.join(os.pa h.expanduse (’~’), ’Desk op TFG
’)
# De ini el nomb e del a chi o
a chi o_nomb e = ’OSL_ins _la ge.xlsx’
# C ea la u a comple a al a chi o
a chi o_ u a = os.pa h.join(ca pe a, a chi o_nomb e)
# Gua da el a chi o
wb.sa e(a chi o_ u a)
""""""
""""""""""""""""""""""""
##### RESULTADOS LSL INSTANCIAS PEQUEñAS #####
""""""""""""""""""""""""
om heu is icas_ 8 impo *
impo openpyxl
impo os
""" LSL PARA TODOS LOS ARCHIVOS (AUTOMATIZADO) """
# C eo a chi o pa a esul ados
wi h open(’LSL_INST_SMALL. x ’,’w’) as a chi o_ esul ados_ins _small:
a chi o_ esul ados_ins _small.w i e("")
# Esc ibo i ulo en x
wi h open("LSL_INST_SMALL. x ","a") as RESULTADOS:
RESULTADOS.w i e("RESULTADOS LSL: Ins ancia, Valo FO, Secuencias, Tiempo
de ejecución n")
# C ea un nue o lib o de abajo y selecciona la hoja ac i a
wb = openpyxl.Wo kbook()
ws = wb.ac i e
ila = 1
ws.cell( ow = ila, column = 1, alue = "Ins ancia")
ws.cell( ow = ila, column = 2, alue = "Valo FO")
ws.cell( ow = ila, column = 3, alue = "Secuencias")
ws.cell( ow = ila, column = 4, alue = "Tiempo ejecución")
o in ange(2,5):
o jj in ange(4,18,2):
o ii in ange(2,6):
o kk in ange(1,6):
Anexo: Código de p og amación en Py hon 71
# Ins ancias au oma izadas
a chi o=’DPFSP_DD/I_’ + s ( ) + ’_’ + s (jj) + ’_’ + s (ii)
+ ’_’ + s (kk) + ’. x ’
ins ancia=FlowShop(a chi o)
# Resul ados de cada ins ancia
ila += 1
ws.cell( ow = ila, column = 1, alue = "I_" + s ( ) + "_" +
s (jj) + "_" + s (ii) + "_" + s (kk) + ". x ")
1 = ime()
secuencias = LSL(ins ancia, a chi o)
2 = ime()
alo _ o = objec i e_ unc ion(ins ancia, secuencias, a chi o)
p in ("Valo FO:", alo _ o)
wi h open("LSL_INST_SMALL. x ","a") as RESULTADOS:
RESULTADOS.w i e(" nI_" + s ( ) + "_" + s (jj) + "_" + s
(ii) + "_" + s (kk) + ". x | " + "FO=" + s ( alo _ o)
+ " | secs=" + s (secuencias) + " | ime ex=" + s ( 2-
1) + " n")
# Esc ibi alo es en las celdas
ws.cell( ow = ila, column = 2, alue = alo _ o)
ws.cell( ow = ila, column = 3, alue = s (secuencias))
ws.cell( ow = ila, column = 4, alue = ( 2- 1))
# Ob ene la u a a la ca pe a deseada
ca pe a = os.pa h.join(os.pa h.expanduse (’~’), ’Desk op TFG’)
# De ini el nomb e del a chi o
a chi o_nomb e = ’LSL_ins _small.xlsx’
# C ea la u a comple a al a chi o
a chi o_ u a = os.pa h.join(ca pe a, a chi o_nomb e)
# Gua da el a chi o
wb.sa e(a chi o_ u a)
""""""
""""""""""""""""""""""""
##### RESULTADOS LSL INSTANCIAS GRANDES #####
""""""""""""""""""""""""
om heu is icas_ 8 impo *
impo openpyxl
impo os
""" LSL PARA TODOS LOS ARCHIVOS (AUTOMATIZADO) """
# C eo a chi o pa a esul ados
wi h open(’LSL_INST_LARGE. x ’,’w’) as a chi o_ esul ados_ins _la ge:
72 Anexo: Código de p og amación en Py hon
a chi o_ esul ados_ins _la ge.w i e("")
# Esc ibo i ulo en x
wi h open("LSL_INST_LARGE. x ","a") as RESULTADOS:
RESULTADOS.w i e("RESULTADOS LSL: Ins ancia, Valo FO, Secuencias, Tiempo
de ejecución n")
# C ea un nue o lib o de abajo y selecciona la hoja ac i a
wb = openpyxl.Wo kbook()
ws = wb.ac i e
ila = 1
ws.cell( ow = ila, column = 1, alue = "Ins ancia")
ws.cell( ow = ila, column = 2, alue = "Valo FO")
ws.cell( ow = ila, column = 3, alue = "Secuencias")
ws.cell( ow = ila, column = 4, alue = "Tiempo ejecución")
ws.cell( ow = ila, column = 5, alue = "La ge Ins ances")
o pp in ange(2):
o qq in ange(10):
o in ange(10):
o in ange(2,8):
i (pp==0 and qq==0 and ==0):
b eak
else:
# Ins ancias au oma izadas
a chi o = ’DPFSP_DD/Ta’ + s (pp) + s (qq) + s ( ) + ’_’ +
s ( ) + ’. x ’
ins ancia=FlowShop(a chi o)
# Resul ados de cada ins ancia
ila += 1
ws.cell( ow = ila, column = 1, alue = "Ta" + s (pp) + s (
qq) + s ( ) + "_" + s ( ) + ". x ")
1 = ime()
secuencias = LSL(ins ancia, a chi o)
2 = ime()
alo _ o = objec i e_ unc ion(ins ancia, secuencias, a chi o)
p in ("Valo FO:", alo _ o)
wi h open("LSL_INST_LARGE. x ","a") as RESULTADOS:
RESULTADOS.w i e(" nTa" + s (pp) + s (qq) + s ( ) +
"_" + s ( ) + ". x | " + "FO=" + s ( alo _ o) + "
| secs=" + s (secuencias) + " | ime ex=" + s ( 2-
1) + " n")
# Esc ibi alo es en las celdas
ws.cell( ow = ila, column = 2, alue = alo _ o)
ws.cell( ow = ila, column = 3, alue = s (secuencias))
ws.cell( ow = ila, column = 4, alue = ( 2- 1))
Anexo: Código de p og amación en Py hon 73
# Ob ene la u a a la ca pe a deseada
ca pe a = os.pa h.join(os.pa h.expanduse (’~’), ’Desk op TFG
’)
# De ini el nomb e del a chi o
a chi o_nomb e = ’LSL_ins _la ge.xlsx’
# C ea la u a comple a al a chi o
a chi o_ u a = os.pa h.join(ca pe a, a chi o_nomb e)
# Gua da el a chi o
wb.sa e(a chi o_ u a)
""""""
""""""""""""""""""""""""
##### RESULTADOS ESL INSTANCIAS PEQUEñAS #####
""""""""""""""""""""""""
om heu is icas_ 8 impo *
impo openpyxl
impo os
""" ESL PARA TODOS LOS ARCHIVOS (AUTOMATIZADO) """
# C eo a chi o pa a esul ados
wi h open(’ESL_INST_SMALL. x ’,’w’) as a chi o_ esul ados_ins _small:
a chi o_ esul ados_ins _small.w i e("")
# Esc ibo i ulo en x
wi h open("ESL_INST_SMALL. x ","a") as RESULTADOS:
RESULTADOS.w i e("RESULTADOS ESL: Ins ancia, Valo FO, Secuencias, Tiempo
de ejecución n")
# C ea un nue o lib o de abajo y selecciona la hoja ac i a
wb = openpyxl.Wo kbook()
ws = wb.ac i e
ila = 1
ws.cell( ow = ila, column = 1, alue = "Ins ancia")
ws.cell( ow = ila, column = 2, alue = "Valo FO")
ws.cell( ow = ila, column = 3, alue = "Secuencias")
ws.cell( ow = ila, column = 4, alue = "Tiempo ejecución")
o in ange(2,5):
o jj in ange(4,18,2):
o ii in ange(2,6):
o kk in ange(1,6):
# Ins ancias au oma izadas
a chi o=’DPFSP_DD/I_’ + s ( ) + ’_’ + s (jj) + ’_’ + s (ii)
+ ’_’ + s (kk) + ’. x ’
ins ancia=FlowShop(a chi o)
# Resul ados de cada ins ancia
80 Anexo: Código de p og amación en Py hon
1 = ime()
alo _ o, bes _seq_IG, alo es_g a ica_ig = ITERATED_GREEDY(d, T
_0, sec_ini ializ, local_sea ch, ins ancia, a chi o, iempo_
compilacion) #Tend e que da d, T_0, secuencia de
inicialización, mé odo búsqueda local y N (nume o de
i e aciones a ealiza )
2 = ime()
p in ("Valo F.O.:", alo _ o, "pa a la mejo secuencia IG:",
bes _seq_IG)
g a ica_IG( alo es_g a ica_ig, , jj, ii, kk)
# C ea ca pe a pa a gua da gan s
ca pe a = "RESULTADOS/small_ins ances/gan _IG/IG_gan _I_" +
s ( ) + "_" + s (jj) + "_" + s (ii) + "_" + s (kk)
i no os.pa h.exis s(ca pe a):
os.makedi s(ca pe a)
# Gene a y gua da gan s
o i in ange(len(bes _seq_IG)):
ins ancia.p in _schedule(bes _seq_IG[i],"RESULTADOS/small_
ins ances/gan _IG/IG_gan _I_" + s ( ) + "_" + s (jj)
+ "_" + s (ii) + "_" + s (kk) + "/ ac o y_" + s (i+1)
+ ".png")
# Esc ibi en x
wi h open("IG_INST_SMALL. x ","a") as RESULTADOS:
RESULTADOS.w i e(" nI_" + s ( ) + "_" + s (jj) + "_" + s
(ii) + "_" + s (kk) + ". x | " + "FO=" + s ( alo _ o)
+ " | secs=" + s (bes _seq_IG) + " | ime ex=" + s ( 2-
1) + " n")
# Esc ibi alo es en las celdas de excel
ws.cell( ow = ila, column = 2, alue = alo _ o)
ws.cell( ow = ila, column = 3, alue = s (bes _seq_IG))
ws.cell( ow = ila, column = 4, alue = ( 2- 1))
# Ob ene la u a a la ca pe a deseada
ca pe a = os.pa h.join(os.pa h.expanduse (’~’), ’Desk op TFG’)
# De ini el nomb e del a chi o
a chi o_nomb e = ’IG_ins _small.xlsx’
# C ea la u a comple a al a chi o
a chi o_ u a = os.pa h.join(ca pe a, a chi o_nomb e)
# Gua da el a chi o
wb.sa e(a chi o_ u a)
# Pa a compa a iempo con HDHHO
indice_ iempo += 1
""""""
""""""""""""""""""""""""
##### RESULTADOS IG INSTANCIAS GRANDES #####
""""""""""""""""""""""""
Anexo: Código de p og amación en Py hon 81
om heu is icas_ 8 impo *
impo openpyxl
impo os
""" ITERATED GREEDY PARA TODOS LOS ARCHIVOS (AUTOMATIZADO) """
# C eo a chi o pa a esul ados
wi h open(’IG_INST_LARGE. x ’,’w’) as a chi o_ esul ados_ins _la ge:
a chi o_ esul ados_ins _la ge.w i e("")
# Esc ibo i ulo en x
wi h open("IG_INST_LARGE. x ","a") as RESULTADOS:
RESULTADOS.w i e("RESULTADOS IG INST LARGE: Ins ancia, Valo FO, Secuencias
, Tiempo de ejecución. Pa a secuencia inicialización NEHDedd, d=0.2, T
_0=1 y búsqueda local RSLS. n")
# C ea un nue o lib o de abajo y selecciona la hoja ac i a
wb = openpyxl.Wo kbook()
ws = wb.ac i e
ila = 1
ws.cell( ow = ila, column = 1, alue = "Ins ancia")
ws.cell( ow = ila, column = 2, alue = "Valo FO")
ws.cell( ow = ila, column = 3, alue = "Secuencias")
ws.cell( ow = ila, column = 4, alue = "Tiempo ejecución")
ws.cell( ow = ila, column = 5, alue = "NEHDedd, d=0.2, T_0=1, RSLS")
iempo_compa a i o = [] # Lis a de iempo del HDHHO en cada ins ancia
indice_ iempo = 0
o pp in ange(2):
o qq in ange(10):
o in ange(10):
o in ange(2,8):
i (pp==0 and qq==0 and ==0):
b eak
else:
# Ins ancias au oma izadas
a chi o = ’DPFSP_DD/Ta’ + s (pp) + s (qq) + s ( ) + ’_’ +
s ( ) + ’. x ’
ins ancia=FlowShop(a chi o)
# Resul ados de cada ins ancia
sec_ini ializ = NEHDedd # P ocedimien o de inicialización de
la solución.
d = 0.2 # % de des ucción de los abajos.
T_0 = 1 # Pa áme o de empe a u a.
local_sea ch = RSLS # Mé odo de búsqueda local.
ila += 1
ws.cell( ow = ila, column = 1, alue = "Ta" + s (pp) + s (
qq) + s ( ) + "_" + s ( ) + ". x ")
82 Anexo: Código de p og amación en Py hon
iempo_compilacion = iempo_compa a i o[indice_ iempo]
1 = ime()
alo _ o, bes _seq_IG, alo es_g a ica_ig = ITERATED_GREEDY(d
, T_0, sec_ini ializ, local_sea ch, ins ancia, a chi o,
iempo_compilacion) #Tend e que da d, T_0, secuencia de
inicialización, mé odo búsqueda local y N (nume o de
i e aciones a ealiza )
2 = ime()
p in ("Valo F.O.:", alo _ o, "pa a la mejo secuencia IG:",
bes _seq_IG)
g a ica_IG_ins _la ge( alo es_g a ica_ig, pp, qq, , )
# C ea ca pe a pa a gua da gan s
ca pe a = "RESULTADOS/la ge_ins ances/gan _IG/IG_gan _Ta" +
s (pp) + s (qq) + s ( ) + "_" + s ( )
i no os.pa h.exis s(ca pe a):
os.makedi s(ca pe a)
# Gene a y gua da gan s
o i in ange(len(bes _seq_IG)):
ins ancia.p in _schedule(bes _seq_IG[i],"RESULTADOS/la ge
_ins ances/gan _IG/IG_gan _Ta" + s (pp) + s (qq)
+ s ( ) + "_" + s ( ) + "/ ac o y_" + s (i+1) +
".png")
# Esc ibi en x
wi h open("IG_INST_LARGE. x ","a") as RESULTADOS:
RESULTADOS.w i e(" nTa" + s (pp) + s (qq) + s ( ) +
"_" + s ( ) + ". x | " + "FO=" + s ( alo _ o) + "
| secs=" + s (bes _seq_IG) + " | ime ex=" + s ( 2-
1) + " n")
# Esc ibi alo es en las celdas de excel
ws.cell( ow = ila, column = 2, alue = alo _ o)
ws.cell( ow = ila, column = 3, alue = s (bes _seq_IG))
ws.cell( ow = ila, column = 4, alue = ( 2- 1))
# Ob ene la u a a la ca pe a deseada
ca pe a = os.pa h.join(os.pa h.expanduse (’~’), ’Desk op TFG
’)
# De ini el nomb e del a chi o
a chi o_nomb e = ’IG_ins _la ge.xlsx’
# C ea la u a comple a al a chi o
a chi o_ u a = os.pa h.join(ca pe a, a chi o_nomb e)
# Gua da el a chi o
wb.sa e(a chi o_ u a)
# Pa a compa a iempo con HDHHO
indice_ iempo += 1
""""""
""""""""""""""""""""""""
Anexo: Código de p og amación en Py hon 83
##### RESULTADOS HDHHO INSTANCIAS PEQUEñAS #####
""""""""""""""""""""""""
om heu is icas_ 8 impo *
impo openpyxl
impo os
""" HDHHO PARA TODOS LOS ARCHIVOS (AUTOMATIZADO) """
# C eo a chi o pa a esul ados
wi h open(’HDHHO_INST_SMALL. x ’,’w’) as a chi o_ esul ados_ins _small:
a chi o_ esul ados_ins _small.w i e("")
# Esc ibo i ulo en x
wi h open("HDHHO_INST_SMALL. x ","a") as RESULTADOS:
RESULTADOS.w i e("RESULTADOS HDHHO INST SMALL: Ins ancia, Valo FO,
Secuencias, Tiempo de ejecución. Pa a población=30 y N=200. n")
# C ea un nue o lib o de abajo y selecciona la hoja ac i a
wb = openpyxl.Wo kbook()
ws = wb.ac i e
ila = 1
ws.cell( ow = ila, column = 1, alue = "Ins ancia")
ws.cell( ow = ila, column = 2, alue = "Valo FO")
ws.cell( ow = ila, column = 3, alue = "Secuencias")
ws.cell( ow = ila, column = 4, alue = "Tiempo ejecución")
ws.cell( ow = ila, column = 5, alue = "POB=30, N=200")
o in ange(2,5):
o jj in ange(4,18,2):
o ii in ange(2,6):
o kk in ange(1,6):
# Ins ancias au oma izadas
a chi o=’DPFSP_DD/I_’ + s ( ) + ’_’ + s (jj) + ’_’ + s (ii)
+ ’_’ + s (kk) + ’. x ’
ins ancia=FlowShop(a chi o)
# Resul ados de cada ins ancia
am_pob = 30 # Tamaño de la población.
N = 200 # Núme o máximo de i e aciones.
ila += 1
ws.cell( ow = ila, column = 1, alue = "I_" + s ( ) + "_" +
s (jj) + "_" + s (ii) + "_" + s (kk) + ". x ")
1 = ime()
bes _Xp ey, bes _ i ness, alo es_ o_g a ica, plo _E = HDHHO(
ins ancia, N, am_pob, a chi o)
2 = ime()
p in ("bes Xp ey y bes i ness",bes _Xp ey,bes _ i ness)
g a ica_HDHHO( alo es_ o_g a ica, , jj, ii, kk)
g a ica_plo _E(plo _E)
84 Anexo: Código de p og amación en Py hon
# C ea ca pe a pa a gua da gan s
ca pe a = "RESULTADOS/small_ins ances/gan _HDHHO/HDHHO_gan _I
_" + s ( ) + "_" + s (jj) + "_" + s (ii) + "_" + s (kk)
i no os.pa h.exis s(ca pe a):
os.makedi s(ca pe a)
# Gene a y gua da gan s
o i in ange(len(bes _Xp ey)):
ins ancia.p in _schedule(bes _Xp ey[i],"RESULTADOS/small_
ins ances/gan _HDHHO/HDHHO_gan _I_" + s ( ) + "_" +
s (jj) + "_" + s (ii) + "_" + s (kk) + "/ ac o y_" +
s (i+1) + ".png")
# Esc ibi en x
wi h open("HDHHO_INST_SMALL. x ","a") as RESULTADOS:
RESULTADOS.w i e(" nI_" + s ( ) + "_" + s (jj) + "_" + s
(ii) + "_" + s (kk) + ". x | " + "FO=" + s (bes _
i ness) + " | secs=" + s (bes _Xp ey) + " | ime ex=" +
s ( 2- 1) + " n")
# Esc ibi alo es en las celdas de excel
ws.cell( ow = ila, column = 2, alue = bes _ i ness)
ws.cell( ow = ila, column = 3, alue = s (bes _Xp ey))
ws.cell( ow = ila, column = 4, alue = ( 2- 1))
# Ob ene la u a a la ca pe a deseada
ca pe a = os.pa h.join(os.pa h.expanduse (’~’), ’Desk op TFG’)
# De ini el nomb e del a chi o
a chi o_nomb e = ’HDHHO_ins _small.xlsx’
# C ea la u a comple a al a chi o
a chi o_ u a = os.pa h.join(ca pe a, a chi o_nomb e)
# Gua da el a chi o
wb.sa e(a chi o_ u a)
""""""
""""""""""""""""""""""""
##### RESULTADOS HDHHO INSTANCIAS GRANDES #####
""""""""""""""""""""""""
om heu is icas_ 8 impo *
impo openpyxl
impo os
""" HDHHO PARA TODOS LOS ARCHIVOS (AUTOMATIZADO) """
# C eo a chi o pa a esul ados
wi h open(’HDHHO_INST_LARGE. x ’,’w’) as a chi o_ esul ados_ins _la ge:
a chi o_ esul ados_ins _la ge.w i e("")
# Esc ibo i ulo en x
wi h open("HDHHO_INST_LARGE. x ","a") as RESULTADOS:
Anexo: Código de p og amación en Py hon 85
RESULTADOS.w i e("RESULTADOS HDHHO INST LARGE: Ins ancia, Valo FO,
Secuencias, Tiempo de ejecución. Pa a población=30 y N=200. n")
# C ea un nue o lib o de abajo y selecciona la hoja ac i a
wb = openpyxl.Wo kbook()
ws = wb.ac i e
ila = 1
ws.cell( ow = ila, column = 1, alue = "Ins ancia")
ws.cell( ow = ila, column = 2, alue = "Valo FO")
ws.cell( ow = ila, column = 3, alue = "Secuencias")
ws.cell( ow = ila, column = 4, alue = "Tiempo ejecución")
ws.cell( ow = ila, column = 5, alue = "POB=30, N=200")
o pp in ange(2):
o qq in ange(10):
o in ange(10):
o in ange(2,8):
i (pp==0 and qq==0 and ==0):
b eak
else:
# Ins ancias au oma izadas
a chi o = ’DPFSP_DD/Ta’ + s (pp) + s (qq) + s ( ) + ’_’ +
s ( ) + ’. x ’
ins ancia=FlowShop(a chi o)
# Resul ados de cada ins ancia
am_pob = 30 # Tamaño de la población.
N = 200 # Núme o máximo de i e aciones.
ila += 1
ws.cell( ow = ila, column = 1, alue = "Ta" + s (pp) + s (
qq) + s ( ) + "_" + s ( ) + ". x ")
1 = ime()
bes _Xp ey, bes _ i ness, alo es_ o_g a ica, plo _E = HDHHO(
ins ancia, N, am_pob, a chi o)
2 = ime()
p in ("Valo F.O.:", bes _ i ness, "pa a la mejo secuencia
HDHHO:", bes _Xp ey)
g a ica_HDHHO_ins _la ge( alo es_ o_g a ica, pp, qq, , )
g a ica_plo _E(plo _E)
# C ea ca pe a pa a gua da gan s
ca pe a = "RESULTADOS/la ge_ins ances/gan _HDHHO/HDHHO_gan
_Ta" + s (pp) + s (qq) + s ( ) + "_" + s ( )
i no os.pa h.exis s(ca pe a):
os.makedi s(ca pe a)
# Gene a y gua da gan s
o i in ange(len(bes _Xp ey)):
ins ancia.p in _schedule(bes _Xp ey[i],"RESULTADOS/la ge_
ins ances/gan _HDHHO/HDHHO_gan _Ta" + s (pp) + s
86 Anexo: Código de p og amación en Py hon
(qq) + s ( ) + "_" + s ( ) + "/ ac o y_" + s (i
+1) + ".png")
# Esc ibi en x
wi h open("HDHHO_INST_LARGE. x ","a") as RESULTADOS:
RESULTADOS.w i e(" nTa" + s (pp) + s (qq) + s ( ) +
"_" + s ( ) + ". x | " + "FO=" + s (bes _ i ness)
+ " | secs=" + s (bes _Xp ey) + " | ime ex=" + s
( 2- 1) + " n")
# Esc ibi alo es en las celdas de excel
ws.cell( ow = ila, column = 2, alue = bes _ i ness)
ws.cell( ow = ila, column = 3, alue = s (bes _Xp ey))
ws.cell( ow = ila, column = 4, alue = ( 2- 1))
# Ob ene la u a a la ca pe a deseada
ca pe a = os.pa h.join(os.pa h.expanduse (’~’), ’Desk op TFG
’)
# De ini el nomb e del a chi o
a chi o_nomb e = ’HDHHO_ins _la ge.xlsx’
# C ea la u a comple a al a chi o
a chi o_ u a = os.pa h.join(ca pe a, a chi o_nomb e)
# Gua da el a chi o
wb.sa e(a chi o_ u a)
""""""
""""""""""""""""""""""""
##### CALIBRADO IG #####
""""""""""""""""""""""""
om heu is icas_ 8 impo *
impo openpyxl
impo os
""" ITERATED GREEDY PARA TODOS LOS ARCHIVOS (AUTOMATIZADO) """
# C eo a chi o pa a esul ados
wi h open(’IG_TUNING_AUXILIAR_2. x ’,’w’) as a chi o_ esul ados_ uning:
a chi o_ esul ados_ uning.w i e("")
# Esc ibo i ulo en x
wi h open("IG_TUNING_AUXILIAR_2. x ","a") as RESULTADOS_TUNING_AUX:
RESULTADOS_TUNING_AUX.w i e("TUNING PARÁMETROS PARA IG: sec_ini ializ,
local_sea ch, d, T_0 n")
# C ea un nue o lib o de abajo y selecciona la hoja ac i a
wb = openpyxl.Wo kbook()
ws = wb.ac i e
ila = 1
ac o ies = [2,3,4,5,6,7]
jobs = [20,50,100]
Anexo: Código de p og amación en Py hon 87
machines = [5,10,20]
o ,num_ ac in enume a e( ac o ies):
o jj,num_jobs in enume a e(jobs):
o ii,num_maq in enume a e(machines):
o kk in ange(1,2):
# Ins ancias au oma izadas
a chi o=’TUNING/Ins ancias_ uning_aux_2/Tuning_’ + s (num_ ac )
+ ’_’ + s (num_jobs) + ’_’ + s (num_maq) + ’_’ + s (kk) +
’. x ’
ins ancia=FlowShop(a chi o)
# Resul ados de cada ins ancia
sec_ini ializ = [ESL, NEHDedd] # P ocedimien o de inicialización
de la solución.
d = [0.2, 0.3, 0.5] # % de des ucción de los abajos.
T_0 = [0.1, 0.4, 1, 10] # Pa áme o de empe a u a.
local_sea ch = [RSLS, RPLS] # Mé odo de búsqueda local.
sec_used = ["ESL","NEHDedd"] # Pa a excel
me _LS = ["RSLS","RPLS"] # Pa a excel
ila += 1
columna = 2
ws.cell( ow = ila, column = 1, alue = "T_" + s (num_ ac ) +
"_" + s (num_jobs) + "_" + s (num_maq) + "_" + s (kk) + ".
x ")
o q in ange(len(sec_ini ializ)):
o in ange(len(d)):
o s in ange(len(T_0)):
o in ange(len(local_sea ch)):
alo _ o, bes _seq_IG, alo es_g a ica_ig =
ITERATED_GREEDY(d[ ], T_0[s], sec_ini ializ[q
], local_sea ch[ ], ins ancia, a chi o) #
Tend e que da d, T_0, secuencia de
inicialización, mé odo búsqueda local y N (
nume o de i e aciones a ealiza )
p in ("Valo F.O.:", alo _ o, "pa a la mejo
secuencia IG:", bes _seq_IG)
g a ica_IG( alo es_g a ica_ig,0,0,0,0)
wi h open("IG_TUNING_AUXILIAR_2. x ","a") as
RESULTADOS_TUNING_AUX:
RESULTADOS_TUNING_AUX.w i e(" nT_" + s (num_
ac ) + "_" + s (num_jobs) + "_" + s (
num_maq) + "_" + s (kk) + ". x " + "sec
=" + s (sec_used[q]) + ", d=" + s (d[ ])
+ ", T_0=" + s (T_0[s]) + ", LS=" + s (
me _LS[ ]) + " " + s ( alo _ o) + " " +
s (bes _seq_IG) + " n")
# Esc ibi alo es en las celdas
88 Anexo: Código de p og amación en Py hon
ws.cell( ow = ila, column = columna, alue =
alo _ o)
p in ("columna:",columna)
i ila == 2:
ws.cell( ow = 1, column = columna, alue = "
sec=" + s (sec_used[q]) + ", d=" + s (d[
]) + ", T_0=" + s (T_0[s]) + ", LS=" +
s (me _LS[ ]))
# Ob ene la u a a la ca pe a deseada
ca pe a = os.pa h.join(os.pa h.expanduse (’~’), ’
Desk op TFG’)
# De ini el nomb e del a chi o
a chi o_nomb e = ’IG_ uning_auxilia _2.xlsx’
# C ea la u a comple a al a chi o
a chi o_ u a = os.pa h.join(ca pe a, a chi o_
nomb e)
# Gua da el a chi o
wb.sa e(a chi o_ u a)
columna += 1
""""""
""""""""""""""""""""""""
##### CALIBRADO HDHHO #####
""""""""""""""""""""""""
om heu is icas_ 8 impo *
impo openpyxl
impo os
""" HDHHO PARA TODOS LOS ARCHIVOS (AUTOMATIZADO) """
# C eo a chi o pa a esul ados
wi h open(’HDHHO_TUNING_AUXILIAR_2. x ’,’w’) as a chi o_ esul ados_ uning:
a chi o_ esul ados_ uning.w i e("")
# Esc ibo i ulo en x
wi h open("HDHHO_TUNING_AUXILIAR_2. x ","a") as RESULTADOS_TUNING_AUX:
RESULTADOS_TUNING_AUX.w i e("TUNING PARÁMETROS PARA HDHHO: amaño_poblacion
, max_i e aciones n")
# C ea un nue o lib o de abajo y selecciona la hoja ac i a
wb = openpyxl.Wo kbook()
ws = wb.ac i e
ila = 1
ac o ies = [2,3,4,5,6,7]
jobs = [20,50,100]
machines = [5,10,20]
o ,num_ ac in enume a e( ac o ies):
Anexo: Código de p og amación en Py hon 89
o jj,num_jobs in enume a e(jobs):
o ii,num_maq in enume a e(machines):
o kk in ange(1,2):
# Ins ancias au oma izadas
a chi o=’TUNING/Ins ancias_ uning_aux_2/Tuning_’ + s (num_ ac )
+ ’_’ + s (num_jobs) + ’_’ + s (num_maq) + ’_’ + s (kk) +
’. x ’
ins ancia=FlowShop(a chi o)
# Resul ados de cada ins ancia
am_pob = [10, 20, 30] # Tamaño de la población.
N = [50, 100, 200] # Núme o máximo de i e aciones.
ila += 1
columna = 2
ws.cell( ow = ila, column = 1, alue = "T_" + s (num_ ac ) +
"_" + s (num_jobs) + "_" + s (num_maq) + "_" + s (kk) + ".
x ")
o q in ange(len( am_pob)):
o in ange(len(N)):
bes _Xp ey, bes _ i ness, alo es_ o_g a ica, plo _E =
HDHHO(ins ancia, N[ ], am_pob[q], a chi o)
p in ("bes Xp ey y bes i ness",bes _Xp ey,bes _ i ness
)
g a ica_HDHHO( alo es_ o_g a ica)
g a ica_plo _E(plo _E)
wi h open("HDHHO_TUNING_AUXILIAR_2. x ","a") as
RESULTADOS_TUNING_AUX:
RESULTADOS_TUNING_AUX.w i e(" nT_" + s (num_ ac ) +
"_" + s (num_jobs) + "_" + s (num_maq) + "_" +
s (kk) + ". x " + " am_pob=" + s ( am_pob[q]) +
", num_i e =" + s (N[ ]) + " " + s (bes _
i ness) + " " + s (bes _Xp ey) + " n")
# Esc ibi alo es en las celdas
ws.cell( ow = ila, column = columna, alue = bes _
i ness)
p in ("columna:",columna)
i ila == 2:
ws.cell( ow = 1, column = columna, alue = " am_pob="
+ s ( am_pob[q]) + ", num_i e =" + s (N[ ]))
# Ob ene la u a a la ca pe a deseada
ca pe a = os.pa h.join(os.pa h.expanduse (’~’), ’Desk op
TFG’)
# De ini el nomb e del a chi o
a chi o_nomb e = ’HDHHO_ uning_auxilia _2.xlsx’
# C ea la u a comple a al a chi o
a chi o_ u a = os.pa h.join(ca pe a, a chi o_nomb e)
