LABORATORY No. 68

SCHEDULING THEORY AND DISCRETE OPTIMIZATION

Alexander A. Lazarev, Head of Laboratory No. 68

The Laboratory was established in 2009 based on a research group of Kazan State University headed by Prof., Dr. Sci. (Phys.–Math.) Alexander A. Lazarev. Nowadays, this is the only laboratory on scheduling theory in Russia. The current staff consists of 16 employees, including 2 Doctors of Physics and Mathematics, 2 Candidate of Physics and Mathematics, 1 Doctor of Engineering, and 1 Candidate of Engineering. Laboratory’s employees teach at the Higher School of Economics, Lomonosov Moscow State University, and the Moscow Institute of Physics and Technology.

The Laboratory deals with complex applications of scheduling theory, combinatorial optimization, production planning and scheduling, and models arising in the practical planning and management of interrelated operations under resource constraints.

When studying NP-hard combinatorial optimization problems, it is essential to consider the complexity structure of examples, obtain new properties of optimal solutions, and construct polynomial and pseudopolynomial algorithms for solving special cases of the problems. The properties and algorithms of polynomially solvable special cases can be used to construct effective algorithms yielding exact and approximate solutions of the general problem. A similar approach—identifying special cases of problems, finding their equivalent well-studied statements, and constructing algorithms for them—is effective for high-dimensional problems arising in applications.

Laboratory’s employees developed an original parameter variation method. This method gives an approximate solution of production planning and scheduling problems with the minimum absolute error of the objective function from the set of feasible (polynomially solvable) solutions.

A new method for solving combinatorial and discrete optimization problems, actively developed in the Laboratory, modifies classical dynamic programming based on Bellman’s optimality principle. This method, called graphical, was successfully applied to solve some scheduling and discrete optimization problems. It significantly reduces the complexity of solving some combinatorial optimization problems. Moreover, as demonstrated, a polynomial algorithm can be constructed for some problems with a previously unknown computational complexity.

The research group endeavors to use the results and construct effective methods for finding accurate and approximate solutions with a guaranteed error in different applications: vehicle motion control in transport and logistics systems, including formation, routing, and dispatching of traffic flows; planning and management of interrelated operations.

Main research areas:

  • NP-hard problems of scheduling theory, production planning and scheduling, and related fields of combinatorial and discrete optimization.
  • Graphical algorithms for obtaining approximate solutions of NP-hard scheduling problems.
  • New methods for solving computationally-intensive problems based on the graphical approach.
  • Development and implementation of information systems with a mathematical component.
  • Effective metrics for the problems under consideration and polynomial algorithms with the guaranteed absolute error based on such metrics.
  • Railway traffic control.
  • Traffic control in transport networks.
  • Optimization methods for academic schedules of universities.
  • Investment portfolio management.

The Laboratory has rich experience of developing interfaces and software complexes for accounting and analytical tasks. Some employees participated in developing IT products for well-known companies (1C, Glavstroy, Siemens, Wabco, and others).

To date, Laboratory’s employees have published more than 400 works, including 29 books (monographs and textbooks for leading Russian universities). Over 70 papers have been published in peer-review journals indexed by Web of Science or Scopus. Laboratory’s employees are editors of the Operations Research section of Mathematics (an abstract journal of All-Russian Institute of Scientific and Technical Information (VINITI)); members of the editorial boards of peer-review journals Automation and Remote Control, Control Sciences, and Large-Scale Systems Control, and dissertation councils.

The Laboratory collaborates with several major research centers: Otto von Guericke University (Magdeburg, Germany); the French National Centre for Scientific Research (CNRS), Institute for Information Sciences and Technologies (INS2I), Paris, France; National Institute for Research in Digital Science and Technology (INRIA), Bordeaux, France; Ecole des Mines de Nantes, Nantes, France; Sydney University of Technology, Sydney, Australia; National Yang-Ming Chiao Tung University, Hsinchu, Taiwan; the Hong Kong Polytechnic University, Hung Hom, Hong Kong. Laboratory’s theoretical and applied results correspond to the world level: they were presented at leading international conferences and published in high-rank international journals.