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 Ant Colony Optimization algorithm (ACO) is proposed. Computational experiments are carried out comparing the proposed approach versus exact methods. Results show the efficiency of our ACO algorithm.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Niebles-Atencio, F., Neira-Rodado, D.: A Sule’s method initiated genetic algorithm for solving QAP formulation in facility layout design: a real world application. J. Theor. Appl. Inf. Technol. 84(2), 157–169 (2016)
Pinedo, M.L.: Scheduling: Theory, Algorithms, and Systems. Springer, Heidelberg (2008)
Hoogeveen, H.: Multicriteria scheduling. Eur. J. Oper. Res. 167(3), 592–623 (2005)
T’kindt, V., Billaut, J.-C.: Multicriteria Scheduling: Theory, Models and Algorithms. Springer, Berlin (2006)
Lei, D., Wu, Z.: Multi-objective production scheduling: a survey. Int. J. Adv. Manuf. Technol. 43(9–10), 926–938 (2009)
Khalouli, S., Ghedjati, F., Hamzaoui, A.: 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 2008), pp. 44–50 (2008)
Ponnamambalam, S.G., Ramkumar, V., Jawahar, N.: A multiobjective evolutionary algorithm for job shop scheduling. Prod. Plan. Control 12(8), 764–774 (2001)
Armentano, V., Claudio, J.: An application of a multi-objective tabu search algorithm to a bicriteria flowshop problem. J. Heuristics 10(5), 463–481 (2005)
Jungwattanakit, J., Reodecha, M., Chaovalitwongse, P., Werner, F.: A comparison of scheduling algorithms for flexible flow shop problems with unrelated parallel machines, setup times, and dual criteria. Comput. Oper. Res. 36(2), 358–378 (2009)
Chang, J., Ma, G., Ma, X.: A new heuristic for minimal makespan in no-wait hybrid flowshops. In: Proceedings of the 25th Chinese Control Conference, Harbin, Heilongjiang, 7–11 August 2009
Niebles Atencio, F., Solano-Charris, E.L., Montoya-Torres, J.R.: Ant colony optimization algorithm to minimize makespan and number of tardy jobs in flexible flowshop systems. In: Proceedings 2012 XXXVIII Conferencia Latinoamericana en Informática (CLEI 2012), Medellin, Colombia, 1–5 October 2012, pp. 1–10 (2012). doi:10.1109/CLEI.2012.6427154
Allaoui, H., Artiba, A.: Integrating simulation and optimization to schedule a hybrid flowshop with maintenance constraints. Comput. Ind. Eng. 47(4), 431–450 (2004)
Khalouli, S., Ghedjati, F., Hamzaoui, A.: An integrated ant colony optimization algorithm for the hybrid flow shop scheduling problem. In: Proceedings of the International Conference on Computers and Industrial Engineering (CIE 2009), pp. 554–559 (2009)
Khalouli, S., Ghedjati, F., Hamzaoui, A.: A meta-heuristic approach to solve a JIT scheduling problem in hybrid flow shop. Eng. Appl. Artif. Intell. 23(5), 765–771 (2010)
Khalouli, S., Ghedjati, F., Hamzaoui, A.: An ant colony system algorithm for the hybrid flow-shop (2011). Alaykýran, K., Engin, O., Döyen, A.: Using ant colony optimization to solve hybrid flow shop scheduling problems. Int. J. Adv. Manuf. Technol. 35 (5–6), 541–550 (2007)
Colorni, A., Dorigo, M., Maniezzo, V.: Distributed optimization by ant colonies. In: European Conference of Artificial Life, pp. 134–142 (1991)
Dorigo, M., Gambardella, L.M.: Ant colony system: a cooperative learning approach to the Traveling Salesman Problem. IEEE Trans. Evol. Comput. 1, 53–66 (1997)
Dorigo, M., Maniezzo, V., Colorni, A.: The ant system: optimization by a colony of cooperating agents. IEEE Trans. Syst. Man Cybern. B 26, 29–41 (1996)
Dorigo, M., Stützle, T.: Ant Colony Optimization. MIT Press, Cambridge (2004)
Stützle, T., Hoos, H.H.: Max–min ant system. Future Gener. Comput. Syst. 16(9), 889–914 (2000)
Tavares Neto, R.F., Godinho Filho, M.: Literature review regarding Ant Colony Optimization applied to scheduling problems: guidelines for implementation and directions for future research. Eng. Appl. Artif. Intell. 26(1), 150–161 (2013)
Blum, C., Sampels, M.: Ant colony optimization algorithm for FOP shop scheduling: a case study on different pheromones representations. In: Proceedings of the 2002 Congress on Evolutionary Computation (CEC 2002), vol. 2, pp. 1558–1563. IEEE Computer Society Press, Los Alamitos (2002)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Atencio, F.N., Prasca, A.B., Rodado, D.N., Casseres, D.M., Santiago, M.R. (2016). A Comparative Approach of Ant Colony System and Mathematical Programming for Task Scheduling in a Mineral Analysis Laboratory. In: Tan, Y., Shi, Y., Niu, B. (eds) Advances in Swarm Intelligence. ICSI 2016. Lecture Notes in Computer Science(), vol 9712. Springer, Cham. https://doi.org/10.1007/978-3-319-41000-5_41
Download citation
DOI: https://doi.org/10.1007/978-3-319-41000-5_41
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-40999-3
Online ISBN: 978-3-319-41000-5
eBook Packages: Computer ScienceComputer Science (R0)