The multistaged and capacitated lot sizing problem for parallel machines

Author(s)

Maristela Oliveira dos Santos

• Document type: Doctoral Thesis
• Press: São Carlos.
• Institution: Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação (ICMC/SB)
• Defense date: 2000-12-21

Examining board members

Marcos Nereu Arenales; Marcius Fabius Henriques de Carvalho; Ismael Regis de Farias Junior; Paulo Morelato França; Reinaldo Morabito Neto

• Advisor: Marcos Nereu Arenales; Vinicius Amaral Armentano

Abstract

This work addresses the lot-sizing problem in a multistage production system, each stage consisting of parallel machines with finite capacity. This problem lies in the determination of a production plan for the end items and their components in order to satisfy the demand in each period of a finite horizon. A setup time is considered to start production on any machine in a given period. The solution should minimize production, setup and invcntory costs. The problem is formulated as a mixed integer programming model and a basic heuristic method is proposed. From this basic method, a few heuristic approaches were developed, and some of them encompass a short-term memory tabu search. The computational analysis was done with thousands of examples randomly generated. For small instances, the heuristic solutions are compared with optimal solutions obtained by CPLEX 4.0. For larger instances, the quality of the solution is evaluated using a lower bound provided by Lagrangean relaxation. This work also presents an approach to lot sizing and scheduling. This problem is an extension of the lot sizing problem, since it integrates the lot sizing and scheduling of items on machines and periods. The goal is to determine the production plan for all items in each period and machine and in what order these items should be produced. The resolution procedure is based on the basic method for the lot sizing problem. The production sequences in each machine and period can be interpreted as a tour of the traveling salesman. In the appendix, a matrix notation is introduced, allowing to show the equivalence among alternative formulations for the multistage lot sizing problem easily, as well as among different approaches for this problem. (AU)