- В работе сформулировано понятие воспроизводимого ресурса и установлена его связь с общепринятыми понятиями возобновимого и невозобновимого ресурсов. Для задач с воспроизводимым ресурсом предложены первые приближенные алгоритмы с гарантированной оценкой точности.
- Разработан общий метод построения приближенных алгоритмов для задач составления энергетически эффективных расписаний. Впервые рассмотрены неоднородные задачи построения энергетически эффективных расписаний. Для них построены алгоритмы решения, близкие по качеству к известным алгоритмам для аналогичных однородных задач.
- Построены первые нетривиальные приближенные алгоритмы для задачи с задержками передачи данных в иерархической системе.
- Предложены новые приближенные алгоритмы для различных задач теории расписаний и проведен анализ погрешности этих алгоритмов. На момент написания диссертации все представленные в ней алгоритмы имели наилучшую оценку точности среди алгоритмов, трудоемкость которых ограничена полиномом от размера входных данных задачи.
2.Каширских К.Н., Кононов А.В., Севастьянов СВ., Черных И.Д. Полиномиально разрешимый случай двухстадийной задачи open shop с тремя машинами // Дискретный анализ и исследование операций. Серия 1. - 2001. - Т 8, N 1. - С. 24-40.
3.Кононов А.В. О расписаниях работ на одной машине с длительностями, нелинейно зависящими от времени. // Дискретный анализ и исследование операций. — 1995. — Т 2, N 1. — С. 21-35.
4.Кононов А.В. Комбинаторная сложность составления расписаний для работ с простым линейным ростом длительностей // Дискретный анализ и исследование операций. - 1996. - Т 3, N 2. - С. 15-32.
5.Кононов А.В. Задачи теории расписаний на одной машине с длительностями работ, пропорциональными произвольной функции // Дискретный анализ и исследование операций. — 1998. — Т 5, N 3. - С. 17-37.
6.Кононов А.В. О цеховой задаче открытого типа на двух машинах с маршрутизацией в двух-вершинной сети // Дискретный анализ и исследование операций. - 2012. - Т 19, N 2. - С. 54-74.
7.Ageev A., Fishkin A., Kononov A., Sevastianov S. Open block scheduling in optical communication networks. // Theoretical Computer Science. - 2006. - V. 361. - P. 257-274.
8.Angel E., Bampis E., Kononov A. On the approximate tradeoff for bicriteria batching and parallel machine scheduling problems. // Theoretical Computer Science. - 2003. - V. 306, N 1-3 - P. 319-338.
9. Bampis E., Giroudeau R., Kononov A. Scheduling tasks with small communication delays for clusters of processors. // Annals of Operations Research. - 2004. - V.129, N 1. - P. 47-63.
10.Bampis E., Kononov A. Bicriteria approximation algorithms for scheduling problems with communication delays. // Journal of Scheduling. - 2005 - V.8, N 4. - P. 281-294.
11.E. Bampis, A. Kononov, D. Letsios, G. Lucarelli, I. Nemparis, From preemptive to non-preemptive speed-scaling scheduling. // COCOON 2013, Lecture Notes in Computer Science - 2013 - V. 7936 - p. 134-146.
12.Bampis E., Kononov A., Letsios D., Lucarelli G., Sviridenko M. Energy efficient scheduling and routing via randomized rounding // FSTTCS 2013, LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik - 2013.
13.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. - P. 272-280.
14.Baptiste Ph., Carlier J., Kononov A., Queyranne M., Sevastianov S., Sviridenko M. Integer preemptive scheduling on parallel machines. // Operations Research Letters. - 2012 - V. 40, N 6. - P. 440-444.
15.Chernykh I., Kononov A., Sevastyanov S. Efficient approximation algorithms for the routing open shop problem. // Computers & Operations Research. - 2013 - V. 40, N 3. - P. 841-847.
16.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.
17.Gawiejnowicz S., Kononov A. Complexity and approximability of scheduling resumable proportionally deteriorating jobs. // European Journal of Operational Research. - 2010. - V. 200, N 1. - P. 305-308.
18.Gawiejnowicz S., Kononov A. Isomorphic scheduling problems. // Annals of operations research. - 2014 - V. 213. - P. 131-145.
19.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.
20.Kononov A., Lin B.M.-T. Relocation problems with multiple working crews. // Discrete Optimization. - 2006. - V. 3. - P. 366-381.
21.Kononov A., Lin B.M.-T. Minimizing the total weighted completion time in the relocation problem. // Journal of Scheduling. - 2010 -V.13, N 2. - P. 123-129.
22.Kononov A., Sevastyanov S. Graph structure analysis and computational tractability of scheduling problems // In: M. Dehmer and F. Emmert-Streib (Eds.) Analysis of Complex Networks: From Biology to Linguistics, 2009, Wiley-VCH Verlag Gmbh & Co. KGaA, Weinheim ISBN 978-3-527-32345-6, P. 295-322.
23.Kononov A., Sevastianov S., Sviridenko M. A complete 4-para-metric complexity classification of short shop scheduling problems. // Journal of Scheduling. - 2012. - V. 15. - P. 427-446.
24.Kononov A., Sevastianov S., Tchernykh I. When the difference in machine loads leads to efficient scheduling in open shops. // Annals of Operations Research. - 1999 - V. 92. - P. 211-239.
25.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.
26.Lin B.M.-T., Kononov A. Customer order scheduling to minimize the number of late jobs. // European Journal of Operational Research. - 2007. - V. 183, N 2. - P. 944-948.