?
Теория расписаний. Исследование задач с отношениями предшествования и ресурсными ограничениями
M. :
-, 2007.
Lazarev A. A., Gafarov E.
Lazarev A. A., Gafarov E., М. : Физический факультет МГУ, 2011
В данном учебном пособии приводятся базовые сведения о специальном разделе дискретной математики - Теории расписаний. Описаны этапы становления теории, свойства и классификации задач теории расписаний, методы их решения. На примерах классических задач представлены приемы доказательства их трудоемкости и алгоритмы решения. Учебное пособие основано на курсе лекций, читаемых в МФТИ, МГУ и ВШЭ, и предназначено для ...
Added: December 10, 2012
Lazarev A. A., Musatova E. G., Kvaratskhelia A. et al., М. : Физический факультет МГУ, 2012
Данное учебное пособие посвящено задачам теории расписаний, возникающим на транспорте. Представлены основы теории расписаний, а также способы построения моделей и методы решения задач управления транспортными системами. Изложенный материал предназначен для студентов и преподавателей вузов математических специальностей, специалистов в области управления и практиков, занимающихся решением задач планирования грузовых перевозок. ...
Added: December 10, 2012
Lazarev A. A., Gafarov E., Саарбрюкен : LAP LAMBERT Academic Publishing, 2011
Фундаментальными задачами теории расписаний для одного прибора являются задачи с критериями минимизации суммарного запаздывания и задачи минимизации максимального временного смещения. В данной книге приводится достаточно полное исследование NP-трудной в обычном смысле задачи минимизации суммарного запаздывания (total tardiness) и ее взаимосвязь с задачей Разбиения. Выделен ряд новых полиномиально и псевдо-полиномиальных разрешимых случаев данной задачи. При исследовании ...
Added: December 17, 2012
Lazarev A. A., М. : Московский физико-технический институт, 2008
Рассматриваются классические NP-трудные задачи теории расписаний для одного и нескольких приборов с критерием минимизации максимального временного смещения и быстродействия. Предлагается качественно новая схема нахождения приближённого решения. Вводится понятие метрики (расстояния) между примерами задачи. Идея предлагаемого подхода состоит в построении по исходному примеру задачи другого примера, для которого удаётся найти оптимальное или приближённое решение с минимальным ...
Added: December 17, 2012
Lazarev A. A., Gafarov E., М. : Вычислительный центр им. А.А. Дородницына РАН, 2006
Фундаментальными задачами теории расписаний для одного прибора являются задачи с критериями минимизации суммарного запаздывания и минимизация максимального временного смещения. В данной работе приводится достаточно полное исследование NP-трудной в обычном смысле задачи минимизация суммарного запаздывания для одного прибора. ...
Added: December 17, 2012
Lazarev A. A., Садыков Р. Р., М. : Вычислительный центр им. А.А. Дородницына РАН, 2007
Рассматриваются классические NP-трудные задачи теории расписаний для одного прибора: минимизация максимального временного смещения (1 | rj | Lmax) и суммарного взвешенного числа запаздывающих требований (1 | rj | ΣwjUj). Исследуемые задачи являются схематичными теоретическими моделями практических задач. Алгоритмы для решения этих задач используются как вспомогательные для решения более сложных задач теории расписаний, приближенных к практике. ...
Added: December 17, 2012
Lazarev A. A., Musatova E. G., Gafarov E. et al., М. : Федеральное государственное бюджетное учреждение науки Институт проблем управления им. В. А. Трапезникова Российской академии наук, 2012
Издание посвящено построению моделей и методам решения задач, возникающих при планировании грузовых железнодорожных перевозок. В зависимости от ограничений на локомотивы, грузоподъёмность составов, предлагаются различные алгоритмы решения задач формирования составов и расписания движения грузовых поездов. Изложенный материал будет полезен как специалистам в области управления, так и практикам, занимающихся решением задач планирования железнодорожных грузоперевозок. ...
Added: December 10, 2012
A Graphical Realization of the Dynamic Programming Method for Solving NP-Hard Combinatorial Problems
Lazarev A. A., Werner F., Computers & Mathematics with Applications 2009 No. 58 P. 619-631
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: November 24, 2012
Lazarev A. A., Садыков Р. Р., Севастьянов С., Дискретный анализ и исследование операций 2006 Т. 13 № 1 С. 57-76
Рассматривается NP-трудная в сильном смысле задача теории расписаний о минимизации максимального временного смещения на одном приборе при неодновременном поступлении работ. Представлена схема приближенного решения, основанная на отыскании по заданному примеру другого (наиболее близкого в некоторой метрике) примера, принадлежащего к известному полиномиально разрешимому классу примеров. Для нескольких конкретных вариантов схемы (с использованием различных полиномиально разрешимых классов ...
Added: November 23, 2012
Lazarev A. A., Werner F., Автоматика и телемеханика 2010 № 10 С. .-5
Foreword to the thematical issue devoted to the seventieth anniversary of Academician V.S. Tanaev ...
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., Автоматика и телемеханика 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., 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., 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., 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
Cheng T., Lazarev A. A., Gafarov E., Computers & Operations Research 2012 Vol. 36 No. 2 P. 308-315
We propose a hybrid algorithm based on the Ant Colony Optimization (ACO) meta-heuristic, in conjunction with four well-known elimination rules, to tackle the NP-hard single-machine scheduling problem to minimize the total job tardiness. The hybrid algorithm has the same running time as that of ACO. We conducted extensive computational experiments to test the performance of ...
Added: November 23, 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., 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
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
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
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
Lazarev A. A., Известия РАН. Теория и системы управления 2006 № 6 С. 103-110
Рассматривается классическая NP-трудная в сильном смысле задача теории расписаний $1\mid r_j\mid L_{\max}$. Найдены новые свойства оптимальных расписаний. Выделен полиномиально-разрешимый случай задачи, когда моменты поступлений ($r_j$), продолжительности обслуживания ($p_j$) и директивные сроки завершения обслуживания($d_j$) требований удовлетворяют ограничениям: $d_1\le\dots\led_n\quad d_1-r_1-p_1\geq\dots\geq d_n-r_n-p_n$. Алгоритм трудоемкости $O(n^3\log n)$ находит Парето-оптимальное множество расписаний по критериям $L_{\max}$ и $C_{\max}$, содержащее не более ...
Added: November 23, 2012
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
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