III Jo nadas de Ingenie ía de O ganización
Ba celona, 16-17 de sep iemb e de 1999
UNA VISIÓN SOBRE EL PROBLEMA DE
PROGRAMACIÓN DE TRANSPORTADORES
Ma eo, M.1; Companys, R.2; Bau is a, J.1
1 Depa amen o de O ganización de Emp esas e Ins i u o de O ganización y Con ol
ETSEIB. Uni e sidad Poli écnica de Ca aluña
e-mails: mma [email protected], bau is [email protected]
2 Depa amen o de O ganización de Emp esas
ETSEIB. Uni e sidad Poli écnica de Ca aluña
e-mail: [email p o ec ed]
RESUMEN
El p oblema HSP (Hois Scheduling P oblem) consis e en es ablece la
p og amación de los mo imien os de anspo ado es que deben aslada
piezas o con enedo es a a és de una línea de p oducción compues a po
di e sas es aciones o baños, pa a el cual se p esen a los modelos asociados
a algunas a ian es. Los iempos de ope ación no son ijos, sino aco ados
in e io y supe io men e. El aslado de obje os en e es aciones lo ealizan
uno o a ios anspo ado es, que consumen un iempo mayo en ca ga que
en acío. El obje i o es es ablece una secuencia de mo imien os del
anspo ado pa a maximiza la asa de p oducción del sis ema.
Palab as cla e: p og amación, secuenciación, HSP.
1. INTRODUCCIÓN
En una pa e del sis ema p oduc i o de emp esas dedicadas a la ab icación de
ci cui os in eg ados imp esos, se u iliza una secuencia de eacciones químicas que
ac úan sob e las placas. Dichas placas son sume gidas secuencialmen e en una
se ie de anques que con ienen las soluciones. Las placas se anspo an en
con enedo es median e anspo ado es o g úas aé eos, que consumen un iempo
impo an e. Es o lo con ie e en cuello de bo ella del sis ema p oduc i o.
Un p oceso de es e ipo equie e de 10 a 20 inme siones di e en es, pa a las cuales
se es ablece un iempo mínimo en que la placa debe es a sume gida en cada
anque de p oceso y, pa a la mayo ía, un iempo máximo de inme sión.
O as ca ac e ís icas obse ables en es as líneas de p oducción ( igu a 1) son:
• Todos los anques se encuen an alineados.
• Las placas se colocan en un con enedo en un ex emo de la línea (es ación de
ca ga).
• El con enedo se desplaza en e anques di e en es anspo ado po una g úa.
• Habi ualmen e, en un ins an e de e minado, se puede encon a más de un
con enedo en el sis ema, cada uno de los cuales debe pasa po la misma
secuencia de ope aciones.
• En ningún caso, dos con enedo es pueden ocupa un mismo anque.
• Después de deja un con enedo , la g úa puede queda lib e del con enedo y
aslada se a o o baño, donde ecoge á o o con enedo . Después de le an a
un con enedo , si se ecoge de un anque con con enido líquido, el
anspo ado debe pa a sob e el anque pa a escu i .
• Cuando un con enedo inaliza odas sus inme siones, se di ige a la es ación de
desca ga, donde se ex aen las placas del con enedo .
Figu a 1: Esquema de un p oceso de gal anización.
A menudo, se plan ean a iaciones a es a si uación básica, como con igu aciones
al e na i as en las ope aciones de ca ga y desca ga, o en la secuencia de anques,
anspo ado es adicionales pa a epa i las ope aciones de anspo e, o anques
con p ocesos duplicados pa a inc emen a la p oducción.
2. DESCRIPCIÓN DEL HOIST SCHEDULING PROBLEM
2.1. P incipales ca ac e ís icas del p oblema
La si uación plan eada en la ab icación de componen es elec ónicos se suele
o maliza de una mane a más simple, conocida como HSP (Hois Scheduling
P oblem), de la que se a a a a en adelan e.
Se supone que deben p ocesa se M obje os o con enedo es (j=1,...,M) ecibiendo
un a amien o o una ope ación en N baños, anques o es aciones dis in as
(i=1,...,N). Es os M obje os pueden se odos ellos idén icos o bien di e en es en e
sí. La pe manencia de una de e minada pieza j en cada es ación debe du a un
iempo comp endido en e un alo mínimo ai,j y un máximo bi,j. Si odos los
obje os son iguales, los alo es sólo dependen de la es ación:
ai : iempo mínimo que un con enedo debe pe manece en un anque i,
bi : iempo máximo que un con enedo puede pe manece en un anque i.
Uno o a ios anspo ado es se enca gan de ealiza el mo imien o de obje os
en e las es aciones co espondien es a dos a amien os consecu i os. La es ación
de ca ga se co esponde al pun o de en ada de los obje os en el sis ema, mien as
que la es ación de desca ga se co esponde al pun o de salida. El iempo de
mo imien o del anspo ado no es desp eciable en e a las o as magni udes
empo ales del p oblema. Suponiendo los anques o denados según las e apas del
p oceso, y pa a un único ipo de obje os, se de inen:
c1i : iempo que anscu e desde que el anspo ado e i a el obje o del
anque i has a que se deposi a en el anque i+1,
c0i,j : iempo que anscu e en el mo imien o del anspo ado sin ca ga
desde el anque i has a el anque j.
En es e ipo de p oblemas, siemp e se cumplen dos p opiedades ela i as al
iempo de mo imien o de los anspo ado es:
1) c0i,j = c0j,i
2) c1i > c0i,i+1 pues c1i = c0i,i+1 + T
T es un iempo cons an e pa a subi y baja el con enedo más el de amo igua la
oscilación del anspo e an es de coloca el con enedo en el anque. Es e iempo
no es necesa io si el anspo ado se mue e sin ca ga en e anques.
Todo es o plan ea un p oblema combina o io, cuyo obje i o es minimiza el
iempo de ocupación de las ins alaciones, pa a así inc emen a al máximo la
p oduc i idad.
2.2. Clasi icación de a ian es en el p oblema HSP
El Hois Scheduling P oblem puede plan ea di e sas si uaciones en unción de
las ca ac e ís icas que p esen en los elemen os p opios del sis ema: baños,
p oduc os y anspo ado es.
Así, los anques de la cadena p oduc i a pueden se de di e en es ipos:
• mono-baño, cuando un anque sólo puede a a un con enedo a la ez;
• mul i-baño, cuando el anque pe mi e a a más de un con enedo a la ez, po
ene compa imen os, o ambién cuando exis en anques epe idos de un
mismo ipo.
Po o o lado, según el núme o de ope aciones dis in as a ealiza se sob e un
obje o en dicho baño, los anques se clasi ican en e:
• mono- unción, si sólo ealizan un a amien o especí ico sob e los obje os;
• mul i- unción, en caso de más de un a amien o sob e los obje os.
Si se obse a los ipos de p oduc os a ados en el p oceso, és os pueden se :
• homogéneos, si se a a de di e sas unidades de un único ipo;
• he e ogéneos, si se a a de unidades di e en es en e sí.
Es a clasi icación compo a di e en es ipos de p og amación de ope aciones pa a
los anspo ado es. En caso de obje os homogéneos, la p oblemá ica se epi e de
mane a cíclica, y el obje i o es halla una secuencia de ope aciones en las
di e en es e apas al que pueda epe i se con inuamen e y que minimice el iempo
de ciclo. Mien as, en caso de obje os he e ogéneos se gene an si uaciones
di e sas, cada una de las cuales pa e de un es ado inicial del sis ema acío y
inaliza cuando la úl ima pieza abandona el sis ema. Po an o, la unción obje i o
minimiza el ins an e de inalización de p oceso del úl imo con enedo .
Finalmen e, la es a egia de búsqueda de secuencias ambién depende del núme o
de anspo ado es o g úas del sis ema.
Combinando es os es g upos de in o mación, es posible es ablece el es ado del
sis ema de e minado po :
• El núme o y la localización de las g úas.
• El núme o, ipo y la localización de los obje os o con enedo es.
• Los iempos de emojo anscu idos en los baños po cada obje o, a cada
momen o.
2.3. Apo aciones his ó icas al p oblema
El Hois Scheduling P oblem como p oblema de p og amación se puede clasi ica
en e los p oblemas de lujos de piezas “ low-shop” o “job-shop” y los p oblemas
de una sola máquina, en caso de un solo anspo ado pa a di e sas a eas.
Manie y Bap is e (1994) de ec a on has a hace unos cinco años ela i amen e
pocos abajos sob e el ema, si bien en es e iempo se ha egis ado un inc emen o
en las apo aciones. No malmen e, se a a de es udios del caso mono-g úa,
p oduc os homogéneos y con ecipien es mono-baño y mono- unción.
Dichos a ículos buscan una secuencia de mo imien os óp ima, p og amando a las
g úas pa a que espe en esc upulosamen e las echas de inalización de los
p oduc os, y suponiendo que el sis ema padece escasas in e upciones imp e is as.
Pa iendo de Philips y Unge (1976), que plan ean un p og ama lineal mix o
en e o, Shapi o y Nu le (1988) y A ms ong e al. (1994) aplican la p og amación
lineal en el con ex o de un p ocedimien o de b anch & bound. Au o es como
Bap is e e al. (1992) y Va nie e al. (1995) han in oducido alguna o a écnica
e ec i a, como la p opagación lógica de es icciones, p o iniendo del campo de
la in eligencia a i icial.
Finalmen e, un conjun o de a ículos, como los apo ados po Yih (1988) y Thesen
y Lei (1990), p esen a un con ol sob e la g úa bajo eglas heu ís icas pa a
de e mina echas de en ada de los sucesi os p oduc os, o lo es de p oduc os, y
es ablece secuencias de mo imien os. Es a ap oximación es sumamen e ú il
cuando se abaja simul áneamen e con di e sos p oduc os en la línea.
3. LÍNEAS DE PRODUCCIÓN CON OBJETOS IDÉNTICOS
Los amaños de lo e pa a es e ipo de líneas suelen se bas an e g andes, po lo que
pasan días e incluso semanas en e cambios en la p og amación. Po an o, las
g úas se con olan numé icamen e median e una secuencia ijada de ope aciones
que se epi e inde inidamen e, secuencia cíclica. Es a si uación se enma ca á en el
caso más básico, con una g úa que isi a ecipien es mono-baño y mono- unción.
3.1. Hipó esis del modelo ma emá ico a plan ea
Las hipó esis de pa ida en que se basa el modelo plan eado son:
1. El iempo de p oceso en cada es ación debe es a en e el in e alo dado.
2. El anspo e de los obje os lo ealiza una única g úa.
3. La ope ación de anspo e no se puede in e umpi .
4. La es ación de ca ga iene los obje os p epa ados cuando llega la g úa.
5. El anque i debe es a acío cuando llega un obje o.
6. Todos los anques es án o denados según las e apas del p oceso.
7. Todos los p oduc os a ados son idén icos y siguen una misma u a.
El obje i o consis e, pues, en minimiza el iempo de ciclo de las acciones de un
único anspo ado pa a un conjun o de p oduc os homogéneos que deben pasa
po N e apas, con un anque asignado a cada una de las cuales y es icciones de
en ana. Es o implica que la du ación de inme sión de un con enedo en un baño
sea idén ica pa a odos los p oduc os y que la solución buscada sea pe iódica.
3.2. Las secuencias de mo imien os y iempos
Sean mi, mo imien o del obje o del baño i al baño i+1, 0≤ i ≤ N; i, iempo de
inicio del mo imien o mi. Una secuencia cíclica (M,T) se de ine a pa i de:
1. Secuencia (o den de mo imien os): M = <m[0], m[1], ..., m[k], ..., m[N]>
2. Tiempos de inicio de los mo imien os: T = < [0], [1], ..., [k], ..., [N]>
La secuencia M es una pe mu ación ci cula de los N+1 baños a isi a po el
anspo ado . Las exp esiones m[k] = mj; [k] = j indican que el mo imien o de

anspo e del con enedo en e los baños i e i+1 ocupa la k-ésima posición de la
secuencia, omando como p ime mo imien o aquél que pa e de la es ación de
ca ga: m[0] = 0; [0] = 0. Finalmen e, la secuencia de iempos debe cumpli que
[0] < [1] < ... < [N], siendo el iempo de ciclo TC(M,T) = [N+1].
3.3. Fo mulación del p og ama lineal ma emá ico PL(M)
Si bien el modelo plan eado puede esol e se con di e en es p ocedimien os, uno
p ime o conside a las elaciones empo ales en los baños y en mo imien os del
anspo ado siguiendo el esquema de un p og ama lineal unción del ec o M.
Se dispone como pa ida de es g upos de da os, ya de inidos en apa ados
an e io es:
1. Res icciones de en ana (pa a cada baño): ai, bi pa a i = 1,2, ...,N
2. Tiempos de mo imien o: c1i, c0i,j pa a i = 1,2, ...,N; 0 ≤ i,j ≤ N+1
3. Secuencia de mo imien os: M = <m[0]=0, m[1], ..., m[N]>
Las a iables cuyos alo es deben halla se en es e p og ama lineal son:
1. Tiempo de inicio de mo imien os: T = < [0], [1], ..., [N]>
2. Tiempo de ciclo: TC(M,T) = [N+1]
siendo i el ins an e en el cual que se ex a un con enedo del anque i (i=0,1,..., N)
y TC, el inicio del mo imien o N+1, o sea, el siguien e mo imien o inicial [0].
Dichas a iables se encuen an some idas a dos ipos de es icciones:
1. Res icciones de iempo de p oceso del obje o en un anque:
si se inicia el ciclo con el anque i acío: ai ≤ i – ( i-1+c1i) ≤ bi
si se inicia el ciclo con el anque i lleno: ai ≤ TC+ i – ( i-1+c1i) ≤ bi
2. Res icciones de iempo de iaje de la g úa: [k] - [k-1] ≥ c1[k-1] + c0[k-1]+1,[k]
omando como obje i o:
[MIN] TC(M,T) = [N+1]
Dada una secuencia de ope aciones M, el p og ama lineal cuen a, pues, con N+1
a iables y 2N+1 es icciones.
3.4. La al e na i a: la esolución median e g a o
El modelo an e io puede plan ea se y esol e se median e un g a o, sin necesidad
de ecu i a la p og amación lineal. Es e mé odo al e na i o, cuya línea de abajo
plan ea Fe nández (1995), se denomina MCM (Mé odo del Camino Mínimo).
Los nodos de dicho g a o son los anques a los que la g úa se desplaza con ca ga,
en caso de ene que deposi a un obje o, o sin ca ga, si a a ecoge se un obje o:
• los nodos de salida co esponden a anques de ecogida (se llega sin ca ga);
• los nodos de llegada co esponden a anques de depósi o (se llega con ca ga).
Los alo es en los a cos se asocian a los iempos (de la g úa o de los obje os):
• los a cos de p oceso son debidos a la pe manencia de los obje os en los baños:
alo es mínimos, ai, y máximos, bi;
• los a cos de mo imien o son debidos a desplazamien os del anspo ado : con
ca ga, c1i y sin ca ga: c0i,j.
4. PROCEDIMIENTO BASADO EN BRANCH & BOUND
Dada una secuencia M, de e mina si es secuencia ac ible, y en dicho caso, halla
el iempo de ciclo óp imo TC*(M,T) implica e alua N! secuencias, es deci :
TC*(M*,T*) = Min { TC(M,T) | ∀ (M,T) ac ible }
Se pueden selecciona p ocedimien os heu ís icos o exac os, como el siguien e, el
cual sigue un esquema de b anch & bound con las siguien es ca ac e ís icas:
1. Ca ac e ización de los é ices de la a bo escencia: El núme o de ni eles de la
a bo escencia es el mismo que el núme o de anques del p oceso, N, siendo el
núme o de nodos del ni el i (i=1,2,...,N) = i! Un nudo o é ice de ni el i puede
de ini se como: P[0][i] = <m[0], m[1], ..., m[i]>, que co esponde a una pe mu ación
de {m[0]=m0, mj | j=1,2,...,i}.
2. P ocedimien o de sepa ación: Cada P[0][i] = <m[0], m[1], ..., m[i]> se ob iene
inse ando mi en e dos mo imien os de P[0][i-1]. Así pues, el núme o de
descendien es de un nudo P[0][i] es de i+1, que se an c eando a pa i del nudo aíz
P[0][1] o mado po los mo imien os: P[0][1] = <m[0], m[1]>.
3. P ocedimien o de aco ación. Pa a cada nudo P[0][i] = <m[0], m[1], ..., m[i]> debe
esol e se el p og ama lineal PL(M) aplicando el MCM, que puede compo a dos
ipos de esul ado: pe mu ación de mo imien os no ac ible o ac ible con
TC(Mi,Ti). Sea Ui, el conjun o de mo imien os no asignados en la pe mu ación
P[0][i]; una co a in e io del iempo de ciclo inco po ando los mo imien os no
asignados mj∈Ui a una P[i][j] se calcula como:
TIn (P[i][j]) = TC(Mi,Ti)+max{ ∑(mj∈Ui) c1j - ∑(0≤ ≤1) e }
siendo ∑e el iempo mue o de la g úa has a es e momen o en un ciclo.
4. Elección del é ice de explo ación inmedia a: Se debe escoge el nudo con
meno TIn (P[i][j]); y en caso que TIn (P[i][j]) > TCbes , se elimina P[0][i], donde
TCbes es la mejo solución has a ese momen o de la explo ación.
Algo i mo basado en b anch &bound
1. TCbes = ∑(k=0;N) c1k + ∑(i=1;N) ai + c0N+1,0 ; k = 1; Q1 = { P[0][1] }
2. Cons ui k+1 secuencias P[0][k+1] inse ando mk+1 en odas las posibles
posiciones de P[0][k].
Si (k+1) < N
3.1. Resol e los k+1 nodos P[0][k+1] po el p ocedimien o MCM.
3.2. Si un nodo es ac ible y TIn (P[0][k+1]) ≤ TCbes ⇒ añadi a Qk+1.
3.3. k = k+1
3.4. Si Qk = {∅} ⇒ k = k-1; i a 3.4.
3.5. Si k=1, en onces FIN.
3.6. Escoge P[0][k] con meno TIn (P[0][k]); Qk = Qk - P[0][k]. I a 2.
Si (k+1) = N
4.1. Resol e cada nodo P[0][N].
4.2. Si TC(M,T) < TCbes ⇒ TCbes =TC(M,T)
4.3. k = k-1; i a 3.4.
5. CONCLUSIONES
Las apo aciones en el p oblema a ado, Hois Scheduling P oblem, pa ecen
indica que el p ocedimien o aquí plan eado pe mi e encon a de mane a e icien e
un p og ama óp imo del anspo ado . No obs an e, la si uación simple analizada
suele da se pocas eces en la ealidad, lo que implica u iliza modelos más
complejos que incluyan las bases concep uales aquí expues as.
6. REFERENCIAS
ARMSTRONG R., LEI L., SHANHONG G. (1994): A bounding scheme o
de i ing he Minimal Cycle Time o a single anspo e N-s age p ocess wi h
ime window cons ain s, Eu opean Jou nal o Ope a ional Resea ch, 130-140.
BAPTISTE P., LEGEARD B., VARNIER C. (1992): Hois scheduling p oblem :
an app oach based on cons ain s logic p og amming, IEEE In e na ional
Con e ence on Robo ics and Au oma ion, ol. 2, 1139-1144.
FERNÁNDEZ R. (1995): Mé odos pa a halla el iempo de ciclo mínimo en un
p oceso de N e apas con un obo anspo ado y es icciones en ana. P oyec o
Final de Ca e a, ETSEIB.
MANIER M.-A., BAPTISTE P. (1994): E a de l’a : o donnancemen de obo s
de manu en ion en gal anoplas ie, APII, ol. 28, nº 1, 7-35.
PHILIPS L.W., UNGER P.S. (1976): Ma hema ical p og amming solu ion o a
hois scheduling p og am, AIEE T ansac ions, ol. 8, nº 2, 219-225.
SHAPIRO G.W., NUTTLE H.L.W. (1988): Hois Scheduling o a PCB
elec opla ing acili y, IEE T ansac ions, ol 20, nº 2, 157-167.
THESEN A., LEI L. (1990): An expe scheduling sys em o ma e ial handling
hois s, Jou nal o Manu ac u ing Sys em, ol. 9, nº 3, 247-252.
VARNIER C., GRUNDER O., BAPTISTE P. (1995): Imp o ing he p oduc i i y
o elec opla ing lines by changing he layou o he anks, IEEE 0-7803-2535-
4/95, 441-450.
YIH Y. (1988): An algo i hm o hois scheduling p oblems, In e na ional
Jou nal o P oduc ion Resea ch, ol. 32, nº 3, 501-516.