Geodesic
A parallel ``Go with the winners'' algorithm for~some scheduling problems
Diskretnyj analiz i issledovanie operacij, Tome 30 (2023) no. 4, pp. 5-23.

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider an approach to solving permutation scheduling problems using graphics accelerators. A parallel evolutionary algorithm based on the iterated random local search and the “Go with the winners” algorithm is proposed. A computational experiment was carried out on test instances of the classic Flow Shop problem and one applied production scheduling problem with time windows. The results show high computing speed and good accuracy of obtained solutions in comparison with various variants of the genetic algorithm and Gurobi solver. The proposed approach is easy to implement and convenient for adaptation to particular features of graphics computing and can be used to solve practical problems. Tab. 3, bibliogr. 18.
Keywords: Flow Shop problem, production scheduling, metaheuristic, GPU. 
@article{DA_2023_30_4_a0,
     author = {P. A. Borisovsky},
     title = {A parallel {``Go} with the winners'' algorithm for~some scheduling problems},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {5--23},
     publisher = {mathdoc},
     volume = {30},
     number = {4},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2023_30_4_a0/}
}
TY  - JOUR
AU  - P. A. Borisovsky
TI  - A parallel ``Go with the winners'' algorithm for~some scheduling problems
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2023
SP  - 5
EP  - 23
VL  - 30
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2023_30_4_a0/
LA  - ru
ID  - DA_2023_30_4_a0
ER  - 
%0 Journal Article
%A P. A. Borisovsky
%T A parallel ``Go with the winners'' algorithm for~some scheduling problems
%J Diskretnyj analiz i issledovanie operacij
%D 2023
%P 5-23
%V 30
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2023_30_4_a0/
%G ru
%F DA_2023_30_4_a0
P. A. Borisovsky. A parallel ``Go with the winners'' algorithm for~some scheduling problems. Diskretnyj analiz i issledovanie operacij, Tome 30 (2023) no. 4, pp. 5-23. http://geodesic.mathdoc.fr/item/DA_2023_30_4_a0/

[1] Metaheuristics for production scheduling, ISTE, London; Wiley, Hoboken, NJ, 2013, 528 pp.

[2] J. Sanders, E. Kandrot, CUDA by Example: An Introduction to General-Purpose GPU Programming, Addison–Wesley, 2011 | MR

[3] Essaid M., Idoumghar L., Lepagnot J., Brévilliers M., “GPU parallelization strategies for metaheuristics: A survey”, Int. J. Parallel Emerg. Distrib. Syst., 34:5 (2019), 497–522 | DOI

[4] Borisovsky P., Kovalenko Yu., “A memetic algorithm with parallel local search for flowshop scheduling problems”, Bioinspired optimization methods and their applications, Proc. 9th Int. Conf. (Brussels, Belgium, Nov. 19–20, 2020), Lect. Notes Comput. Sci., 12438, Springer, Cham, 2020, 201–213 | DOI

[5] Cheng J. R., Gen M., “Accelerating genetic algorithms with GPU computing: A selective overview”, Comput. Ind. Eng., 128 (2019), 514–525 | DOI

[6] Luo J., Fujimura S., el Baz D., Plazolles B., “GPU based parallel genetic algorithm for solving an energy efficient dynamic flexible flow shop scheduling problem”, J. Parallel Distrib. Comput., 133 (2019), 244–257 | DOI

[7] P. A. Borisovsky, “Solving one production scheduling problem using parallel local search algorithm on GPU”, Proc. XVIII Russian Conf. Int. Particip. “Distributed Information and Computational Resources” (Novosibirsk, Russia, Dec. 5–8, 2022), Inst. Vychisl. Technol., Novosibirsk, 2022, 16–19 (Russian)

[8] Berndorfer J., Parragh S. N., “Modeling and solving a real world machine scheduling problem with due windows and processing set restrictions”, Procedia Comput. Sci., 200 (2022), 1646–1653 | DOI

[9] Aldous D., Vazirani U., “«Go with the winners» algorithms”, Proc. 35th Annu. Symp. Foundations of Computer Science (Santa Fe, USA, Nov. 20–22, 1994), IEEE Comput. Soc., Los Alamitos, CA, 1994, 492–501 | DOI

[10] Brizuela C. A., Gutiérrez E., “Multi-objective go with the winners algorithm: A preliminary study”, Evolutionary multi-criterion optimization, Proc. 3rd Int. Conf. (Guanajuato, Mexico, Mar. 9–11, 2005), Lect. Notes Comput. Sci., 3410, Springer, Heidelberg, 2005, 206–220 | DOI | MR | Zbl

[11] Ebert T., Goldstein D., “A «Go with the winners» approach to finding frequent patterns”, Proc. 20th Annu. ACM Symp. Applied Computing (Santa Fe, USA, Mar. 13–17, 2005), ACM, New York, 2005, 498–502

[12] Peinado M., Lengauer T., “Parallel «Go with the winners» algorithms in the LogP model”, Proc. 11th Int. Parallel Processing Symp. (Geneva, Switzerland, Apr. 1–5, 1997), IEEE Comput. Soc., Los Alamitos, CA, 1997, 656–664 | DOI

[13] Juan A. A., Lourenço H., Mateo M., Luo R., Castella Q., “Using iterated local search for solving the flow-shop problem: Parallelization, parametrization, and randomization issues”, Int. Trans. Oper. Res., 21:1 (2014), 103–126 | DOI | MR | Zbl

[14] Reeves C. R., “A genetic algorithm for flowshop sequencing”, Comput. Oper. Res., 22:1 (1995), 5–13 | DOI | Zbl

[15] Taillard E., “Some efficient heuristic methods for the flow shop sequencing problem”, Eur. J. Oper. Res., 47:1 (1990), 65–74 | DOI | MR | Zbl

[16] Umam M. S., Mustafid M., Suryono S., “A hybrid genetic algorithm and tabu search for minimizing makespan in flow shop scheduling problem”, J. King Saud Univ. — Comput. Inf. Sci., 34:9 (2022), 7459–7467

[17] Evolutionary computation 1: Basic algorithms and operators, Taylor Francis, New York, 2000, 340 pp.

[18] Grabowski J., Wodecki M., “A very fast tabu search algorithm for the permutation flow shop problem with makespan criterion”, Comput. Oper. Res., 31:11 (2004), 1891–1909 | DOI | MR | Zbl