?
Decomposition of the Knapsack Problem for Increasing the Capacity of Operating Rooms
Mathematics. 2022. Vol. 10. No. 5. P. 1-18.
Лазарев А. А., Lemtyuzhnikova D. V., Somov M. L.
Ключевые слова: approximation algorithmsdecompositionscheduling problemBin packing problemcapacity increasehealth scheduling
ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА:
Лазарев А. А., Вернер Ф., / 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 ...
Добавлено: 4 марта 2013 г.
Лазарев А. А., Известия РАН. Теория и системы управления 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 г.
Лазарев А. А., Lemtyuzhnikova D., Вернер Ф., Applied Mathematical Modelling 2021 Vol. 89 No. 2 P. 1163-1176
Добавлено: 5 сентября 2020 г.
Лазарев А. А., Мусатова Е. Г., Кварацхелия А. Г. и др., М. : Физический факультет МГУ, 2012
Данное учебное пособие посвящено задачам теории расписаний, возникающим на транспорте. Представлены основы теории расписаний, а также способы построения моделей и методы решения задач управления транспортными системами. Изложенный материал предназначен для студентов и преподавателей вузов математических специальностей, специалистов в области управления и практиков, занимающихся решением задач планирования грузовых перевозок. ...
Добавлено: 10 декабря 2012 г.
Лазарев А. А., Автоматика и телемеханика 2007 № 4 С. 13-23
Рассматривается графическая реализация метода динамического программирования. Идея метода показана на примерах решения задач разбиение и рюкзака. Проведен сравнительный анализ предлагаемого метода с известными алгоритмами решения этих задач. ...
Добавлено: 23 ноября 2012 г.
Гафаров Е. Р., Лазарев А. А., Вернер Ф., Mathematical Social Sciences 2011 No. 62 P. 7-13
Добавлено: 24 ноября 2012 г.
Гафаров Е. Р., Лазарев А. А., Вернер Ф., / 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 ...
Добавлено: 4 марта 2013 г.
Гафаров Е. Р., Лазарев А. А., Вернер Ф., / 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. ...
Добавлено: 4 марта 2013 г.
Вернер Ф., Лазарев А. А., Automation and Remote Control 2010 Vol. 71 No. 10 P. 2019-2020
Тематический выпуск журнала Автоматика и телемеханика, посвященный 70-летию со дня рождения академика Вячеслава Сергеевича Танаева. ...
Добавлено: 23 ноября 2012 г.
Лазарев А. А., Гафаров Е. Р., Автоматика и телемеханика 2008 № 12 С. 86-104
Рассматривается задача построения расписания проекта с учётом ограничений на ресурсы (RCPSP) и её частные случаи. Проведён сравнительный анализ известных нижних оценок целевой функции - минимизации общего времени выполнения проекта. Выдвинута гипотеза, что для задачи RCPSP без прерываний в обслуживании требований оптимальное значение целевой функции не более чем в два раза больше оптимального значения целевой функции ...
Добавлено: 23 ноября 2012 г.
Лазарев А. А., Вернер Ф., / 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 \}$, ...
Добавлено: 4 марта 2013 г.
Лазарев А. А., Вернер Ф., Mathematical and Computer Modelling 2009 Vol. 49 No. 9-10 P. 2061-2072
Добавлено: 24 ноября 2012 г.
Гафаров Е. Р., Лазарев А. А., Вернер Ф., / 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. ...
Добавлено: 4 марта 2013 г.
Bliznets Ivan, Cygan M., Komosa P. и др., ACM Transactions on Computation Theory 2018 Vol. 10 No. 2 P. 1-32
Добавлено: 30 октября 2018 г.
Гафаров Е. Р., Лазарев А. А., 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 г.
Гафаров Е. Р., Лазарев А. А., Вернер Ф., Annals of Operations Research 2012 Vol. 196 No. 1 P. 247-261
Добавлено: 24 ноября 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 г.
Лукьянова А. Л., / Высшая школа экономики. Серия WP3 "Проблемы рынка труда". 2013. № WP3/2013/04.
В этой работе на данных РМЭЗ – НИУ ВШЭ за 2000–2010 гг. изучалось влияние неформальной занятости на общий уровень неравенства заработков на российском рынке труда с использованием декомпозиции квантильных регрессий. Декомпозиции базируются на методе рецентрированных функций влияния, предложенном Фипро, Фортин и Лемье (Fipro et al., 2009). Результаты исследования подтверждают неоднородность неформальной занятости, указывая на особое ...
Добавлено: 3 мая 2013 г.
Лазарев А. А., Кварацхелия А. Г., Автоматика и телемеханика 2010 № 10 С. 80-89
Рассматривается задача теории расписаний минимизации суммарного взвешенного момента окончания для одного прибора с возможностью прерывания обслуживания требований. Продолжительности обслуживания всех требований одинаковы. На текущий момент данная задача является открытой, т.е. не известен полиномиальный алгоритм ее решения и не доказано, что она является NP-трудной. Приводятся свойства оптимальных расписаний данной задачи. ...
Добавлено: 24 ноября 2012 г.
Лазарев А. А., Кварацхелия А. Г., Доклады Академии наук 2010 Т. 432 № 6 С. 746-749
Одним из актуальных вопросов разработки математической теории расписаний является построение метрик, которые можно использовать при разработке точных и приближенных алгоритмов решения задач. Введение метрических пространств для $NP$-трудных задач теории расписаний позволяет применять общие математические подходы к нахождению приближенного решения с гарантированной абсолютной погрешностью. Ранее для $NP$-трудных задач с критерием минимизации максимального временн\'ого смещения $\{P,R,Q\}|prec,r_j|\{L_{\max},C_{\max}\}$ была ...
Добавлено: 23 ноября 2012 г.
Лазарев А. А., Кварацхелия А. Г., Гафаров Е. Р., Доклады Академии наук 2007 Т. 412 № 6 С. 739-742
В работе рассматривается классическая NP-трудная в обычном смысле проблема теории расписаний минимизации суммарного запаздывания для одного прибора $1\mid\,\mid\sum T_j$. Для NP-трудного случая задачи предложена процедура его разбиения на частные подслучаи, для которых приводятся полиномиальные и псевдополиномиальные алгоритмы решения, трудоемкости не превышающей $O(n^2\sum p_j)$. ...
Добавлено: 23 ноября 2012 г.
Гафаров Е. Р., Лазарев А. А., Вернер Ф., Автоматика и телемеханика 2010 № 10 С. 63-79
Рассматриваются две одноприборные задачи теории расписаний максимизации суммарного запаздывания и максимизации количества запаздывающих требований, когда простои в обслуживании требований запрещены и требования начинают обслуживаться с момента времени 0. Показано, что задача максимизации количества запаздывающих требований полиномиально разрешима. Для некоторых частных случаев задачи максимизации суммарного запаздывания представлены точные полиномиальные алгоритмы решения, а также два точных алгоритма ...
Добавлено: 24 ноября 2012 г.
Гафаров Е. Р., Лазарев А. А., Вернер Ф., / Otto-von-Guericke Universitaet. 2010. No. 8.
Problem RCPSP may be formulated as follows. Given a set $N=\{1,\dots,n\}$ of jobs. A constant amount (quantity) of $Q_k>0$ units of resource $k, k=1,\dots,K,$ is available at any time. Job $j\in N$has to be processed for $p_j\geq 0$ time units without preemption. During this period, a constant amount (quantity) of $q_{jk} \geq 0$ units of ...
Добавлено: 4 марта 2013 г.