?
III International Conference on Optimization Methods and Application (OPTIMA-2012), Costa da Caparica, Portugal, september 2012
М. :
Вычислительный центр им. А.А. Дородницына РАН, 2012.
Proceedings include extended abstracts of reports presented at the III International Conference on Optimization Methods and Applications “Optimization and application” (OPTIMA-2012) held in Costa da Caparica, Portugal, September 23—30, 2012.
Архипов Д. И., Лазарев А. А., Мусатова Е. Г., , in : III International Conference on Optimization Methods and Application (OPTIMA-2012), Costa da Caparica, Portugal, september 2012. : M. : -, 2012. P. 42-47.
The paper is devoted to a schedulling theory problem. There are some railway stations and a set of orders (cars). Our goal is to transport all cars to destination stations with the minimal maximum lateness. New polynomial-time algorithm is proposed for solving this problem. Firstly, an auxiliary problem is solved. Then a special algorithm improves ...
Добавлено: 20 декабря 2012 г.
Мусатова Е. Г., Лазарев А. А., Хуснуллин Н. Ф., , in : III International Conference on Optimization Methods and Application (OPTIMA-2012), Costa da Caparica, Portugal, september 2012. : M. : -, 2012. P. 187-191.
The paper is devoted to the problem of railway transportation. The railway network consists of stations between which freight cars are transported.
Our goal is to design freight trains and work out their schedule. In this paper we propose an algorithm for the special case of three stations.
New dynamic programming algorithm is proposed for solving this ...
Добавлено: 27 декабря 2012 г.
Петров Л. Ф., , in : III International Conference on Optimization Methods and Application (OPTIMA-2012), Costa da Caparica, Portugal, september 2012. : M. : -, 2012. P. 213-218.
Рассматриваются существенно нелинейные динамические системы с возможностью реализации хаотического поведения и детерминированных решений различных видов. Среди детерминированных решений выделяются разнообразные периодические решения различных периодов. Эта работа посвящена численным алгоритмам построения и анализа устойчивости периодических решений сильно нелинейных динамических систем. ...
Добавлено: 17 февраля 2013 г.
Armen Beklaryan, , in : III International Conference on Optimization Methods and Application (OPTIMA-2012), Costa da Caparica, Portugal, september 2012. : M. : -, 2012. P. 47-50.
В работе рассматривается первая краевая задача для эллиптических систем, заданных в неограниченных областях, решения которых удовлетворяют условию конечности интеграла Дирихле, называемого также интегралом энергии. ...
Добавлено: 5 июня 2013 г.
Приоритетные направления:
математика
Язык:
английский
Лазарев А. А., Гафаров Е. Р., Саарбрюкен : LAP LAMBERT Academic Publishing, 2011
Фундаментальными задачами теории расписаний для одного прибора являются задачи с критериями минимизации суммарного запаздывания и задачи минимизации максимального временного смещения. В данной книге приводится достаточно полное исследование NP-трудной в обычном смысле задачи минимизации суммарного запаздывания (total tardiness) и ее взаимосвязь с задачей Разбиения. Выделен ряд новых полиномиально и псевдо-полиномиальных разрешимых случаев данной задачи. При исследовании ...
Добавлено: 17 декабря 2012 г.
Лазарев А. А., М. : Московский физико-технический институт, 2008
Рассматриваются классические NP-трудные задачи теории расписаний для одного и нескольких приборов с критерием минимизации максимального временного смещения и быстродействия. Предлагается качественно новая схема нахождения приближённого решения. Вводится понятие метрики (расстояния) между примерами задачи. Идея предлагаемого подхода состоит в построении по исходному примеру задачи другого примера, для которого удаётся найти оптимальное или приближённое решение с минимальным ...
Добавлено: 17 декабря 2012 г.
Лазарев А. А., Гафаров Е. Р., М. : Вычислительный центр им. А.А. Дородницына РАН, 2006
Фундаментальными задачами теории расписаний для одного прибора являются задачи с критериями минимизации суммарного запаздывания и минимизация максимального временного смещения. В данной работе приводится достаточно полное исследование NP-трудной в обычном смысле задачи минимизация суммарного запаздывания для одного прибора. ...
Добавлено: 17 декабря 2012 г.
Лазарев А. А., Гафаров Е. Р., М. : Вычислительный центр им. А.А. Дородницына РАН, 2007
Рассматривается задача построения расписания проекта с учетом ограничений на ресурсы и ее частные случаи. Приводятся результаты исследования известных нижних оценок. Выдвинута гипотеза о свойствах оптимального значения целевой функции в задаче с прерываниями и без прерываний обслуживания требований и представлено доказательство гипотезы для частных случаев задачи. Показано, что любой проект можно преобразовать в проект с "планарным" ...
Добавлено: 17 декабря 2012 г.
М. : ИПУ РАН, 2012
В сборнике представлены труды конференции с международным участием «ТЕХНИЧЕСКИЕ И ПРОГРАММНЫЕ СРЕДСТВА СИСТЕМ УПРАВЛЕНИЯ, КОНТРОЛЯ И ИЗМЕРЕНИЯ» УКИ`12 по следующим направлениям:
Научная тематика
1. Теория, методы исследования и проектирования, опыт применения технических средств (от датчиков до исполнительных механизмов), основанных на различных физических и схемотехнических принципах.
2. Теория, алгоритмы и программное обеспечение систем УКИ.
3. Анализ состояния, тенденций и перспектив ...
Добавлено: 29 декабря 2012 г.
Лазарев А. А., Мусатова Е. Г., Кварацхелия А. Г. и др., М. : Физический факультет МГУ, 2012
Данное учебное пособие посвящено задачам теории расписаний, возникающим на транспорте. Представлены основы теории расписаний, а также способы построения моделей и методы решения задач управления транспортными системами. Изложенный материал предназначен для студентов и преподавателей вузов математических специальностей, специалистов в области управления и практиков, занимающихся решением задач планирования грузовых перевозок. ...
Добавлено: 10 декабря 2012 г.
Лазарев А. А., Садыков Р. Р., М. : Вычислительный центр им. А.А. Дородницына РАН, 2007
Рассматриваются классические NP-трудные задачи теории расписаний для одного прибора: минимизация максимального временного смещения (1 | rj | Lmax) и суммарного взвешенного числа запаздывающих требований (1 | rj | ΣwjUj). Исследуемые задачи являются схематичными теоретическими моделями практических задач. Алгоритмы для решения этих задач используются как вспомогательные для решения более сложных задач теории расписаний, приближенных к практике. ...
Добавлено: 17 декабря 2012 г.
Лазарев А. А., Гафаров Е. Р., М. : Физический факультет МГУ, 2011
В данном учебном пособии приводятся базовые сведения о специальном разделе дискретной математики - Теории расписаний. Описаны этапы становления теории, свойства и классификации задач теории расписаний, методы их решения. На примерах классических задач представлены приемы доказательства их трудоемкости и алгоритмы решения. Учебное пособие основано на курсе лекций, читаемых в МФТИ, МГУ и ВШЭ, и предназначено для ...
Добавлено: 10 декабря 2012 г.
NY : Springer, 2011
This book constitutes the proceedings of the 11th International Conference on Parallel Computing Technologies, PaCT 2011, held in Kazan, Russia on September 19-23, 2011.
The 44 full papers presented together with 2 invited papers were carefully reviewed and selected from 68 submissions. The papers are organized in topical sections on models and languages, cellular automata, parallel ...
Добавлено: 1 декабря 2012 г.
Лазарев А. А., Мусатова Е. Г., Гафаров Е. Р. и др., М. : Федеральное государственное бюджетное учреждение науки Институт проблем управления им. В. А. Трапезникова Российской академии наук, 2012
Издание посвящено построению моделей и методам решения задач, возникающих при планировании грузовых железнодорожных перевозок. В зависимости от ограничений на локомотивы, грузоподъёмность составов, предлагаются различные алгоритмы решения задач формирования составов и расписания движения грузовых поездов. Изложенный материал будет полезен как специалистам в области управления, так и практикам, занимающихся решением задач планирования железнодорожных грузоперевозок. ...
Добавлено: 10 декабря 2012 г.
Leuven : Katholieke Universiteit Leuven, 2012
Добавлено: 27 декабря 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 г.
Лазарев А. А., Кварацхелия А. Г., Автоматика и телемеханика 2010 № 10 С. 80-89
Рассматривается задача теории расписаний минимизации суммарного взвешенного момента окончания для одного прибора с возможностью прерывания обслуживания требований. Продолжительности обслуживания всех требований одинаковы. На текущий момент данная задача является открытой, т.е. не известен полиномиальный алгоритм ее решения и не доказано, что она является NP-трудной. Приводятся свойства оптимальных расписаний данной задачи. ...
Добавлено: 24 ноября 2012 г.
Лазарев А. А., Вернер Ф., Mathematical and Computer Modelling 2009 Vol. 49 No. 9-10 P. 2061-2072
Добавлено: 24 ноября 2012 г.
Лазарев А. А., Гафаров Е. Р., Доклады Академии наук 2008 Т. 424 № 1 С. 7-9
Для задач на графах построен алгоритм трудоёмкости О(n^5), где n - количество вершин в графе, преобразующий непланарный неориентированный граф в планарный. В результате получается планарный граф, у которого сумма вершин и рёбер не больше, чем у исходного непланарного графа. Причём, если между вершинами i и j был путь, то он сохраниться, если не было такого ...
Добавлено: 23 ноября 2012 г.
Лазарев А. А., Гафаров Е. Р., Автоматика и телемеханика 2008 № 12 С. 86-104
Рассматривается задача построения расписания проекта с учётом ограничений на ресурсы (RCPSP) и её частные случаи. Проведён сравнительный анализ известных нижних оценок целевой функции - минимизации общего времени выполнения проекта. Выдвинута гипотеза, что для задачи RCPSP без прерываний в обслуживании требований оптимальное значение целевой функции не более чем в два раза больше оптимального значения целевой функции ...
Добавлено: 23 ноября 2012 г.
Лазарев А. А., Мусатова Е. Г., Управление большими системами: сборник трудов 2012 № 38 С. 161-169
Рассматривается задача формирования грузовых составов и маршрутов их следования по железнодорожной сети. Необходимо их следования по железнодорожной сети. Необходимо из имеющихся на станциях заказов сформировать составы и определить расписание и маршрут их движения до станций назначения так, чтобы минимизировать суммарное взвешенное время выполнения заказов. Предлагаются целочисленные постановки данной задачи, учитывающие ограничения, возникающие на практике. ...
Добавлено: 23 ноября 2012 г.
Гафаров Е. Р., Лазарев А. А., Вернер Ф., Автоматика и телемеханика 2010 № 10 С. 63-79
Рассматриваются две одноприборные задачи теории расписаний максимизации суммарного запаздывания и максимизации количества запаздывающих требований, когда простои в обслуживании требований запрещены и требования начинают обслуживаться с момента времени 0. Показано, что задача максимизации количества запаздывающих требований полиномиально разрешима. Для некоторых частных случаев задачи максимизации суммарного запаздывания представлены точные полиномиальные алгоритмы решения, а также два точных алгоритма ...
Добавлено: 24 ноября 2012 г.
Гафаров Е. Р., Лазарев А. А., Вернер Ф., Mathematical Social Sciences 2011 No. 62 P. 7-13
Добавлено: 24 ноября 2012 г.
Вернер Ф., Лазарев А. А., Automation and Remote Control 2010 Vol. 71 No. 10 P. 2019-2020
Тематический выпуск журнала Автоматика и телемеханика, посвященный 70-летию со дня рождения академика Вячеслава Сергеевича Танаева. ...
Добавлено: 23 ноября 2012 г.
Лазарев А. А., Садыков Р. Р., Севастьянов С., Дискретный анализ и исследование операций 2006 Т. 13 № 1 С. 57-76
Рассматривается NP-трудная в сильном смысле задача теории расписаний о минимизации максимального временного смещения на одном приборе при неодновременном поступлении работ. Представлена схема приближенного решения, основанная на отыскании по заданному примеру другого (наиболее близкого в некоторой метрике) примера, принадлежащего к известному полиномиально разрешимому классу примеров. Для нескольких конкретных вариантов схемы (с использованием различных полиномиально разрешимых классов ...
Добавлено: 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 г.
Лазарев А. А., Автоматика и телемеханика 2007 № 4 С. 13-23
Рассматривается графическая реализация метода динамического программирования. Идея метода показана на примерах решения задач разбиение и рюкзака. Проведен сравнительный анализ предлагаемого метода с известными алгоритмами решения этих задач. ...
Добавлено: 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 г.