Soluciones aproximadas al problema de distribución a dos niveles

QtleatilóV. 1 O, n.o 3 (setembre 1 986) pp. 181-1 91 SOLUCIONES APROXIMADAS AL PROBLEMA DE DISTRIBUCIÓN A DOS NIVELES LUIS ONIEVA, JUAN LARRAÑETA UNIVERSIDAD DE SEVILLA La determinación de los lotes de aprovisionamiento de un sistema de distribución de dos niveles formado por una instalación principal que surte a un conjunto de detallistas sujetos a demanda externa es un problema complejo aún en el supuesto de demanda constante y determinista. El empleo de politicas de ciclo simple en que cada vez que ordena el almacén prin cipal lo hacen todos los detallistas, renovándose el estado del sistema, reune ciertas pro~ piedades que la hacen adecuada para muchos sistemas multinivel. En este trabajo se propone un método iterati~o de obtención de noliticas de ciclo simnle oue satisfacen vroviedades si multáneas de ovtim~lidad. asi como una reala heuristica de un solo vaso vara obtener buenas soluciones. Keywords: INVENTORY, DETERMINISTIC MODELS MULTI-ECHELON, ORDERING POLICES. l. INTRODUCCION. El supuesto de inventarios de distribución a dos niveles que se analiza es el análogo al del lote económico con demanda determinista, incluyendo las ligaduras entre un almacén -- principal y n-1 detallistas como se muestra en la figura l. La estructura de los costes relevantes viene dada por un coste de lanzamiento si en el que se incurre cada vez que se solicita un lote por la unidad i (detallista o almacén principal) y un coste de mantenimiento de sistema (Clark y Scarf /1/) hi imputado al nivel medio de stock de sistema. Los detallistas están sujetos a una demanda externa Almacén Principal R n n-1 E i=l R. l Ri' i=1,2, ... ,n-1 determinista y constante en el tiempo. El almacén principal n ha de alimentar las necesidades de los detallistas, - respondiendo a una demanda inducida Figura 1: Sistema de Inventarios de Distribución de Dos Niveles. El problema que se plantea es el de determinar el lote económico Qi (1=1,2, ... ,n) a emplear por cada una de las instalaciones bajo una política de ciclo simple, es decir, cada vez que el almacén principal solicita un lote, también lo solicitan todos y cada uno de los detallistas. Así, se ha de satisfacer la reLuis Onieva - Escuela Superior de Ingenieros Industriales - Depto. Organización de la Producción - Av. Reina Mercedes, s/n. 41012 Sevilla Article rebut el maig de 1986. 181 QitentlóV. 1 O, n.o 3 (setembre 1 986) laci6n: i=l,2, ••• ,n-l para ciertos valores enteros de ki. El modelo a resolver es: min. n r (siRi/Qi + hiQi/2) i=l i=l,2, ... ,n-l entero i=l, .•• ,n-1 (1) Llamando T = Qn/Rn y Ti = Qi/Ri' obsérvese que cada intervalo T se reitera periodicamente el estado del sistema. T es la duraci6n del lote Qn que emplea el almacén pri~ cipal sujeto a la demanda inducida Rn. Eneste intervalo el detallista i recibe ki 1~ tes de tamaño Qi con un intervalo Ti entre lotes. Así, T es el intervalo base y Ti los de los detallistas, que han de ser diviso-- res del base, como aparece en el ejemplo de la figura 2. T 15 I------IT 2 1.875, k2 = 8 3 Figura 2: Ejemplo de un sistema formado por cinco instalaciones. Una soluci6n al problema (1) viene determinada por (k 1 ,k 2, ... ,kn_ 1, kn,Qn) donde Qn es el lote empleado por el almacén principal y ki la multiplicidad asociada al detallista i, indicando el número de veces que solicita entre dos aprovisionamientos sucesivos del almacén principal. N6tese que kn = 1 por definici6n. Este problema fue inicialmente tratado por Schwarz /6/, en su tesis doctoral, resolvié~ dolo para el caso de un solo detallista. La obtenci6n de la soluci6n 6ptima al modelo, - mediante exploraci6n dirigida, se contiene - en Graves y Schwarz /2/. Recientemente Roundy /5/ ha presentado resultados muy potentes, extendiendo el conjunto de políticas consid~ radas más allá de las de ciclo simple. Para sistemas complejos de producci6n-inventario, Maxwell y Muckstadt /3/ han resuelto el modelo análogo al aquí estudiado mediante el empleo de grafos y reduciendo la exploraci6n de las multiplicidades que intervienen a las potencias de 2. 2. ANALISIS DEL MODELO. Llamando f al número medio de veces en que el sistema completo se renueva en el horizon te al que las demandas están referidas: el modelo (1) puede reescribirse como: min. s.a. entero i=l,2, ••. ,n-l k 1 n ( 2) Denominando costes totales relevantes, CTR ( f, k i , s ) : f i ¿ i a los costes globales medios del sistema em pleando una frecuencia f y unas multiplicidades ki para cada detallista, que refleja la frecuencia fi = kif de cada uno de ellos, se obtiene una funci6n convexa en f y unímodal para cada ki. Manteniendo f constante, se obtienen las -- condiciones locales de optimalidad, exponie~ do: > CTR(f,ki's'kj+l) 182 QtleattióV. 1 O, n.o 3 (setembre 1986) para cada j=l,2, ... ,n-1, que expresan como los costes totales relevantes se degradan - al variar los valores óptimos de las multiplicidades ki. Estas relaciones son equivalentes para cada j, a: k.(k.-1) < J J - h. R. J J 2 sj ( 3) Para valores particulares de ki, la frecue~ cia F(ki 1 s) que da lugar al coste mínimo es: F (k. 1 ) = ( (E h. R. /k. ) /2 E s. k. ] ~ l S . l l l . l l (4) l l con un coste total relevante: CTR ( F (k i 1 s) , k i 1 s) = ( 2 ( E h iR i /k i) • E ( 5) que sólo depende de los valores de las multiplicidades ki. Dado el carácter unimodal de la expresión del radicando de (5) para cada ki, que sie~ pre es positivo, las condiciones simultáneas de optimalidad se pueden obtener imponiendo para cada j=1,2, ... ,n-1 y análogamente incrementando kj a kj+l. Estas relaciones conducen a: I: hiRi/ki k~ - k. i;ij J J E hiRi/ki i h. R. E s.k. i l l .5. J J .5. s. E hiRi/ki J i E hiRi/ki .5. k~ + k . i;ij J J E hiRi/ki i Si se representa por FE. a la frecuencia J ( 6) ( 7) económica de la instalación i, si actuara independientemente FE. = (h.R./2 sJ.)~ J J J y FA. al del conjunto del sistema en el suJ puesto de que el coste de mantenimiento de la demanda anual del artículo fuera nulo FA. J ( ( E dj h.R./k. )/ 2 E s.k. ]~ l l l . l 1 l la relación (7) es equivalente a FE. FA. .5_(-+) .5. kj + kj(-+) (8) Además, es inmediato de (3) que las multipl~ cidades de las instalaciones tienen que estar lexicográficamente ordenadas con las frecuencias económicas de las mismas: implica en el óptimo. 3. ALGORITMO DE RESOLUCION. El algoritmo de obtención de óptimos locales que satisfacen las condiciones simultáneas - de optimalidad, sobre el valor de la frecue~ cia y el de las multiplicidades, se recoge en el diagrama de flujo de la figura 3. 4, DERIVACION DE LA REGLA HEURISTICA. Considerando la relajación contínua de las - restricciones de integridad del modelo (2) resulta: min. s.a. k n 1 n E hiRi/ki i=l i=2, .•. ,n-l ( 9) Las condiciones necesarias de optimalidad en (9) implican la existencia de multiplicado-- res i i=1,2, ... ,n con i i=1,2, ... ,n-1 tales que 1 h.R. f -l l s. ---u- - A. l k. l 1 n n O para o i=l,2, ..• ,n (lO) l f E k.s. E hiRi/ki i=l l 1 -ui=l ( 11) m .¡,. f2 = fi 2 No 1 Si No Test de incrementó de Test de disminución las k(j) posteriores de las k(j) anteriores a "i". a 11 i". '--------o· 1 No Si f2 ___t__ ~ Figura 3. Diagrama de Flujo del Algoritmo de Res,,lución. i tt. o. :< ~ p ? w -¡¡;- CD ¡;) 3 cr ca c.o 00 Ol QU.eatlióV. 1 O, n.o 3 (setembre 1986) Ai(l-ki) o i:l,2, .•• ,n-l ( 12) Ai ~ o i:l,2, •.. ,n-l ( 13) k 1 ( 14) n De estas condiciones se derivan los siguientes resultados: a) Cuando ki > 1, Ai que O según (12) con lo b) Cuando ki : 1, las condiciones (10) equivalen a: Gráficamente: Coste FE. f 1 Frecuencia Figura 4: Interpretación de Ai. Al ser los multiplicadores i no negativos, 1 cuando f FE. se satisface f si 2f h.R .. J. J. l Se tiene que para k. = 1, f > FE .. l J. A partir de estos elementos resulta que sólo aquellas instalaciones en las que f ~ FEi, intervienen en la fijación de f con ki : l. Cuando f < FEi, el valor de la correspondie~ te multiplicidad será superior a la unidad (ki > 1). Para la determinación de f se ordenan los de tallistas según orden creciente de sus frecuencias naturales: para i,j-1, ... ,n-1 i < j si y sólo si Supuesta esta ordenación se considera sucesi vamente la combinación de los costes y deman da del almacén principal con los detallistas, hasta que el siguiente a combinar tenga una frecuencia natural superior a la obtenida -- con los anteriores (figura 5). FE, FE 2 1 1 f FH FE n l Figura 5: Ordenación de las FEi. Formalmente, la frecuencia FH que correspo~ de a la solución de (9) viene dada por: m h R + E hiRi n n i:l F2 H m 2(sn + E si) i:l donde m es la última instalación para la que se cumple: m h R + E h.R. h R n n i:l l l m m ~ S m m S + E s. n i:l l En términos de las frecuencias naturales, se calcula iterativamente: j h R + E hiRi n n i:l F2 [ 1, j l H -j S + E si n i:l comparándose F~[l,j] con FEj para j=0,1,2, .•. hasta la primera vez en que F~[1,jJ<FE~. Cuando éso suceda m:j-1. Nótese que en el s~ matorio para el cálculo de FH[1,j] se considera j=O, que corresponde al caso en que FEn< FE1. En esta situación se tiene FH = FEn, por ser el almacén principal que tiene menor frecuencia natural. que el Obsérvese que el multiplicador An asociado al almacén principal es libre en el signo. De las relaciones (10), sumándolas sobre todos los detallistas, se obtiene: f n E i:l k.s. + l l 1 -uque al compararla con (11) da lugar a: o Para i > m, i ~ n, ki > 1 por lo que los 185 QtieatiióV. 1 O, n.o 3 (setembre 1 986) multiplicadores Ai son nulos. Por ello esta relación es: m An + E Ai O; o lo que es lo mismo: i=l m E Ai < 0. i=l Este resultado corrobora la interpretación a que da lugar la fijación de FH. Pues si FEn no es la menor de todas las frecuencias naturales FEn < FH, por lo que si bien kn=l, su multiplicador es negativo como se observa en la figura 6. Coste f S n Frecuencia Figura 6: Interpretación de la fijación de FH" 5. REGLA HEURISTICA. La heurística de un solo paso que se propone es la heurística miope de Graves y Schwarz /2/, partiendo de la frecuencia FH, según se ha definido en la sección anterior. l. Calcular FH. 2. Para i=l,2, ... ,m; k. l 1 3. Para i=m+l, ••. ,n-1; ki es el mayor entero tal que FE~ l p2 H La heurística con la que comparamos los re-- sultados obtenidos por ésta es la propuesta por Graves y Schwarz /2/ que se puede interpretar como la análoga de la aouí propue~ ta haciendo FH FEn en el primer paso. En la figura 7, se recoge el diagrama de flujo de esta heurística. 6. EXPERIENCIAS COMPUTACIONALES. Para comprobar la eficiencia del método propuesto se ha empleado, en primer lugar, el conjunto de problemas test utilizados por Graves y Schwarz /2/ para mostrar la bondad de los resultados de su heurística miope -- respecto a la solución óptima. Para ello se han generado y resuelto 500 -- problemas test para cuatro sistemas distintos (un total de 2000 problemas) formados - por un almacén principal y 2,3,5 y 10 detallistas con idénticos costes, es decir: s y hj = h para j=l, ... ,n-1, con S. J sn hn = l. El valor de s se fija según una distribución uniforme entre los valores 0.01, 0.1, 0.5, 1, 2, 10 y 100. De igual-- forma, el valor de h se obtiene de acuerdo con una distribución uniforme entre los valores: 0.5, 1 y 2. La demanda de los n-1 detallistas se genera como: Rj d.Rj-l para j=2, ... , n-1; siendo R1 = 1 y fijando el coeficiente d de forma similar a s y a h en tre los valores: 0.2, 0.4, 0.6, 0.8 y l. Los resultados de la regla diseñada son co~ parados con los de la heurística miope de Graves y Schwarz /2/, analizando el error me dio, su desviación estándar y el error máximo que producen ambas soluciones aproximadas con respecto a la solución óptima. Asimismo, para cada sistema se calcula el número de ve ces que la solución de cada heurística queda más próxima al valor final y el número de ve ces que acierta con dicho valor óptimo. Este análisis se realiza en términos del coste g~ nerado por la solución de cada heurística respecto al coste generado por la solución óptima (tabla 1.1) y en términos de la frecuencia que propone cada método respecto de la frecuencia óptima (tabla 1.2). Así por ejemplo, para los 500 problemas gen~ radas para el sistema formado por un almacén principal y tres detallistas (tabla 1.1), el error medio en el coste obtenido por la heurística de Graves y Schwarz (G/S) es del 0.069%, frente al 0.0005% obtenido por el mé todo propuesto, con una desviación tipo del 0.383%, frente al 0.0063%, y con un error má ximo de aproximadamente el 4%, frente al 0.0854%. También se observa en la tabla 1.1 como de los 500 problemas test resueltos para este sistema de tres detallistas (n=4), 186 ~ OJ -J ...,.}-- Ordenar los articules según su i=1,n-1 Si h n F2 = R h R Fz=~ 2 S n j + ¡; h. n i=1 l. j 2(s + ¡:: S.) n l. --- Si No R. l. Figura 7. Diagrama de Flujo de la Regla Heurística. F /F2 H Hacer: k.= 1 l. para i = 1,m Si Calcular 1 entero tal que: 1 * (1-1) FE2 < i ~ H <1*(1+1) Si volver i ~ o. < p ~ "o w éñ (!) .... (!) 3 eco (O 00 ~ QtlesttióV. 1 O, n.o 3 (setembre 1 986) el coste proporcionado por la regla de G/S ha quedado en 478 ocasiones más próximo al coste óptimo, frente a las 500 (o sea todas) de la heurística propuesta (que por tanto ha quedado más próxima al coste óptimo en 22 ocasiones más que la de G/S). De las 478 veces, la regla de G/S ha acertado 473 veces con el coste óptimo, frente a las 495 de la regla propuesta para este tipo de problemas. Los resultados acumulados referidos a la pr~ ximidad del coste de cada regla respecto al coste óptimo para los 2000 problemas resueltos son los siguientes: el coste proporcion~ do por la heurística de G/S ha sido mínimo - el 77.85% de las veces, frente al 98.6% dela heurística propuesta, habiéndose alcanzado el coste óptimo el 77.15% de las veces, - frente al 96.45% de la regla que se propone. Realizando el mismo análisis, pero en términos de frecuencia inicial fijada por cada -- heurística, respecto a la frecuencia óptima o final, se obtienen los resultados que aparecen en la tabla 1.2. Para el caso de tres detallistas, en los 500 problemas resueltos, se observa en la tabla 1.2 como el error medio obtenido, en la determinación de la frecuencia inicial, por la regla de G/S es del 145.87%, frente al 2.21% obtenido por la heurística propuesta. La de~ viación estándar es del 283.43%, frente al 3.22%; siendo el error máximo del 1316% para G/S, frente al 14.84%. El número de veces -- que la frecuencia inicial ha estado más cercana a la final ha sido, para G/S, 113 frente a las 484; habiendo coincidido ambas -la inicial y la óptima191 veces de las 500 en la heurística propuesta y ninguna vez en el caso de G/S. Para analizar la bondad de la regla propuesta frente a la de G/S en sistemas con deta-- llistas cuyos costes, tanto de lanzamiento como de mantenimiento, sean distintos entre sí se han resuelto los problemas cuyos datos base aparecen en la tabla 2.1. Como se obser va, se han generado 250 problemas para siste mas con 2, 3, 4, 5, 10, 20 y 100 detallistas. La demanda de cada detallista se asigna se-- gún una distribución uniforme entre 15o y 2000. El coste de lanzamiento y de mantenimiento correspondiente a cada detallista se genera de la misma forma que la demanda en-- tre los valores 3 y 20; y 5 y 20 respectivamente (Chakravarty /7/) . Los resultados se ofrecen en las tablas 2.2 en términos de costes, y 2.3 en términos de frecuencias. Como se deduce de estas tablas, la solución que se propone es mejor que la de G/S también para sistemas con detallistas de distintos costes, tanto en los resultados expresados en términos de costes (tabla 2.2) como en los resultados expresados en térmi-- nos de frecuencias (tabla 2.3). Así por eje~ plo, G/S obtienen el coste inicial mínimo el 53.1%, frente al 98.15%, de los 2000 problemas resueltos y una frecuencia inicial más próxima a la óptima en el 2.75% de las veces, frente al 97.9% que obtiene el método pro-- puesto. 7 1 CONCLUSIONES 1 De la inspección de las tablas se pueden obtener las siguientes conclusiones: El orden de magnitud de los errores y desvi~ ción tipo es mucho mayor en el caso de comp~ rar las frecuencias que en el caso de comparar los costes. Como ya se ha comentado, este hecho se debe a la estructura de la fun-- ción de costes para este tipo de problemas. Si se observa el número de veces que cada -- heurística proporciona el coste mínimo para cada grupo de problemas (tablas 1.1 y 2.2, frente al número de veces que cada una proporciona una frecuencia más próxima a la óptima (tablas 1.2 y 2.3, se deduce que para el caso de G/S el segundo índice disminuye bastante respecto al primer9 conforme aumenta el número de detallistas; lo cual es debi do, además de a la estructura de la función de costes, a que G/S tienen en cuenta para determinar la frecuencia un solo detallista (el de menor frecuencia económica) , mientras que en el caso de la heurística propuesta no ocurre así. En cualquier caso, los resultados que ofrece el método propuesto son mejores que los que ofrece la heurística miope de Graves y Schwarz /2/; aplicando este resultado tanto a los problemas test propuestos por ellos mis mos, o sea a sistemas con detallistas de idén ticos costes, como a otros sistemas en que la 188 QtleattióV. 1 O, n.o 3 (setembre 1986) Numero TABLA 1.1. Resultados de las heurísticas, en términos de COSTES, respecto a la solución óptima. Coste Final de Heur. Error Desviación Error Núm. de veces Detallistas Medio Tipo Máximo Mas prox. Alcanz. --------- -------- ¡---------- ------------- --------- --------·- ------- 2 L/0 .0074% .0821% .9217% 500 496 G/ S .0220% .1725% 1.9049% 494 490 3 L/0 .0005% .0063% .0854% 500 495 G/ S .0690% .3830% 4.0043% 478 473 5 L/0 .0082% .0538% .7184% 486 479 G/S .2728% .8614% 6.5995% 406 401 lO L/O .0091% .0415% .4245% 486 459 G/ S l. 8333% 2.6066% l3. 3464% 179 179 Número de problemas generados: 500 por sistema. TABLA 1.2. Resultados de las heurísticas, en términos de FRECUENCIA, respecto a la solución óptima. Numero Frecuenc1a F1nal de Heur. Error Desviación Error Núm. de veces Detallistas Medio Tipo Máximo Mas prox. Alcanz. r---------- ------- ---------- ------------ --------- -------- --------- 2 L/0 l. 7499% 3.5166% 22.4745% 456 258 G/S 144.1610% 277.8695% 1057.5830% 188 54 3 L/0 2.2190% 3.2248% 14.8408% 484 191 G/S 145.8739% 283.4331% 1316.5680% 113 o 5 L/0 2.7897% 3.0070% 15.0120% 478 98 G/S 226.7976% 407.6952% 1823.4930% 70 5 lO L/0 2.8930% 2.4270% 13.3542% 489 ll G/S 376.2868% 616.6898% 2803.9970% 16 o Número de problemas generados: 500 por sistema. TABLA 2 .l. Datos del conjunto de problemas resuelto Número de detallistas: Demanda Coste lanzamiento Coste mantenimiento 2 3 4 5 lO 20 Valor inicial 150.000 3.000 5.000 50 lOO Valor final 2.000.000 20.000 ' 20.000 Peso aleatorio aleatorio aleatorio Número de problemas generados: 250 por sistema (2000 en total). 189