?
Теория расписаний. Исследование задач с отношениями предшествования и ресурсными ограничениями
М. :
Вычислительный центр им. А.А. Дородницына РАН, 2007.
Лазарев А. А., Гафаров Е. Р.
Рассматривается задача построения расписания проекта с учетом ограничений на ресурсы и ее частные случаи. Приводятся результаты исследования известных нижних оценок. Выдвинута гипотеза о свойствах оптимального значения целевой функции в задаче с прерываниями и без прерываний обслуживания требований и представлено доказательство гипотезы для частных случаев задачи. Показано, что любой проект можно преобразовать в проект с "планарным" сетевым графиком. Представлены некоторые новые общие свойства задач теории расписаний с ограничениями предшествования.
Приоритетные направления:
математика
Язык:
русский
Лазарев А. А., Гафаров Е. Р., М. : Физический факультет МГУ, 2011
В данном учебном пособии приводятся базовые сведения о специальном разделе дискретной математики - Теории расписаний. Описаны этапы становления теории, свойства и классификации задач теории расписаний, методы их решения. На примерах классических задач представлены приемы доказательства их трудоемкости и алгоритмы решения. Учебное пособие основано на курсе лекций, читаемых в МФТИ, МГУ и ВШЭ, и предназначено для ...
Добавлено: 10 декабря 2012 г.
Лазарев А. А., Мусатова Е. Г., Кварацхелия А. Г. и др., М. : Физический факультет МГУ, 2012
Данное учебное пособие посвящено задачам теории расписаний, возникающим на транспорте. Представлены основы теории расписаний, а также способы построения моделей и методы решения задач управления транспортными системами. Изложенный материал предназначен для студентов и преподавателей вузов математических специальностей, специалистов в области управления и практиков, занимающихся решением задач планирования грузовых перевозок. ...
Добавлено: 10 декабря 2012 г.
Лазарев А. А., Гафаров Е. Р., Саарбрюкен : LAP LAMBERT Academic Publishing, 2011
Фундаментальными задачами теории расписаний для одного прибора являются задачи с критериями минимизации суммарного запаздывания и задачи минимизации максимального временного смещения. В данной книге приводится достаточно полное исследование NP-трудной в обычном смысле задачи минимизации суммарного запаздывания (total tardiness) и ее взаимосвязь с задачей Разбиения. Выделен ряд новых полиномиально и псевдо-полиномиальных разрешимых случаев данной задачи. При исследовании ...
Добавлено: 17 декабря 2012 г.
Лазарев А. А., М. : Московский физико-технический институт, 2008
Рассматриваются классические NP-трудные задачи теории расписаний для одного и нескольких приборов с критерием минимизации максимального временного смещения и быстродействия. Предлагается качественно новая схема нахождения приближённого решения. Вводится понятие метрики (расстояния) между примерами задачи. Идея предлагаемого подхода состоит в построении по исходному примеру задачи другого примера, для которого удаётся найти оптимальное или приближённое решение с минимальным ...
Добавлено: 17 декабря 2012 г.
Лазарев А. А., Гафаров Е. Р., М. : Вычислительный центр им. А.А. Дородницына РАН, 2006
Фундаментальными задачами теории расписаний для одного прибора являются задачи с критериями минимизации суммарного запаздывания и минимизация максимального временного смещения. В данной работе приводится достаточно полное исследование NP-трудной в обычном смысле задачи минимизация суммарного запаздывания для одного прибора. ...
Добавлено: 17 декабря 2012 г.
Лазарев А. А., Садыков Р. Р., М. : Вычислительный центр им. А.А. Дородницына РАН, 2007
Рассматриваются классические NP-трудные задачи теории расписаний для одного прибора: минимизация максимального временного смещения (1 | rj | Lmax) и суммарного взвешенного числа запаздывающих требований (1 | rj | ΣwjUj). Исследуемые задачи являются схематичными теоретическими моделями практических задач. Алгоритмы для решения этих задач используются как вспомогательные для решения более сложных задач теории расписаний, приближенных к практике. ...
Добавлено: 17 декабря 2012 г.
Лазарев А. А., Мусатова Е. Г., Гафаров Е. Р. и др., М. : Федеральное государственное бюджетное учреждение науки Институт проблем управления им. В. А. Трапезникова Российской академии наук, 2012
Издание посвящено построению моделей и методам решения задач, возникающих при планировании грузовых железнодорожных перевозок. В зависимости от ограничений на локомотивы, грузоподъёмность составов, предлагаются различные алгоритмы решения задач формирования составов и расписания движения грузовых поездов. Изложенный материал будет полезен как специалистам в области управления, так и практикам, занимающихся решением задач планирования железнодорожных грузоперевозок. ...
Добавлено: 10 декабря 2012 г.
A Graphical Realization of the Dynamic Programming Method for Solving NP-Hard Combinatorial Problems
Лазарев А. А., Вернер Ф., 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 ...
Добавлено: 24 ноября 2012 г.
Лазарев А. А., Садыков Р. Р., Севастьянов С., Дискретный анализ и исследование операций 2006 Т. 13 № 1 С. 57-76
Рассматривается NP-трудная в сильном смысле задача теории расписаний о минимизации максимального временного смещения на одном приборе при неодновременном поступлении работ. Представлена схема приближенного решения, основанная на отыскании по заданному примеру другого (наиболее близкого в некоторой метрике) примера, принадлежащего к известному полиномиально разрешимому классу примеров. Для нескольких конкретных вариантов схемы (с использованием различных полиномиально разрешимых классов ...
Добавлено: 23 ноября 2012 г.
Лазарев А. А., Вернер Ф., Автоматика и телемеханика 2010 № 10 С. .-5
Тематический выпуск журнала Автоматика и телемеханика, посвященный 70-летию со дня рождения академика Вячеслава Сергеевича Танаева. ...
Добавлено: 23 ноября 2012 г.
Гафаров Е. Р., Лазарев А. А., Вернер Ф., Автоматика и телемеханика 2010 № 10 С. 63-79
Рассматриваются две одноприборные задачи теории расписаний максимизации суммарного запаздывания и максимизации количества запаздывающих требований, когда простои в обслуживании требований запрещены и требования начинают обслуживаться с момента времени 0. Показано, что задача максимизации количества запаздывающих требований полиномиально разрешима. Для некоторых частных случаев задачи максимизации суммарного запаздывания представлены точные полиномиальные алгоритмы решения, а также два точных алгоритма ...
Добавлено: 24 ноября 2012 г.
Лазарев А. А., Автоматика и телемеханика 2007 № 4 С. 13-23
Рассматривается графическая реализация метода динамического программирования. Идея метода показана на примерах решения задач разбиение и рюкзака. Проведен сравнительный анализ предлагаемого метода с известными алгоритмами решения этих задач. ...
Добавлено: 23 ноября 2012 г.
Гафаров Е. Р., Лазарев А. А., Вернер Ф., Mathematical Social Sciences 2011 No. 62 P. 7-13
Добавлено: 24 ноября 2012 г.
Лазарев А. А., Гафаров Е. Р., Автоматика и телемеханика 2008 № 12 С. 86-104
Рассматривается задача построения расписания проекта с учётом ограничений на ресурсы (RCPSP) и её частные случаи. Проведён сравнительный анализ известных нижних оценок целевой функции - минимизации общего времени выполнения проекта. Выдвинута гипотеза, что для задачи RCPSP без прерываний в обслуживании требований оптимальное значение целевой функции не более чем в два раза больше оптимального значения целевой функции ...
Добавлено: 23 ноября 2012 г.
Лазарев А. А., Вернер Ф., Mathematical and Computer Modelling 2009 Vol. 49 No. 9-10 P. 2061-2072
Добавлено: 24 ноября 2012 г.
Cheng T., Лазарев А. А., Гафаров Е. Р., Computers & Operations Research 2012 Vol. 36 No. 2 P. 308-315
Добавлено: 23 ноября 2012 г.
Лазарев А. А., Журнал вычислительной математики и математической физики 2007 Т. 47 № 6 С. 1087-1099
Рассматривается классическая $NP$-трудная в обычном смысле задача теории расписаний для одного прибора минимизации суммарного запаздывания $1~\mid~\mid~\sum T_j$. Проведен полный анализ $NP$-трудного случая задачи. Предлагается процедура разбиения исходного множества требований на подмножества. Построены алгоритмы нахождения оптимального расписания в зависимости от количества подмножеств. Трудоемкость алгоритмов не превышает $O(n^2\sum p_j)$ операций, где $n$ -- количество требований, а $p_j$ ...
Добавлено: 23 ноября 2012 г.
Гафаров Е. Р., Лазарев А. А., 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 ...
Добавлено: 24 ноября 2012 г.
Лазарев А. А., Кварацхелия А. Г., Автоматика и телемеханика 2010 № 10 С. 80-89
Рассматривается задача теории расписаний минимизации суммарного взвешенного момента окончания для одного прибора с возможностью прерывания обслуживания требований. Продолжительности обслуживания всех требований одинаковы. На текущий момент данная задача является открытой, т.е. не известен полиномиальный алгоритм ее решения и не доказано, что она является NP-трудной. Приводятся свойства оптимальных расписаний данной задачи. ...
Добавлено: 24 ноября 2012 г.
Лазарев А. А., Кварацхелия А. Г., Гафаров Е. Р., Доклады Академии наук 2007 Т. 412 № 6 С. 739-742
В работе рассматривается классическая NP-трудная в обычном смысле проблема теории расписаний минимизации суммарного запаздывания для одного прибора $1\mid\,\mid\sum T_j$. Для NP-трудного случая задачи предложена процедура его разбиения на частные подслучаи, для которых приводятся полиномиальные и псевдополиномиальные алгоритмы решения, трудоемкости не превышающей $O(n^2\sum p_j)$. ...
Добавлено: 23 ноября 2012 г.
Гафаров Е. Р., Лазарев А. А., Вернер Ф., Annals of Operations Research 2012 Vol. 196 No. 1 P. 247-261
Добавлено: 24 ноября 2012 г.
Лазарев А. А., Известия РАН. Теория и системы управления 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}$, содержащее не более ...
Добавлено: 23 ноября 2012 г.
Лазарев А. А., Гафаров Е. Р., Доклады Академии наук 2008 Т. 424 № 1 С. 7-9
Для задач на графах построен алгоритм трудоёмкости О(n^5), где n - количество вершин в графе, преобразующий непланарный неориентированный граф в планарный. В результате получается планарный граф, у которого сумма вершин и рёбер не больше, чем у исходного непланарного графа. Причём, если между вершинами i и j был путь, то он сохраниться, если не было такого ...
Добавлено: 23 ноября 2012 г.
Вернер Ф., Лазарев А. А., Automation and Remote Control 2010 Vol. 71 No. 10 P. 2019-2020
Тематический выпуск журнала Автоматика и телемеханика, посвященный 70-летию со дня рождения академика Вячеслава Сергеевича Танаева. ...
Добавлено: 23 ноября 2012 г.