|
|||||
|
|
LOT-SIZING IN CAPACITATED MULTI-STAGE SERIAL SYSTEMS |
|
| Authors: | VINÍCIUS A. ARMENTANO REGINA ESTHER BERRETTA PAULO M. FRANCA |
| Affiliation: | 1. Faculdade de Engenharia Elétrica e de Computação, Universidade Estadual de Campinas-UNICAMP, 13081-970 Campinas, SP, Brazil Vinicius A. Armentano is Professor in the Department of Systems Engineering at the State University of Campinas—UNICAMP, São Paulo, Brazil. His research activities embrace combinatorial optimization with particular emphasis on production planning and scheduling. He received a degree in Electrical Engineering from Mackenzie University, São Paulo, an M.Sc. in Operational Research from the State University of Campinas—UNICAMP amd a Ph.D. in Control Systems from Imperial College, London University, England. He has published in Automatica, IEEE Transactions on Automatic Control, SIAM Journal on Control and Optimization, Annals of Operations Research, Journal of the Operational Research Society, Computers&Operations Research, European Journal of Operational Research, OMEGA and other international journals.;2. Centra de Ciências Exatas e Tecnológicas, Universidade São Francisco, 13251-900 Itatiba, SP, Brazil Regina Esther Berretta is Professor in the “Centro de Ciências Exatas e Tecnológicas” at the University of São Francisco, Itatiba, São Paulo, Brazil. Her research activities and interests are combinatorial optimization and planning of manufacturing systems, with particular emphasis in heuristics and metaheuristics. She received her M.Sc. in 1993 and her Ph.D. in 1997 in Operational Research from the State University of Campinas—UNICAMP.;3. Faculdade de Engenharia Elétrica e de Computação, Universidade Estadual de Campinas-UNICAMP, 13081-970 Campinas, SP, Brazil Paulo M. França is Professor in the Department of Systems Engineering at State University of Campinas—UNICAMP, São Paulo, Brazil. His main research interests relate to the development and use of combinatorial optimization methods in the design and operation of manufacturing—especially scheduling—systems. He received his M.Sc. and doctorate in Electical Engineering at UNICAMP in 1974 and 1979, respectively. His publications have appeared in Transportation Science, Computers & Operations Research, European Journal of Operational Research, OMEGA, International Journal of Production Economics, International Transactions in Operational Research, IEEE Transactions on Power Systems and other international journals. |
| Abstract: | The lot-sizing problem in capacitated multi-stage systems with a serial product structure is addressed. This is a complex optimization problem that is part of the decision set in material requirements planning (MRP) systems. The mathematical model that describes the problem uses the concept of echelon stock and includes lead times. Setup times are taken into account, which implies that the problem of finding a feasible solution is NP-Complete. This paper proposes a heuristic method that provides a production plan in order to minimize inventory, production, and setup costs. The heuristic starts from a solution for the uncapacitated problem, which is given by the sequential application of the Wagner-Whitin algorithm. Feasibility is then attempted by shifting production amounts between periods. Computational tests conducted in 1,800 instances with up to 40 components and 18 periods have shown that feasible solutions were obtained in 83.7% of the instances. For the infeasible instances, on average, the heuristic is able to find solutions with very low capacity excess. The solutions' quality is evaluated through a lower bound provided by Lagrangean relaxation and on average the gap is less than 10%. |
| Keywords: | LOT-SIZING MULTI-STAGE PRODUCTION SYSTEMS SERIAL SYSTEMS HEURISTICS |