Институт математики им. С.Л. Соболева СО РАН
Лаборатория "Математические модели принятия решений"

Образование, ученая степень, звания:

• В 1989 г. закончил Новосибирский государственный университет, 
  механико-математический факультет, 

• Кандидат физико-математических наук.
  Тема диссертации "О сложности задач теории расписаний с длительностями, зависящими от времени"
  защищена в 1999 г. в Институте математики им. С.Л. Соболева СО РАН,
  Научный руководитель д.ф.-м.н., профессор В.Л. Береснев 

• Доцент по специальности 01.01.09 — дискретная математика и математическая кибернетика. 
  Звание присуждено в 2007 г.

• Доктор физико-математических наук.
  01.01.09 — дискретная математика и математическая кибернетика. 
  Тема диссертации "Актуальные задачи теории расписаний: вычислительная сложность и приближенные алгоритмы "
  защищена в 2015 г. в Институте математики им. С.Л. Соболева СО РАН,
  Автореферат  PDF-файл (547 Кб)                    Полный текст PDF-файл (1,4 Mб)

Научные интересы

• Теория расписаний:

параметрические задачи теории расписаний

полиномиально разрешимые классы

аппроксимационные алгоритмы

• Оптимизационные задачи на железнодорожном транспорте
• Игры на графах

Курсы лекций

Профессор National Chi Nan University (Puli, Taiwan)
      Курсы лекций Комбинаторная оптимизация (для аспирантов), 
      Комбинаторика (для студентов), Теория расписаний (для аспирантов)

Старший преподаватель кафедры дискретного анализа и исследования операций ФИТ НГУ
     Спецкурс Комбинаторная оптимизация

Доцент кафедры теоретической кибернетики ММФ НГУ

Курс для магистрантов  Scheduling Theory  (на английском)

Курс для магистрантов 2 года Combinatorial optimization (на английском)

Курс для магистрантов 1 года  Приближенные алгоритмы

Курс для магистрантов 1 года Approximation algorithms (на английском)

Спецкурс Дискретные экстремальные задачи

Учебное пособие:  А.В. Кононов, П.А. Кононова. Приближенные алгоритмы для NP-трудных задач. Учебно-методическое пособие. Новосиб. гос. ун-т. – Новосибирск : РИЦ НГУ, 2014. – 117 с.

Публикации

2024

I. Chernykh, A. Kononov, S. Sevastyanov. An exact solution with an improved running time for the routing flow shop problem with two machines // Journal of Scheduling. 27, 329–340 (2024).
 https://doi.org/10.1007/s10951-023-00784-8  

A. Kononov, M. Pakulich. An exact borderline between the NP-hard and polynomial-time solvable cases of flow shop scheduling with job-dependent storage requirements // Journal of Combinatorial Optimization. Vol. 47, article number 45 (2024)  https://doi.org/10.1007/s10878-024-01121-1

2023

 Erzin A.I. , Kononov A.V. , Melidi G.E., Nazarenko S.A., 4/3 OPT+2/3 Approximation for Big Two-Bar Charts Packing Problem // Journal of Mathematical Sciences (United States), 2023, Vol. 269. N6. pp. 813-822. https://doi.org/10.1007/s10958-023-06319-y

 A.V. Kononov, Yu.V. Zakharova. Speed Scaling Scheduling of Multiprocessor Jobs with Energy Constraint and Total Completion Time Criterion // International Journal of Artificial Intelligence. 2023 Vol. 21(2), P. 109-129.

A. Kononov, V. Il’ev. On Cluster Editing Problem with Clusters of Small Sizes. OPTIMA 2023 Lecture Notes in Computer Science.  2023. Vol. 14395. P. 316-328. https://doi.org/10.1007/978-3-031-47859-8_23

E. Bampis, A. Kononov, G. Lucarelli, F. Pascual. Non-Clairvoyant Makespan Minimization Scheduling with  Predictions. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Vol. 283, p. 9:1-9:15,  https://doi.org/10.4230/LIPIcs.ISAAC.2023.9

  A.I. Erzin, A.V. Kononov, S.A. Nazarenko, K. Sharankhaev.  An O(n log n)-time OPT+1 approximation for packing big 2-bar charts.  MOTOR 2023. Communications in Computer and Information Science 2023.  Vol. 1881, p. 122-133  https://doi.org/10.1007/978-3-031-43257-6_10

2022

 Kononov A. , Memar J., Zinder Y. Algorithms for Flow Shop with Job–Dependent Buffer Requirements, MCO 2021 Lecture Notes in Networks and Systems. 2022. V.363 LNNS. P.63-74. DOI: 10.1007/978-3-030-92666-3_6

  Bampis E., Dogeas K., Kononov A., Lucarelli G., Pascual F. Scheduling with Untrusted Predictions // Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22) July 23-29, 2022. Messe Wien, Vienna, Austria. 

  Kononov A., Zakharova Yu. Minimizing makespan for parallelizable jobs with energy constraint // Siberian Electronic Mathematical Reports 2022. Vol. 19 (2022), N 2. pp. 586-600.  DOI 10.33048/semi.2022.19.049   PDF

A. Kononov, I. Lushchakova, Cost-aware scheduling on uniform parallel machines // Computers & Industrial Engineering, (2022), Vol. 167, 107845, https://doi.org/10.1016/j.cie.2021.107845 .

Bampis E., Christou D., Escoffier B., Kononov A., Nguyen K.T.  A simple rounding scheme for multistage optimization // Theoretical Computer Science, (2022), Vol. 907, pp. 1-10, https://doi.org/10.1016/j.tcs.2022.01.009

Kononov, A., Memar, J., Zinder, Y. On a borderline between the NP-hard and polynomial-time solvable cases of the flow shop with job-dependent storage requirements // Journal of Global Optimization, 2022. Vol. 83, P. 445-456.  https://doi.org/10.1007/s10898-021-01097-w

2021

Kononov, A., Zakharova, Y. Speed scaling scheduling of multiprocessor jobs with energy constraint and makespan criterion // Journal of Global Optimization, 2021 https://doi.org/10.1007/s10898-021-01115-x

Berlińska, J., Kononov, A., Zinder, Y. Two-machine flow shop with dynamic storage space // Optimization Letters, 2021, Vol. 15(7), P. 2433–2454. https://doi.org/10.1007/s11590-020-01645-5

  Zinder Y., Kononov A., Fung J. A 5-parameter complexity classification of the two-stage flow shop scheduling problem with job dependent storage requirements // Journal of Combinatorial Optimization (2021) Vol. 42, P.  276–309, https://doi.org/10.1007/s10878-021-00706-4.

  Bampis E., Escoffier B., Kononov A. LP-Based Algorithms for Multistage Minimization Problem // WAOA 2020, Lecture Notes in Computer Science, 2021, V. 12806, p. 1-15. DOI: 10.1007/978-3-030-80879-2_1

  Kononov, A., Kovalenko, Y. Minimizing Total Completion Time in Multiprocessor Job Systems with Energy Constraint //MOTOR 2021, Lecture Notes in Computer Science 2021, Vol. 12755,
P.267-279.  DOI:10.1007/978-3-030-77876-7_18

  Bampis E., Dogeas K., Kononov A., Lucarelli G., Pascual F. Speed Scaling with Explorable Uncertainty // SPAA 2021, Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures, ACM, P. 83-94.

2020

Berlińska, J., Kononov, A., Zinder, Y. Two-machine flow shop with dynamic storage space // Optimization Letters, 2020  Vol. 15 P. 2433–2454, https://doi.org/10.1007/s11590-020-01645-5 

Kononov, A.; Kovalenko, Y. Approximation algorithms for energy-efficient scheduling of parallel jobs // Journal of Scheduling. 2020, Vol. 23(6), P. 693–709. https://doi.org/10.1007/s10951-020-00653-8 

Kononov, A., Kononova, P., Gordeev, A. Branch-and-bound approach for optima localization in scheduling multiprocessor jobs // International Transactions in Operational Research. 2020. Vol. 27, Issue 1, P. 381-393. https://doi.org/10.1111/itor.12503 

Berlińska, J., Kononov, A., Zinder, Y. Two-Machine Flow Shop with a Dynamic Storage Space and UET Operations // Advances in Intelligent Systems and Computing. 2020. Vol. 991, P. 1139-1148. DOI:10.1007/978-3-030-21803-4_112

Kononov, A., Kovalenko, Y. Makespan Minimization for Parallel Jobs with Energy Constraint // MOTOR 2020, Lecture Notes in Computer Science 2020, Vol. 12095 , P.289-300. DOI:10.1007/978-3-030-49988-4_20

Chernykh, I., Kononov, A., Sevastyanov, S. A Polynomial-Time Algorithm for the Routing Flow Shop Problem with Two Machines: An Asymmetric Network with a Fixed Number of Nodes// MOTOR 2020, Lecture Notes in Computer Science 2020, Vol. 12095, P. 301-312 DOI:10.1007/978-3-030-49988-4_21

Bampis, E., Dogeas, K., Kononov, A., Lucarelli, G., Pascual, F. Scheduling Malleable Jobs under Topological Constraints // Proceedings - 2020 IEEE 34th International Parallel and Distributed Processing Symposium, IPDPS 2020, 2020, с. 316-325, DOI: 10.1109/IPDPS47924.2020.00041 

A. Ageev, and A. Kononov. A 0.3622-Approximation Algorithm for the Maximum k-Edge-Colored Clustering Problem // MOTOR 2020, Communications in Computer and Information Science 2020 Vol. 1275, P. 3–15. DOI: 10.1007/978-3-030-58657-7_1

2019

Kononov, A.V., Panin, A.A., Plyasunov, A.V. A Bilevel Competitive Location and Pricing Model with Nonuniform Split of Demand//Journal of Applied and Industrial Mathematics 2019 Vol. 13(3), с. 500-510. DOI: 10.1134/S1990478919030104

Kononov, A.V., Kovalyov, M.Y., Lin, B.M.T. Minimizing machine assignment costs over Δ-approximate solutions of the scheduling problem P||C_max // Theoretical Computer Science 2019 Vol. 793, P. 70-78  DOI: 10.1016/j.tcs.2019.05.024

Kononov, A., Kovalenko, Y.  Approximate schedules for non-migratory parallel jobs in speed-scaled multiprocessor systems// Siberian Electronic Mathematical Reports 2019. Vol.16, с. 249-257
DOI: 10.33048/semi.2019.16.016

Kononov, A., Memar, J., Zinder, Y.  Flow shop with job–dependent buffer requirements—a polynomial–time algorithm and efficient heuristics//MOTOR 2019, Lecture Notes in Computer Science  2019 Vol. 11548, P 342-357 DOI: 10.1007/978-3-030-22629-9_24

Alhamdan, Y.M., Kononov, A. Approximability and inapproximability for maximum k-edge-colored clustering problem//CSR 2019, Lecture Notes in Computer Science 2019 Vol. 11532, P. 1-12
DOI: 10.1007/978-3-030-19955-5_1

A. Eremeev, A. Kononov, I. Ziegler. On Complexity and Exact Solution of Production Groups Formation Problem// Communications in Computer and Information Science, 2019. Vol 974. p. 111-122.

2018

  H. Gu, A. Kononov, J. Memar, Y. Zinder. Efficient Lagrangian heuristics for the two-stage flow shop with job dependent buffer requirements // Journal of Discrete Algorithms 2018, Vol. 52-53, p.143-155  DOI: 10.1016/j.jda.2018.11.011

 E. Bampis, A. Kononov, D. Letsios, G. Lucarelli, M. Sviridenko, Energy-efficient scheduling and routing via randomized rounding // Journal of Scheduling, 2018, Vol. 21, pp. 35–51. DOI: 10.1007/s10951-016-0500-2.

L. Arantes, E. Bampis, A. Kononov, M. Letsios, G. Lucarelli, P. Sens. Scheduling under uncertainty: A Query-based Approach //  IJCAI International Joint Conference on Artificial Intelligence. 2018,  p. 4646-4652

A.V. Kononov, A.A. Panin, A.V. Plyasunov. A new model of competitive location and pricing with the uniform split of the demand //Communications in Computer and Information Science. 2018. Vol. 871, p.16-28.

J. Memar, Y. Zinder, A.V. Kononov. Worst-case analysis of a modification of the Brucker-Garey-Johnson algorithm // Communications in Computer and Information Science 2018, Vol. 871 , p. 78-92

 

 E. Angel, E. Bampis, A. Kononov, D. Paparas, E. Pountourakis, V. Zissimopoulos. Clustering on k-Edge-Colored Graphs // Discrete Applied Mathematics, 2016. Vol 211. P. 15-22 DOI:10.1016/j.dam.2016.04.017

  B.M.T. Lin, F.J.Hwang, A.V. Kononov. Relocation scheduling subject to fixed processing sequences // Journal of Scheduling. 2016. Vol. 19, Issue 2, pp. 153-163, DOI: 10.1007/s10951-015-0455-8.

A. Dugarzhapov, A. Kononov. A polynomial-time algorithm for the preemptive mixed-shop problem with two unit operations per job // Journal of Scheduling. 2016. Vol. 19, Issue 1. P 61-72

E. Angel, E. Bampis, V. Chau, A. Kononov, Min-Power Covering Problems // ISAAC 2015, Lecture Notes in Computer Science, 2015, V. 9472, p. 367-377.

A.V. Kononov, B. M.T. Lin, K.-T. Fang. Single-machine scheduling with supporting tasks, Discrete Optimization 2015. Vol. 17 P. 69-79.

Ageev A., Kononov A., Improved Approximation for the Max k-Colored Clustering Problem, WAOA 2014, Lecture Notes in Computer Science, 2015, Vol. 8952, P. 1-10.

E. Bampis, A. Kononov, D. Letsios, G. Lucarelli, I. Nemparis.  From preemptive to non-preemptive speed-scaling scheduling.  Discrete Applied Mathematics  2015. Vol. 181. P. 11–20.

Kononov A. O(log m)-approximation for the routing open shop problem. RAIRO Oper. Res. 2015. Vol. 49, No 2. P. 383-391 .

 Bampis E., A. Kononov, G. Lucarelli and I. Milis, Bounded max-colorings of graphs, Journal of Discrete Algorithms. 2014. v. 26: p. 56-68.

 Gawiejnowicz S., Kononov A., Isomorphic scheduling problems, Annals of Operations Research. 2014, Vol. 213. pp. 131-145. DOI: 10.1007/s10479-012-1222-2.

Chernykh I., Kononov A., Sevastyanov S., Efficient approximation algorithms for the routing open shop problem, Computers & Operations Research, 2013, v. 40, No. 3, pp 841-847.

  Baptiste Ph., Carlier J., Kononov A., Queyranne M., Sevastianov S., Sviridenko M., Integer preemptive scheduling on parallel machines, Operations Research Letters, v. 40, N 6, 2012, pp. 440 – 444.

  Kononov A., Sevastianov S., Sviridenko M., A complete 4-parametric complexity classification of short shop scheduling problems, Journal of Scheduling, 2012, v. 15, p 427-446.

 Kononov A., Hong J-S., Kononova P., Lin F-C. Quantity-based buffer-constrained two machine flowshop problem: active and passive prefetch models for multimedia applications, Journal of Scheduling, 2012, v. 15, p. 487-497.

Kononov A.  About the two-machine routing open shop problem on a 2-node network, Discrete Analysis and Operations Research, 2012, v.19,  No. 2, p. 54-74 (in Russian), translated in Journal of Applied and Industrial Mathematics, 2012, Vol. 6, No. 3, pp. 318–331.

Baptiste Ph., Carlier J., Kononov A., Queyranne M., Sevastianov S., Sviridenko M., Properties of Optimal Schedules in Preemptive Shop Scheduling, Discrete Applied Mathematics, 2011, v. 159.  pp. 272-280

Gawiejnowicz S., Kononov A., Complexity and approximability of scheduling resumable proportionally deteriorating jobs, European Journal of Operational Research, 2010, v. 200/1, pp. 305-308.

Kononov A., Lin B.M.-T. Minimizing the total weighted completion time in the relocation problem, Journal of Scheduling, v.13, N 2, 2010, pp 123 -129.

Baptiste P., Carlier J., Kononov A.V., Queyranne M.,Sevastjanov S.V., Sviridenko M. I. Structural properties of optimal schedules with preemption // Discr. analisys and oper. research.  2009. Vol. 16, N 1.  P. 3–36.

A. V. Kononov, S. Sevastyanov. Graph Structure Analysis and Computational Tractability of Scheduling Problems // In: Analysis of Complex Networks: From Biology to Linguistics. Edited by M. Dehmer and F. Emmert-Streib, 2009, Wiley-VCH Verlag Gmbh & Co. KGaA, Weinheim ISBN 978-3-527-32345-6, c. 295-322.

A. V. Kononov, Yu. A. Kochetov, and A. V. Plyasunov Competitive Facility Location Models // Computational Mathematics and Mathematical Physics, 2009, Vol. 49, No. 6, pp. 994–1009. (pdf.file 259 Kb)

Kononov A., Lin B.M.-T. Customer Order Scheduling to Minimize the Number of Late Jobs, European Journal of Operational Research. 2007. v. 183/2 pp 944-948

Ageev A., Fishkin A., Kononov A., Sevastianov S., Open Block Scheduling in Optical Communication Networks, Theoretical Computer Science, 2006, v. 361, pp 257-274.

Kononov A., Lin B.M.-T. Relocation Problems with Multiple Working Crews, Discrete Optimization, 2006, v. 3, pp 366-381.

Агеев А.А. , Ильев И.П., Кононов А.В., Талевнин А.С. Вычислительная сложность задачи аппроксимации графов, Дискретный анализ и исследование операций. Серия 1. 2006.  том 13.  № 1. с. 3-15.

Bampis E., Kononov A., Bicriteria Approximation Algorithms for Scheduling Problems with Communication Delays, Journal of Scheduling, v.8, N 4, 2005, pp 281 -294

Baptiste Ph., Carlier J., Kononov A., Queyranne M., Sevastianov S., Sviridenko M., Structural Properties of Preemptive Schedules,, submitted in Journal of Scheduling

Bampis E., Giroudeau R., Kononov A., Scheduling tasks with small communication delays for clusters of processors,  Annals of Operations Research. 2004, V.129, Issue 1, pp. 47 - 63.

Angel.E, Bampis E., Kononov A., On the approximate tradeoff for bicriteria batching and parallel machine scheduling problems, Theoretical Computer Science, 2003, V. 306 (1-3), p. 319-338.

Kononov A., Sviridenko M., Linear time combinatorial approximation scheme for makespan minimization in open shop with release dates, Operations Research Letters, 2002, v.30, p.276-280.

Kashirskih K., Kononov A., Sevastianov S., Tchernyh I., Polynomially solvable case of two-stage open-shop problem with three machines, Discrete Analysis and Operations Research, series 1. 2001, v.8, N 1, p.24-40. (in russian)

Gawiejnowicz S., Kononov A., NP-hard Cases in Scheduling Deteriorating Jobs on Dedicated Machines, Journal of the Operational Research Society, 2001 V.52, p. 708-717.

Кононов А.В., Севастьянов С.В. О сложности нахождения связной предписанной раскраски вершин графа, Дискретный анализ и исследование операций. Серия 1. 2000.  том 7.  № 2. с. 21-46

Kononov A., Sevastianov S. and Tchernykh I. When the difference in machine loads leads to efficient scheduling in open shops, Annals of Operations Research, 92, 1999, p.211-239.

Gawiejnowicz S., Kononov A. NP-hard Cases in Scheduling Deteriorating Jobs on Dedicated Machines, Adam Mickiewicz Univerity Report No. 101/1999, 26 p.

Kononov A. On schedules of a single machine jobs with processing times nonlinear in time. Operations Research and Discrete Analysis, Kluwer Academic Pubishers, Dordrecht. 1997, p.109-123.

Кононов А.В. О расписаниях работ наодной машине с длительностями, нелинейно зависящими от времени. Дискретный анализ и исследование операций, 1995, том 2, № 1, с.21-35.

Кононов А.В. Комбинаторная сложность составления расписаний для работ с простым линейным ростом длительностей. Дискретный анализ и исследование операций, 1995, том 3, № 2, с.15-32.

Kononov A. Scheduling Problems with Linear Increasing Processing Times. In Operations Research Proceedings 1996, Springer-Verlag, Berlin, 1997, p. 90-94.

Увлечения 

• шахматы
• коллекционирование альбомов по искусству
• пейзажная фотография

    Версия  01.11.24