An analysis of the economic lot-sizing problem with return options focused on the remanufacturing plan

Abstract

El Problema del Tamaño del Lote Económico (ELSP por sus siglas en inglés) puede ser definido como el problema de determinar los períodos y las cantidades a producir en cada período para satisfacer los requerimientos de demanda de un cierto artículo sobre un horizonte de planificación finito, minimizando la suma de todos los costos involucrados. Los valores de demanda se asumen conocidos y pueden ser diferentes para cada período, es decir, demanda determinística y dinámica. Hay costos fijos y variables por producir en cada período, y por unidad almacenada en inventario de un período a otro siguiente. El ELSP es un problema bien conocido en la literatura y varias extensiones han sido planteadas para atender de una mejor manera las necesidades de la industria. Una de las más recientes y relevantes extensiones del ELSP es cuando se incluye el retorno de artículos usados, los cuales pueden ser remanufacturados para satisfacer la demanda. También debe tenerse en cuenta que los artículos usados y retornados (o retornos simplemente) puedan ser descartados de una manera adecuada, como por ejemplo, cuando los mismos no satisfacen ciertos requerimientos mínimos para ser remanufacturados. La remanufacturación es un proceso de recuperación de artículos usados mediante la cual se puede asegurar que los productos remanufacturados ofrecen la misma calidad y funcionalidad que los artículos nuevos. Ejemplos de productos remanufacturados son: autopartes, motores, neumáticos, equipamiento de aviones, cámaras fotográficas, instrumentos médicos, muebles, cartuchos, fotocopiadoras, computadoras y equipo de telecomunicaciones. La remanufacturación ofrece beneficios para todas las partes involucradas. El consumidor puede obtener productos de la misma calidad a un precio generalmente inferior que el de uno nuevo. El fabricante se ve beneficiado ya que la remanufacturación necesita menos la energía y de las materias primas, y además la remanufacturación tiende a reducir el número total de artículos puestos en el mercado al extender la vida útil de los mismos. En esta tesis consideramos la extensión del ELSP en la cual la demanda puede ser también satisfecha mediante la remanufacturación de artículos usados y retornados al origen, además de con artículos nuevos. Nos referiremos a este problema como el Problema del Tamaño del Lote Económico con Retornos (ELSR por sus siglas en inglés). Teniendo en cuenta que el ELSR es un problema NP-difícil en general e incluso para casos particulares de funciones de costos, decidimos analizar el ELSR desde el enfoque \201Cdivide y reinaras\201D, aplicado a la actividad de remanufacturación. Esta decisión está basada en el hecho de que la actividad de remanufacturación juega un rol fundamental en la resolución del ELSR ya que los planes de producción y de disposición final óptimos pueden ser determinados eficientemente y de forma independiente si el plan de remanufacturación es conocido, ya que ambos pueden ser formulados como problemas ELSP independientes. Por lo tanto en esta tesis nos enfocaremos en el problema de determinar la remanufacturación de una solución óptima del ELSR, el cual referiremos como el problema de obtener el Plan de Remanufacturación de Costo Perfecto. Se debe tener en cuenta que resolver este último problema es equivalente a resolver el ELSR, y por lo tanto es NP-difícil para los mismos casos. Considerando esta dificultad, analizaremos el problema de determinar las cantidades óptimas de remanufacturación suponiendo que el conjunto de períodos en donde la remanufacturación es posible ha sido definido con anterioridad, o en otras palabras el ESLR con Períodos Fijos para la Remanufacturación. Este supuesto está soportado tanto por motivos académicos como de la vida real, como por ejemplo: razones operativas si los operarios y las máquinas son los mismos para la producción y la remanufacturación; disponibilidad de artículos usados solo en ciertos períodos; o razones económicas causadas por remanufacturación a bajo costo en ciertos períodos. Asumiendo que la cantidad a remanufacturar en los períodos permitidos es estrictamente positiva, y que los costos son no especulativos (es decir que es conveniente producir o remanufacturar lo más tarde posible) pudimos demostrar que la cantidad total de remanufacturación de una solución óptima puede ser obtenida de manera eficiente a través de un procedimiento de tiempo lineal en el número de períodos. Entre otras implicaciones, este resultado sirve como sustento teórico para una regla de remanufacturación simple pero efectiva, utilizada para resolver el ELSR con períodos fijos de remanufacturación. La regla establece que la cantidad a remanufacturar en un cierto período fijado debe ser el mínimo entre la cantidad de retornos disponibles en le período y la demanda acumulada desde el período en cuestión hasta el período inmediatamente anterior al próximo periodo fijado como de remanufacturación positiva. En esta tesis se muestra además que esta regla puede ser aplicada con muy buenos resultados para el caso del ELSR con Sustitución en Una Vía, es decir, los productos nuevos pueden utilizarse para satisfacer al demanda de artículos remanufacturados pero no viceversa. Esta clase de problemas ocurre en la práctica cuando hay segmentos de mercado diferentes para los productos nuevos y los remanufacturados. El análisis del ELSR centrado en la remanufacturación se completa demostrando que el problema de cantidades óptimas para cada uno de los períodos fijados es NP-difícil en general, aún en el caso en que el número de períodos que se han fijado como de remanufacturación positiva, es menor que el número total de períodos. Considerando este resultado para el caso general, se provee un algoritmo recursivo de orden pseudopolinomial que puede resultar efectivo en los casos en que la cantidad de períodos fijados es pequeña en relación al largo del horizonte de planificación, o la cantidad total de retornos es pequeña en comparación con la cantidad de demanda total. Finalmente, teniendo en cuenta los buenos resultados obtenidos para el ELSR bajo el supuesto de costos no especulativos, decidimos analizar la extensión del ELSP en la cual existen restricciones de capacidad en la producción (CLSP por sus siglas en inglés) bajo este supuesto en los costos. Para este problema fuimos capaces de mejorar el orden del reconocido algoritmo de Florian y Klein (1974) de O(T 4) a O(T 3) para el caso de costos cóncavos y no especulativos y capacidad de producción estacionaria. Hasta donde sabemos, este tipo de estructura de costos incluye casos de interés que no son abarcados por trabajos previos en la literatura.

The Economic Lot-Sizing Problem (ELSP) can be defined as the problem of determining the periods and the quantities to produce in order to meet the demand requirements of a single item for each one of the periods over a finite planning horizon on time, minimizing the sum of all the costs involved. The values of the demand are known in advance and can be different for each period, i.e. deterministic and dynamic demand. Set-up and unit costs are incurred by producing at each period, and unit costs for holding inventory from one period to the next. The ELSP is a wellknown problem in the literature and several extensions have been considered in order to better attend practical and industrial needs. One of the recent and relevant extensions on the ELSP is to consider return options, i.e., used products returned to the origin that can be remanufactured to satisfy the demand requirements. On the other hand, used items (or returns) can be discarded properly, e.g. when they do not satisfy certain minimum requirements for remanufacturing. Among the recovery options, remanufacturing can be defined as the recovery process of returned products after which it is warranted that the remanufactured products offer the same quality and functionality that those newly manufactured. Products that are remanufactured include automotive parts, engines, tires, aviation equipment, cameras, medical instruments, furniture, toner cartridges, copiers, computers, and telecommunications equipment. Remanufacturing offers benefits for all of the parties involved. From the consumer’s point-of-view, remanufactured products assume the same quality of new products and are sometimes offered at an inferior market price. For the manufacturer, remanufacturing provides cost savings in energy consumption, raw materials, and labor. Finally, the environment benefits from the more efficient use of energy and raw materials. In addition, remanufacturing tends to reduce the total number of products put in the market and later disposed, i.e. long-life products. In this thesis we consider the ELSP extension for which the demand requirements can be also satisfied by remanufacturing used items returned to the origin. We refer to this problem as the Economic Lot-Sizing Problem with Remanufacturing and Final Disposal options (ELSR). Since the ELSR is an NP-hard problem, even for particular types of cost structures, we address the ELSR by means of a divide-and-conquer approach, focused on the remanufacturing activity. This approach is supported by the fact that the remanufacturing plan plays a key-role in the ELSR resolution since both the optimal production plan and the optimal final disposal plan can be determined separately and in an effective-time way if the remanufacturing plan is known, since both can be formulated as classical ELSP. Therefore, we focus on the problem of obtaining the remanufacturing plan of an optimal solution of the ELSR, which we refer as the remanufacturing plan of perfect cost. The problem of determining the remanufacturing plan of perfect cost can be considered equivalent to solve the ELSR, and then it is also NP-hard for the same cases. Considering this difficulty, we study the problem of obtaining the remanufacturing plan of perfect cost for which the periods where remanufacturing is allowed to be positive are known in advance, or in other words, the ELSR with fixed periods for remanufacturing. This assumption is supported by academic as well as practical reasons, e.g., operative reasons if the machinery and workers are the same for production and remanufacturing operations; availability of used items only in certain periods; or economic reasons due to periods with remanufacturing at low cost. Assuming strictly positive remanufacturing quantities in the periods fixed and a non-speculative motives on the costs (i.e., it is profitable to produce or remanufacture as late as possible) we prove that the total remanufacturing quantity of the remanufacturing plan of perfect cost can be obtained in linear time. Among further implications, this result serves as a theoretical support for a simple but effective rule proposed for obtaining the remanufacturing quantities of an ELSR with fixed periods for remanufacturing. This rule establishes that the remanufacturing quantity in a certain period is the minimum between the available returns and the accumulative demand from the current period until the period preceding the next period with positive remanufacturing. In this thesis we show that this rule can be effective employed for the case in which one-way substitution is allowed for the ELSR, i.e., manufactured items can satisfy the demand requirements of remanufactured items but not viceversa. This kind of situation occurs in practice when there are different market segments for new and remanufactured items. We complete the study of the remanufacturing plan showing that the problem of determining the optimal quantities for each one of the periods of an ELSR problem with fixed periods for remanufacturing is NP-hard in general, even in the case that the number of periods where remanufacturing is allowed is less than the total number of periods. In addition, we provide a recursive algorithm of pseudopolynomial time for solving the problem that can be time-effective if either the number of fixed periods for remanufacturing or the number of total returns is small. Taking into account the good results obtained for the ELSR with non-speculative motives on the costs, we decided to address the capacitated version of the economic lot-sizing problem (CLSP) under this last assumption. Thus, we are able to show that the well-known algorithm of Florian and Klein (1971) for the CLSP can be improved from O(T 4) to O(T 3) time for the case of concave cost functions with non-speculative motives and stationary capacities. This type of cost structure includes many situations of interest; including some particular cases that are not covered by algorithms proposed in previous works in the literature.