In e na ional Con e ence on Indus ial Enginee ing & Indus ial Managemen -
In e na ional Con e ence on Indus ial Enginee ing & Indus ial Managemen -
CIO 2007
1343
Compa ación de dos medidas de la efi ciencia de algo i mos pa alelos
José Miguel León Blanco, José Manuel F amiñán To es, Ped o L. González-R,
Paz Pé ez González, Ra ael Ruiz-Usano
1
Dp o. de O ganización. Escuela Supe io de Ingenie os. Uni e sidad de Se illa. Camino de los
Descub imien os s/n. 41092. Se illa. [email p o ec ed], [email p o ec ed], [email p o ec ed],
[email p o ec ed], [email p o ec ed]
Resumen
Se compa an, en es e abajo, dos posibilidades pa a medi la efi ciencia de un algo i mo pa alelo, o
su capacidad de ap o echa los ecu sos de un sis ema in o má ico pa alelo. Po un lado, median e
la compa ación de los iempos de ejecución con uno y a ios p ocesado es. Po o o, median e
la compa ación de la calidad de las soluciones ob enidas cuando se emplea el mismo núme o de
i e aciones con uno y con a ios p ocesado es. Los esul ados en cuan o a dispe sión de los alo es
de efi ciencia pa a di e en es amaños de p oblema, lle an a plan ea la aplicabilidad de ambas
medidas a uno o a o o ipo de sis ema pa alelo.
Palab as cla e:
Algo i mo pa alelo, efi ciencia, me aheu ís ica
1. In oducción
Uno de los pa áme os más empleados pa a conoce la calidad de un algo i mo pa alelo es
su efi ciencia, que mide el ap o echamien o que hace de los p ocesado es que con o man el
sis ema de compu ación. En es e abajo se compa an, pa a el p oblema de secuenciación de
abajos en fl ujo uni o me sin es icciones de capacidad, dos o mas de medi la efi ciencia
que apa ecen con ecuencia en la li e a u a sob e algo i mos pa alelos: po un lado, el iempo
de ejecución y, po o o, el núme o de i e aciones que debe ealiza el algo i mo pa alelo en
elación al algo i mo secuencial
*
.
2. Efi ciencia en algo i mos pa alelos
La defi nición de efi ciencia de un algo i mo pa alelo median e el iempo de ejecución sigue la
exp esión (1):
(1)
donde
1
es el iempo necesa io pa a encon a una solución cuando se emplea un solo p ocesado
y
n
es el empleado en encon a una solución de la misma calidad que la que se encon ó con
un p ocesado empleando aho a
n
p ocesado es. El p ime obje i o de un algo i mo pa alelo es
mejo a el iempo de esolución de p oblemas en e al algo i mo secuencial, pa a ap o echa la
po encia que o ecen a ios p ocesado es abajando de o ma simul ánea. De es e modo, cuando
la efi ciencia se ace ca a 1 (100%), el iempo necesa io con n p ocesado es es in e samen e
p opo cional al núme o de los mismos y se es á ap o echando casi oda la po encia de cálculo
disponible.
*
Es e abajo se de i a de la pa icipación de sus au o es en el p oyec o de in es igación fi nanciado po CICYT con
e e encia DPI-2004-02902 i ulado “Sis emas A anzados de Secuenciación y Con ol”.
1344
Quan i a i e Me hods
O os au o es como Wodecki y Bozejko (2002) emplean el núme o de i e aciones que ealiza
cada uno de los p ocesos pa a con as a la efi ciencia del algo i mo. No se mide aho a el iempo
empleado po el algo i mo sino la calidad de las soluciones ob enidas. Si se ob iene una solución
de mejo calidad con más p ocesado es pe o el mismo núme o o al de i e aciones, el algo i mo
iene una efi ciencia supe io a la unidad. Se puede deci que cada i e ación, al emplea más
p ocesado es, p oduce un mayo sal o en la calidad que cuando se emplean menos p ocesado es,
debido en la mayo ía de los casos a la comunicación en e los dis in os p ocesos.
Es a medida de la efi ciencia iene la limi ación de que pa a man ene cons an e el núme o
o al de i e aciones, debe obliga se a que cada uno de los p ocesos ealice un núme o cada
ez meno de i e aciones. Cuando se emplean p ocedimien os no de e minis as, es posible que
en bas an es ejecuciones del algo i mo no se llegue a la calidad de soluciones ob enidas con
un solo p ocesado . La en aja de es e mé odo es limi a la expe imen ación a un núme o de
i e aciones conocido de an emano, con lo que el mé odo end á mayo alidez en algo i mos
que emplean g an núme o de i e aciones, ípicamen e algo i mos de g ano fi no.
3. Expe imen ación
En la expe imen ación, hemos empleado una e sión en pa alelo del algo i mo CLM de Ghosh
y Sie ksma (2002) aplicado al p oblema de la secuenciación de abajos en fl ujo uni o me
sin es icciones de capacidad, con el obje i o de minimiza el
makespan
. El esquema de
uncionamien o del algo i mo pa alelo es el p esen ado en el abajo de León e al (2006), cuyo
seudocódigo es el siguien e:
P oceso mas e :
1. En ío inicial: Pa a cada p oceso escla o
1.1. Se gene a una solución alea o ia y dis in a pa a cada p oceso
1.2. Se añade al pool cen al
1.3. Se en ía la solución al p oceso escla o
2. Mien as el núme o o al de i e aciones sea meno al fi jado
2.1. Se eciben las b mejo es soluciones de un p oceso escla o
2.2. Se almacenan en el pool cen al las que sean dis in as de las exis en es
2.3. Se gene a una nue a solución de pa ida pa a el p oceso escla o
2.4. Se gene a una nue a polí ica de explo ación pa a ese p oceso
2.5. Se en ía la solución de pa ida jun o con la polí ica de explo ación
3. Se en ía una señal de pa ada a los p ocesos escla os
P oceso escla o:
1. Recibe la solución inicial del p oceso mas e jun o con la polí ica de explo ación
2. Se incluye en la lis a LIVE
3. Mien as no se eciba la señal de pa ada
3.1. Pa a un núme o de i e aciones dado y la lis a LIVE no es é acía
3.1.1. Se oman k soluciones de la lis a LIVE
3.1.2. Se pasan a la lis a DEAD
3.1.3. Se ac ualiza el umb al de acep ación de soluciones
3.1.4. Se gene an soluciones ecinas de cada una de las an e io es, ales que es én
den o del umb al de acep ación
3.1.5. Si no es án en ninguna de las lis as, se incluyen en la lis a NEWGEN
3.1.6. Si alguna mejo a la mejo solución has a el momen o, se ac ualiza el alo del
mínimo
In e na ional Con e ence on Indus ial Enginee ing & Indus ial Managemen -
In e na ional Con e ence on Indus ial Enginee ing & Indus ial Managemen -
CIO 2007
1345
3.1.7. Se pasan odas las soluciones de NEWGEN a LIVE
3.2. Pos p oceso: Se pasan odas las soluciones que queden en la lis a LIVE a DEAD
después de una búsqueda local
3.3. Se en ían las B mejo es soluciones de la lis a DEAD al p oceso mas e
3.4. Se acían las lis as DEAD y POOL
3.5. Recibe la siguien e solución de pa ida jun o con la polí ica de explo ación y la señal de
con inua o pa a del mas e
3.6. Si no ecibe la señal de pa ada, ecibe ambién las soluciones de la lis a cen al y las
almacena en la lis a POOL.
Pa a educi el iempo o al de expe imen ación, las ejecuciones del algo i mo en un solo
p ocesado se han ealizado pa a un o al de 10 i e aciones, con lo que ob enemos una des iación
po cen ual en p omedio (ARPD) espec o a las o ecidas po los expe imen os de la ba e ía de
Tailla d (1993) del 2,13%. Se han ep esen ado los alo es de la efi ciencia en p omedio pa a
cada amaño de p oblema po 3 ejecuciones pa a cada uno de los p oblemas de amaño 20x20
has a 200x20. La efi ciencia del algo i mo es muy educida, e abla 1, aunque la con e gencia
sea muy ápida, ya que se es á empleando un algo i mo pa alelo de ipo sínc ono.
3.2. Medición de la efi ciencia según el iempo de ejecución
Tabla 1.
Efi ciencia según iempo de ejecución, de 3 a 12 p ocesado es, ag upada po amaño de p oblema
e3
e6
e9
e12
20x20
74,90%
39,70%
25,60%
17,90%
50x5
45,10%
25,30%
12,70%
12,40%
50x10
29,70%
19,50%
26,70%
20,20%
50x20
59,70%
29,60%
31,60%
20,00%
100x5
11,80%
5,90%
8,50%
7,70%
100x10
23,40%
11,70%
8,40%
14,80%
100x20
55,20%
27,58%
26,27%
24,58%
200x10
27,50%
13,80%
13,50%
11,10%
200x20
41,00%
42,50%
23,80%
22,60%
Se p esen an, a con inuación, en o ma de g áfi co (Figu a 1), los esul ados an e io es, pa a
pone de manifi es o algunos pun os con anomalías, po ejemplo en el caso de la efi ciencia
medida con 9 p ocesado es, mayo que la ob enida con 6 pa a los p oblemas de 50 abajos
y 10 ó 20 máquinas. Pa a más cla idad, se han ag upado po un lado los p oblemas de mayo
dimensión, 100 y 200 abajos (Figu a 2) y po o o los de 50 o menos abajos (Figu a 1).
El mismo ipo de anomalías se obse an (Figu a 2) pa a algunos de los p oblemas de mayo
dimensión.
3.3. Medición de la efi ciencia según el núme o de i e aciones
En el caso de la medición de la efi ciencia compa ando el núme o de i e aciones, deben hace se
a ias conside aciones ela i as al mé odo empleado pa a llega a las ci as p esen adas. Pa a
con a el núme o o al de i e aciones ealizadas po odos los p ocesos, se han con ado cada
una de las eces que los p ocesos abajado es e minan su explo ación y se comunican con el
p oceso je e.
1346
Quan i a i e Me hods
Figu a 1.
Efi ciencia según el iempo de ejecución pa a p oblemas de 20 y 50 abajos
Figu a 2.
Efi ciencia según el iempo de ejecución pa a p oblemas de 100 y 200 abajos
En gene al, las ci as ob enidas con es e mé odo son supe io es a las ob enidas midiendo el
iempo de ejecución.
Po o o lado, no se ha empleado el concep o p esen ado po Wodecki y Bozejko (2002), que
medían la calidad de las soluciones ob enidas con el mismo núme o de i e aciones, sino que se
han compa ado el o al de i e aciones ealizadas po odos los p ocesos con las 10 i e aciones
empleadas po el algo i mo secuencial pa a llega a la calidad de soluciones mos ada.
In e na ional Con e ence on Indus ial Enginee ing & Indus ial Managemen -
In e na ional Con e ence on Indus ial Enginee ing & Indus ial Managemen -
CIO 2007
1347
Tabla 2.
Efi ciencia según el núme o de i e aciones ag upada po amaño de p oblema
e3
e6
e9
e12
20x20
133,30%
50,50%
17,50%
23,70%
50x5
69,40%
25,50%
14,90%
32,80%
50x10
31,70%
15,10%
14,10%
8,50%
50x20
50,80%
19,60%
13,90%
14,30%
100x5
98,00%
18,30%
14,60%
12,80%
100x10
41,50%
19,50%
15,40%
7,90%
100x20
39,70%
23,40%
13,90%
9,10%
200x10
44,60%
15,30%
11,80%
9,10%
200x20
34,70%
27,10%
23,10%
15,00%
Figu a 3.
Efi ciencia según el núme o de i e aciones pa a p oblemas de 20 y 50 abajos
Figu a 4.
Efi ciencia según el núme o de i e aciones pa a p oblemas de 100 y 200 abajos

1348
Quan i a i e Me hods
4. Conclusiones y ampliaciones del abajo
Se obse an esul ados dispa es en e ambas o mas de medi la efi ciencia del algo i mo. Aunque,
en gene al, la efi ciencia decae con el núme o de p ocesado es, los alo es obse ados no siguen
el mismo compo amien o en ambos casos. Po ejemplo, midiendo el iempo de ejecución, la
efi ciencia ob enida con p oblemas de dimensión 100x20 ( abla 1 y fi gu a 2) es mejo que la
ob enida con p oblemas de dimensión 200x10. En cambio, con ando el núme o de i e aciones
( abla 2 y fi gu a 4), nos encon amos con alo es de efi ciencia p ác icamen e idén icos. Puede
hace se es a compa ación pa a o as dimensiones de p oblema.
Po la dispa idad de los esul ados ob enidos, el empleo del núme o de i e aciones como medida
de la efi ciencia de un algo i mo pa alelo se ha e elado como un p ocedimien o al amen e
inexac o compa ado con el esul ado de medi el iempo de compu ación y debe ía es ingi se
a aquellos casos en los que no se disponga de o os elemen os pa a juzga la efi ciencia del
algo i mo. En gene al
En equipos con o a ipología como las edes de anspu e s, pod ían emplea se más i e aciones,
con lo que posiblemen e se ace ca ían los esul ados de ambas mediciones, y po an o con
dispe sión en los esul ados se end ía una buena medida de la efi ciencia. De es e modo puede
ap o echa se la sencillez de compa a efi ciencias median e el núme o de i e aciones en e al
iempo de ejecución. El p oblema aho a se plan ea ía en elación con el ipo de algo i mo y las
posibilidades de emplea lo en sis emas de bajo cos e o mados po edes de o denado es ipo
PC, más ácilmen e disponibles.
Una ex ensión a la in es igación ealizada se ía el análisis es adís ico de los esul ados, que nos
da ía una medida cuan i a i a de la dispe sión de los mismos y de la di e encia en e las dos
medidas que se es án compa ando.
Re e encias
Alba, E. (2005). Pa allel Me aheu is ics. A new class o Algo i hms. John Wiley & Sons.
Bozejko, W.; Wodecki, M. (2004). The New Concep s in Pa allel Simula ed Annealing Me hod.
L. Ru kowski e al. (Eds.): ICAISC 2004, LNAI 3070, pp. 853–859.
Ghosh, D.; Sie ksma, G. (2002). Comple e Local Sea ch wi h Memo y. Jou nal o Heu is ics,
No. 8, pp. 571-584. Kluwe .
León, J.M.; F amiñán, J.M.; González-R., P.L.; Pé ez, P. (2006). Infl uencia de la g anula idad
en las p es aciones de algo i mos pa alelos. X Cong eso de Ingenie ía de O ganización.
Tailla d, E. (1993). Benchma ks o basic scheduling p oblems. Eu opean Jou nal o Ope a ional
Resea ch, Vol. 64, pp. 278-285.
Wodecki, M.; Bozejko, W. (2002). Sol ing he Flow Shop P oblem by Pa allel Simula ed
Annealing. R. Wy zykowski e al. (Eds.): PPAM 2001, LNCS 2328, pp. 236–244.