Heurística complementaria a enfoques duales para la planificación de la producción

QÜESTIIÓ, Vol 16, 1,2,3 pp. 77-98, 1992 , HEURISTICA COMPLEMENTARIA A ENFOQUES DUALES PARA LA , , PLANIFICACION DE LA PRODUCCION S. LOZANO, J. LARRAÑETA y L. ONIEVA Es e abajo p esen a una heu ís ica de a ios pasos pa a la ob ención de soluciones admisibles al p oblema de plani icación de la p oducción con limi aciones de capacidad, a pa i de las soluciones ap oxima- das que p opo cionan los mé odos duales basados en la elajación del p oblema. La heu ís ica es complemen a ia a la aplicación de dichos mé odos, buscando soluciones admisibles de i adas de las p opo cio- nadas po la solución a la elajación. Complemen a y heu is ic o dual app oaches o he capaci- a ed lo -sizing p oblem. Keywo ds: Plani icación de la p oducción, limi aciones de capa- cidad, elajación Lag angiana, p ecio de los ecu sos, iempos de pues a a pun o, soluciones heu ís icas. -Escuela Supe io de Ingenie os Indus iales de Se illa. A da. Reina Me cedes s/n. 41012 Se illa. -A icle ebu el no emb e de 1991. -Accep a el juny de 1992. 77 l. INTRODUCCIÓN La de e minación del plan de allado de p oducción supone la ijación de las can idades que se han de ab ica de cada uno de los ipos de p oduc os en los pe iodos conside ados de o ma que los cos es de ope ación que dependen de es a decisión sean mínimos. La li e a u a sob e p oducción o ece soluciones ope a i as azonables al p oblema cuando la ep esen ación de los cos es y del consumo de la capacidad disponible da luga a modelos lineales (La añe a e al. [9]}. Si las limi aciones de capacidad no ac úan es posible ealiza la plani i- cación indi idual de cada uno de los p oduc os, po lo que la conside ación de los cos es ijos no supone un inc emen o ap eciable de complejidad, esol iéndose el p oblema median e p og amación dinámica (Wagne y Whi in [22]). Pe o si es necesa io inclui cos es ijos y limi aciones de capacidad, el modelo esul an e es N P-comple o (Flo ian e al. [7]), po lo que la op imización es sólo aplica- ble a si uaciones en las que in e ienen muy pocos p oduc os. El en oque que apa ece como más uc í e o en el caso gene al es la elajación del modelo a un p oblema lineal, que se abo da median e p ocedimien os duales, ap oximando sucesi amen e los p ecios in e nos de los ecu sos. (Onie a e al. [19], Lozano e al. [11]). En el apa ado 2 se ecoge explíci amen e el modelo analizado, desc ibiendo las ca ac e ís icas de las soluciones a los en oques duales en el apa ado 3. La heu ís ica se p esen a en el apa ado 4 y su in eg ación con los en oques duales en el 5. El apa ado 6 incluye las expe iencias compu acionales ealizadas aplicando la heu ís ica a un conjun o de p oblemas. 2. TERMINOLOGÍA, NOTACIÓN Y MODELO La no ación es la siguien e: N -núme o de a ículos i -índice co espondien e a cada a ículo (i = 1, 2, ... , N) L -núme o de pe iodos en el ho izon e de plani icación -índice co espondien e a cada pe iodo ( = 1, 2, ... , L) Zi -unidades p oducidas del a ículo i en el pe iodo l¡ -unidades de in en a io del p oduc o i al inal del pe iodo 78 D; -unidades de demanda del p oduc o i en el pe iodo s; -cos e ijo en el que se incu e po inicia un lo e de ab icación de i p; -cos e a iable de ab icación del p oduc o i h; -cos e a iable de man enimien o del s ock del p oduc o i K -capacidad disponible en el pe iodo a; -capacidad consumida po inicia la ab icación de i b; -consumo ma ginal de capacidad po unidad ab icada de i Con es os elemen os, un modelo que ecoge el p oblema de encon a un plan óp imo de p oducción que minimice los cos es o ales de ab icación e in en a io es, N L Min LL (s;8(x; ) + p;X; + h;l; ) i=1 =1 suje o a Ii, -1 + Xi - l; = D; i = 1, .. . ,N; = 1, . .. ,L N L(a;8(x; )+b;x; ) ~ I< = 1, ... ,L i=1 Xi 2: 0, ; 2: 0, J;o = 0 ep esen ando 8(x) = { ~ si x >O si x =O La p oducción global en el ho izon e de iempo conside ado es, pa a cada p oduc o i, la demanda o al en el mismo. Debido a ello, el cos e a iable o al es cons an e, independien emen e de las decisiones que se omen, po lo que puede sup imi se del modelo. En el análisis del modelo se conside a el subconjun o de las o mas de p o- ducción compues as po secuencias dominan es. Se de inen és as como las que sa is acen la p opiedad Xi · Ii, - 1 = O pa a cada . Co esponden a planes de p oducción en los que, +• x; = ¿nik s =o, 1, 2, ... k= 79 cub iendo cada lo e la demanda de un núme o comple o de pe iodos. Además, los lo es se ab ican en pe iodos que se inician sin in en a io. Las secuencias dominan es ienen la p opiedad de se óp imas cuando las limi aciones de capa- cidad no ac úan. En el caso de que lo hagan, una p opiedad de las soluciones óp imas es (Zangwill [23]) 0::::: Xi ) · 0::::: Ii, -d · H = O, siendo H la holgu a de capacidad del pe iodo . Las secuencias dominan es son un subconjun o de las o mas de p oduci que sa is acen es a p opiedad. Además, la esolución ap oximada del p oblema que nos ocupa median e los mé odos duales descon- side a las limi aciones de capacidad como es icción explíci a, pe mi iendo su ansg esión. La solución óp ima del modelo ap oximado sa is ace las limi acio- nes de capacidad, pe o con una conside ación ap oximada de los consumos de capacidad asociados a las pues as a pun o de las se ies de p oducción. Dado que exis en L pe iodos, el núme o máximo de secuencias dominan es pa a cada a ículo es de F = 2L-l. Cada secuencia de ine una o ma de p oducción y un in en a io esul an e en odo el ho izon e: Xij = (Xijl, Xij2, · · ·, XijL) = (Xij ) indica la secuencia dominan e de p oducción j (= 1, 2, ... , 2L-l) aplicada al a ículo i l;; (I;;¡,l;;2,···•lijL)=(I;j ) indica el in en a io en cada uno de los pe iodos, que esul a de emplea la secuencia de p oducción z;;. Esc ibiendo el modelo con es os elemen os esul a, donde N F Min LLc¡;O;; i=lj =1 N F suje o a LLmi; O;; $ I< = 1, 2, ... , L. i=lj=l F ¿:o¡;=1 i=1,2, ... ,N. j=l O¡;= O, 1 pa a cada i,j. L e;; = L (s;ó(x;; ) + p;z;; + h¡l;; ) =l es el cos e de p oducción e in en a io de la secuencia x;; en odo el ho izon e; T lij = a¡Ó(Xij ) + b¡Xij 80 el consumo de capacidad de la secuencia X;j en el pe iodo ; ()¡i son a iables de decisión bina ias indicando el empleo, ó no, de la secuencia Xij. Es e modelo de a iables en e as esul a de g andes dimensiones, cons ando de N+ L es icciones y N· 2L-l a iables bina ias. La elajación con inua del modelo con B;j 2: O se analiza como la ap oxi- mación a la solución del p oblema de plani icación con cos es ijos y limi aciones de capacidad. Es e plan eamien o del p oblema ue in oducido po Manne [16) y ha se ido como modelo base pa a los es udios pos e io es. La ex ensión del p oblema a la conside ación explíci a de es uc u as de ab icación mul ini el con un "cuello de bo ella" en o ma de limi aciones de capacidad ue modelada po Billing on e al. [1), y ep esen a una ex ensión del modelo aquí conside- ado, si bien la heu ís ica que se desc ibe en es e abajo es aplicable ambién a la ob ención del plan de p oducción de dicho cuello de bo ella. 3. SOLUCIONES APROXIMADAS Han sido nume osos los en oques empleados pa a abo da la esolución del modelo desc i o. El p ime o de ellos co esponde a in en a desde el inicio solu- ciones heu ís icas simples que den luga a planes admisibles. Las limi aciones de capacidad desaconsejan la posibilidad de aplica mé odos ales como el "Pa Pe- iod Balancing" (Eisenhu [5]) o el de "Mínimos Cos es Medios" (Sil e y Meal [20]) al p oblema. Los p opues os po Lamb ech y Vande eken [8) y Dixon y Sil e [2) conside an explíci amen e las limi aciones de capacidad. Pos e io - men e Maes y Van Wassenho e [13, 14) e undie on las p opues as con enidas en es as heu ís icas o mulándolas de o ma simpli icada con lo que las necesidades compu acionales disminuyen. Su p ocedimien o es some e el p oblema a una ba e ía de es e ipo de heu ís icas simples y selecciona la mejo de las soluciones ob enidas con ellas. Pa a si uaciones en las que las limi aciones de capacidad son poco es ic as (es o es, las componen es ijas de los cos es y de los consumos de capacidad de ecu sos son educidas) se ob ienen soluciones acep ables. O o en oque ha sido abo da el modelo de p og amación lineal con inua de Manne median e p ocedimien os p imales. His ó icamen e ue el p ime en oque, y en él se incluyen las p opues as de Dzielinski e al. [3), Dzielinski y Gomo y [4), Lasdon y Te jung [10), pudiendo conside a se ambién en e ellas la de Newson [18) o 81 Más ecien emen e se han aplicado p ocedimien os duales que analizan la elajación Lag angiana del p oblema. Las es icciones elajadas son las de ca- pacidad, que se inco po an a la unción obje i o median e la impu ación de p e- cios a los ecu sos empleados. Thizy y Van Wassenho e [21) aplican el mé odo del subg adien e a la esolución del Lag angiano. Onie a e al. [19] y Lozano e al. [11] aplican el mé odo p imal dual, ex endiendo dicho p ocedimien o a si uaciones mul ini el con un ·"cuello de bo ella" en Lozano e al. [12). El análisis dual iene a ias en ajas sob e los o os p ocedimien os (Fishe [6]) pe o, y en es e aspec o es igual a los mé odos p imales, la solución inal ob enida no da luga , necesa iamen e, a una solución admisible. Con el mé odo p imal dual se esuel e en cada i e ación un subp oblema p imal educido en el que se iden i ican las can idades p oducidas en cada pe iodo. Y lo que es más signi ica i o, el g ado de inadmisibilidad de dicho plan. En pa icula , indica cual es el exceso u holgu a de capacidad en cada pe iodo, ac ualizando en con- sonancia la impu ación de p ecios a los ecu sos. La solución óp ima del dual con iene un plan de p oducción admisible desde el pun o de is a de la ela- jación con ínua del p oblema. Pe o la es imación de los iempos de pues a a pun o se lle a a cabo median e la linealización de los mismos. En la implemen- ación p ác ica dicha linealización no se co esponde con la ealidad, po lo que la solución óp ima del modelo puede se inadmisible pa a el p oblema o iginal, al inclui és e las pues as a pun o comple as. Po ello, odos los mé odos, ya sean p imales o duales, que abo dan el p oblema de la plani icación de la p oducción con cos es ijos y iempos de pues a a pun o median e el modelo ap oximado de Manne [16) equie en de la inco po ación de algún p ocedimien o que modi ique la solución ap oximada disponible. Es a egla heu ís ica ha de ene en cuen a explíci amen e el consumo disc e o de la capacidad al inicia las se ies de p o- ducción pa a la ob ención de soluciones admisibles. Asimismo, ha de alo a explíci amen e los cos es a pa i de la conside ación explíci a de la componen e ija de los mismos. Thizy y Van Wassenho e [21) p opusie on como egla heu ís ica esol e , en cada i e ación de su mé odo dual, un modelo de anspo e. La solución dis- ponible del p oblema dual p opo ciona en cada i e ación los pe iodos en que se inician se ies de p oducción pa a cada uno de los p oduc os. Fijados los componen es ijos de los cos es Si y de los consumos de ecu sos ai asociados a los lanzamien os de la p oducción, y e aluada la capacidad disponible es an e, esul a un p oblema con ínuo en las can idades a p oduci en dichos pe iodos pa a sa is ace la demanda. Pe o ija a p io i los pe iodos en los que se a a p oduci conduce en muchos casos a la inadmisibilidad del plan de p oducción, pues el modelo de anspo e esul an e es ecuen emen e inadmisible. Además, el núme o de a iables que·in e ienen en el modelo de anspo e es O( N L2 ), 82 con lo que su amaño y iempo de esolución aumen an signi ica i amen e con el núme o de pe iodos. La heu ís ica p opues a en la siguien e sección abo da es os aspec os. 4. HEURÍSTICA Como hemos señalado, el p oblema de plani icación de la p oducción con cos es ijos y limi aciones de capacidad es N ?-comple o. Los mé odos de eso- lución, sal o pa a p oblemas de muy educidas dimensiones, son de ipo ap oxi- mado. En pa icula , odos los basados en la o mulación de Manne [16]. Cuando exis en iempos de pues a a pun o, la búsqueda de una solución admisible -aún cuando no sea un plan de p oducción e icien e-- ya es de po sí N ?-comple o (Maes e al. [15]). Es po ello imp escindible dispone de una egla heu ís ica. En los mé odos duales se pa e de los p ecios in e nos>. asociados al consumo de los ecu sos, si bien es posible ija dichos alo es a bi a iamen e "a p io i". Aplicando el algo i mo de Wagne - Whi in [22] empleando como cos es L c¡i + l:mij A =l que ienen en cuen a los cos es p opios de p oducción C¡j más un é mino aso- ciado a la alo ación del consumo de los ecu sos, se esuel e el p oblema de plani icación desconside ando las limi aciones de capacidad. Las secuencias de p oducción ob enidas y los in en a ios esul an es sa is acen Xij(i) ·l;j(i), -l =O. Con ellas se o man las ablas de p oducción Xi y de in en a ios l; , que indican pa a las secuencias de p oducción iden i icadas la can idad p oducida de cada a ículo en cada uno de los pe iodos del ho izon e y sus in en a ios esul an es, e aluándose el ec o de capacidades disponibles Si Z > O pa a odo , la solución ob enida es admisible. En caso con a io ha de modi ica se el plan de p oducción median e la heu ís ica. La heu ís ica que se p opone puede aplica se po sí misma, ijando los p ecios in e nos de los ecu sos>. a bi a iamen e, o mejo en conjunción con un mé odo 83 de selección de los mismos. En los mé odos duales, al como en el mé odo p imal- dual (Onie a e al. [19], Lozano e al. [11], [12]) se pueden emplea los p ecios in e nos >. p oceden es de las soluciones admisibles del p oblema dual que se ob ienen en cada i e ación. Así, cada i e ación del mé odo p imal-dual supone una aplicación de la egla heu ís ica. La egla heu ís ica cons a de es bloques: Bloque I. Las eglas del p ime bloque pa icionan los lo es ab icados en el úl imo pe iodo en el que exis e inadmisibilidad, e asándola en la medida de lo posible hacia el pe iodo pos e io en el que la holgu a sea máxima, con el in de que la si uación esul an e no sea des a o able. El e aso se lle a a cabo inc emen ando los cos es lo menos posible. 1° Sea = max{ ': Z ' < 0}. Se iden i ica con el pe iodo más a dío en el que se p esen a inadmisibilidad. Ob iamen e, si Z ' > O pa a odos los pe iodos, la solución ob enida es admisible. FIN. 2° Sean= {i: Xi ·li > 0}. Es el conjun o de a ículos que p oducen en exceso de la demanda del pe iodo conside ado . Son a ículos pa a los que se puede con empla el e aso de su p oducción, man eniendo la admisibilidad. 3° 3.1 Si n = 0, no se puede e asa la p oducción. I a 8 {segundo bloque). 3.2 Se o denan los a ículos en o den c ecien e{no dec ecien es si hay empa- es) del indicado de inc emen o de cos es s¡{a¡ + 1) b¡h¡ La acionalidad de es e c i e io p o iene del hecho de que al ompe un lo e se incune en un cos e de lanzamien o adicional y se aho a el cos e de man enimien o debido al e aso de la p oducción. Se incluyen ambién los consumos de ecu so a¡ y b¡ con la inalidad de libe a la máxima can idad del mismo en el pe iodo , comp ome iendo la meno can idad posible del pe iodo al que se e asa ( éase el pun o 5° de es e bloque). La inclusión de la unidad elimina la degene ación cuando a¡ = O. Obsé ese que al no depende el c i e io de o denación de la solución conc e a de pa ida, dicha o denación puede hace se a p io i una sola ez. Obsé ese ambién que el c i e io a o ece el doble obje i o de la heu ís ica: minimiza el consumo de ecu sos y el inc emen o de los cos es. 84 4° 4.1 Si l; = O, elimina i de n y ol e a 3°. P oba con el siguien e a ículo. 4.2 Sea T = min{ ': ' > , li ' = 0}, el pe iodo has a el que se abas ece la demanda del a ículo i con el lo e p oducido en el pe iodo . 5° Sea ( , T) el pe iodo pa a el que se ob iene la máxima holgu a de capaci- dad; i.e., max{ Z ': < ' < T}. Es el pe iodo candida o al que e asa el exceso de p oducción del a ículo i en . Si ZT :::; a;, el e aso p oduci ía inadmisibilidad en T, en cuyo caso, elimina i de l e Í a 3°. 6° Re asa al pe iodo la p oducción de la can idad A • { [ZT- a; (1- 8(x;T ))] . I } u = mln b ) mln i ' i :S '<T Ac ualiza las a iables del plan de p oducción y los indicado es de consumo de ecu sos: Z {::== Z + bib. ZT {::== ZT- bib.-a; (1- 8(x;T)) Xi {::== Xi -b. XiT {::== XiT + b. li ' {::== li ' -b. pa a ' = , + 1, ... , T- l. La can idad b. a aspasa es á limi ada po la holgu a del pe iodo T y los in en a ios e asados has a dicho pe iodo. El co che e signi ica "pa e en- e a", ga an izando median e el edondeo hacia abajo la admisibilidad en el pe iodo T. 7° Si Z 2: O, se ha eliminado la inac!misibilidad en . I a 1°. Si Z < O, se ha de con inua ompiendo lo es en . I a 4°. Obsé ese que el conjun o de eglas del bloque 1 inalizan: -Al alcanza la admisibilidad (pun o 7°). - Al ago a se el conjun o ele a ículos cuya p oducción pueda a asa se (pun o 3.1). En es e caso se aplican las eglas del bloque 11. Bloque II. Las eglas del segundo bloque adelan an la p oducción a pe iodos an e io es en los que haya holgu a de capacidad sin c ea nue as pues as a pun o (po ya exis i en ellos ab icación de lo es). 85 Pa a mejo mos a el ca ác e complemen a io de la heu ís ica p opues a y los mé odos duales, en la igu a 1 se ecoge la e olución del Lag angiano jun o con la de la mejo solución p opo cionada po la heu ís ica, a medida que i e a el mé odo p imal-dual aplicado al p oblema que se ha denominado MARS- TEN l. Se obse a que la co a in e io p opo cionada po el Lag angiano con- e ge monó onamen e a su óp imo (el de la elajación con inua). Simé icamen e, las soluciones de la heu ís ica an mejo ando p og esi amen e a medida que se apoya en las secuencias de p oducción más ap opiadas, las cuales su gen al asig- na mejo los p ecios in e nos de los ecu sos escasos. Función ObJe i o 49500 49300 49100 48900 48700 48500 48300 48100 47900 47700 E olución de la heu ís ica Lag anglano + Heu s lca 4750()~,---~--------~--~--- ---.----~--~--- ---.-- 1 5 g 13 17 21 25 29 33 37 4i N• I e aciones Figu a l. 92 7. REFERENCIAS (1] Billing on, P.; McClain, J. y Thomas, L. (1983). "Ma hema i- cal P og amming App oaches o Capaci y-Cons ained MRP Sys ems: Re iew, Fo mula ion and P oblema Reduc ion". Managemen Science, Vol. 29, 1126-1141. (2] Dixou, P.S. y Sil e , E.A. (1981). "A Heu is ic Solu ion P ocedu e o he Mul i-i em Single-Le e! Limi ed Capaci y Lo -Sizing P oblem". J. o Ope a ions M anagemen , Vol. 2, 23-29. (3] Dzieliuski, B.P.; Bake , C.T. y Manne, A.S. (1963). "Simula ion Tes s o Lo Size P og amming". Managemen Science, Vol. 9, 229-258. (4] Dzieliuski, B.P. y Gomo y, R.E. (1965). "Op imal P og amming o Lo Sizes, In en o y and Labo Alloca ions". Managemen Science, Vol. 11, 874-890. (5] Eisenhu , P.S. (1975). "A Dynamic Lo Sizing Algo i hm wi h Capa- ci y Cons ain s". AIIE T ansac ions, Vol.7, 170-176. (6] Fishe , M.L. (1981). "The Lag angean Relaxa ion Me hod o Sol ing ln ege P og amming P oblems". Managemen Science, Vol. 27, 1-18. [7] Flo iau, M.; Leus a, J .K. y Rinooy Kan, A.H.G. (1980). "De- e minis ic P oduc ion Planning: Algo i hms and Complexi y". Mana- gamen Science, Vol. 26, 669-679. [8] Lamb ech , M.R. y Vande eken, H. (1979). "Heu is ic P ocedu e o he Single-Ope a ion Mul i-i em Loading P oblem". AIIE T ansac- ions, Vol. 11, 319-326. [9] La añe a, J.; Onie a, L. y Lozano, S. (1988) Mé odos Mode nos de Ges ión de P oducción. Alianza Edi o ial. [10] Lasdon, L.S. y Te jung, R.C. {1971). "An E icien Algo i hm o Mul i-i em Scheduling". Ope a ions Resea ch, Vol. 19, 946-969. [11] Lozano, S.; La añe a, J. y Ouie a, L. (1991). "P imal-Dual Ap- p oach · o he Single Le e! Capaci a ed Lo -Sizing P oblem". Eu opean J. o Ope a ional Resea ch, Vol. 51, 354-366. [12] Lozano, S.; La añe a, J. y Onie a, L. (1991). "Plani icación Mul- ini el con Limi aciones de Capacidad". Qües iió, Vol. 15. [13] Maes, J. y Van Wassenho e, L. (1986). "A simple Heu is ic o he Mul i-i em Single-Le e! Capaci a ed Lo -Sizing P oblem". Ope a ions Resea ch Le e s, Vol. 4, 265-273. (14] Maes, J. y Van Wassenho e, L. (1986). "Mul i-i em Single-Le e} Ca- paci a ed Dynamic Lo -Sizing Heu is ics: A Compu a ional Compa ison (Pa 1: S a ic Case)". IEE T ansac ions, Vol. 18, 114-123. 93 [15] Maes, J.; McClain, J.O. y Van Wassenho e, L. (1991). "Mul ile el Capaci a ed Lo sizing Complexi y and LP-based Heu is ics". Eu opean J. o Ope a ional Resea ch, Vol. 53, 131-148. [16] Manne, A.S. (1958). "P og amming o Economic Lo Sizes". Mana- gemen Science, Vol. 4, 115-135. [17] Ma s en, R.E. (1975). "The Use o he BOXSTEP Me hod in Disc e e Op imiza ion". Ma hema ical P og amming S udy, Vol. 3, 127-144. [18] Newson, E.F. (1975). "Mul i-i em Lo Size Scheduling by Heu is ic. Pa 1: Wi h Fixed Resou ces". Managemen Science, Vol. 21, 1186- 1193. [19] O nie a, L.; Lozano, S.; La aiie a, J. y Ruiz, R. (1987). "Mé odo P imal Dual pa a Modelos de Plani icación con Cos es Cónca os y Li- mi aciones de Capacidad". Qües iió, Vol. 11, 117-133. [20] Sil e , E.A. y Meal, H. (1973). "A Heu is ic o Selec ing Lo -Size Quan i ies o he Case o a De e minis ic Time-Va ying Demand Ra e and Disc e e Opo uni ies o Replenishmen ". P oduc ion and In en- o y Managemen , Vol. 12, 64-74. [21] Thizy, J .M. y Van Wassenho e, L. (1985). "Lag angean Relaxa- ion o he Mul i-i em Capaci a ed Lo -Sizing P oblem: A Heu is ic Implemen a ion". IIE T ansac ions, Vol. 17, 308-313. [22] Wagne , H.M. y Whi in, T.M. (1958). "A Dynamic Ve sion o he Economic Lo Size M o del". M anagemen S cien ce, Vol. 5, 89-96. [23] Zangwill. W.I. (1968). "Minimun Con a e Cos Flows in Ce ain Ne wo ks". Managemen Science, Vol. 14, 429-450. ENGLISH SUMMARY: COMPLEMENTARY HEURISTIC TO DUAL APPROACHES TO THE CAPACITATED LOT-SIZING PROBLEM S. Lozano, J. La añe a y L. Onie a l. INTRODUCTION The single le e! capaci a ed lo -sizing p ciblem (SLCLSP) consis s in de e - mining he quan i ies and iming o p oduc ion ba ches in o de o sa is y known 94 o expec ed ex e na! equi emen s while incu ing in mínimum cos s. No back- logging is allowed. The e a e limi s on he amoun o esou ce a ailable in each pe íod. This p oblem is known o be N ?-Comple e [7]. 2. MODEL FORMULATION Le : N -Numbe o i ems L -Numbe o pe iods Zi - P oduc ion o í em i in pe iod l¡ -ln en o y o i em i in pe iod D¡ - Demand o i em i in pe iod s¡ -Se up cos o i em i p¡ -Ma ginal p oduc ion cos o i em i h¡ -Uni holding cos o í em i I< -A ailable capaci y in pe iod a¡ -Se up ime o i em i b¡ -Capaci y abso p ion coe icien o í em i The ma hema ical model is: whe e N L Min ¿¿ (s¡6(xi ) + PiXi + h¡l¡ ) i=l =l subjec o Ii, -1 + Xi - li = Di i = 1, ... , N; = 1, .. . ,L N 2:::: (a¡c5(xi ) + b¡Xi ):::; /{1 = 1, ... , L i=l Xi 2: O, [¡, 2: O, /¡o = O 6(:z:) = { ~ 95 si x >O si :e= O This p oblem can be e o mula ed in e ms o dominan schedules. Such schedules a e he ones o whoch he ollowing holds: +s Xi = ¿nik S = 0, 1, 2, ... k= This is known as Manne's [16] o mula ion: whe e N F Min ¿¿c;;B;; i=lj=l N F subjec o LLmij Bij ~ K = 1, 2, ... , L. i=li=l F ¿oij = 1 i = 1, 2, ... , N. j=l B;i =O, 1 L Cij ¿ (s;b(Xij ) + p¡Xij + h¡Jij ) =l iij a¡b(Xij ) + b;Xij 3. APPROXIMATE SOLUTIONS The p e ious linea p og am is di icul o sol e because o he big numbe o a iables in ol ed. I has been sol ed using specialized la ge scale algo i hms ([3], [4], [10], [18]). Ano he p ac ica! app oach is o use p imal heu is ics {[5], [20], [8], [2], [13], [14]). Howe e , a mo e p omising app oach is o use a dual app oach ([21], [19], [11], [12]). This app oach consis s in elaxing he capaci y cons ain s, com- pu ing adequa e shadow p ices. The uncapaci a ed elaxed p oblem can be independen ly sol ed o each i em. The solu ion o Manne's o mula ion assumes a linea app oxima ion o he se up consump ion o capaci y. Thus, he esul ing p oduc ion plan usually is 96 un easible. The e o e, i is necessa y o de ise a manne o look o easibili y by mino modi ica ion o he solu ion. 4. HEURISTIC This sec ion desc ~bes a heu is ic aimed a ob aining a easible p oduc ion plan. I can be used in p oblems wi h se up imes. Recall ha in his case, e en o ind such a solu ion is N P-comple e (15]. The heu is ic consis s in educing he capaci y equi emen s in hose pe iods in which insu icien capaci y exis s. S a ing wi h he las pe iod, he p e ious pe iod in which in easibili y occu s is de ec ed and h ee a emp s a e made o elimina e i . I hese a emp s a e success ul, hen he closes p e ious pe iod showing in easibili y is conside ed nex and he p ocess is epea ed. I he algo- i hm ails o elimina e he in easibili y in any o hese pe iods, i s ops. I , in u n, pe iod O is eached, a easible p oduc ion plan has been ound. The h ee a emp s a e called Blocks 1, II and III because ha is he o de in which hey a e applied. Block 1 spli s lo s c ea ing new se ups in la e pe iods wi hou in oducing new in easibili ies. I ems a e conside ed in non-dec easing o de o he ollowing a io. This a io penalizes he cos and ime due o he new se ups and a ou s holding cos sa ings and in easibili y educ ion. As a consequence, his ou ine makes be e use o he a ailable capaci y s¡(a¡ + 1) b;h; o he la e pe iods o he ho izon. Such unused can be impo an depending on he deg ee o ba ching o he solu ion. An example o his si ua ion is he o en ound ini e-ho izon e ec which consis s in ha he la es pe iods se ups a e a ely cos e ec i e. Block 11 shi s p oduc ion o ea lie pe iods in which a se up al eady exis s and enough slack is a ailable. l ems a e conside ed in non-dec easing o de o he a io h¡ b; which penalizes holding cos inc ease and a ou s in easibili y educ ion. These shi s lead oan inc ease in holding cos s hough no addi ional se up cos s a e incu ed. E en se ups can be sa ed in he easible pe iod i en i e lo s a e shi ed. 97 Block 111 also shi s p oduc ion o ea lie pe iods wi h slack capaci y bu c ea ing new se ups. I ems a e conside ed in non-dec easing o de o he a io s¡h¡(a¡ + 1) b¡ which penalizes se up and holding cos inc ease, and esou ce consump ion due o he new se ups, a ou ing in easibili y educ ion. E e y shi inc eases bo h se up and holding cos s. The e o e, his ou ine is in oked only i blocks 1 and II ail o elimina e all he in easibili y in he gi en pe iod. 5. INTEGRATION WITH DUAL APPROACHES The p oposed heu is ic is a pe ec complemen o dual app oaches since he la e upda e he esou ce p ices in e e y i e a ion gene a ing a cos e ec i e solu ion (composed o dominan schedules) which, un o una ely, is no easible. The heu is ic makes mino adjus men s o such solu ions in o de o imp o e i s easibili y. In pa icula , i has been in eg a ed wi h a p imal dual app oach [11] and he subg adien me hod [21]. Also, dual app oaches p o ide lowe bounds on he op imal solu ion, which can be used o assess he quali y o he solu ion ob ained by he heu is ic. 6. COMPUTATIONAL EXPERIENCES The heu is ic, appended o he p imal dual and subg adien me hods, has been applied o se e a! p oblems, compa ing he solu ion ob ained o hose p o- ided by o he heu is ics ([8], [13]). The esul s a e included in able l. They show he me i o his heu is ic app oach. 98