Firefly algorithm applied to the job-shop scheduling problem

• Autorzy: Świtalski Piotr , Bolesta Arkadiusz

Identyfikatory

DOI

10.34739/si.2021.25.05

• Języki publikacji: EN

Abstrakty

EN

The job shop scheduling problem (JSSP) is one of the most researched scheduling problems. This problem belongs to the NP-hard class. An optimal solution for this category of problems is rarely possible. We try to find suboptimal solutions using heuristics or metaheuristics. The firefly algorithm is a great example of a metaheuristic. In this paper, this algorithm is used to solve JSSP. We used some benchmarking JSSP datasets for experiments. The experimental program was implemented in the aitoa library. We investigated the optimal parameter settings of this algorithm in terms of JSSP. Analysis of the experimental results shows that the algorithm is useful to solve scheduling problems.

Słowa kluczowe

EN

scheduling; job shop; firefly algorithm; aitoa library

• Wydawca: Wydawnictwo Uniwersytetu Przyrodniczo-Humanistycznego w Siedlcach
• Czasopismo: Studia Informatica : systems and information technology
• Rocznik: 2021
• Tom: Vol. 1-2(25)
• Strony: 87--100
• Opis fizyczny: Bibliogr. 19 poz., rys., tab.

Twórcy

autor

Świtalski Piotr

• Siedlce University of Natural Sciences and Humanities, Faculty of Exact and Natural Sciences, Institute of Computer Science, ul. 3 Maja 54, 08-110 Siedlce, Poland

autor

Bolesta Arkadiusz

• Siedlce University of Natural Sciences and Humanities, Faculty of Exact and Natural Sciences, Institute of Computer Science, ul. 3 Maja 54, 08-110 Siedlce, Poland

Bibliografia

• 1. Adams J., Balas E., Zawack D., The Shifting Bottleneck Procedure for Job Shop Scheduling. Management Science, 34(3), pp. 391-401, 1988. DOI: 10.1287/mnsc.34.3.391
• 2. Beasley, J.E., OR-Library: Distributing Test Problems by Electronic Mail. Journal of the Operations Research Society. 41, 11, pp. 1069-1072, 1990. DOI: 10.2307/2582903
• 3. Demirkol E., Mehta S.V., Uzsoy R., Benchmarks for Shop Scheduling Problems. European Journal of Operational Research (EJOR), 109(1), pp. 137-141, 1988. DOI: 10.1016/S0377-2217(97)00019-2
• 4. Fisher H., Thompson G.L., Probabilistic Learning Combinations of Local Job-Shop Scheduling Rules. In Muth JF, Thompson GL (eds.), Industrial Scheduling, pp. 225-251, 1963.
• 5. Khadwilard A., Chansombat S., Thepphakorn T., Thapatsuwan P., Thapatsuwan W., Pongcharoen P., Application of Firefly Algorithm and Its Parameter Setting for Job Shop Scheduling. The Journal of Industrial Technology, 2012.
• 6. Lawrence S.R., Resource Constrained Project Scheduling: An Experimental Investigation of Heuristic Scheduling Techniques (Supplement). PhD thesis, Graduate School of Industrial Administration (GSIA), 1984. Carnegie-Mellon University, Pittsburgh, PA, USA.
• 7. Lin T.L., Horng S.J., Kao T.W., Chen Y.H., Run R.S., Chen R.J., Lai J.L., Kuo I.H., An efficient job-shop scheduling algorithm based on particle swarm optimization. Expert Syst. Appl. 37 pp. 2629-36, 2010
• 8. Liu Z., Investigation of Particle Swarm Optimization for Job Shop Scheduling Problem 3rd Int. Conf. Nat. Comput. (ICNC 2007) vol 3 (Haikou: IEEE) pp. 799-803, 2007
• 9. Miller T.J., Steinhöfel K., Veenstra P., Firefly-inspired Algorithm for Job Shop Scheduling, 2018. DOI: 10.1007/978-3-319-98355-4_24
• 10. Nurul I.A., Adi S., Performance evaluation of different types of particle representation procedures of Particle Swarm Optimization in Job-shop Scheduling Problems IOP Conf. Ser.: Mater. Sci. Eng. 114, 2016
• 11. Pongchairerks P., Kachitvichyanukul V., A Particle Swarm Optimization algorithm on Job-Shop Scheduling Problems with multi-purpose machines Asia-Pacific J. Oper. Res. 26, pp. 161-84, 2009.
• 12. Storer R.H., Wu S.D., Vaccari R., New Search Spaces for Sequencing Problems with Application to Job Shop Scheduling. Management Science, 38(10), pp. 1495-1509, 1992. DOI: 10.1287/mnsc.38.10.1495
• 13. Taillard É.D., Benchmarks for Basic Scheduling Problems. European Journal of Operational Research (EJOR), 64(2), pp. 278-285, 1993. DOI: 10.1016/0377-2217(93)90182-M
• 14. Udaiyakumar K., Chandrasekaran, M., Optimization of Multi Objective Job Shop Scheduling Problems Using Firefly Algorithm. Applied Mechanics and Materials. 591, pp. 157-162, 2014. DOI: 10.4028/www.scientific.net/AMM.591.157.
• 15. Waqar A.K., Nawaf N.H., Surafel L.T., Jean M.T.N., A Review and Comparative Study of Firefly Algorithm and its Modified Versions, Optimization Algorithms - Methods and Applications, InTech, pp. 281-313, 2016. DOI: 10.5772/62472
• 16. Weise T., An Introduction to Optimization Algorithms. Hefei, Anhui, China: Institute of Applied Optimization (IAO), School of Artificial Intelligence and Big Data, Hefei University, 2018-2019. Available at: http://thomasweise.github.io/aitoa/
• 17. Yang X.S., Nature-inspired metaheuristic algorithms. Luniver Press, UK, 2010.
• Internet sources:
• 18. Oleg V. Shylo's page (http://optimizizer.com/DMU.php), accessed 13.11.2021
• 19. Éric Taillard's page (http://mistic.heigvd.ch/taillard/problemes.dir/ordonnancement.dir/ordonnancement.html), accessed 13.11.2021