RUS ENG

Научная
работа

Научные направления:

  • Дискретная оптимизация;
  • Теория расписаний;
  • Приближенные алгоритмы.

В рамках первого направления (дискретной оптимизации) основное внимание уделяется разработке и исследованию эффективных алгоритмов для дискретных задач. Указанные задачи имеют важное прикладное значение, так как они возникают при проектировании коммуникационных сетей и размещении оборудования, оптимальном планировании и управлении сложными техническими и организационными системами. Принципиальная трудность большинства задач дискретной оптимизации делает сегодня невозможным построение для них эффективных точных алгоритмов, и в связи с этим можно утверждать, что построение эффективных приближенных алгоритмов стало доминирующей тенденцией. В направлении дискретной оптимизации сотрудниками кафедры исследованы различные модели дискретных оптимизационных задач, разработаны методы построения и анализа эффективных приближенных алгоритмов, установлены нижние оценки точности алгоритмов. В частности, исследованы модели задач дискретной оптимизации с неполной или частичной информацией, которые наиболее адекватно соответствуют реальным задачам, возникающим в производстве и при принятии управленческих решений.

В рамках второго направления (теории расписаний) исследованы различные задачи распределения работ на системе с идентичными и разноскоростными параллельными процессорами, on-line и semi on-line версии задач распределения работ на параллельных приборах, задач с убывающими длительностями обслуживания, on-line версий задач упаковки с растяжением. Для указанных задач построены рекордные по гарантированной оценке приближенные алгоритмы. Предложены подходы, позволяющие оценивать качество приближенных алгоритмов для решения подобных задач.

Исследования в рамках третьего направления (теоретико-графовые исследования) направлены на решение проблем характеризации и гамильтоновости графов с заданным локальным строением; алгоритмических задач, связанных с геометрическими графами плоских и пространственных решеток; установление вычислительной сложности и сложности аппроксимации теоретико-графовых задач, связанных с понятиями независимости, доминирования и паросочетания. Следует отметить, что понятия независимости и доминирования в теории графов широко используются при решении различных проблем в области информационных технологий.

В ближайшей перспективе на кафедре предполагается продолжить исследования во всех трех указанных выше направлениях, усилив акцент на приложения в задачах распределения ресурсов, упаковки и складирования, логистики. Эти исследования в значительной мере стимулируются экономическими потребностями, соответствуют приоритетным направлениям развития науки в области информационных и инновационных технологий. Для задач дискретной оптимизации актуальными остаются исследования алгоритмов градиентного типа и алгоритмов локального поиска, серий приближенных алгоритмов, а также вопросы их эффективной реализации. Планируется также построение и исследование новых комбинаторно-геометрических моделей, ориентированных на приложения в компьютерной графике, обработке изображений и анализе данных.

В более отдаленной перспективе предполагается изучить возможности разработки новых концепций эффективности алгоритмов для задач дискретной оптимизации и теории графов, повысить роль многокритериальных задач и робастности вычислений, исследовать применение различных методов в медицине, биоинформатике, задачах логистики, поиска информации и семантического анализа данных. Указанные аспекты вызваны ужесточением требований к адекватности моделей для прикладных дискретных оптимизационных задач.

Коллектив кафедры хорошо сбалансирован – в его состав входят специалисты по дискретной оптимизации, теории расписаний и теории графов. Сотрудниками подразделения получены существенные научные результаты во всех названных основных направлениях, что составляет серьезный задел и предпосылки для успешного выполнения дальнейших исследований. Высокий уровень исследований, проводимый сотрудниками кафедры, подтверждается рядом успешно завершенных и выполняемых международных проектов. В течении последних пяти лет выполнялось задание по ГПНИ «Конвергенция–2020».

Результаты проведенных научных исследований имеют мировой уровень и отражены в значительном числе публикаций в отечественных и зарубежных журналах. Список наиболее значимых публикаций приведен ниже.

  1. Cheng T.C.E., Ng C.T., Kotov V. A new algorithm for online uniform-machine scheduling to minimize the makespan // Inf. Process. Lett.– 2006.– Vol. 99.– P. 102-105.
  2. Barketau M.S., Cheng T.C.E., Ng C.T., Kotov V.M., Kovalyov M.Y. Batch scheduling of step deteriorating jobs // J. Sched.– 2008.– Vol. 11.– P. 17-28.
  3. Ng C.T., Cheng T.C.E., Kotov V., Kovalyov M.Y. The EOQ problem with decidable warehouse capacity: Analysis, solution approaches and applications // Discrete Appl. Math.– 2009.– Vol. 157.– P. 1806-1824.
  4. Kellerer H., Kotov V. A 3/2-approximation algorithm for ki –partitioning // Oper. Res. Lett.– 2011.– Vol. 39.– P. 359-362.
  5. Cheng T.C.E., Kellerer H., Kotov V. Algorithms better than LPT for semi-online scheduling with decreasing processing times // Oper. Res. Lett.–2012.– Vol. 40.– P. 349-352.
  6. Kellerer H., Kotov V. An efficient algorithm for bin stretching // Oper. Res. Lett.–2013.– Vol. 41.– P. 343-346.
  7. Emelichev V.A., Kotov V.M., Kuzmin K.G., Lebedeva T.T., Semenova N.V., Sergienko T.I. Stability and effective algorithms for solving multiobjective discrete optimization problems with incomplete information // J. Automat. Inf. Scien.– 2014.– Vol. 46.– P. 27-41.
  8. Duginov, O. Partitioning the vertex set of a bipartite graph into complete bipartite subgraphs / O. Duginov // Discrete Mathematics and Theoretical Computer Science. - 2014. - Vol. 16, № 3. - P. 203-214.
  9. Gabay M., Kotov V., Brauner N. Semi-online bin stretching with bunch techniques // Theor. Comput. Sci.– 2015.– Vol. 602.– P. 103-113.
  10. Irzhavski P.A. Cyclic properties of the topological graphs of hexagonal grids // J. Appl. Ind. Math. – 2015. – Vol. 9. – P. 367-380.
  11. Kellerer H., Kotov V., Gabay M. An efficient algorithm for semi-online multiprocessor scheduling with given total processing time // J. Sched.– 2015.– Vol. 18.– P. 623-630.
  12. Gabay M., Brauner N., Kotov V. Improved lower bounds for the online bin stretching problem // 4OR – Q. J. Oper. Res.– 2017.– Vol. 15.– P. 183-199.
  13. Irzhavskii P.A., Kartynnik Yu.A., Orlovich Yu.L. 1-Triangle graphs and perfect neighborhood sets // J. Appl. Ind. Math.– 2017.– Vol. 11.– P. 58-69.
  14. Duginov, O. Secure total domination in graphs: Bounds and complexity / / O. Duginov // Discrete Applied Mathematics/– 2017.­- Vol. 222.- P. 97-108
  15. Dolgui, A. Alexandre Dolgui, Vladimir Kotov, Aliaksandr Nekrashevich, Alain Quilliot. General parametric scheme for the online uniform machine scheduling problem with two different speeds / A. Dolgui, V. Kotov, A. Nekrashevich, A. Quilliot // Information Processing Letters. – 2018. – Vol. 134. – P. 18-23.
  16. Комаровский, И.В. Использование α-взвешенных деревьев в учебном процессе / И.В. Комаровский, С.П. Петрович // Актуальные вопросы современной информатики: материалы IX Всероссийской научно-практической конференции (1-15 апреля 2019 года). – Коломна: Государственный социально-гуманитарный университет, 2019.
  17. Котов, В. М. Semi on-line версия задачи теории расписаний с двумя группами предметов / В. М. Котов, Н. С. Богданова // Журнал БГУ. Математика. Информатика. – 2019. – № 3. – С. 134–138.
  18. Волчкова, Г.П. Задача Qm||Cmax с ограничениями на количество работ, выполняемыми на каждом приборе / Г.П. Волчкова, В.М. Котов // Вестник Брестского государственного технического университета. Серия 4. – 2018.  № 5 (113). – С. 18–19.
  19. Иржавский, П. А. Совершенные паросочетания и K_{1, p}-ограниченные графы / П. А. Иржавский,Ю. Л. Орлович // Дискретная математика. – 2020. – Т. 32, Вып. 1. – С. 27–50.
Другие сайты факультетаСтруктураОбразованиеМагистратураНаукаСтудентуВнеучебная деятельностьСистема
менеджмента
качества (СМК)
ОлимпиадыПравовые акты
БГУ, приказы
АбитуриентуШкольникуИсторияИздания факультетаПрофбюро ФПМИПерсональные страницыФотогалереи Центр
Компетенций
по ИТ
Газета ФПМыНаши партнеры