informИнформатикаInformatics1816-03012617-6963UIIP NASBinform-263Research ArticleСТАТЬИ ПО МАТЕРИАЛАМ КОНФЕРЕНЦИЙARTICLES ON THE MATERIALS CONFERENCEЭВРИСТИЧЕСКИЕ АЛГОРИТМЫ ДЛЯ ПОСТРОЕНИЯ РАСПИСАНИЙ ОБСЛУЖИВАНИЯ ТРЕБОВАНИЙ С РАЗЛИЧНЫМИ МАРШРУТАМИГоламиО.СотсковЮ. Н.Объединенный институт проблем информатики НАН БеларусиBelarus20122302201804(36)4555Copyright © Голами О., Сотсков Ю.Н., 20182018Голами О., Сотсков Ю.Н.Голами О., Сотсков Ю.Н.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/263

Задача построения оптимального расписания обслуживания m приборами n требований с различными маршрутами является NP-трудной при любом m > 2 для всех регулярных критериев, рассматриваемых в теории расписаний. Для ее решения разработаны эвристические алгоритмы для трех регулярных критериев: минимизации общего времени обслуживания заданных требований; минимизации суммарного времени обслуживания n требований и минимизации суммарного запаздывания обслуживания n требований. Экспериментальное сравнение разработанных программ с одним из наиболее эффективных эвристических алгоритмов показало их превосходство по времени реализации и достаточно близкие результаты по качеству получаемых расписаний в случае, когда число m больше числа n. Неравенство m > n выполняется, в частности, для задач, возникающих при составленииоптимальных расписаний движения поездов по одноколейным железным дорогам.

ReferencesТанаев, В.С. Теория расписаний. Многостадийные системы / В.С. Танаев,Танаев, В.С. Теория расписаний. Многостадийные системы / В.С. Танаев,Ю.Н. Сотсков, В.A. Струсевич. – М. : Наука. Гл. ред. физ.-мат. лит, 1989. – 328 с.Ю.Н. Сотсков, В.A. Струсевич. – М. : Наука. Гл. ред. физ.-мат. лит, 1989. – 328 с.Sequencing and scheduling: Algorithms and complexity / E.L. Lawler [et al.] // Handbooks inSequencing and scheduling: Algorithms and complexity / E.L. Lawler [et al.] // Handbooks inOperations Research and Management Science. Logistics of Production and Inventory. – North-Operations Research and Management Science. Logistics of Production and Inventory. – North-Holland, 1993. – P. 445–522.Holland, 1993. – P. 445–522.Carlier, J. An algorithm for solving the job shop problem / J. Carlier, E. Pinson // ManagementCarlier, J. An algorithm for solving the job shop problem / J. Carlier, E. Pinson // ManagementScience. – 1989. – Vol. 35, № 2. – P. 164–176.Science. – 1989. – Vol. 35, № 2. – P. 164–176.Brucker, P. The job-shop problem and immediate selection / P. Brucker, B. Jurusch,Brucker, P. The job-shop problem and immediate selection / P. Brucker, B. Jurusch,A. Kramer // Annals of Operations Research. – 1994. – Vol. 50. – P. 73–114.A. Kramer // Annals of Operations Research. – 1994. – Vol. 50. – P. 73–114.Sotskov, Yu.N. NP-hardness of shop-scheduling problems with three jobs / Yu.N. Sotskov,Sotskov, Yu.N. NP-hardness of shop-scheduling problems with three jobs / Yu.N. Sotskov,N.V. Shakhlevich // Discrete Applied Mathematics. – 1995. – Vol. 59, № 3. – P. 237–266.N.V. Shakhlevich // Discrete Applied Mathematics. – 1995. – Vol. 59, № 3. – P. 237–266.Adams, J. The shifting bottleneck procedure for jobshop scheduling / J. Adams, E. Balas,Adams, J. The shifting bottleneck procedure for jobshop scheduling / J. Adams, E. Balas,D. Zawack // Management Science. – 1988. – Vol. 34, № 3. – P. 391–401.D. Zawack // Management Science. – 1988. – Vol. 34, № 3. – P. 391–401.Balas, Е. Guided local search with shifting bottleneck job shop scheduling / E. Balas,Balas, Е. Guided local search with shifting bottleneck job shop scheduling / E. Balas,A. Vazacopoulos // Management Science. – 1998. – Vol. 44, № 2. – P. 262–275.A. Vazacopoulos // Management Science. – 1998. – Vol. 44, № 2. – P. 262–275.Glover, F. Tabu search – part 1 / F. Glover // ORSA Journal on Computing. – 1989. – Vol. 1,Glover, F. Tabu search – part 1 / F. Glover // ORSA Journal on Computing. – 1989. – Vol. 1,№ 2. – P. 190–206.№ 2. – P. 190–206.Dell’Amico, M. Applying tabu search to the job-shop scheduling problem / M. Dell’Amico,Dell’Amico, M. Applying tabu search to the job-shop scheduling problem / M. Dell’Amico,M. Trubian // Annals of Operations Research. – 1993. – Vol. 41. – P. 231–252.M. Trubian // Annals of Operations Research. – 1993. – Vol. 41. – P. 231–252.Britto, R.A. Combined approach of the shifting bottleneck and tabu search heuristics for minimizing total weighted tardiness in job shop scheduling problems / R.A. Britto, G.M. Delgadillo,Britto, R.A. Combined approach of the shifting bottleneck and tabu search heuristics for minimizing total weighted tardiness in job shop scheduling problems / R.A. Britto, G.M. Delgadillo,J.P. Villalobos // Third International Conference on Production Research (ICPR-AM06). – Brazil,J.P. Villalobos // Third International Conference on Production Research (ICPR-AM06). – Brazil,Werner, F. Genetic algorithms for shop scheduling problems: a survey / F. Werner. – Germany, Magdeburg, 2011. – (Preprint 31/11, FMA. Otto-von-Guericke-University).Werner, F. Genetic algorithms for shop scheduling problems: a survey / F. Werner. – Germany, Magdeburg, 2011. – (Preprint 31/11, FMA. Otto-von-Guericke-University).Szpigel, B. Optimal train scheduling on a single line railway / B. Szpigel // Operations Research. – 1973. – Vol. 72. – P. 344–351.Szpigel, B. Optimal train scheduling on a single line railway / B. Szpigel // Operations Research. – 1973. – Vol. 72. – P. 344–351.

The authors declare that there are no conflicts of interest present.