Sobolev Institute of Mathematics
Laboratory "Mathematical Models of Decision Making"

line.jpg (1129 bytes)

Dr. Alexander Kononov
Senior Researcher, Professor

E-mail: alvenko@math.nsc.ru
Phone: +7 (383) 329 75 80
Fax:     +7 (383) 333 25 98

Russian page

| Sobolev Institute of Mathematics | Laboratory "Mathematical Models of Decision Making" |

line.jpg (1129 bytes)


Curriculum Vitae

Name: Alexander KONONOV
Date of birth: 28.08.1965
Place of birth: Leninsk-Kuzneckii, Russia
Marital status: married
Nationality: Russian

Education:

PhD in Mathematics and Physics, Sobolev Institute of Mathematics, 1999.
PhD Thesis: Complexity of scheduling problem with time dependent processing times
Advisor: Prof. Vladimir L.Beresnev.

M.D. in Applied Mathematics, Novosibirsk State University, 1989.

Positions:

Other activities:

line.jpg (1129 bytes)

Scientific interests

Scheduling theory

line.jpg (1129 bytes)

 

Industrial experience

  1. Development of Decision Support System for construction time-table of local trains: development of mathematical models, algorithms, design the Delphi software (1997-1998).

  2. Participation in development of mathematical models, algorithms and software for long range strategic planing R&D programs and creation DOS application to solve multi-mode project scheduling problem with resource-constraints (1992-1993).

  3. Participation in development of mathematical models, algorithms and software for middle-time planing on steel processing manufactory and creation DOS application to solve the large scale job-shop scheduling problems with parallel machines, release and due dates, delays and other parameters (1990-1991).

line.jpg (1129 bytes)

Publications

 

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

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

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. 1120.

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. 318331.

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. 336.

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. 9941009. (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.

Ageev A., Iliev V., Kononov A., Talevnin A. Complexity of Approximation Graph Problem, Discrete Analysis and Operations Research, series 1. 2006, v.13, N 1, p. 3-15. (in russian)

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.

Kononov A., Sevastianov S., Complexity of finding of connected, prescribed colouring, Discrete Analysis and Operations Research, 2000, v.7, 2, p.21-46. (in russian)

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

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.

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

Kononov A., Complexity of scheduling problems with simple linear detoriorations. Discrete Analysis and Operations Research, 1996, v.3, 2, p.15-32. (in russian)

Extended Abstracts

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.

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 // COCOON 2013, Lecture Notes in Computer Science, 2013, V. 7936, p. 134-146.

E. Angel, E. Bampis, A. Kononov, D. Paparas, E. Pountourakis, V. Zissimopoulos, Clustering on k-Edge-Colored Graphs // MFCS 2013, Lecture Notes in Computer Science, 2013, V. 8087, pp 50-61

E. Bampis, D. Letsios, G. Lucarelli, M. Sviridenko, Energy Efficient Scheduling and Routing via Randomized Rounding // FSTTCS 2013, Leibniz International Proceedings in Informatics, Schloss Dagstuhl Leibniz-Zentrum fur Informatik, Dagstuhl  Publishing, Germany, 2013. V. 24, pp 449-460.

Bampis E.,  Kononov A., Lucarelli G.,  Milis I. Bounded Max-colorings of Graphs // ISAAC 2010, Lecture Notes in Computer Science, 2010, V. 6506, p. 353-365

Chernykh I,  Dryuck N,   Kononov A., Sevastyanov S. The Routing Open Shop Problem: New Approximation Algorithms //  WAOA 2009, Lecture Notes in Computer Science, 2010, V. 5893, p. 75-85.

  Kononov A.V., Sevastjanov S.V., Sviridenko M. I. Complete Complexity Classification  of Short Shop Scheduling  // CSR 2009, Lecture Notes in Computer Science, 2009, V. 5675, p. 227-236.

  Baptiste P., Carlier J., Kononov A.V., Queyranne M., Sevastjanov S.V., Sviridenko M. I. Integrality Property in Preemptive Parallel Machine Scheduling  // CSR 2009, Lecture Notes in Computer Science, 2009, V. 5675, p. 38-46.

Bhattacharia B., Hu Y., Kononov A., Approximation Algorithms for the Black and White Traveling Salesman Problem // COCOON 2007, Lecture Notes in Computer Science, 2007, V. 4598, p. 559-567.

Ageev A., Kononov A., Approximation Algorithms for Scheduling Problems with Exact Delays // WAOA 2006, Lecture Notes in Computer Science, 2006, v 4368, p.1 - 14.

Ageev A., Fishkin A., Kononov A., Sevastianov S., Open Block Scheduling in Optical Communication Networks // WAOA 2003, Lecture Notes in Computer Science, 2004, V. 2909, p. 13-26.

Bampis E., Kononov A., Bicriteria Approximation Algorithms for Scheduling Problems with Communication Delays, Proceedings of The Fifteenth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA '03)).

Angel.E., Bampis E., Kononov A., A FPTAS for approximating the Pareto curve
of the unrelated parallel machines scheduling problem with costs, Algorithms - ESA 2001, Lecture Notes in Computer Science. 2001, V. 2161, p. 194-205.

Bampis E., Giroudeau R., Kononov A., Scheduling tasks with small communication delays for clusters of processors, Proceedings of The Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA '01)).

Bampis E., Kononov A., On the approximability of scheduling multiprocessor tasks with Time-dependent and Time Requirements, Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS 2001), IEEE Computer Society Press, 8 p

 

Hobby

line.jpg (1129 bytes)

 E-mail: alvenko@math.nsc.ru

Update 17.02.16