?
Решение задачи минимизации времени выполнения заказа для конвейера с отношеними предшествования заданными набором рекурсивных функций
С. 1141–1145.
Lazarev A. A., Куприянов Б. В.
Alexander Lazarev, Nikolay Pravdivets, Barashov E., Mathematics 2024 Vol. 12 No. 5 Article 699
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 ...
Added: May 16, 2024
Alexander Lazarev, Lemtyuzhnikova D., Nikolay Pravdivets et al., , 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.
Added: December 16, 2022
A. A. Lazarev, Lemtyuzhnikova D. V., N. A. Pravdivets, Computational Mathematics and Mathematical Physics 2021 Vol. 61 No. 7 P. 1169–1180
Metric functions are introduced for various classes of single-machine scheduling problems.It is shown how approximate solutions of NP-hard problems can be found using these functions. The metric value is determined by solving a linear programming problem with constraints being systems of linear inequalities for polynomial or pseudopolynomial solvable instances of the problem under study.In fact, ...
Added: February 4, 2022
Ададуров С. Е., Алексеев А. М., Анисимов В. А. et al., М.: ООО "Издательство "ЛЕМА", 2020.
В коллективной монографии членов и научных партнеров Объединенного ученого совета ОАО «РЖД», объединяющего ведущих представителей отраслевой и фундаментальной российской науки, отражены ключевые вопросы научной поддержки перевозочного процесса и управления товарными потоками на железнодорожном транспорте, повышения эффективности его деятельности на основе клиентоориентированности и логистических принципов.
Рассмотрены системные вопросы развития логистических технологий, научные принципы прогнозирования и планирования железнодорожных ...
Added: February 4, 2022
Gafarov E., Lazarev A. A., Werner F., Автоматика и телемеханика 2020 Т. 5 С. 119–138
Рассматривается задача теории расписаний, в которой необходимо минимизировать суммарное взвешенное запаздывание на одном приборе с равными продолжительностями обслуживания требований и неодновременным поступлением требований на обслуживание. Эта задача упомянута как минимальная, статус вычислительной сложности которой неизвестен: http://www2.informatik.uniosnabrueck.de/knust/class/dateien/classes/ein_ma/ein_ma. Последние результаты по данной задаче опубликованы в 2000 и 2005 гг., а именно, алгоритмы решения частных случаев задачи. В ...
Added: September 2, 2020
Гришин Е. М., Lazarev A. A., Musatova E. G. et al., В кн.: Материалы 12-й мультиконференции по проблемам управления (МКПУ-2019, Дивноморское, Геленджик)Т. 1: XII МУЛЬТИКОНФЕРЕНЦИЯ ПО ПРОБЛЕМАМ УПРАВЛЕНИЯ.: Таганрог: Издательство Южного феделального университета, 2019. С. 178–181.
Рассмотрена задача построения графика проведения технического обслуживания локомотивов в объеме ТО-2 в пункте технического обслуживания локомотивов (ПТОЛ). Задано множество локомотивов, время их прибытия на ПТОЛ, продолжительность проведения ТО-2, характеристики и параметры ПТОЛ. На ПТОЛ можно выделить несколько групп ремонтных позиций определенной вместимости, на которых могут быть обслужены локомотивы разных серий, а также подъездные (тракционные) пути ...
Added: April 27, 2020
Гришин Е. М., Musatova E. G., Галахов С. А. et al., В кн.: Труды 8-ой научно-технической конференции с международным участием «Интеллектуальные системы управления на железнодорожном транспорте. Компьютерное и математическое моделирование» (ИСУЖТ-2019, Москва).: М.: ОАО "НИИАС", 2019. С. 115–119.
Россия является одним из мировых лидеров по протяженности железных дорог. Для обеспечения перевозок по такой обширной сети железных дорог необходимо использовать крупный парк локомотивов. В России насчитывается более 14 тысяч различных типов локомотивов (тепловозы, электровозы, газотурбовозы и др.). Каждая серия любого типа локомотивов имеет свои особенности при обслуживании. В силу большого разнообразия локомотивов весьма затруднительно ...
Added: April 27, 2020
Lazarev A. A., Grishin E. M., Galakhov S. A. et al., 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 ...
Added: April 27, 2020
Lazarev A. A., Lemtuzhnikova D., Werner F., /. 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 ...
Added: April 26, 2020
Аничкин А. С., Морозов С. В., Семенов В. А. et al., Труды Института системного программирования РАН 2017 Т. 29 № 5 С. 239–256
В статье описывается практический опыт разработки перспективной системы визуального планирования проектов на основе объектно-ориентированного каркаса. Используемый каркас представляет собой систему классов и интерфейсов, предназначенных для программной реализации моделей, методов и приложений теории расписаний. Благодаря наличию готовых компонентов для решения типовых задач, а также предусмотренным механизмам их конфигурирования и расширения, создание приложений осуществляется относительно просто. Применение ...
Added: December 12, 2018
Аничкин А. С., Семенов В. А., Труды Института системного программирования РАН 2017 Т. 29 № 3 С. 247–296
Статья адресована вопросам программной реализации моделей, методов и приложений теории расписаний с использованием объектно-ориентированного каркаса. Каркас представляет собой систему классов вместе с предусмотренными механизмами взаимодействия и расширения, что обеспечивает эволюционную разработку серий приложений на единой методологической, программной и инструментальной основе. В статье детально обсуждаются принципы организации и функционирования разработанного каркаса, а также его возможности для ...
Added: December 12, 2018
Аничкин А. С., Семенов В. А., Труды Института системного программирования РАН 2017 Т. 29 № 2 С. 231–256
Задачи теории расписаний и проектного планирования находят широкое применение в научных и индустриальных областях. В статье обсуждаются возможности обобщенной математической постановки задач проектного планирования и их эффективного решения эвристическими алгоритмами полиномиальной сложности. ...
Added: December 12, 2018
Lazarev A. A., Архипов Д.И. Д. И., Доклады Академии наук 2018 Т. 480 № 5 С. 523–527
A method for finding an approximate solution for NP-hard scheduling problems is proposed. The example of the classical NP-hard in the strong sense problem of minimizing the maximum lateness of job processing with a single machine shows how a metric introduced on the instance space of the problem and polynomially solvable areas can be used ...
Added: October 1, 2018
А.А.Лазарев, Зиндер Я., Мусатова Е. Г. et al., Автоматика и телемеханика 2018 № 3 С. 144–166
The paper is concerned with scheduling the two-way traffic between two stations connected by a single-track railway with a siding. It is shown that if, for each station, the order in which trains leave this station is known or can be found, then for various objective functions an optimal schedule can be constructed in polynomial ...
Added: May 30, 2018
Chusovliankin A., Morozenko V. V., Вестник Пермского национального исследовательского политехнического университета. Электротехника, информационные технологии, системы управления 2016 № 20 С. 13–25
The optimal schedule, on the one hand, is a practical necessity to conserve resources, for example, problem in the multiprocessor computing systems. On the other hand, many of the scheduling problems are NP-hard and can not be solved exactly in polynomial time. Flow shop scheduling problem is the one of the most famous optimization problem. ...
Added: January 26, 2017
Lazarev A. A., Мусатова Е. Г., Тарасов И. А., Автоматика и телемеханика 2016 № 11 С. 158–174
Рассматривается задача составления оптимального расписания движения поездов между двумя станциями, соединенными однопутной железной дорогой с разъездом. На основе метода динамического программирования предлагаются алгоритмы решения задач минимизации максимального временн´ого смещения и минимизации суммы взвешенных моментов окончания перевозок. Трудоемкость алгоритмов составляет O(n 2 ) операций, где n — количество поездов. ...
Added: December 22, 2016
Lazarev A. A., Arkhipov D. I., Werner F., В кн.: Танаевские чтения. Доклады Седьмой Международной научной конференции (28-29 марта 2016 года, Минск).: Мн.: Объединенный институт проблем информатики НАН Беларуси, 2016. С. 4–8.
Предлагается алгоритм решения класса задач теории расписаний для одного прибора. На одном приборе необходимо обслужить множество из $n$ требований, для каждого из которых заданы момент поступления, директивный срок и функция штрафа $\phi_j(t)$. Кроме того, заданы интервалы доступности прибора. ...
Added: October 31, 2016
Lazarev A. A., Некрасов И. В., Правдивец Н. А., В кн.: Танаевские чтения. Доклады Седьмой Международной научной конференции (28-29 марта 2016 года, Минск).: Мн.: Объединенный институт проблем информатики НАН Беларуси, 2016. С. 108–113.
Рассматривается задача объемного планирования выпуска продукции промышленного предприятия. Строится целочисленная модель решения задачи и предлагаются ее расширения в виде дополнительных линейных ограничений, позволяющие учесть некоторые типовые сценарии загрузки ресурсов. Сформулированная задача разрешима полиномиально, так как является задачей ЛП. ...
Added: October 19, 2016
Lazarev A. A., Musatova E. G., Тарасов И. А., В кн.: Танаевские чтения. Доклады Седьмой Международной научной конференции (28-29 марта 2016 года, Минск).: Мн.: Объединенный институт проблем информатики НАН Беларуси, 2016. С. 103–107.
В работе предлагается алгоритм решения задачи планирования движения поездов между двумя станциями, соединенными однопутной железной дорогой с разъездом. Трудоёмкость алгоритма составляет $O(n^2)$ операций, где $n$ — количество поездов. ...
Added: October 19, 2016
Мн.: Объединенный институт проблем информатики НАН Беларуси, 2016.
Представлены доклады 7-й Международной научной конференции «Танаевские чтения», посвященной памяти академика Национальной академии наук Вячеслава Сергеевича Танаева. Описаны последние результаты исследований в области теории расписаний, теории графов, оптимизации проектирования сложных технических объектов, логических схем и математического моделирования. Рекомендованы специалистам в области теории расписаний, теории графов, оптимизации проектирования сложных технических объектов, логических схем и математического моделирования. ...
Added: October 19, 2016
Lazarev A. A., Архипов Д. И., Автоматика и телемеханика 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) операций. ...
Added: August 3, 2016
Lazarev A. A., 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.
A railway connection of two stations by a single railway track is usually found on branch lines of railway network and is very common in various manufacturing supply chains. Our paper isДля книг на иностранных языках concerned with a scheduling problem for two stations with a single railway track with one siding. On single-track railway ...
Added: October 20, 2015
Bronnikov S., Lazarev A. A., Petrov A. S. et al., , in: VI International Conference on Optimization Methods and Applications "Optimization and applications" (OPTIMA-2015), Petrovac, Montenegro, September 2015.: M.: -, 2015. P. 196–197.
We consider the problem of planning the ISS cosmonaut training with different objectives. A pre-defined set of minimum qualification levels should be distributed between the crew members with minimum training time differences, training expenses or a maximum of the training level with a limitation of the budget. First, a description of the cosmonaut training process ...
Added: October 20, 2015