ANT COLONY OPTIMIZATION WITH DOUBLE SELECTIONS FOR SOLVING INTEGRATED SCHEDULING PROBLEM IN MANUFACTURER

Sobri Abusini, Mita Akbar Sukmarini, Corina Karim

Abstract


In this paper, we studied ant colony optimization for solving integrated scheduling of production and distribution problems. We improved the ant colony optimization by adding double selections, there are, roulette wheel and elitism selections. Roulette wheel selection is used to determine the path where ants pass through before knowing pheromone information in that path. Meanwhile, elitism selection is used to keep the best solution before the more optimum solution obtained. Then, ant colony optimization and improved ant colony optimization are implemented in solving integrated scheduling of production and distribution problem in PT. BFPI. The aim of this paper is to achieve optimum production and distribution schedule in order to minimize the total cost of production and distribution. We also compare performance of both applied methods and draw the conclusion. The results show that the method we proposed has more advantage.

Keywords


ant colony optimization; roulette wheel selection; elitism selection; integrated scheduling

Full Text:

PDF

References


M. Dorigo, and T. Stutzle, Ant Colony Optimizaton. Cambridge: MIT Press, 2004.

M. Dorigo, V. Maniezzo, and A. Colorni, “The ant system: optimization by a colony of cooperating agents,” Transactions on Systems, Man, and Cybernetics – Part B, vol. 26, p. 29-41, 1996.

C. Rajendran and H. Ziegler, “Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs,” European Journal of Operational Research, vol. 115, p. 426-438, 2004.

J. Zhang, X. Hu, X. Tan, J. H. Zhong and Q. Huang, “Implementation of an ant colony optimization technique for job shop scheduling problem,” Transactions of the Institute of Measurement and Control, vol. 28, no. 1, p. 93–108, 2006.

R. Vodak, M. Bil, and Z. Krivankova, “A modified ant colony optimization algorithm to increase the speed of the road network recovery process after disasters,” International Journal of Disaster Risk Reduction, vol. 31, p. 1092-1106, 2018.

D. Sudholt and C. Thyssen, “Running time analysis of ant colony optimization for shortest path problems,” Journal of Discrete Algorithms, vol. 10, p. 165-180, 2012.

J. Yang, X. Shi, M. Marchese, and Y. Liang, “An ant colony optimization method for generalized TSP problem,” Progress in Natural Science, vol. 18, p. 1417-1422, 2008.

H. Eldem and E. Ulker, “The application of ant colony optimization in the solution of 3D traveling salesman problem on a sphere,” Engineering Science and Technology, an International Journal, vol. 20, p. 1242-1248, 2017.

G.Singh, R. Metha, Sonigoswami, and S. Katiyar, “implementation of travelling salesman problem using ant colony optimization,” Journal of Engineering Research and Applications, vol. 4, no. 6, p. 63-67, 2014.

B. Li, L. Wang, and W. Song, “Ant colony optimization for the traveling salesman problem based on ants with memory,” Fourth International Conference on Natural Computation, p. 496-501, 2008.

P. Mathiyalagan, S. Suriya, and S. N. Sivanandam, “Modified ant colony algorithm for grid scheduling,” International Journal on Computer Science and Engineering, vol. 2, no. 2, p. 132-139, 2010.

B. Cheng, Q. Wang, S. Yang, and X. Hu, “An improved ant colony optimization for scheduling identical parallel batching machines with arbitrary job sizes,” Applied Soft Computing, vol. 13, p. 765-772, 2013.

I. Chaouch, O. B. Driss, and K. Ghedira, “A modified ant colony optimization algorithm for the distributed job shop scheduling problem,” Procedia Computer Science, vol. 112, p. 296-305, 2017.

C. M. Pessoa, C. Ranzan, L. F. Trierweiler, and J. O. Trierweiler, “Development of ant colony optimization (ACO) algorithms based on statistical analysis and hypothesis testing for variable selection,” IFAC-Papers OnLine, vol. 48, no. 8, p. 900-905, 2015.

H. Idris, A. E. Ezugwu, S. B. Junaidu, and A. O. Adewumi, “An improved ant colony optimization algorithm with fault tolerance for job scheduling in grid computing systems,” PLoS ONE, vol. 12, no. 5, 2017.

X. Zhang, X. Shen, and Z. Yu, “A novel hybrid ant colony optimization for a multicast routing problem,” Algorithms, vol. 12, no. 1, p. 1-33, 2019.

X. Hu, P. Lu, X. Zhang, and J. Wang, “Improved ant colony optimization for weapon-target assignment,” Mathematical Problems in Engineering, 2018.

W. Gao, “Improved ant colony clustering algorithm and its performance study,” Computational Intelligence and Neuroscience, 2016.

J. Bagherzadeh and M. Madadyaradeh, “Improved an improved ant algorithm for grid scheduling problem,” 14th International CSI conference, 2009..

Y. B. Yang, Methods and techniques used for job shopscheduling, University of Central Florida, 1977.

J. Blazewicz, W. Domschke, and E. Pesch, “The job shop scheduling problem: Conventional and new solution techniques,” European Journal of Operational Research, vol. 93, p. 1-33, 1996.

M. Yousefi, M. Yousefi, D. Hooshyar, and J. A. D. S. Oliveira, “An evolutionary approach for solving the job shop scheduling problem in a service industry,” International Journal of Advances in Intelligent Informatics, vol. 1, no. 1, p. 1-6, 2015.

C. Ozguven, L. Ozbakir, and Y. Yavuz, “Mathematical models for job-shop scheduling problems with routing and process plan flexibility,” Applied Mathematical Modelling, vol. 34, p. 1539-1548, 2010.

R. Matai, S. P. Singh, and M. L. Mittal, “Traveling salesman problem: an overview of applications, formulations, and solution approaches,” Traveling Salesman Problem, Theory and Applications, 2010.

M. Dorigo, M. Birattari, and T. Stutzle, “Ant colony optimization: artificial ants as a computational intelligence technique,” IEEE Computational Intelligence Magazine, p. 28-39, 2006.

K. Jebari and M. Madiafi, “Selection methods for genetic algorithms,” International Journal of Emerging Sciences, vol. 3, no. 4, p. 333-344, 2013.

S. L. Yadav and A. Sohal, “Study of the various selection techniques in genetic algorithms,” International Journal of Engineering, Science and Mathematics, vol. 6, no. 3, p. 198-204, 2017.

F. Alabsi and R. Naoum, “Comparison of selection methods and crossover operations using steady state genetic based intrusion detection system,” Journal of Emerging Trends in Computing and Information Sciences, vol. 3, no. 7, p. 1053-1058, 2012.

E. G. Talbi, Metaheuristics from Design to Implementation. Canada: John Wiley & Sons, Inc., 2009.

R. L. Haupt and S. E. Haupt, Practical Genetic Algorithms Second Edition. Canada: John Wiley & Sons, Inc., 2004.




DOI: https://doi.org/10.21776/ub.jemis.2019.007.01.4

Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.