?
Подходы решения задачи составления учебного расписания
С. 44.
Лазарев А. А., Дудченко А. М.
Рассматриваются две задачи составления учебных расписаний. Первая -- составление расписаний в зарубежных вузах, когда каждый студент рассматривается отдельно, и вторая -- составление расписаний в российских вузах, когда студенты обучаются в группе.
Язык:
русский
В книге
Иркутск : Институт систем энергетики им. Л.А. Мелентьева СО РАН, 2014
Лазарев А. А., Архипов Д.И. Д. И., Доклады Академии наук 2018 Т. 480 № 5 С. 523-527
Предложен метод нахождения приближённого решения NP-трудных задач теории расписаний. Для задачи минимизации максимального временно`го смещения показано, как с помощью метрики, введённой на пространстве примеров задачи, можно использовать полиномиально разрешимые области для нахождения приближённого решения с гарантированной абсолютной погрешностью. Приведена теоретическая и экспериментальная оценка метода, а также сравнительный анализ с ED-эвристикой. Предложена численная характеристика полиномиальной неразрешимости ...
Добавлено: 1 октября 2018 г.
Лазарев А. А., Кварацхелия А. Г., , in : Optimization and applications (OPTIMA-2009). : M. : -, 2009. P. 58-59.
In this paper, we propose an approach for obtaining metrics for a variety of scheduling problems. ...
Добавлено: 4 марта 2013 г.
Гафаров Е. Р., Лазарев А. А., В кн. : Труды 1-й научно-технической конференции "Интеллектуальные системы управления на железнодорожном транспорте" (ИСУЖТ-2012, Москва). : М. : ОАО "НИИАС", 2012. С. 114-129.
Рассматривается задача теории расписаний для однопутной железной дороги между двумя станциями и множеством поездов. ...
Добавлено: 20 октября 2014 г.
Лазарев А. А., Баранов А. В., Amsterdam : University of Amsterdam, 2011
Добавлено: 4 марта 2013 г.
Лазарев А. А., Мусатова Е. Г., Тарасов И. А., Автоматика и телемеханика 2016 № 11 С. 158-174
Рассматривается задача составления оптимального расписания движения поездов между двумя станциями, соединенными однопутной железной дорогой с разъездом. На основе метода динамического программирования предлагаются алгоритмы решения задач минимизации максимального временн´ого смещения и минимизации суммы взвешенных моментов окончания перевозок. Трудоемкость алгоритмов составляет O(n 2 ) операций, где n — количество поездов. ...
Добавлено: 22 декабря 2016 г.
Аничкин А. С., Семенов В. А., Труды Института системного программирования РАН 2017 Т. 29 № 2 С. 231-256
Задачи теории расписаний и проектного планирования находят широкое применение в научных и индустриальных областях. В статье обсуждаются возможности обобщенной математической постановки задач проектного планирования и их эффективного решения эвристическими алгоритмами полиномиальной сложности. ...
Добавлено: 12 декабря 2018 г.
Гафаров Е. Р., Лазарев А. А., Вернер Ф., Mathematical Social Sciences 2011 No. 62 P. 7-13
Добавлено: 24 ноября 2012 г.
Гафаров Е. Р., Лазарев А. А., Вернер Ф., Annals of Operations Research 2012 Vol. 196 No. 1 P. 247-261
Добавлено: 24 ноября 2012 г.
Лазарев А. А., Архипов Д. И., , in : 28th Conference of the European Chapter on Combinatorial Optimization. : Катания : University of Catania, 2015. P. 64.
The following classical NP-complete scheduling problem is considered. ...
Добавлено: 22 июня 2015 г.
Лазарев А. А., В кн. : Труды третьей российской конференции с международным участием «Технические и программные средства систем управления, контроля и измерения»: труды и пленарные доклады участников конференции УКИ`12. : М. : ИПУ РАН, 2012. С. 371-380.
В статье представлены новые модели задач, возникающих в области маршрутизации железнодорожного грузового транспорта, формирования составов и графиков их движения. Предлагаются точные полиномиальные алгоритмы решения частных случаев сформулированных задач. ...
Добавлено: 29 декабря 2012 г.
Лазарев А. А., Gafarov E., Werner F., Information Processing Letters 2012 Vol. 112 No. 3 P. 72-76
Добавлено: 15 октября 2014 г.
Лазарев А. А., Гафаров Е. Р., , in : IFAC Symposium on Information Control Problems in Manufacturing (2009). : M. : [б.и.], 2009. P. 1512-1515.
We consider some special cases of the NP-hard resource-constrained projects cheduling problem (RCPSP) to minimize the makespan. We show that a well-known lowerbounds for the problem may yield bad approximation ratios or its calculation is an NP-hardproblem too. We conjecture that the ratio of the optimal makespan of RCPSP to that of the preemptive version ...
Добавлено: 4 марта 2013 г.
Лазарев А. А., Гафаров Е. Р., М. : Вычислительный центр им. А.А. Дородницына РАН, 2007
Рассматривается задача построения расписания проекта с учетом ограничений на ресурсы и ее частные случаи. Приводятся результаты исследования известных нижних оценок. Выдвинута гипотеза о свойствах оптимального значения целевой функции в задаче с прерываниями и без прерываний обслуживания требований и представлено доказательство гипотезы для частных случаев задачи. Показано, что любой проект можно преобразовать в проект с "планарным" ...
Добавлено: 17 декабря 2012 г.
A. A. Lazarev, Lemtyuzhnikova D. V., N. A. Pravdivets, Computational Mathematics and Mathematical Physics 2021 Vol. 61 No. 7 P. 1169-1180
Вводятся функции метрики для разных классов задач теории расписаний для одного прибора. Показано, как с помощью введенных функций находятся приближенные решения NP-трудных задач. Величина метрики находится в результате решения задачи линейного программирования, ограничениями которой являются системы линейных неравенств полиномиальных или псевдополиномиальных разрешимых случаев исследуемых задач. Фактически находится проекция во введенной метрике решаемого примера на разрешимые ...
Добавлено: 4 февраля 2022 г.
Гафаров Е. Р., Лазарев А. А., 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 г.
Кварацхелия А. Г., Лазарев А. А., , in : Multidisciplinary International Conference on Scheduling: Theory and Application, Paris, France, 2009. : Dublin : [б.и.], 2009. P. 68-76.
In this paper, we consider the minimizing total weighted completion time inpreemptive equal-length job with release dates scheduling problem on a single machine. Before this paper the problem is known to be open. Here, we present a polynomial timealgorithm that solves the problem with O(n^7) operations. ...
Добавлено: 4 марта 2013 г.
Чусовлянкин А. А., Морозенко В. В., Вестник Пермского национального исследовательского политехнического университета. Электротехника, информационные технологии, системы управления 2016 № 20 С. 13-25
Cоставление оптимальных расписаний, с одной стороны, является практической потребностью и диктуется необходимостью экономии ресурсов, например, времени выполнения комплекса заданий в многопроцессорных вычислительных системах. С другой стороны, многие из задач теории расписаний являются NP-трудными и не могут быть решены точно за полиномиальное время ни одним из известных алгоритмов. Конвейерная задача – это одна из известных задач, ...
Добавлено: 26 января 2017 г.
Лазарев А. А., , in : European Chapter on Combinatorial Optimization (ECCO 2009). : Jerusalem : [б.и.], 2009. P. 13-13.
In this paper, for $NP$-hardness single and multi-machine scheduling problems with the criterion of minimization maximum lateness the metrics $\rho$ has been used. We consider some approaches finding of the approximate solution for the problems. The idea of approaches consists in construction to a initial instance $A$ such instance $B$ (with the same number of ...
Добавлено: 4 марта 2013 г.
Лазарев А. А., Некрасов И. В., Правдивец Н. А., В кн. : Танаевские чтения. Доклады Седьмой Международной научной конференции (28-29 марта 2016 года, Минск). : Мн. : Объединенный институт проблем информатики НАН Беларуси, 2016. С. 108-113.
Рассматривается задача объемного планирования выпуска продукции промышленного предприятия. Строится целочисленная модель решения задачи и предлагаются ее расширения в виде дополнительных линейных ограничений, позволяющие учесть некоторые типовые сценарии загрузки ресурсов. Сформулированная задача разрешима полиномиально, так как является задачей ЛП. ...
Добавлено: 19 октября 2016 г.
Лазарев А. А., Журнал вычислительной математики и математической физики 2007 Т. 47 № 6 С. 1087-1099
Рассматривается классическая $NP$-трудная в обычном смысле задача теории расписаний для одного прибора минимизации суммарного запаздывания $1~\mid~\mid~\sum T_j$. Проведен полный анализ $NP$-трудного случая задачи. Предлагается процедура разбиения исходного множества требований на подмножества. Построены алгоритмы нахождения оптимального расписания в зависимости от количества подмножеств. Трудоемкость алгоритмов не превышает $O(n^2\sum p_j)$ операций, где $n$ -- количество требований, а $p_j$ ...
Добавлено: 23 ноября 2012 г.
Лазарев А. А., Автоматика и телемеханика 2014 № 7 С. 14-16
Теория расписаний -- это раздел дискретной математики, изучающий математические постановки и методы решения задач оптимального выполнения некоторого набора требований (работ, задач, процессов и т.п.). К теории расписаний относятся вопросы, связанные с построением оптимальных расписаний (календарных планов, графиков) выполнения конечных или периодических комплексов операций в системах, содержащих ограниченные ресурсы. Область приложений результатов теории расписаний включает в ...
Добавлено: 8 сентября 2014 г.
Гафаров Е. Р., Лазарев А. А., Вернер Ф., / 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 г.
Лазарев А. А., Мусатова Е. Г., Ласкова М. В., В кн. : Труды 1-й научно-технической конференции "Интеллектуальные системы управления на железнодорожном транспорте" (ИСУЖТ-2012, Москва). : М. : ОАО "НИИАС", 2012. С. 115-118.
Рассматривается задача формирования расписания движения железнодорожных составов между двумя станциями при условии, что станции соединены одноколейной дорогой. ...
Добавлено: 20 октября 2014 г.
Архипов Д. И., Лазарев А. А., , in : EURO-INRORMS Rome 2013. : Rome : Sapienza Università di Roma, 2013. P. 156.
Добавлено: 21 октября 2014 г.