A Bee Colony Algorithm based Solver for Flow Shop Scheduling Problem

Yosua Halim - Department of Informatics, Parahyangan Catholic University, Jl. Ciumbueuit 94, Bandung,40141, Indonesia
Cecilia Nugraheni - Department of Informatics, Parahyangan Catholic University, Jl. Ciumbueuit 94, Bandung,40141, Indonesia


Citation Format:



DOI: http://dx.doi.org/10.30630/joiv.5.2.491

Abstract


Flow Shop Scheduling (FSS) is scheduled to involve n jobs and m machines in the same process sequence, where each machine processes precisely one job in a certain period. In FSS, when a machine is doing work, other machines cannot do the same job simultaneously. The solution to this problem is the job sequence with minimal total processing time.  Many algorithms can be used to determine the order in which the job is performed. In this paper, the algorithm used to solve the flow shop scheduling problem is the bee colony algorithm. The bee colony algorithm is an algorithm that applies the metaheuristic method and performs optimization according to the workings of the bee colony. To measure the performance of this algorithm, we conducted some experiments by using Taillard's Benchmark as problem instances. Based on experiments that have been carried out by changing the existing parameter values, the size of the bee population, the number of iterations, and the limit number of bees can affect the candidate solutions obtained. The limit is a control parameter for a bee when looking for new food sources. The more the number of bees, the more iterations, and the limit used, the better the final time of the sequence of work. The bee colony algorithm can reach the upper limit of the Taillard case in some cases in the number of machines 5 and 20 jobs. The more the number of machines and jobs to optimize, the worse the total processing time.

Keywords


Scheduling; flow shop scheduling; metaheuristics; Bee Colony Algorithm.

Full Text:

PDF

References


Mumtaz, J., Zailin, G., Mirza, J., Rauf, M., Sarfraz, S., & Shehab, E. (2018). “makespan†minimization for flow shop scheduling problems using modified operators in genetic algorithm. In K. Case, & P. Thorvald (Eds.), Advances in Manufacturing Technology XXXII - Proceedings of the 16th International Conference on Manufacturing Research, ICMR 2018, incorporating the 33rd National Conference on Manufacturing Research (Vol. 8, pp. 435-440). IOS Press BV. https://doi.org/10.3233/978-1-61499-902-7-435

Laxmi A. Bewoor, V. Chandra Prakash, Sagar U. Sapkal. (2017). Comparative Analysis of Metaheuristic Approaches for “makespan†Minimization for No Wait Flow Shop Scheduling Problem. International Journal of Electrical and Computer Engineering (IJECE) Vol.7, No.1, February2017, pp. 417~423. ISSN: 2088-8708, DOI: 10.11591/ijece.v7i1.pp417-423.

Bultmann, M., Knust, S., & Waldherr, S. (2018). Flow shop scheduling with flexible processing times. OR Spectrum, 40(3), 809-829. https://doi.org/10.1007/s00291-018-0520-8Modrak, V. dan Pandian, R. S. (2010) Flow shop scheduling algorithm to minimize completion time for -jobs -machines problem. Tehni ki vjesnik, 17,3, 273–278.

Nugraheni, C. E., Abednego, L. (2016) A comparison of heuristics for scheduling problems in textile industry. Jurnal Teknologi, 78:6-6, 99–104.

Kurniawati, D.A., Nugroho, Y. I. (2017). Computational Study of N-Job M-Machine Flow Shop Scheduling Problems: SPT, EDD, NEH, NEH-EDD, and Modified-NEH Algorithms. Journal of Advanced Manufacturing SystemsVol. 16, No. 04, pp. 375-384 (2017).

Nugraheni, C. E., Abednego, L. (2021). A Combination of Palmer Algorithm and Gupta Algorithm for Scheduling Problem in Apparel Industry. International Journal of Fuzzy Logic Systems Vol. 11, No. 1, January 2021.

Sauvey, C., Sauer, N. (2020). Two NEH Heuristic Improvements for Flowshop Scheduling Problem with “makespan†Criterion. Algorithms 2020, 13, 112; doi:10.3390/a13050112.

Dr. S. Sridhar, S. Sabareesanand Dr. R. Kannan, Particle Swarm Optimization Approach for Flow Shop Scheduling Problem – a Case Study, International Journal of Mechanical Engineering and Technology, 9(11), 2018, pp. 72–80. http://www.iaeme.com/IJMET/ issues.asp?JType=IJMET&VType=9&IType=11.

Arık, O. A. (2020). Population-based Tabu search with evolutionary strategies for permutation flow shop scheduling problems under effects of position-dependent learning and linear deterioration. Soft computing. https://doi.org/10.1007/s00500-020-05234-7.

Deb S.,Tian Z.,Fong S.,Tang R.,Wong R.,&Dey N..(2018).Solving permutation flow-shop scheduling problem by rhinoceros search algorithm.Soft Computing,22(18),6025-6034.

Mohammadzadeh, H., Sahebjamnia, N., Fathollahi-Fard, A., Hajiaghaei-Keshteli, M. (2018). New Approaches in Metaheuristics to Solve the Truck Scheduling Problem in a Cross-docking Center. International Journal of Engineering, 31(8), 1258-1266.

Ilyass Mzili, Mohammed Essaid Riffi, Fatiha Benzakri (2020). Discrete penguins search optimization algorithm to solve flow shop scheduling problem. International Journal of Electrical and Computer Engineering (IJECE) Vol.10, No.4, August 2020, pp. 4426~4435ISSN: 2088-8708, DOI: 10.11591/ijece.v10i4.pp4426-4435.

Sanjeev Kumar, R., Padmanaban, K., & Rajkumar, M. (2018). Minimizing “makespan†and total flow time in permutation flow shop scheduling problems using modified gravitational emulation local search algorithm. Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture, 232(3), 534–545. https://doi.org/10.1177/0954405416645775.

Nugraheni, C. E., Abednego, L. (2016). On the Development of Hyper Heuristics Based Framework for Scheduling Problems in Textile Industry. International Journal of Modeling and Optimization, Vol. 6, No. 5, October 2016.

Weixing Su, Hanning Chen, Fang Liu, Na Lin, Shikai Jing, Xiaodan Liang, Wei Liu (2017). A novel comprehensive learning artificial bee colony optimizer for dynamic optimization biological problems, Saudi Journal of Biological Sciences, Volume 24, Issue 3, 2017, Pages 695-702, ISSN 1319-562X.

Hagh, M.T., Orandi, O.B. (2018). A Modified Artificial Bee Colony Algorithm Application for Economic Environmental Dispatch. IOP Conf. Series: Materials Science and Engineering 339 (2018) 012008 doi:10.1088/1757-899X/339/1/012008.

Chong, Chin & Sivakumar, Appa Iyer & Low, Malcolm Y. H. & Gay, Kheng. (2006). A Bee Colony Optimization Algorithm to Job Shop Scheduling. Simulation Conference, WSC. 06. 1954-1961. 10.1145/1218112.1218469.

X. Li and S. Ma, (2017). "Multiobjective Discrete Artificial Bee Colony Algorithm for Multiobjective Permutation Flow Shop Scheduling Problem with Sequence Dependent Setup Times," in IEEE Transactions on Engineering Management, vol. 64, no. 2, pp. 149-165, May 2017, doi: 10.1109/TEM.2016.2645790.

Oğuzhan Ahmet Arık. (2021). Artificial bee colony algorithm including some components of iterated greedy algorithm for permutation flow shop scheduling problems. Neural Computing and Applications. Issue 8/2021

Taillard, E. (1993) Benchmark for basic scheduling problems. European Journal of Operational Research, 64, 278–285.

Karaboga, D. (2005) An idea based on honeybee swarm for numerical optimization. Technical Report TR06. Erciyes University, Kayseri, Turkiye.

Liao, T., Aydın, D, Stützle, T. (2013) Artificial bee colonies for continuous optimization: Experimental analysis and improvements. Springer, 13, 1935–3820.

Nugraheni, C.E., Abednego, L., Widyarini, M. (2020). A Tabu Search Based Hyper-heuristic for Flexible Flowshop Scheduling Problems. International Journal of Advanced Science and Technology, 29(2), 301 - 310.