?
Решение задачи минимизации времени выполнения заказа для конвейера с отношеними предшествования заданными набором рекурсивных функций
С. 1141–1145.
Лазарев А. А., Куприянов Б. В.
В статье вводится определение конвейера, описываемого связным ациклическим графом, каждая вершина которого, представляет собой операцию или функцию управления, ассоциированную с соответствующей рекурсивной функцией из некоторого конечного набора. Каждая рекурсивная функция определяет отношение предшествования операции конвейера. Рассматривается решение задачи минимизации времени выполнения заказа конвейером на конечном множестве возобновляемых ресурсов. Решение осуществляется методом Удовлетворения Ограничений, являющимся составной частью Constraint Programming.
Язык:
русский
The problem of the approximation of the coefficients of the objective function of a scheduling problem for a single machine is considered. It is necessary to minimize the total weighted completion times of jobs with unknown weight coefficients when a set of problem instances with known optimal schedules is given. It is shown that the ...
Добавлено: 16 мая 2024 г.
Alexander Lazarev, Lemtyuzhnikova D., Nikolay Pravdivets и др., , in: Advances in Optimization and Applications: 11th International Conference, OPTIMA 2020, Moscow, Russia, September 28 – October 2, 2020, Revised Selected PapersVol. 1340: Advances in Optimization and Applications.: Champaign: Springer Publishing Company, 2020. P. 211–223.
Добавлено: 16 декабря 2022 г.
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 г.
Ададуров С. Е., Алексеев А. М., Анисимов В. А. и др., М.: ООО "Издательство "ЛЕМА", 2020.
В коллективной монографии членов и научных партнеров Объединенного ученого совета ОАО «РЖД», объединяющего ведущих представителей отраслевой и фундаментальной российской науки, отражены ключевые вопросы научной поддержки перевозочного процесса и управления товарными потоками на железнодорожном транспорте, повышения эффективности его деятельности на основе клиентоориентированности и логистических принципов.
Рассмотрены системные вопросы развития логистических технологий, научные принципы прогнозирования и планирования железнодорожных ...
Добавлено: 4 февраля 2022 г.
Гафаров Е. Р., Лазарев А. А., Вернер Ф., Автоматика и телемеханика 2020 Т. 5 С. 119–138
Рассматривается задача теории расписаний, в которой необходимо минимизировать суммарное взвешенное запаздывание на одном приборе с равными продолжительностями обслуживания требований и неодновременным поступлением требований на обслуживание. Эта задача упомянута как минимальная, статус вычислительной сложности которой неизвестен: http://www2.informatik.uniosnabrueck.de/knust/class/dateien/classes/ein_ma/ein_ma. Последние результаты по данной задаче опубликованы в 2000 и 2005 гг., а именно, алгоритмы решения частных случаев задачи. В ...
Добавлено: 2 сентября 2020 г.
Гришин Е. М., Лазарев А. А., Мусатова Е. Г. и др., В кн.: Материалы 12-й мультиконференции по проблемам управления (МКПУ-2019, Дивноморское, Геленджик)Т. 1: XII МУЛЬТИКОНФЕРЕНЦИЯ ПО ПРОБЛЕМАМ УПРАВЛЕНИЯ.: Таганрог: Издательство Южного феделального университета, 2019. С. 178–181.
Рассмотрена задача построения графика проведения технического обслуживания локомотивов в объеме ТО-2 в пункте технического обслуживания локомотивов (ПТОЛ). Задано множество локомотивов, время их прибытия на ПТОЛ, продолжительность проведения ТО-2, характеристики и параметры ПТОЛ. На ПТОЛ можно выделить несколько групп ремонтных позиций определенной вместимости, на которых могут быть обслужены локомотивы разных серий, а также подъездные (тракционные) пути ...
Добавлено: 27 апреля 2020 г.
Гришин Е. М., Мусатова Е. Г., Галахов С. А. и др., В кн.: Труды 8-ой научно-технической конференции с международным участием «Интеллектуальные системы управления на железнодорожном транспорте. Компьютерное и математическое моделирование» (ИСУЖТ-2019, Москва).: М.: ОАО "НИИАС", 2019. С. 115–119.
Россия является одним из мировых лидеров по протяженности железных дорог. Для обеспечения перевозок по такой обширной сети железных дорог необходимо использовать крупный парк локомотивов. В России насчитывается более 14 тысяч различных типов локомотивов (тепловозы, электровозы, газотурбовозы и др.). Каждая серия любого типа локомотивов имеет свои особенности при обслуживании. В силу большого разнообразия локомотивов весьма затруднительно ...
Добавлено: 27 апреля 2020 г.
Лазарев А. А., Grishin E. M., Galakhov S. A. и др., IFAC-PapersOnLine 2019 Vol. 52-13 P. 951–956
This paper is devoted to the problem of scheduling maintenance of locomotives in a depot. The problem based on the operation Eastern polygon of Russian Railways. A heuristic algorithm and a constraint programming model are presented. Numerical experiments on real data for real depot configurations were carried out to compare the performance of the heuristic ...
Добавлено: 27 апреля 2020 г.
Лазарев А. А., Lemtuzhnikova D., Вернер Ф., /. 2019.
We consider NP-hard multi{machine scheduling problems with the criterion of minimizing the maximum penalty, e.g. maximum lateness. For such problems, we introduce a metric which delivers an upper bound on the absolute error of the objective function value. Taking the given in- stance of some problem and using the introduced metric, we determine the nearest ...
Добавлено: 26 апреля 2020 г.
Аничкин А. С., Морозов С. В., Семенов В. А. и др., Труды Института системного программирования РАН 2017 Т. 29 № 5 С. 239–256
В статье описывается практический опыт разработки перспективной системы визуального планирования проектов на основе объектно-ориентированного каркаса. Используемый каркас представляет собой систему классов и интерфейсов, предназначенных для программной реализации моделей, методов и приложений теории расписаний. Благодаря наличию готовых компонентов для решения типовых задач, а также предусмотренным механизмам их конфигурирования и расширения, создание приложений осуществляется относительно просто. Применение ...
Добавлено: 12 декабря 2018 г.
Аничкин А. С., Семенов В. А., Труды Института системного программирования РАН 2017 Т. 29 № 3 С. 247–296
Статья адресована вопросам программной реализации моделей, методов и приложений теории расписаний с использованием объектно-ориентированного каркаса. Каркас представляет собой систему классов вместе с предусмотренными механизмами взаимодействия и расширения, что обеспечивает эволюционную разработку серий приложений на единой методологической, программной и инструментальной основе. В статье детально обсуждаются принципы организации и функционирования разработанного каркаса, а также его возможности для ...
Добавлено: 12 декабря 2018 г.
Аничкин А. С., Семенов В. А., Труды Института системного программирования РАН 2017 Т. 29 № 2 С. 231–256
Задачи теории расписаний и проектного планирования находят широкое применение в научных и индустриальных областях. В статье обсуждаются возможности обобщенной математической постановки задач проектного планирования и их эффективного решения эвристическими алгоритмами полиномиальной сложности. ...
Добавлено: 12 декабря 2018 г.
Лазарев А. А., Архипов Д.И. Д. И., Доклады Академии наук 2018 Т. 480 № 5 С. 523–527
Предложен метод нахождения приближённого решения NP-трудных задач теории расписаний. Для задачи минимизации максимального временно`го смещения показано, как с помощью метрики, введённой на пространстве примеров задачи, можно использовать полиномиально разрешимые области для нахождения приближённого решения с гарантированной абсолютной погрешностью. Приведена теоретическая и экспериментальная оценка метода, а также сравнительный анализ с ED-эвристикой. Предложена численная характеристика полиномиальной неразрешимости ...
Добавлено: 1 октября 2018 г.
А.А.Лазарев, Зиндер Я., Мусатова Е. Г. и др., Автоматика и телемеханика 2018 № 3 С. 144–166
Рассматривается построение расписания двухстороннего движения поездов между двумя станциями, соединенными однопутной железной дорогой с разъездом. Показано, что если для каждой станции известен или может быть найден порядок отправления поездов, то для различных целевых функций за полиномиальное от количества поездов время может быть построено оптимальное расписание методом динамического программирования. На основе данного результата предложен полиномиальный алгоритм ...
Добавлено: 30 мая 2018 г.
Чусовлянкин А. А., Морозенко В. В., Вестник Пермского национального исследовательского политехнического университета. Электротехника, информационные технологии, системы управления 2016 № 20 С. 13–25
Cоставление оптимальных расписаний, с одной стороны, является практической потребностью и диктуется необходимостью экономии ресурсов, например, времени выполнения комплекса заданий в многопроцессорных вычислительных системах. С другой стороны, многие из задач теории расписаний являются NP-трудными и не могут быть решены точно за полиномиальное время ни одним из известных алгоритмов. Конвейерная задача – это одна из известных задач, ...
Добавлено: 26 января 2017 г.
Лазарев А. А., Мусатова Е. Г., Тарасов И. А., Автоматика и телемеханика 2016 № 11 С. 158–174
Рассматривается задача составления оптимального расписания движения поездов между двумя станциями, соединенными однопутной железной дорогой с разъездом. На основе метода динамического программирования предлагаются алгоритмы решения задач минимизации максимального временн´ого смещения и минимизации суммы взвешенных моментов окончания перевозок. Трудоемкость алгоритмов составляет O(n 2 ) операций, где n — количество поездов. ...
Добавлено: 22 декабря 2016 г.
Лазарев А. А., Архипов Д. И., Вернер Ф., В кн.: Танаевские чтения. Доклады Седьмой Международной научной конференции (28-29 марта 2016 года, Минск).: Мн.: Объединенный институт проблем информатики НАН Беларуси, 2016. С. 4–8.
Предлагается алгоритм решения класса задач теории расписаний для одного прибора. На одном приборе необходимо обслужить множество из $n$ требований, для каждого из которых заданы момент поступления, директивный срок и функция штрафа $\phi_j(t)$. Кроме того, заданы интервалы доступности прибора. ...
Добавлено: 31 октября 2016 г.
Лазарев А. А., Некрасов И. В., Правдивец Н. А., В кн.: Танаевские чтения. Доклады Седьмой Международной научной конференции (28-29 марта 2016 года, Минск).: Мн.: Объединенный институт проблем информатики НАН Беларуси, 2016. С. 108–113.
Рассматривается задача объемного планирования выпуска продукции промышленного предприятия. Строится целочисленная модель решения задачи и предлагаются ее расширения в виде дополнительных линейных ограничений, позволяющие учесть некоторые типовые сценарии загрузки ресурсов. Сформулированная задача разрешима полиномиально, так как является задачей ЛП. ...
Добавлено: 19 октября 2016 г.
Лазарев А. А., Мусатова Е. Г., Тарасов И. А., В кн.: Танаевские чтения. Доклады Седьмой Международной научной конференции (28-29 марта 2016 года, Минск).: Мн.: Объединенный институт проблем информатики НАН Беларуси, 2016. С. 103–107.
В работе предлагается алгоритм решения задачи планирования движения поездов между двумя станциями, соединенными однопутной железной дорогой с разъездом. Трудоёмкость алгоритма составляет $O(n^2)$ операций, где $n$ — количество поездов. ...
Добавлено: 19 октября 2016 г.
Мн.: Объединенный институт проблем информатики НАН Беларуси, 2016.
Представлены доклады 7-й Международной научной конференции «Танаевские чтения», посвященной памяти академика Национальной академии наук Вячеслава Сергеевича Танаева. Описаны последние результаты исследований в области теории расписаний, теории графов, оптимизации проектирования сложных технических объектов, логических схем и математического моделирования. Рекомендованы специалистам в области теории расписаний, теории графов, оптимизации проектирования сложных технических объектов, логических схем и математического моделирования. ...
Добавлено: 19 октября 2016 г.
Лазарев А. А., Архипов Д. И., Автоматика и телемеханика 2016 № 4 С. 134–152
Рассматривается классическая NP-трудная задача теории расписаний 1|r_j|L_max. Представлен алгоритм нахождения оптимального расписания обслуживания n требований (работ), когда параметры требований удовлетворяют системе линейных ограничений. Расширена полиномиально разрешимая область задачи 1|r_j|L_max. Представлен алгоритм построения Парето-оптимального множества расписаний по критериям L_max и C_max трудоёмкости O(n^3 log n) операций. ...
Добавлено: 3 августа 2016 г.
Лазарев А. А., Tarasov I., , in: VI International Conference on Optimization Methods and Applications "Optimization and applications" (OPTIMA-2015), Petrovac, Montenegro, September 2015.: M.: -, 2015. P. 198–199.
Задача составления оптимального расписания на однопутных участках актуальна как для пассажирских, так и для грузовых поездов, так как такие участки составляют значительную часть любой железнодорожной сети. В данной работе рассматривается задача составления оптимального расписания движения поездов на однопутной железной дороге между двумя станциями в случае одновременного поступления поездов на станции. Для увеличения пропускной способности на ...
Добавлено: 20 октября 2015 г.
Bronnikov S., Лазарев А. А., Петров А. С. и др., , in: VI International Conference on Optimization Methods and Applications "Optimization and applications" (OPTIMA-2015), Petrovac, Montenegro, September 2015.: M.: -, 2015. P. 196–197.
Рассматривается проблема планирования подготовки экипажей Международной космической станции (МКС). Разработаны математические модели, описывающие подготовку космонавтов для работы на МКС. Также предлагаются эвристические алгоритмы для решения этой задачи, и приводятся результаты экспериментов на различных исходных данных. ...
Добавлено: 20 октября 2015 г.