Heurística e limites duais para o problema de dimensionamento de lotes e sequenciamento com tempos de preparação dependentes da sequência

Abstract

This work addresses the lot sizing and scheduling integrated problem in single-level manufacturing systems, which consists in determining levels of production over various periods of time to meet production demands for a range of products. The objective of the problem is to get a plan that minimizes production, inventory, backlog and setup costs. We consider an industrial park consisting of unrelated parallel machines withsequence dependent setup times. A heuristic method is proposed to solve the problem. The basic idea of the algorithm is to generate solutions to an uncapacitated lot-sizing problem with only one resource and implement algorithms that restore the scheduling and time constraints. These initial feasible solutions are subjected to a process of improvement based on a Tabu Search metaheuristic. To measure the quality of solutions, we propose a combinatorial relaxation that generates dual bounds for the problem. Computational experiments are performed on random instances. The test scenarios are built to consider instances of small and large sizes. The computational results prove the efficiency of both heuristics as the procedure for generation of dual bounds.