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 Este trabajo presenta una heurística de varios pasos para la obtención de soluciones admisibles al problema de planificación de la producción con limitaciones de capacidad, a partir de las soluciones aproximadas que proporcionan los métodos duales basados en la relajación del problema. La heurística es complementaria a la aplicación de dichos métodos, buscando soluciones admisibles derivadas de las proporcionadas por la solución a la relajación. Complementary heuristic to dual approaches to the capacitated lot-sizing problem. Keywords: Planificación de la producción, limitaciones de capacidad, relajación Lagrangiana, precio de los recursos, tiempos de puesta a punto, soluciones heurísticas. -Escuela Superior de Ingenieros Industriales de Sevilla. Avda. Reina Mercedes s/n. 41012 Sevilla. -Article rebut el novembre de 1991. -Acceptat el juny de 1992. 77 l. INTRODUCCIÓN La determinación del plan detallado de producción supone la fijación de las cantidades que se han de fabricar de cada uno de los tipos de productos en los periodos considerados de forma que los costes de operación que dependen de esta decisión sean mínimos. La literatura sobre producción ofrece soluciones operativas razonables al problema cuando la representación de los costes y del consumo de la capacidad disponible da lugar a modelos lineales (Larrañeta et al. [9]}. Si las limitaciones de capacidad no actúan es posible realizar la planificación individual de cada uno de los productos, por lo que la consideración de los costes fijos no supone un incremento apreciable de complejidad, resolviéndose el problema mediante programación dinámica (Wagner y Whitin [22]). Pero si es necesario incluir costes fijos y limitaciones de capacidad, el modelo resultante es N P-completo (Florian et al. [7]), por lo que la optimización es sólo aplicable a situaciones en las que intervienen muy pocos productos. El enfoque que aparece como más fructífero en el caso general es la relajación del modelo a un problema lineal, que se aborda mediante procedimientos duales, aproximando sucesivamente los precios internos de los recursos. (Onieva et al. [19], Lozano et al. [11]). En el apartado 2 se recoge explícitamente el modelo analizado, describiendo las características de las soluciones a los enfoques duales en el apartado 3. La heurística se presenta en el apartado 4 y su integración con los enfoques duales en el 5. El apartado 6 incluye las experiencias computacionales realizadas aplicando la heurística a un conjunto de problemas. 2. TERMINOLOGÍA, NOTACIÓN Y MODELO La notación es la siguiente: N -número de artículos i -índice correspondiente a cada artículo (i = 1, 2, ... , N) L -número de periodos en el horizonte de planificación -índice correspondiente a cada periodo (t = 1, 2, ... , L) Zit -unidades producidas del artículo i en el periodo t l¡t -unidades de inventario del producto i al final del periodo t 78 D;t -unidades de demanda del producto i en el periodo t s; -coste fijo en el que se incurre por iniciar un lote de fabricación de i p; -coste variable de fabricación del producto i h; -coste variable de mantenimiento del stock del producto i Kt -capacidad disponible en el periodo t a; -capacidad consumida por iniciar la fabricación de i b; -consumo marginal de capacidad por unidad fabricada de i Con estos elementos, un modelo que recoge el problema de encontrar un plan óptimo de producción que minimice los costes totales de fabricación e inventario es, N L Min LL (s;8(x;t) + p;X;t + h;l;t) i=1 t=1 sujeto a Ii,t-1 + Xitl;t = D;t i = 1, .. . ,N; t = 1, . .. ,L N L(a;8(x;t)+b;x;t) ~ I<t t = 1, ... ,L i=1 Xit 2: 0, f;t 2: 0, J;o = 0 representando 8(x) = { ~ si x >O si x =O La producción global en el horizonte de tiempo considerado es, para cada producto i, la demanda total en el mismo. Debido a ello, el coste variable total es constante, independientemente de las decisiones que se tomen, por lo que puede suprimirse del modelo. En el análisis del modelo se considera el subconjunto de las formas de producción compuestas por secuencias dominantes. Se definen éstas como las que satisfacen la propiedad Xit · Ii,t- 1 = O para cada t. Corresponden a planes de producción en los que, t+• x;t = ¿nik s =o, 1, 2, ... k=t 79 cubriendo cada lote la demanda de un número completo de periodos. Además, los lotes se fabrican en periodos que se inician sin inventario. Las secuencias dominantes tienen la propiedad de ser óptimas cuando las limitaciones de capacidad no actúan. En el caso de que lo hagan, una propiedad de las soluciones óptimas es (Zangwill [23]) 0::::: Xit) · 0::::: Ii,t-d · Ht = O, siendo Ht la holgura de capacidad del periodo t. Las secuencias dominantes son un subconjunto de las formas de producir que satisfacen esta propiedad. Además, la resolución aproximada del problema que nos ocupa mediante los métodos duales desconsidera las limitaciones de capacidad como restricción explícita, permitiendo su transgresión. La solución óptima del modelo aproximado satisface las limitaciones de capacidad, pero con una consideración aproximada de los consumos de capacidad asociados a las puestas a punto de las series de producción. Dado que existen L periodos, el número máximo de secuencias dominantes para cada artículo es de F = 2L-l. Cada secuencia define una forma de producción y un inventario resultante en todo el horizonte: Xij = (Xijl, Xij2, · · ·, XijL) = (Xijt) indica la secuencia dominante de producción j (= 1, 2, ... , 2L-l) aplicada al artículo i l;; (I;;¡,l;;2,···•lijL)=(I;jt) indica el inventario en cada uno de los periodos, que resulta de emplear la secuencia de producción z;;. Escribiendo el modelo con estos elementos resulta, donde N F Min LLc¡;O;; i=lj =1 N F sujeto a LLmi;tO;; $ I<t t = 1, 2, ... , L. i=lj=l F ¿:o¡;=1 i=1,2, ... ,N. j=l O¡;= O, 1 para cada i,j. L e;; = L (s;ó(x;;t) + p;z;;t + h¡l;;t) t=l es el coste de producción e inventario de la secuencia x;; en todo el horizonte; Trlijt = a¡Ó(Xijt) + b¡Xijt 80 el consumo de capacidad de la secuencia X;j en el periodo t; ()¡i son variables de decisión binarias indicando el empleo, ó no, de la secuencia Xij. Este modelo de variables enteras resulta de grandes dimensiones, constando de N+ L restricciones y N· 2L-l variables binarias. La relajación continua del modelo con B;j 2: O se analiza como la aproximación a la solución del problema de planificación con costes fijos y limitaciones de capacidad. Este planteamiento del problema fue introducido por Manne [16) y ha servido como modelo base para los estudios posteriores. La extensión del problema a la consideración explícita de estructuras de fabricación multinivel con un "cuello de botella" en forma de limitaciones de capacidad fue modelada por Billington et al. [1), y representa una extensión del modelo aquí considerado, si bien la heurística que se describe en este trabajo es aplicable también a la obtención del plan de producción de dicho cuello de botella. 3. SOLUCIONES APROXIMADAS Han sido numerosos los enfoques empleados para abordar la resolución del modelo descrito. El primero de ellos corresponde a intentar desde el inicio soluciones heurísticas simples que den lugar a planes admisibles. Las limitaciones de capacidad desaconsejan la posibilidad de aplicar métodos tales como el "Part Period Balancing" (Eisenhut [5]) o el de "Mínimos Costes Medios" (Silver y Meal [20]) al problema. Los propuestos por Lambrecht y Vanderveken [8) y Dixon y Silver [2) consideran explícitamente las limitaciones de capacidad. Posteriormente Maes y Van Wassenhove [13, 14) refundieron las propuestas contenidas en estas heurísticas formulándolas de forma simplificada con lo que las necesidades computacionales disminuyen. Su procedimiento es someter el problema a una batería de este tipo de heurísticas simples y seleccionar la mejor de las soluciones obtenidas con ellas. Para situaciones en las que las limitaciones de capacidad son poco estrictas (esto es, las componentes fijas de los costes y de los consumos de capacidad de recursos son reducidas) se obtienen soluciones aceptables. Otro enfoque ha sido abordar el modelo de programación lineal continua de Manne mediante procedimientos primales. Históricamente fue el primer enfoque, y en él se incluyen las propuestas de Dzielinski et al. [3), Dzielinski y Gomory [4), Lasdon y Terjung [10), pudiendo considerarse también entre ellas la de Newson [18) o 81 Más recientemente se han aplicado procedimientos duales que analizan la relajación Lagrangiana del problema. Las restricciones relajadas son las de capacidad, que se incorporan a la función objetivo mediante la imputación de precios a los recursos empleados. Thizy y Van Wassenhove [21) aplican el método del subgradiente a la resolución del Lagrangiano. Onieva et al. [19] y Lozano et al. [11] aplican el método primal dual, extendiendo dicho procedimiento a situaciones multinivel con un ·"cuello de botella" en Lozano et al. [12). El análisis dual tiene varias ventajas sobre los otros procedimientos (Fisher [6]) pero, y en este aspecto es igual a los métodos primales, la solución final obtenida no da lugar, necesariamente, a una solución admisible. Con el método primal dual se resuelve en cada iteración un subproblema primal reducido en el que se identifican las cantidades producidas en cada periodo. Y lo que es más significativo, el grado de inadmisibilidad de dicho plan. En particular, indica cual es el exceso u holgura de capacidad en cada periodo, actualizando en consonancia la imputación de precios a los recursos. La solución óptima del dual contiene un plan de producción admisible desde el punto de vista de la relajación contínua del problema. Pero la estimación de los tiempos de puesta a punto se lleva a cabo mediante la linealización de los mismos. En la implementación práctica dicha linealización no se corresponde con la realidad, por lo que la solución óptima del modelo puede ser inadmisible para el problema original, al incluir éste las puestas a punto completas. Por ello, todos los métodos, ya sean primales o duales, que abordan el problema de la planificación de la producción con costes fijos y tiempos de puesta a punto mediante el modelo aproximado de Manne [16) requieren de la incorporación de algún procedimiento que modifique la solución aproximada disponible. Esta regla heurística ha de tener en cuenta explícitamente el consumo discreto de la capacidad al iniciar las series de producción para la obtención de soluciones admisibles. Asimismo, ha de valorar explícitamente los costes a partir de la consideración explícita de la componente fija de los mismos. Thizy y Van Wassenhove [21) propusieron como regla heurística resolver, en cada iteración de su método dual, un modelo de transporte. La solución disponible del problema dual proporciona en cada iteración los periodos en que se inician series de producción para cada uno de los productos. Fijados los componentes fijos de los costes Si y de los consumos de recursos ai asociados a los lanzamientos de la producción, y evaluada la capacidad disponible restante, resulta un problema contínuo en las cantidades a producir en dichos periodos para satisfacer la demanda. Pero fijar a priori los periodos en los que se va a producir conduce en muchos casos a la inadmisibilidad del plan de producción, pues el modelo de transporte resultante es frecuentemente inadmisible. Además, el número de variables que·intervienen en el modelo de transporte es O( N L2 ), 82 con lo que su tamaño y tiempo de resolución aumentan significativamente con el número de periodos. La heurística propuesta en la siguiente sección aborda estos aspectos. 4. HEURÍSTICA Como hemos señalado, el problema de planificación de la producción con costes fijos y limitaciones de capacidad es N ?-completo. Los métodos de resolución, salvo para problemas de muy reducidas dimensiones, son de tipo aproximado. En particular, todos los basados en la formulación de Manne [16]. Cuando existen tiempos de puesta a punto, la búsqueda de una solución admisible -aún cuando no sea un plan de producción eficiente-- ya es de por sí N ?-completo (Maes et al. [15]). Es por ello imprescindible disponer de una regla heurística. En los métodos duales se parte de los precios internos>. asociados al consumo de los recursos, si bien es posible fijar dichos valores arbitrariamente "a priori". Aplicando el algoritmo de Wagner- Whitin [22] empleando como costes L c¡i + l:mijtAt t=l que tienen en cuenta los costes propios de producción C¡j más un término asociado a la valoración del consumo de los recursos, se resuelve el problema de planificación desconsiderando las limitaciones de capacidad. Las secuencias de producción obtenidas y los inventarios resultantes satisfacen Xij(i)t·l;j(i),t-l =O. Con ellas se forman las tablas de producción Xit y de inventarios l;t, que indican para las secuencias de producción identificadas la cantidad producida de cada artículo en cada uno de los periodos del horizonte y sus inventarios resultantes, evaluándose el vector de capacidades disponibles Si Zt > O para todo t, la solución obtenida es admisible. En caso contrario ha de modificarse el plan de producción mediante la heurística. La heurística que se propone puede aplicarse por sí misma, fijando los precios internos de los recursos>. arbitrariamente, o mejor en conjunción con un método 83 de selección de los mismos. En los métodos duales, tal como en el método primaldual (Onieva et al. [19], Lozano et al. [11], [12]) se pueden emplear los precios internos >. procedentes de las soluciones admisibles del problema dual que se obtienen en cada iteración. Así, cada iteración del método primal-dual supone una aplicación de la regla heurística. La regla heurística consta de tres bloques: Bloque I. Las reglas del primer bloque particionan los lotes fabricados en el último periodo en el que existe inadmisibilidad, retrasándola en la medida de lo posible hacia el periodo posterior en el que la holgura sea máxima, con el fin de que la situación resultante no sea desfavorable. El retraso se lleva a cabo incrementando los costes lo menos posible. 1° Sea t = max{t': Zt' < 0}. Se identifica con t el periodo más tardío en el que se presenta inadmisibilidad. Obviamente, si Zt' > O para todos los periodos, la solución obtenida es admisible. FIN. 2° Sean= {i: Xit ·lit > 0}. Es el conjunto de artículos que producen en exceso de la demanda del periodo considerado t. Son artículos para los que se puede contemplar el retraso de su producción, manteniendo la admisibilidad. 3° 3.1 Si n = 0, no se puede retrasar la producción. Ir a 8 {segundo bloque). 3.2 Se ordenan los artículos en orden creciente{no decrecientes si hay empates) del indicador de incremento de costes s¡{a¡ + 1) b¡h¡ La racionalidad de este criterio proviene del hecho de que al romper un lote se incune en un coste de lanzamiento adicional y se ahorra el coste de mantenimiento debido al retraso de la producción. Se incluyen también los consumos de recurso a¡ y b¡ con la finalidad de liberar la máxima cantidad del mismo en el periodo t, comprometiendo la menor cantidad posible del periodo al que se retrasa (véase el punto 5° de este bloque). La inclusión de la unidad elimina la degeneración cuando a¡ = O. Obsérvese que al no depender el criterio de ordenación de la solución concreta de partida, dicha ordenación puede hacerse a priori una sola vez. Obsérvese también que el criterio favorece el doble objetivo de la heurística: minimizar el consumo de recursos y el incremento de los costes. 84 4° 4.1 Si l;t = O, eliminar i de n y vol ver a 3°. Probar con el siguiente artículo. 4.2 Sea T = min{t': t' > t, lit' = 0}, el periodo hasta el que se abastece la demanda del artículo i con el lote producido en el periodo t. 5° Sea r(t, T) el periodo para el que se obtiene la máxima holgura de capacidad; i.e., max{ Zt': t < t' < T}. Es el periodo candidato al que retrasar el exceso de producción del artículo i en t. Si ZT :::; a;, el retraso produciría inadmisibilidad en T, en cuyo caso, eliminar i de fl e Ír a 3°. 6° Retrasar al periodo r la producción de la cantidad A • { [ZT- a; (1- 8(x;T ))] . I } u = mln b ) mln it' i t:St'<T Actualizar las variables del plan de producción y los indicadores de consumo de recursos: Zt {::== Zt + bib. ZT {::== ZT- bib.-a; (1- 8(x;T)) Xit {::== Xit -b. XiT {::== XiT + b. lit' {::== lit' -b. para t' = t, t + 1, ... , T- l. La cantidad b. a traspasar está limitada por la holgura del periodo T y los inventarios retrasados hasta dicho periodo. El corchete significa "parte entera", garantizando mediante el redondeo hacia abajo la admisibilidad en el periodo T. 7° Si Zt 2: O, se ha eliminado la inac!misibilidad en t. Ir a 1°. Si Zt < O, se ha de continuar rompiendo lotes en t. Ir a 4°. Obsérvese que el conjunto de reglas del bloque 1 finalizan: -Al alcanzar la admisibilidad (punto 7°). - Al agotarse el conjunto ele artículos cuya producción pueda atrasarse (punto 3.1). En este caso se aplican las reglas del bloque 11. Bloque II. Las reglas del segundo bloque adelantan la producción a periodos anteriores en los que haya holgura de capacidad sin crear nuevas puestas a punto (por ya existir en ellos fabricación de lotes). 85 Para mejor mostrar el carácter complementario de la heurística propuesta y los métodos duales, en la figura 1 se recoge la evolución del Lagrangiano junto con la de la mejor solución proporcionada por la heurística, a medida que itera el método primal-dual aplicado al problema que se ha denominado MARSTEN l. Se observa que la cota inferior proporcionada por el Lagrangiano converge monótonamente a su óptimo (el de la relajación continua). Simétricamente, las soluciones de la heurística van mejorando progresivamente a medida que se apoya en las secuencias de producción más apropiadas, las cuales surgen al asignar mejor los precios internos de los recursos escasos. Función ObJetivo 49500 49300 49100 48900 48700 48500 48300 48100 47900 47700 Evolución de la heurística Lagranglano + Heurfstlca 4750()~,---~--------~--~---r---.----~--~---r---.-- 1 5 g 13 17 21 25 29 33 37 4i N• Iteraciones Figura l. 92 7. REFERENCIAS (1] Billington, P.; McClain, J. y Thomas, L. (1983). "Mathematical Programming Approaches to Capacity-Constrained MRP Systems: Review, Formulation and Problema Reduction". Management Science, Vol. 29, 1126-1141. (2] Dixou, P.S. y Silver, E.A. (1981). "A Heuristic Solution Procedure for the Multi-item Single-Leve! Limited Capacity Lot-Sizing Problem". J. of Operations M anagement, Vol. 2, 23-29. (3] Dzieliuski, B.P.; Baker, C.T. y Manne, A.S. (1963). "Simulation Tests of Lot Size Programming". Management Science, Vol. 9, 229-258. (4] Dzieliuski, B.P. y Gomory, R.E. (1965). "Optimal Programming of Lot Sizes, Inventory and Labor Allocations". Management Science, Vol. 11, 874-890. (5] Eisenhut, P.S. (1975). "A Dynamic Lot Sizing Algorithm with Capacity Constraints". AIIE Transactions, Vol.7, 170-176. (6] Fisher, M.L. (1981). "The Lagrangean Relaxation Method for Solving lnteger Programming Problems". Management Science, Vol. 27, 1-18. [7] Floriau, M.; Leustra, J .K. y Rinooy Kan, A.H.G. (1980). "Deterministic Production Planning: Algorithms and Complexity". Managament Science, Vol. 26, 669-679. [8] Lambrecht, M.R. y Vanderveken, H. (1979). "Heuristic Procedure for the Single-Operation Multi-item Loading Problem". AIIE Transactions, Vol. 11, 319-326. [9] Larrañeta, J.; Onieva, L. y Lozano, S. (1988) Métodos Modernos de Gestión de Producción. Alianza Editorial. [10] Lasdon, L.S. y Terjung, R.C. {1971). "An Efficient Algorithm for Multi-item Scheduling". Operations Research, Vol. 19, 946-969. [11] Lozano, S.; Larrañeta, J. y Ouieva, L. (1991). "Primal-Dual Approach · to the Single Leve! Capaci tated Lot-Sizing Problem". European J. of Operational Research, Vol. 51, 354-366. [12] Lozano, S.; Larrañeta, J. y Onieva, L. (1991). "Planificación Multinivel con Limitaciones de Capacidad". Qüestiió, Vol. 15. [13] Maes, J. y Van Wassenhove, L. (1986). "A simple Heuristic for the Multi-item Single-Leve! Capacitated Lot-Sizing Problem". Operations Research Letters, Vol. 4, 265-273. (14] Maes, J. y Van Wassenhove, L. (1986). "Multi-item Single-Leve} Capacitated Dynamic Lot-Sizing Heuristics: A Computational Comparison (Part 1: Static Case)". IEE Transactions, Vol. 18, 114-123. 93 [15] Maes, J.; McClain, J.O. y Van Wassenhove, L. (1991). "Multilevel Capacitated Lotsizing Complexity and LP-based Heuristics". European J. of Operational Research, Vol. 53, 131-148. [16] Manne, A.S. (1958). "Programming of Economic Lot Sizes". Management Science, Vol. 4, 115-135. [17] Marsten, R.E. (1975). "The Use ofthe BOXSTEP Method in Discrete Optimization". Mathematical Programming Study, Vol. 3, 127-144. [18] Newson, E.F. (1975). "Multi-item Lot Size Scheduling by Heuristic. Part 1: With Fixed Resources". Management Science, Vol. 21, 1186- 1193. [19] O nieva, L.; Lozano, S.; Larraiieta, J. y Ruiz, R. (1987). "Método Primal Dual para Modelos de Planificación con Costes Cóncavos y Limitaciones de Capacidad". Qüestiió, Vol. 11, 117-133. [20] Silver, E.A. y Meal, H. (1973). "A Heuristic for Selecting Lot-Size Quantities for the Case of a Deterministic Time-Varying Demand Rate and Discrete Oportunities for Replenishment". Production and Inventory Management, Vol. 12, 64-74. [21] Thizy, J .M. y Van Wassenhove, L. (1985). "Lagrangean Relaxation for the Multi-item Capacitated Lot-Sizing Problem: A Heuristic Implementation". IIE Transactions, Vol. 17, 308-313. [22] Wagner, H.M. y Whitin, T.M. (1958). "A Dynamic Version of the Economic Lot Size M o del". M anagement S cien ce, Vol. 5, 89-96. [23] Zangwill. W.I. (1968). "Minimun Convave Cost Flows in Certain Networks". Management Science, Vol. 14, 429-450. ENGLISH SUMMARY: COMPLEMENTARY HEURISTIC TO DUAL APPROACHES TO THE CAPACITATED LOT-SIZING PROBLEM S. Lozano, J. Larrañeta y L. Onieva l. INTRODUCTION The single leve! capacitated lot-sizing prciblem (SLCLSP) consists in determining the quantities and timing of production batches in order to satisfy known 94 or expected externa! requirements while incurring in mínimum costs. No backlogging is allowed. There are limits on the amount of resource available in each períod. This problem is known to be N ?-Complete [7]. 2. MODEL FORMULATION Let: N -Number of items L -Number of periods Zit - Production of ítem i in period t l¡t -lnventory of item i in period t D¡t - Demand of item i in period t s¡ -Setup cost for item i p¡ -Marginal production cost for item i h¡ -Unit holding cost for ítem i I<t -A vailable capacity in period t a¡ -Setup time for item i b¡ -Capacity absorption coefficient for ítem i The mathematical model is: where N L Min ¿¿ (s¡6(xit) + PiXit + h¡l¡t) i=l t=l subject to Ii,t-1 + Xitlit= Dit i = 1, ... , N; t = 1, .. . ,L N 2:::: (a¡c5(xit) + b¡Xit):::; /{1 t = 1, ... , L i=l Xit 2: O, [¡, 2: O, /¡o = O 6(:z:) = { ~ 95 si x >O si :e= O This problem can be reformulated in terms of dominant schedules. Such schedules are the ones for whoch the following holds: t+s Xit = ¿nik S = 0, 1, 2, ... k=t This is known as Manne's [16] formulation: where N F Min ¿¿c;;B;; i=lj=l N F subject to LLmijtBij ~ Kt t = 1, 2, ... , L. i=li=l F ¿oij = 1 i = 1, 2, ... , N. j=l B;i =O, 1 L Cij ¿ (s;b(Xijt) + p¡Xijt + h¡Jijt) t=l ffiijt a¡b(Xijt) + b;Xijt 3. APPROXIMATE SOLUTIONS The previous linear program is difficult to solve because of the big number of variables in volved. It has been sol ved using specialized large scale algorithms ([3], [4], [10], [18]). Another practica! approach is to use primal heuristics {[5], [20], [8], [2], [13], [14]). However, a more promising approach is to use a dual approach ([21], [19], [11], [12]). This approach consists in relaxing the capacity constraints, computing adequate shadow prices. The uncapacitated relaxed problem can be independently solved for each item. The solution to Manne's formulation assumes a linear approximation of the setup consumption of capacity. Thus, the resulting production plan usually is 96 unfeasible. Therefore, it is necessary to devise a manner to look for feasibility by minor modification of the solution. 4. HEURISTIC This section descr~bes a heuristic aimed at obtaining a feasible production plan. It can be used in problems with setup times. Recall that in this case, even to find such a solution is N P-complete (15]. The heuristic consists in reducing the capacity requirements in those periods in which insufficient capacity exists. Starting with the last period, the previous period in which infeasibility occurs is detected and three attempts are made to eliminate it. If these attempts are successful, then the closest previous period showing infeasibility is considered next and the process is repeated. If the algorithm fails to eliminate the infeasibility in any of these periods, it stops. If, in turn, period O is reached, a feasible production plan has been found. The three attempts are called Blocks 1, II and III because that is the order in which they are applied. Block 1 splits lots creating new setups in later periods without introducing new infeasibilities. Items are considered in non-decreasing order of the following ratio. This ratio penalizes the cost and time due to the new setups and favours holding cost savings and infeasibility reduction. As a consequence, this routine makes better use of the available capacity s¡(a¡ + 1) b;h; of the later periods of the horizon. Such unused can be important depending on the degree of batching of the solution. An example of this situation is the often found finite-horizon effect which consists in that the latest periods setups are rarely cost effective. Block 11 shifts production to earlier periods in which a setup already exists and enough slack is available. ltems are considered in non-decreasing order of the ratio h¡fb; which penalizes holding cost increase and favours infeasibility reduction. These shifts lead toan increase in holding costs though no additional setup costs are incurred. Even setups can be saved in the feasible period if entire lots are shifted. 97 Block 111 also shifts production to earlier periods with slack capacity bu creating new setups. Items are considered in non-decreasing order of the ratio s¡h¡(a¡ + 1) b¡ which penalizes setup and holding cost increase, and resource consumption due to the new setups, favouring infeasibility reduction. Every shift increases both setup and holding costs. Therefore, this routine is invoked only if blocks 1 and II fail to eliminate all the infeasibility in the given period. 5. INTEGRATION WITH DUAL APPROACHES The proposed heuristic is a perfect complement to dual approaches since the latter update the resource prices in every iteration generating a cost effective solution (composed of dominant schedules) which, unfortunately, is not feasible. The heuristic makes minor adjustments to such solutions in order to improve its feasibility. In particular, it has been integrated with a primal dual approach [11] and the subgradient method [21]. Also, dual approaches provide lower bounds on the optimal solution, which can be used to assess the quality of the solution obtained by the heuristic. 6. COMPUTATIONAL EXPERIENCES The heuristic, appended to the primal dual and subgradient methods, has been applied to severa! problems, comparing the solution obtained to those provided by other heuristics ([8], [13]). The results are included in table l. They show the merit of this heuristic approach. 98