Programación multiobjetivo de las operaciones en un laboratorio de análisis de minerales usando colonia de hormigas
Resumen
Este trabajo considera el problema de programar un conjunto de muestras en un laboratorio de análisis de minerales ubicado en Barranquilla Colombia. Teniendo en cuenta la complejidad intrínseca del proceso y la gran cantidad de variables involucradas, este problema es considerado como NP-duro en sentido estricto. Por lo tanto, es posible encontrar una solución óptima en un tiempo razonablemente corto solo para instancias pequeñas, las cuales en general no reflejan la realidad en la industria. Por esta razón, se propone el uso de metaheurísticas como enfoque alternativo en este problema con el fin de determinar, con un costo computacional bajo, la mejor secuencia para el análisis de las muestras que optimice el makespan y la tardanza total ponderada simultáneamente. Estos objetivos de optimización permitirán al laboratorio mejorar su productividad y el servicio al cliente respectivamente. Un Algoritmo Multiobjetivo de Colonia de Hormigas (MOACO) es presentado aquí. Experimentos computacionales son realizados para comparar el algoritmo propuesto con respecto a métodos exactos. Los resultados obtenidos muestran la eficiencia de nuestro algoritmo MOACO.Descargas
Citas
M. L. Pinedo, Scheduling - Theory, Algorithms, and Systems. Springer, 2012.
E.G. Talbi, Metaheuristics: From Design to Implementation. Wiley Publishing, 2009.
http://dx.doi.org/10.1002/9780470496916
L. Jourdan, M. Basseur, and E.-G. Talbi, "Hybridizing exact methods and metaheuristics: A taxonomy," Eur. J. Oper. Res., vol. 199, no. 3, pp. 620–629, Dec. 2009.
http://dx.doi.org/10.1016/j.ejor.2007.07.035
R. F. Tavares Neto and M. Godinho Filho, "Literature review regarding Ant Colony Optimization applied to scheduling problems: Guidelines for implementation and directions for future research," Eng. Appl. Artif. Intell., vol. 26, no. 1, pp. 150–161, Jan. 2013.
http://dx.doi.org/10.1016/j.engappai.2012.03.011
H. Hoogeveen, "Multicriteria scheduling," Eur. J. Oper. Res., vol. 167, no. 3, pp. 592–623, Dec. 2005
http://dx.doi.org/10.1016/j.ejor.2004.07.011
T'kindt, V., Billaut, J.-C. Multicriteria scheduling: Theory, models and algorithms. Berlin: Springer, 2006
D. Lei, "Multi-objective production scheduling: a survey," Int. J. Adv. Manuf. Technol., vol. 43, no. 9–10, pp. 926–938, Oct. 2008.
S. Khalouli, F. Ghedjati, and A. Hamzaoui, "A meta-heuristic approach to solve a JIT scheduling problem in hybrid flow shop," Eng. Appl. Artif. Intell., vol. 23, no. 5, pp. 765–771, Aug. 2010.
http://dx.doi.org/10.1016/j.engappai.2010.01.008
S. Khalouli, F. Ghedjati, and A. Hamzaoui, "An Ant Colony System Algorithm for the Hybrid Flow-Shop Scheduling Problem," Int. J. Appl. Metaheuristic Comput., vol. 2, no. 1, pp. 29–43, 2011.
http://dx.doi.org/10.4018/jamc.2011010103
S. G. Ponnambalam, V. Ramkumar, and N. Jawahar, "A multiobjective genetic algorithm for job shop scheduling," Prod. Plan. Control, vol. 12, no. 8, pp. 764–774, Jan. 2001.
http://dx.doi.org/10.1080/09537280110040424
V. A. Armentano and J. E. Claudio, "An Application of a Multi-Objective Tabu Search Algorithm to a Bicriteria Flowshop Problem," J. Heuristics, vol. 10, no. 5, pp. 463–481, Sep. 2004.
http://dx.doi.org/10.1023/B:HEUR.0000045320.79875.e3
J. Jungwattanakit, M. Reodecha, P. Chaovalitwongse, and F. Werner, "A comparison of scheduling algorithms for flexible flow shop problems with unrelated parallel machines, setup times, and dual criteria," Comput. Oper. Res., vol. 36, no. 2, pp. 358–378, Feb. 2009.
http://dx.doi.org/10.1016/j.cor.2007.10.004
J. Chang, G. Ma, and X. Ma, "A New Heuristic for Minimal Makespan in No-Wait Hybrid Flowshops," in 2006 Chinese Control Conference, 2006, pp. 1352–1356.
http://dx.doi.org/10.1109/CHICC.2006.280673
H. Allaoui and A. Artiba, "Integrating simulation and optimization to schedule a hybrid flow shop with maintenance constraints," Comput. Ind. Eng., vol. 47, no. 4, pp. 431–450, Dec. 2004.
http://dx.doi.org/10.1016/j.cie.2004.09.002
A. Colorni, M. Dorigo, and V. Maniezzo, "Distributed optimization by ant colonies," in European Conference of Artificial Life, 1991, pp. 134–142.
M. Dorigo and L. M. Gambardella, "Ant colony system: a cooperative learning approach to the traveling salesman problem," IEEE Trans. Evol. Comput., vol. 1, no. 1, pp. 53–66, Apr. 1997.
http://dx.doi.org/10.1109/4235.585892
T. Stützle and H. H. Hoos, "MAX-MIN Ant system," Futur. Gener. Comput. Syst., vol. 16, no. 9, pp. 889–914, Jun. 2000
http://dx.doi.org/10.1016/S0167-739X(00)00043-1
M. Dorigo, V. Maniezzo, and A. Colorni, "Ant system: optimization by a colony of cooperating agents," IEEE Trans. Syst. Man. Cybern. B. Cybern., vol. 26, no. 1, pp. 29–41, Jan. 1996.
http://dx.doi.org/10.1109/3477.484436
C. Blum, "Beam-ACO—hybridizing ant colony optimization with beam search: an application to open shop scheduling," Comput. Oper. Res., vol. 32, no. 6, pp. 1565–1591, Jun. 2005.
http://dx.doi.org/10.1016/j.cor.2003.11.018
C. Blum and M. Sampels, "Ant colony optimization for FOP shop scheduling: a case study on different pheromone representations," in Proceedings of the 2002 Congress on Evolutionary Computation. CEC'02 (Cat. No.02TH8600), 2002, vol. 2, pp. 1558–1563.
http://dx.doi.org/10.1109/cec.2002.1004474
K. Alaykýran, O. Engin, and A. Döyen, "Using ant colony optimization to solve hybrid flow shop scheduling problems," Int. J. Adv. Manuf. Technol., vol. 35, no. 5–6, pp. 541–550, May 2007.
http://dx.doi.org/10.1007/s00170-007-1048-2
S. Khalouli, F. Ghedjati, and A. Hamzaoui, "Hybrid approach using ant colony optimization and fuzzy logic to solve multi-criteria hybrid flow shop scheduling problem," in Proceedings of the 5th international conference on Soft computing as transdisciplinary science and technology - CSTST '08, 2008, p. 44.
http://dx.doi.org/10.1145/1456223.1456236
S. Khalouli, F. Ghedjati, and A. Hamzaoui, "An integrated ant colony optimization algorithm for the hybrid flow shop scheduling problem," in 2009 International Conference on Computers & Industrial Engineering, 2009, pp. 554–559.
http://dx.doi.org/10.1109/ICCIE.2009.5223779
A. Colorni, M. Dorigo, and V. Maniezzo, "Distributed optimization by ant colonies," in European Conference of Artificial Life, 1991, pp. 134–142.
M. Dorigo and T. Stützle, Ant Colony Optimization. Cambridge MA: The MIT Press, 2004.
Los artículos publicados son de exclusiva responsabilidad de sus autores y no reflejan necesariamente las opiniones del comité editorial.
IJMSOR respeta los derechos morales de sus autores, los cuales ceden al comité editorial los derechos patrimoniales del material publicado. A su vez, los autores informan que el presente trabajo es inédito y no ha sido publicado anteriormente.
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.
