Multiobjective scheduling using an ant colony system in a mineral analysis laboratory

  • Alexander Bustacara Prasca Universidad del Atlántico. Barranquilla, Colombia.
  • Eduardo Becerra Rueda Universidad del Atlántico. Barranquilla, Colombia.
  • Fabricio Niebles-Atencio Universidad de la Costa. Barranquilla, Colombia.
DOI: https://doi.org/10.17981/ijmsor.v1i1.72
Keywords: Scheduling, Ant Colony Optimization, Multi-objective Optimization

Abstract

This paper considers the problem of scheduling a given set of samples in a mineral laboratory, located in Barranquilla Colombia. Taking into account the natural complexity of the process and the large amount of variables involved, this problem is considered as NP-hard in strong sense. Therefore, it is possible to find an optimal solution in a reasonable computational time only for small instances, which in general, does not reflect the industrial reality. For that reason, it is proposed the use of metaheuristics as an alternative approach in this problem with the aim to determine, with a low computational effort, the best assignation of the analysis in order to minimize the makespan and weighted total tardiness simultaneously. These optimization objectives will allow this laboratory to improve their productivity and the customer service, respectively. A Multi-objective Ant Colony Optimization algorithm (MOACO) is proposed. Computational experiments are carried out comparing the proposed approach versus exact methods. Results show the efficiency of our MOACO algorithm.

Downloads

Download data is not yet available.

References

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.

Published
2016-08-22
How to Cite
Bustacara Prasca, A., Becerra Rueda, E., & Niebles-Atencio, F. (2016). Multiobjective scheduling using an ant colony system in a mineral analysis laboratory. International Journal of Management Science and Operations Research, 1(1), 8-19. https://doi.org/10.17981/ijmsor.v1i1.72
Issue
Vol 1 No 1 (2016): (January - December)
Section
PAPERS
Copyright (c) 2016 This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

Published papers are the exclusive responsibility of their authors and do not necessary reflect the opinions of the editorial committee. 

IJMSOR respects the moral rights of its authors, whom must cede the editorial committee the patrimonial rights of the published material. In turn, the authors inform that the current work is unpublished and has not been previously published. 

 

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.