Algoritmo recocido simulado para el problema de la programación del tamaño del lote económico bajo el enfoque de ciclo básico Simulated annealing algorithm to solve the economic lot scheduling problem and the basic cycle approach

Ingeniare : Revista Chilena de Ingeniería. 2011;19(3):473-485

 

Journal Homepage

Journal Title: Ingeniare : Revista Chilena de Ingeniería

ISSN: 0718-3291 (Print); 0718-3305 (Online)

Publisher: Universidad de Tarapacá

LCC Subject Category: Technology: Mechanical engineering and machinery | Technology: Technology (General): Industrial engineering. Management engineering

Country of publisher: Chile

Language of fulltext: Spanish; Castilian, English

Full-text formats available: PDF, HTML

 

AUTHORS

José Omar Hernández
Salvador Hernández
Idalia Flores

EDITORIAL INFORMATION

Blind peer review

Editorial Board

Instructions for authors

Time From Submission to Publication: 30 weeks

 

Abstract | Full Text

La programación del tamaño del lote económico consiste en determinar la secuencia y la cantidad a fabricar de N productos en un equipo o máquina, la cual tiene una capacidad limitada. Se trata de un problema NP-duro y las propuestas de solución son diversas. En esta investigación se trabaja con el enfoque del ciclo básico planteado por Bomberger, para el cual existen varias propuestas, dentro de las cuales se pueden encontrar hasta el momento sólo algoritmos genéticos en lo que se refiere a la implementación de técnicas metaheurísticas para resolver el problema. En este trabajo se resuelve el problema de muestra de Bomberger mediante la metaheurística recocido simulado; las aportaciones de esta investigación consisten en la forma de obtener un espacio de búsqueda más restringido de las variables, y una estrategia para controlar la exploración del espacio de soluciones que realiza el algoritmo, de tal manera que se realice una búsqueda eficiente. Dado que es una primera implementación de recocido simulado se experimenta con varias combinaciones de parámetros. El algoritmo obtiene los mismos costos en casi todas las pruebas realizadas; sin embargo, en las pruebas donde la relación <img border=0 width=35 height=25 id="_x0000_i1095" src="http://fbpe/img/ingeniare/v19n3/art15-sigma.jpg" alt="http://fbpe/img/ingeniare/v19n3/art15-sigma.jpg">es alta, el algoritmo se desempeña mejor, mejorando la solución reportada anteriormente en algunos de los experimentos.<br>The problem considered is that of scheduling the production of several different items over the same machine with restricted capacity and on a repetitive basis. The problem is NP-hard and there exist several methods for the problem. In this research we worked with Bomberger's basic cycle approach, for which there are reported several solution proposals, among which are found so far only genetic algorithms in regard to the implementation of metaheuristic techniques to solve the problem. We solved Bomberger's classical example problem, applying simulated annealing metaheuristic. The contributions of this research consist on how to obtain bounds for search space of the variables, and a strategy to control the search along the solution space performed by the algorithm. Because this is a first implementation, we tested several values of the parameters. The algorithm achieves the same cost in almost all tests and the algorithm performs better where the ratio <img border=0 width=35 height=25 id="_x0000_i1094" src="http://fbpe/img/ingeniare/v19n3/art15-sigma.jpg" alt="http://fbpe/img/ingeniare/v19n3/art15-sigma.jpg">is high, improving some of the results reported in the literature.