?
Scheduling the Two-Way Traffic on a Single-Track Railway with a Siding
Automation and Remote Control. 2018. Vol. Vol. 79. No. 3. P. 506-523.
Zinder Y., Lazarev A. A., Musatova E. G., Tarasov I. A.
The paper is concerned with scheduling the two-way traffic between two stations connected by a single-track railway with a siding. It is shown that if, for each station, the order in which trains leave this station is known or can be found, then for various objective functions an optimal schedule can be constructed in polynomial time using the method of dynamic programming. Based on this result, the paper also presents a polynomial-time algorithm minimising the weighted number of late trains.
А.А.Лазарев, Зиндер Я., Мусатова Е. Г. et al., Автоматика и телемеханика 2018 № 3 С. 144-166
The paper is concerned with scheduling the two-way traffic between two stations connected by a single-track railway with a siding. It is shown that if, for each station, the order in which trains leave this station is known or can be found, then for various objective functions an optimal schedule can be constructed in polynomial ...
Added: May 30, 2018
Lazarev A. A., Автоматика и телемеханика 2007 № 4 С. 13-23
Consideration was given to a graphic realization of the method of dynamic programming. Its concept was demonstrated by the examples of the partition and knapsack problems. The proposed method was compared with the existing algorithms to solve these problems. ...
Added: November 23, 2012
Gafarov E., Lazarev A. A., Information Processing Letters 2012 Т. 112 № 3 С. 72-76
In this note, we consider a single machine scheduling problem with generalized total tardiness objective function.
A pseudo-polynomial time solution algorithm is proposed for a special case of this problem. Moreover, we present a new
graphical algorithm for another special case, which corresponds to the classical problem of minimizing the weighted number
of tardy jobs on a single ...
Added: November 24, 2012
Werner F., Lazarev A. A., Automation and Remote Control 2010 Vol. 71 No. 10 P. 2019-2020
Foreword to the thematical issue devoted to the seventieth anniversary of Academician V.S. Tanaev ...
Added: November 23, 2012
Lazarev A. A., Musatova E. G., Kvaratskhelia A. et al., М. : Физический факультет МГУ, 2012
Данное учебное пособие посвящено задачам теории расписаний, возникающим на транспорте. Представлены основы теории расписаний, а также способы построения моделей и методы решения задач управления транспортными системами. Изложенный материал предназначен для студентов и преподавателей вузов математических специальностей, специалистов в области управления и практиков, занимающихся решением задач планирования грузовых перевозок. ...
Added: December 10, 2012
Protasov V., Voinov A. S., Linear Algebra and its Applications 2017 No. 513 P. 376-408
Multiplicative matrix semigroups with constant spectral radius (c.s.r.) are studied and applied to several problems of algebra, combinatorics, functional equations, and dynamical systems. We show that all such semigroups are characterized by means of irreducible ones. Each irreducible c.s.r. semigroup defines walks on Euclidean sphere, all its nonsingular elements are similar (in the same basis) ...
Added: March 11, 2017
Gafarov E., Lazarev A. A., Werner F., Annals of Operations Research 2012 Vol. 196 No. 1 P. 247-261
We consider the problem of maximizing total tardiness on a single machine, where the first job starts at time zero and idle times between the processing of jobs are not allowed.We present a modification of an exact pseudo-polynomial algorithm based on a graphical approach, which has a polynomial running time. This result settles the complexity ...
Added: November 24, 2012
Andreev N. A., Mathematics 2019 Vol. 7 No. 12 P. 1147
We present a robust dynamic programming approach to the general portfolio selection problem in the presence of transaction costs and trading limits. We formulate the problem as a dynamic infinite game against nature and obtain the corresponding Bellman-Isaacs equation. Under~several additional assumptions, we get an alternative form of the equation, which is more feasible for ...
Added: October 30, 2019
Gafarov E., Lazarev A. A., Werner F., / Otto-von-Guericke Universitaet. 2010. No. 12.
In this paper, we consider the problem of maximizing total tardiness on a single machine, where the first job starts at time zero and idle times between the processing of jobs are not allowed. We present a modification of an exact pseudo-polynomial algorithm based on a graphical approach, which has a polynomial running time. ...
Added: March 4, 2013
Lazarev A. A., Kvaratskhelia A., Gafarov E., Доклады Академии наук 2007 Т. 412 № 6 С. 739-742
27.47.19 Исследование операций
28.15.19 Нелинейные детерминированные системы
28.19.15 Оптимальные системы
28.29.15 Методы исследования операций ...
Added: November 23, 2012
Lazarev A. A., Gafarov E., Автоматика и телемеханика 2008 № 12 С. 86-104
Consideration was given to the resource-constrained project scheduling problem and its special cases. The existing lower estimates of the objective function—minimization of the project time—were compared. It was hypothesized that the optimal value of the objective function of the nonpreemptive resource-constrained project scheduling problem is at most twice as great as that of the objective ...
Added: November 23, 2012
Lazarev A. A., Werner F., / Otto-von-Guericke Universitaet. 2008. No. 12.
The scheduling problem of minimizing total tardiness on a single machine is knownto be NP-hard in the ordinary sense. In this paper, we consider the special case of the problem when the processing times $p_j$ and the due dates $d_j$ of the jobs $j, \, j \in N = \{ 1, 2, \ldots, n \}$, ...
Added: March 4, 2013
Lazarev A. A., Werner F., Mathematical and Computer Modelling 2009 Vol. 49 No. 9-10 P. 2061-2072
The scheduling problem of minimizing total tardiness on a single machine is known to be NP-hard in the ordinary sense. In this paper, we consider the special case of the problem when the processing times p_j and the due dates d_j of the jobs are oppositely ordered: p_1 >= p_2>=...>=p_n and d_1. ...
Added: November 24, 2012
Gafarov E., Lazarev A. A., Werner F., / Otto-von-Guericke Universitaet. 2009. No. 38.
We consider single machine problems with opposite criteria, namely we consider the maximization of total tardiness, the maximization of the number of tardy jobs and the maximization of total completion time (in contrast to usual minimization problems)and a minimization version of the Knapsack problem. ...
Added: March 4, 2013
Lazarev A. A., Gafarov E., Werner F., Information Processing Letters 2012 Vol. 112 No. 3 P. 72-76
In this note, we consider a single machine scheduling problem with generalized total tardiness objective function. A pseudo-polynomial time solution algorithm is proposed for a special case of this problem. Moreover, we present a new graphical algorithm for another special case, which corresponds to the classical problem of minimizing the weighted number of tardy jobs ...
Added: October 15, 2014
Gafarov E., Lazarev A. A., Werner F., Mathematical Social Sciences 2011 No. 62 P. 7-13
We consider single machine scheduling problems with a non-renewable resource. These types of problems have not been intensively investigated in the literature so far. For several problems of these types with standard objective functions (namely the minimization of makespan, total tardiness, number of tardy jobs, total completion time and maximum lateness), we present some complexity ...
Added: November 24, 2012
Lazarev A. A., Журнал вычислительной математики и математической физики 2007 Т. 47 № 6 С. 1087-1099
The classical NP-hard (in the ordinary sense) problem of scheduling jobs in order to minimize the total tardiness for a single machine 1‖ΣT j is considered. An NP-hard instance of the problem is completely analyzed. A procedure for partitioning the initial set of jobs into subsets is proposed. Algorithms are constructed for finding ...
Added: November 23, 2012
Gafarov E., Lazarev A. A., Werner F., / Otto-von-Guericke Universitaet. 2010. No. 10.
In this note, we consider a single machine scheduling problem with generalized total tardiness objective function. An NP-hardness proof and a pseudo-polynomial time solution algorithm are proposed for a special case of this problem. Moreover, we present a new graphical algorithm for another special case, which corresponds to the classical problem of minimizing the weighted ...
Added: March 4, 2013
Lazarev A. A., Gafarov E., Доклады Академии наук 2008 Т. 424 № 1 С. 7-9
27.47.19 Исследование операций
28.15.19 Нелинейные детерминированные системы
28.19.15 Оптимальные системы
28.29.15 Методы исследования операций ...
Added: November 23, 2012
Lazarev A. A., Kvaratskhelia A., Автоматика и телемеханика 2010 № 10 С. 80-89
In this paper, we consider the minimizing total weighted completion time in preemptive equal-length job with release dates scheduling problem on a single machine. This problem is known to be open. Here, we give some properties of optimal schedules for the problem and its special cases. ...
Added: November 24, 2012
Malyshev D., Дискретный анализ и исследование операций 2012 Т. 19 № 3 С. 58-64
An algorithm is implemented in the article for finding the independence number of a n-vertex graph from the class Free({P5,C5, Kp}) in time O(np+O(1)). ...
Added: June 6, 2012
Lazarev A. A., Kvaratskhelia A., Доклады Академии наук 2010 Т. 432 № 6 С. 746-749
Одним из актуальных вопросов разработки математической теории расписаний является построение метрик, которые можно использовать при разработке точных и приближенных алгоритмов решения задач. Введение метрических пространств для $NP$-трудных задач теории расписаний позволяет применять общие математические подходы к нахождению приближенного решения с гарантированной абсолютной погрешностью. Ранее для $NP$-трудных задач с критерием минимизации максимального временн\'ого смещения $\{P,R,Q\}|prec,r_j|\{L_{\max},C_{\max}\}$ была ...
Added: November 23, 2012
Gafarov E., Lazarev A. A., Werner F., Автоматика и телемеханика 2010 № 10 С. 63-79
In this paper, we consider two scheduling problems on a single machine, where a specific objective function has to be maximized in contrast to usual minimization problems. We propose exact algorithms for the single machine problem of maximizing total tardiness 1‖max-ΣT j and for the problem of maximizing the number of tardy jobs ...
Added: November 24, 2012
Lazarev A. A., Werner F., / Otto-von-Guericke Universitaet. 2008. No. 15.
In this paper we consider a graphical realization of dynamic programming. The concept is discussed on the partition and knapsack problems. In contrast to dynamic programming, the new algorithm can also treat problems with non-integer data without necessary transformations of the corresponding problem. We compare the proposed method with existing algorithms for these problems on ...
Added: March 4, 2013