автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Многокритериальные модели однопроцессорного обслуживания стационарных объектов: исследование оптимизационных задач, построение решающих алгоритмов

кандидата технических наук
Пушкин, Антон Михайлович
город
Нижний Новгород
год
2015
специальность ВАК РФ
05.13.01
Автореферат по информатике, вычислительной технике и управлению на тему «Многокритериальные модели однопроцессорного обслуживания стационарных объектов: исследование оптимизационных задач, построение решающих алгоритмов»

Автореферат диссертации по теме "Многокритериальные модели однопроцессорного обслуживания стационарных объектов: исследование оптимизационных задач, построение решающих алгоритмов"

На правах рукописи

Пушкин Антон Михайлович

МНОГОКРИТЕРИАЛЬНЫЕ МОДЕЛИ ОДНОПРОЦЕССОРНОГО ОБСЛУЖИВАНИЯ СТАЦИОНАРНЫХ ОБЪЕКТОВ: ИССЛЕДОВАНИЕ ОПТИМИЗАЦИОННЫХ ЗАДАЧ, ПОСТРОЕНИЕ РЕШАЮЩИХ АЛГОРИТМОВ

Специальность 05.13.01 — Системный анализ, управление и обработка информации (в науке и промышленности) по техническим наукам

Автореферат 2 1 ОКТ 2015

диссертации на соискание ученой степени кандидата технических наук

Нижний Новгород - 2015 005563514

Работа выполнена на кафедре «Прикладной математики и механики» Федерального государственного бюджетного образовательного учреждения высшего образования «Московский государственный университет информационных технологий, радиотехники и электроники».

Научный руководитель: доктор технических наук,

профессор Коган Дмитрий Израилевич

Научный консультант: доктор технических наук,

профессор Федосенко Юрий Семенович

Официальные оппоненты: Прилуцкин Михаил Хаимович,

доктор технических наук, профессор, Нижегородский государственный университет им. Н.И. Лобачевского, заведующий кафедрой Информатики и автоматизации научных исследований Института информационных технологий, математики и механики

Лазарев Евгений Александрович,

кандидат технических наук, ЗАО «ИНТЕЛ А/О» (филиал в Нижнем Новгороде), старший инженер по разработке программного обеспечения

Ведущая организация: Федеральное государственное бюджетное

учреждение науки Институт проблем управления им. В.А. Трапезникова РАН, г. Москва

Защита диссертации состоится 10 декабря 2015 г. в 13 часов в аудитории 1258 на заседании диссертационного совета Д 212.165.05 при Нижегородском государственном техническом университете им. P.E. Алексеева по адресу: 603950, г. Нижний Новгород, ул. Минина, 24.

С диссертацией можно ознакомиться в библиотеке Нижегородского государственного технического университета им. P.E. Алексеева.

Автореферат разослан « 9 » октября 2015 г.

Ученый секретарь диссертационного совета

Суркова Анна Сергеевна

Общая характеристика работы

Растущие требования к экономической эффективности функционирования целого ряда организационно-технических систем предопределяют необходимость повышения качества их логистико-технологического обеспечения. Принимаемые оперативные управленческие решения заключаются в планировании и диспетчеризации процессов обслуживания совокупностей объектов процессорами того или иного функционального назначения. Именно к такому классу обслуживания относятся, например, локальные логистические технологии снабжения дизельным топливом плавучих специализированных комплексов (земснарядов), осуществляющих на полигонах внутренних водных путей РФ русловую добычу и погрузку в порожние грузовые суда нерудных строительных материалов. Такие процессы характеризуются высоким темпом изменения оперативной обстановки и, как следствие, могут эффективно управляться лишь при реализации автоматизированной технологии формирования диспетчерских решений, основанной на адекватных теоретических моделях и быстродействующих вычислительных алгоритмах.

Вышеуказанное обусловливает актуальность темы диссертационной работы, направленной на:

1) создание и исследование новых, обобщенных теоретических моделей процессов обслуживания стационарных объектов перемещающимся процессором;

2) постановку и исследование семейства оптимизационных задач обслуживания, покрывающих массовые типы эксплуатационных ситуаций;

3) конструирование и исследование алгоритмов решений поставленных оптимизационных задач с приемлемыми для штатной реализации показателями быстродействия и требуемой памяти.

Средства для математического описания изучаемых проблем предоставляет аппарат теории расписаний. При этом точность моделирования определяется выбором шага дискретности пространственных и временных параметров, а синтез оптимальных стратегий (расписаний) обслуживания осуществим методами дискретного программирования.

Соответствующее направление в науке берет начало с известной работы Gantt H.L. (1903 г.). Термин «теория расписаний» в 50-х годах ввел Bellman R.; одними из первых были работы Johnson S.M., Jackson J.R., Smith W.E. Отдельным направлением в области исследования операций данная проблематика стала благодаря работам Bellman R., Brucker P., Coffman E.G., Conway R.W., Garey M., Graham R.L., Johnson D., Karp R.M., Lawler E.L., Lenstra J.K., Maxwell W.L., Miller L.W., Pinedo M.L., Танаева B.C., Шкурбы B.B.

Различные проблемы управления обслуживанием в моделях транс-портно-технологических систем и соответствующие им задачи синтеза расписаний обслуживания исследовались в работах Батищева Д.И., Беленького A.C., Буркова В.Н., Гимади Э.Х., Гордона B.C., Долгия А.Б., Зака Ю.А.,

Ковалева М.Я., Корбута A.A., Лазарева A.A., Левнера Е.В., Новикова Д.И., Под-часовой Т.П., Прилуцкого М.Х., Серваха В.В., Сигала И.Х., Сотскова Ю.Н., Струсевича В.А., Ульянова М.В., Фазылова В.Р., Финкельштейна Ю.Ю., Шафранского Я.М., Blazewicz J., Gendreau М., Nossack J., Pesch E., Sterna M., Werner F. и ряда других авторов.

В работах указанных исследователей, как правило, полагается, что обслуживающие процессоры стационарны, а требующие обслуживания объекты поступают к ним в заданные моменты времени; при этом оптимизируемым является единственный критерий.

В данной диссертационной работе объекты считаются стационарными, расположенными в рабочей зоне их обслуживающего перемещающегося процессора. Соответствующее направление активно изучалось в работах Дунич-киной H.A., Когана Д.И., Федосенко Ю.С., Шлюгаева А.Ю. Настоящее исследование развивает работы перечисленных авторов. При этом принципиальными являются следующие диктуемые транспортно-технологическими приложениями обстоятельства:

- учет ранних сроков готовности объектов к обслуживанию;

- системные ограничения на возможные траектории перемещения обслуживающего процессора;

- возможность одновременного учета нескольких критериев оценки качества стратегий обслуживания.

В наиболее общей ситуации рабочая зона процессора определяется конечным взвешенным ориентированным графом G, вершины которого соответствуют точкам расположения объектов, подлежащих обслуживанию, а веса ребер могут задавать как расстояния между парами смежных точек, так и времена перемещений процессора между ними.

При перемещениях процессора не ограничивается число его транзитных проходов через точки расположения объектов. Такие модели и порождаемые ими оптимизационные задачи имеют ряд транспортно-технологических интерпретаций, связанных с обходом обслуживающим процессором пространственно рассредоточенной системы стационарных объектов.

Моделирование изучаемых процессов выполняется с помощью их формализации как систем обслуживания перемещающимся процессором Р совокупности объектов Оп = {о,,о2,...,оп}, расположенных в соответствующих вершинах графа G. Обслуживание процессором Р объекта о;, j = \,п, осуществляется за временной промежуток zv с началом либо в предписанный ранний срок rJt либо от момента прибытия процессора в точку j (если на момент прибытия процессора объект готов к обслуживанию). В случае прибытия процессора

в точку у в момент времени /*, < г, процессор простаивает в ожидании готовности объекта о]. Объекты подлежат однократному обслуживанию, при

этом накладывается ряд ограничений:

- обслуживание осуществляется без прерываний;

- простои процессора, не связанные с обслуживанием объектов и с ожиданием наступления ранних сроков, запрещены.

Специфика задач диспетчеризации на внутреннем водном транспорте заключается в том, что между моментом, когда полностью определились исходные данные для построения расписания, и моментом начала реализации этого расписания проходит относительно небольшой промежуток времени, в течение которого расписание должно быть составлено. В связи с этим существенную роль играют рассматриваемые в работе вопросы вычислительной сложности изучаемых задач и конструируемых алгоритмов.

Диспетчерское управление осуществляется в оперативно изменяющихся ситуационных условиях: при учете существенных внешних обстоятельств доминирующими могут оказываться различные факторы (например, степень выполнения договорных обязательств, наличие запасов топлива, целевые указания). Математический аппарат для формирования качественных проектов управленческих решений должен быть комплексным, т.е. обеспечен достаточно широким спектром решаемых задач, многокритериальностью в их постановках.

В диссертационной работе рассматриваются типовые для транс-портно-технологических приложений конфигурации рабочей зоны и способы перемещения процессора.

Целью работы является построение формализованных моделей, постановка и исследование многокритериальных задач обслуживания (возникающих в транспортной логистике), разработка комплекса алгоритмических и программных средств синтеза оптимальных и субоптимальных стратегий обслуживания пространственно рассредоточенной системы стационарных объектов перемещающимся процессором.

Достижение поставленной цели потребовало реализации следующих этапов:

- обзор литературы по теме исследования;

- разработка теоретических моделей обслуживания группы стационарных объектов перемещающимся процессором, соответствующих имеющимся содержательным интерпретациям;

- постановка однокритериальных и многокритериальных задач синтеза оптимальных стратегий обслуживания;

- разработка алгоритмов синтеза оптимальных, парето-оптималь-ных, а также субоптимальных стратегий обслуживания с приемлемыми для решения практических задач характеристиками;

— создание программного комплекса для решения задач оперативного планирования обслуживания перемещающимся процессором группы пространственно рассредоточенных стационарных объектов.

Научная новизна работы состоит в следующих основных результатах.

1. Построены обобщенные теоретические модели одностадийного обслуживания группы пространственно рассредоточенных стационарных объектов перемещающимся процессором, учитывающие ограничения на возможные траектории его движения, а также предписанные объектам ранние сроки начала обслуживания.

2. В рамках моделей п. 1 поставлены однокритериальные и многокритериальные задачи синтеза стратегий обслуживания. В частности, сформулированы трехкритериальные задачи, где наряду с известными критериями оценки (суммарный по всем объектам штраф, максимальный из индивидуальных штрафов по объектам) введены ранее не рассматривавшиеся критерии (общее время работы процессора в пределах рабочей зоны, суммарное время простоев процессора в ожидании наступления ранних сроков, длина пройденного процессором пути).

3. Для однокритериальных задач п. 2 на основе идеологии динамического программирования разработаны алгоритмы синтеза оптимальных стратегий обслуживания. Для многокритериальных задач п. 2 в условиях концепции Парето реализован принцип динамического программирования в его многокритериальном обобщении, что позволяет строить полные совокупности эффективных оценок с одновременным обеспечением возможности синтеза по любой из таких оценок порождающей её оптимальной стратегии обслуживания. Для решения задач п. 2 больших размерностей дополнительно разработаны алгоритмы синтеза субоптимальных стратегий обслуживания, базирующиеся на концепции эволюционно-генетических вычислений.

Теоретическая значимость результатов работы. Исследована вычислительная сложность поставленных оптимизационных задач. Для однокритериальных задач синтеза стратегий обслуживания стационарных объектов перемещающимся процессором разработаны методы поиска оптимального значения критерия и построения соответствующей стратегии обслуживания. Для многокритериальных задач синтеза стратегий обслуживания стационарных объектов перемещающимся процессором разработана методика построения обобщенных на случай нескольких критериев рекуррентных соотношений динамического программирования. Указанные соотношения для всех рассмотренных задач обеспечивают синтез полных совокупностей эффективных оценок и возможность построения по любой из полученных оценок соответствующей парето-оптимальной стратегии обслуживания.

Практическая значимость результатов диссертационной работы определяется следующим. Разработанные теоретические модели, построенные решающие алгоритмы и их программные реализации применимы в исследовательских и производственных компьютерных системах, целью которых

является решение однокритериальных и многокритериальных задач диспетчерского управления обслуживанием группы рассредоточенных стационарных объектов. Указанные задачи возникают в транспортно-технологических системах снабжения топливом плавучих дизель-электрических добывающих комплексов на русловых месторождениях внутренних водных путей, на производственных участках лесозаготовительной промышленности и т.д. Изучаемый класс приложений достаточно широк и активно развивается. Существуют проектные решения по управлению дозаправкой орбитальной группы спутников1 и магистральных гражданских самолетов2.

Положения, выносимые на защиту:

- обобщенные теоретические модели, учитывающие ранние сроки начала обслуживания стационарных объектов;

- постановки в рамках сконструированных моделей однокритериальных и многокритериальных задач, в том числе с ранее не рассматриваемыми типами критериев;

- результаты оценки вычислительной сложности поставленных оптимизационных задач;

- построенные на основе принципа динамического программирования точные решающие алгоритмы для всех поставленных задач;

- созданные с использованием идеологии эволюционно-генетиче-ских вычислений эвристические алгоритмы, предназначенные для решения задач больших размерностей;

- специализированное программное обеспечение, реализующее разработанные алгоритмы решения всех задач, поставленных в рамках сконструированных моделей.

Обоснованность и достоверность результатов диссертационной работы обеспечивается: разработанными теоретическими моделями, адекватно описывающими транспортно-технологические процессы рассматриваемого типа; применяемой методикой исследования; корректным использованием математического аппарата и выполненными массовыми вычислительными экспериментами.

Реализация и внедрение результатов работы. Исследования по теме диссертационной работы выполнялись в соответствии с государственной программой РФ «Информационное общество (2011-2020 годы)», частично поддержаны грантом Российского фонда фундаментальных исследований (проект № 15-07-03141). Результаты диссертации внедрены в процесс проектирования систем поддержки организационного управления в ОАО «ТАТФЛОТ», а также используются в учебном процессе в Волжском государственном

1 Shen, Н. Optimal Scheduling for Satellite Refueling in Circular Orbits [Text] / H. Shen II PhD thesis. School of Aerospace Engineering, Georgia Institute of Technology, Atlanta, Georgia, March 2003.

2 Дозаправка в полете гражданских самолетов: перспективы и проблемы [Электронный ресурс] / ЦАГИ. URL: http://www.tsagi.nl/cgi-bin/jet/viewnews.cgi7id-20101230080777618957 (дата обращения: 21.05.2015).

университете водного транспорта и Московском государственном университете информационных технологий, радиотехники и электроники. Разработанная программа синтеза парето-оптимальных стратегий обслуживания стационарных объектов зарегистрирована в Реестре программ для ЭВМ Федеральной службы по интеллектуальной собственности, патентам и товарным знакам РФ (сведения о практическом использовании приведены в приложениях диссертации).

Апробация работы. Основные результаты диссертации докладывались и обсуждались на следующих научных мероприятиях:

- XIX Международная научно-техническая конференция «Информационные системы и технологии», ИСТ-2013 (г. Нижний Новгород, 2013 г.);

- XVI Всероссийская научно-техническая конференция «Новые информационные технологии» МГУПИ (г. Москва, 2013 г.);

- Международная научно-практическая конференция «Информационные управляющие системы и технологии», ИУСТ-ОДЕССА-2013 (г. Одесса,

2013 г.);

- XII Всероссийское совещание по проблемам управления, ВСПУ-2014 (г. Москва, 2014 г.);

- Научно-практическая конференция «Актуальные проблемы приборостроения, информатики и социально-экономических наук» (г. Москва,

2014 г.);

- 27th Conference of the European Chapter on Combinational Optimization, ECCO XXVII - CO 2014 Joint Conference (г. Мюнхен, 2014);

- Шестая международная научная конференция: Танаевские чтения (г. Минск, 2014 г.);

- XX Международная научно-техническая конференция «Информационные системы и технологии», ИСТ-2014 (г. Нижний Новгород, 2014 г.);

- Международная научно-техническая конференция «Информатика и технологии. Инновационные технологии в промышленности и информатике» (г. Москва, 2015 г.);

- XXI Международная научно-техническая конференция «Информационные системы и технологии», ИСТ-2015 (г. Нижний Новгород, 2015 г.);

- 17-й Международный научно-промышленный форум «Великие реки -2015» (г. Нижний Новгород, 2015).

Публикации. Основные результаты диссертационного исследования отражены в 19 работах, опубликованных соискателем лично или в соавторстве в научных изданиях, в том числе в 3 статьях, представленных в рецензируемых изданиях из перечня ВАК РФ3.

Личный вклад автора. Автору принадлежат содержащиеся в диссертации формулировки теоретических моделей, постановки возникающих в их

3 Позиции 1016, 1340, 1354 Перечня российских рецензируемых научных журналов (http://vak.ed.gov.ru/87)

рамках оптимизационных задач, математическое исследование этих задач, создание решающих алгоритмов, как точных, так и приближенных, а также их программных реализаций.

Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения и пяти приложений. Работа содержит 156 страниц текста, библиографический список включает 126 позиций.

Краткое содержание работы

Во введении излагается общая структура работы, обосновывается актуальность проведенных исследований, формулируется цель работы, раскрывается научная и практическая значимость полученных результатов, аннотировано, по главам, излагается содержание диссертации.

В первой главе (Современное состояние теории расписаний): а) обоснована актуальность исследования новых задач теории расписаний (§ 1.1); б) рассмотрены вопросы вычислительной сложности задач и алгоритмов (§ 1.2); в) представлены некоторые регулярные методы решения задач теории расписаний (§ 1.3); г) изложена технология решения многокритериальных задач оптимизации (§ 1.4); д) описано отличие типовых задач обслуживания объектов перемещающимся процессором от рассматриваемых в диссертационном исследовании (§ 1.5).

Во второй главе (Однокритериальные задачи обслуживания стационарных объектов перемещающимся процессором [4, 5, 7, 9, 12, 13, 17, 18]) выполняется построение ряда моделей обслуживания стационарных объектов перемещающимся процессором, формулируются однокритериальные оптимизационные задачи, излагаются разработанные на основе идеологии динамического программирования алгоритмы синтеза оптимальных стратегий обслуживания. Приводятся примеры вычислений по составленным рекуррентным соотношениям и результаты вычислительных экспериментов.

П. 2.1.1 параграфа 2.1 посвящен описанию математической модели Ш21 обслуживания совокупности стационарных объектов в одномерной рабочей зоне при выполнении процессором двух рейсов - прямого (рейс Л+) и обратного

(рейс Я_). Полагается, что для каждого объекта oj, j = 1,п, указаны величины: т] - требуемая продолжительность обслуживания объекта о] процессором Р; г - ранний срок начала обслуживания объекта о]; (р^) - монотонно возрастающая (в нестрогом смысле) функция индивидуального штрафа, выражающая зависящую от момента завершения обслуживания объекта величину экономических потерь по данному объекту. Также заданы величины у]_11 и у] - затраты времени на перемещения процессора между точками (у -1) и _/ в рейсах и Л_ соответственно, при этом у0, и уи) - затраты времени на перемещение процессора между базовой точкой 0 и объектом о, в прямом и обратном рейсах

соответственно. Все величины ., у] , т] - натуральные числа; г - целые

неотрицательные числа.

Стратегией обслуживания именуется произвольное подмножество элементов р = (/,,/2,...,4) из совокупности индексов N = {1,2,...,и}. Объекты оу., j е р, в реализации стратегии р обслуживаются процессором в рейсе Я+, все остальные объекты группы Оп - в рейсе Л_. Полагается, что объект оп обслуживается при завершении процессором рейса Л+. Множество допустимых для модели стратегий обозначается через 9?).

Считается, что при реализации определяемого стратегией р рейса обслуживание любого объекта , У е N, начинается либо от предписанного раннего срока г1, либо от момента прибытия процессора в точку у (если на момент прибытия объект уже готов к обслуживанию). В случае прибытия процессора в точку у в момент времени ^ < , процессор простаивает в ожидании готовности объекта о к обслуживанию; время ожидания равно (r¡ — ). Завершив

обслуживание, процессор продолжает выполняемый рейс. В качестве критериев выступают:

1) КзР (р) - суммарный по объектам штраф;

2) КтР(р) - максимальный из индивидуальных штрафов.

С позиций повышения эффективности диспетчерского управления обслуживанием совокупности объектов Оп возникают следующие оптимизационные задачи (п. 2.1.2):

Задача Шг^вР). Минимизировать суммарный штраф по всем объектам множества Оп:

(1)

Задача 1Б21(тР). Минимизировать максимальный из индивидуальных штрафов по всем объектам множества Оп:

(2)

Решение поставленных задач выполняется путем их расширения до бикритериальных постановок, где в качестве второго критерия вводится общее время работы процессора на рабочей зоне. Общий алгоритм решения представлен в п. 3.1.2; там же объясняются причины невозможности записи рекуррентных соотношений динамического программирования для исходных однокритериальных задач.

В п. 2.1.3 приводятся доказательства ЛТ'-трудности задач (1) и (2).

П. 2.2.1. в § 2.2 посвящен описанию математической модели \DZ2- Она отличается от модели выполнением процессором только одного рейса -из базовой точки в конечную. При этом определяется, что при необходимости

обслуживание объектов может быть перенесено на более позд-

ний срок. В таком случае их обслуживание реализуется непосредственно после объекта . Иными словами, разрешаются возвратные движения процессора Р на к пунктов назад. Промежуточные простои процессора Р, не связанные с обслуживанием объектов о], _/ = \,п, запрещены.

Дополнительно учитываются величины д1 и - расстояния между смежными точками (_/ -1) и_/; считается, что . = у,. Через ур д обозначаются затраты времени на перемещение процессора от точкир до точки с\\ через й — кратчайшее расстояние от точки р до точки ¡7.

Стратегией здесь именуется последовательность индексов р = (/,,/2,...,/„) из совокупности N = \\,2,....,п}, определяющая порядок обслуживания объектов. Согласно ограничениям на возвратные движения процессора условие допустимости стратегии записывается следующим образом: |/и—и|<&, и = \,п. Множество допустимых для модели Ю22 стратегий обозначается через .

В п. 2.2.2 выполняются постановки следующих однокритериальных оптимизационных задач для модели Ш2г.

Задача Шгг^Р). Минимизировать суммарный штраф по всем объектам множества Оп:

пип{М/>)}- (3)

Задача Ш2г(тР). Минимизировать максимальный из индивидуальных штрафов по всем объектам множества Оп:

В п. 2.2.3 описываются алгоритмы решения задач (3) и (4).

В п. 2.2.4 рассматривается пример синтеза стратегий для задачи Шгг^Р) и приводятся результаты вычислительных экспериментов для задач Ш2г(5Р) и Ш^тР), демонстрирующие временные характеристики работы решающих алгоритмов в зависимости от размерности множества Оп и параметра к.

П. 2.3.1 в § 2.3 посвящен описанию математической модели Ш2з, в которой, в отличие от моделей и УВЪг, процессор выполняет обслуживание объектов без каких-либо ограничений на возможные перемещения между пунктами одномерной рабочей зоны.

Стратегией именуется произвольная перестановка индексов р = (/,,/2,...,/л) из совокупности N = {1,2,....,«}, определяющая порядок обслуживания объектов. Множество допустимых для модели \Т>Тъ стратегий обозначается через Э?з.

В п. 2.3.2 выполняются постановки двух однокритериальных оптимизационных задач для модели Ш2з.

Задача Ш2з(бР). Минимизировать суммарный штраф по всем объектам множества Оп:

(5)

Задача Ш2з(тР). Минимизировать максимальный из индивидуальных штрафов по всем объектам множества Оп:

(6)

Рекуррентные соотношения динамического программирования для задач (5) и (6) записываются в п. 2.3.3. Для записи соотношений, решающих задачу (5), вводится функция определяющая минимальный штраф, получаемый после обслуживания совокупности объектов с индексами из V, а затем объекта оп г г V, при этом в качестве индекса указывается момент времени, в который данный штраф был получен. Соотношения имеют следующий вид:

б({0},/) = «('.,)„. 'о,, = тах(Уо,1<г,) + Г,> ЛГ; (7)

в(У,0 = тш{[е(К \ {у},у) + гЛ = тах(,у + уи,г) + г„ ^

здесь Г соответствует штрафу (?(^\{у},у);

(9)

В п. 2.3.4 рассматривается пример синтеза стратегий для задачи Ш2з(зР); приводятся результаты вычислительных экспериментов для задач Ш23(5Р) и Ш2з(тР).

П. 2.4.1 в § 2.4 посвящен описанию математической модели 2ИХъ обслуживания группы стационарных объектов в двумерной рабочей зоне. Считаются заданными матрицы Г = {/,у} и 5 = размерности (и +1)х (и +1), где у - затраты времени на перемещения процессора между точками /' и у непосредственно, я,. у - расстояние между точками / и у"; здесь у = 00, у = °°, если в графе Б отсутствует ребро (/,у), т.е. для процессора такое перемещение недоступно. В общем случае * , s¡j = лу,. Величины /,., =0 и £,¡=0 для

/ = 0,п. По матрицам Т и 5 однозначно строятся матрицы I7 = {/, и II = где /К1 - затраты времени на перемещение процессора по кратчайшему пути между пунктами / и у, /г - кратчайшее расстояние между г и у. Матрицы ^ и Н получают применением алгоритма Флойда.

Описание стратегии обслуживания аналогично описанию стратегии в модели \Т>2з. Множество допустимых для модели 2Б2з стратегий обозначается через 9?з.

В п. 2.4.2 выполняются постановки двух однокритериальных оптимизационных задач для модели 2Б2з.

Задача 2Б2з(5Р). Минимизировать суммарный штраф по всем объектам множества Оп:

™»?{Мр)}- (10)

Задача 202з(шР). Минимизировать максимальный из индивидуальных штрафов по всем объектам множества Оп:

(п)

Рекуррентные соотношения на основе принципа динамического программирования для задач (10) и (11) записываются в п. 2.4.3.

В п. 2.4.4 приведен иллюстрирующий пример решения задачи 2В2з(зР).

В третьей главе (Многокритериальные задачи обслуживания стационарных объектов перемещающимся процессором [1-6, 8-11, 14-17]) для введенных в главе 2 моделей формулируются и решаются многокритериальные задачи. На основе идеологии динамического программирования в его многокритериальном обобщении разрабатываются алгоритмы синтеза полных совокупностей эффективных оценок; по любой из таких оценок может быть построена порождающая ее парето-оптимальная стратегия. Приводятся примеры вычислений по составленным рекуррентным соотношениям и результаты вычислительных экспериментов.

В п. 3.1.1 § 3.1 для модели \ DZ\ ставится ряд многокритериальных задач. Здесь вводятся два новых критерия оценки качества работы процессора: КТс (р) - момент завершения обслуживания последнего при реализации стратегии объекта, Кт(р) - общее время работы процессора на рабочей зоне. Рассматриваются следующие задачи.

Задача Шг^Т.вР). Найти полную совокупность Е эффективных по Па-рето оценок в бикритериальной проблеме минимизации общего времени работы процессора и величины суммарного штрафа по всем объектам множества^:

(12)

ре-К,

Задача 107|(Т,тР). Найти полную совокупность Е эффективных по Парето оценок в бикритериальной проблеме минимизации общего времени работы процессора и величины максимального из индивидуальных штрафов по всем объектам множества Оп:

тш^гНД^И' (13)

Задача Ш2|(Тс,Т). Найти полную совокупность Е эффективных по Парето оценок в бикритериальной проблеме минимизации момента завершения обслуживания последнего при реализации стратегии объекта и общего времени работы процессора:

(14)

Рекуррентные соотношения динамического программирования для решения задач (12) и (13) выводятся в п. 3.1.2. Для записи соотношений, решающих задачу (12), вводится функция £(£,/) - совокупность эффективных оценок в ситуации, где процессор при реализации рейса Л+ прибывает в точку к в

момент времени t. Соотношения имеют следующий вид:

E(n,t) = {a„, сгл=шах(г,/;) + г„; (15)

A{t,k,p,q) = [p + yMk, ? + % (max (/,/;) +г,)); (16)

P{k,t) = [A{t,k,p,q):(p,q)&E{k + \,p'k)],p'k=mwi{t,rk) + Tk+ykM{-, (17)

B{t,k,p',q') = (<rk, q' + <pk(crj), <7к=тах(р' + умл,гк) + тк; (18)

Q{k,t) = {B{t,k,p\q'):{p\q')eE{k + \yk)}, vk=t + ykM1- (i9)

E(k,t) = eff(p(k,t)uQ(k,t))-, (20)

£ = |* = (дс„л:2):х1 =yi,x2=y2+yl0,raey = (yi,y2)eE(\,y0i)}. (21)

Вычислениям по соотношениям (15)-(21) предваряется сокращающая объем вычислений процедура разметки - определение для каждого значения к, к = \,п, множества 0А возможных значений моментов t прибытия процессора в точку к при реализации рейса Л+:

= К : Mt = max (в, гк) + тк+ укм, в е 0,};

= {»I :vl=e + е0,}; (22)

В п. 3.1.3 для решения задачи (14) вводится новый параметр tr (р) - суммарное время простоев процессора в ожидании наступления ранних сроков /¡, r2,..., г при реализации стратегии р. Задача (14) сводится к минимизации значения данного параметра:

(23)

Для записи рекуррентных соотношений вводятся обозначения: Sj (р') и Сj (/?') - моменты начала и завершения обслуживания каждого из объектов oj при реализации специальной стратегии р' = {1,2,...,«}; F( j) - оценка работы

процессора при условии, что последним обслуживается объект оу. Решающие соотношения динамического программирования следующие:

S, (р') = max(Го1 ,rl),Cl(p') = S, (/>') + г,, (24)

SM {р') = шах (С, (р') + у.м, гм), С,, (/>') = (р') + тм; (25)

= + (26) F(1) = (7I'7l+?'i.o)1» (27)

^МВД+Ы' (28)

E = eff[F{j)j = u\. (29)

В п. 3.1.4 рассматривается два примера решения задач 1DZi(T,sP), lDZi(Tc,T) и приводятся результаты вычислительных экспериментов, демонстрирующие зависимость продолжительности решения и количества эффективных стратегий для задач 1DZi(T,sP), lDZi(T,mP) и 1DZi(Tc,T) от размерности группы Оп. В частности, на рисунках 1 и 2 представлены такие зависимости для задачи lDZi(T,mP), где приняты следующие обозначения: imin, tmg и С« ~~ соответственно минимальное, среднее и максимальное время отработки решающего алгоритма; Emin, Emg и Emax - соответственно минимальное, среднее и максимальное количество эффективных стратегий.

В п. 3.2.1 § 3.2 вводится новый критерий KL[p) - длина пути, пройденного процессором. Для модели 1DZ2 рассматриваются следующие многокритериальные задачи.__

10 12 14 16 18 20 ■»t_ min л. t шах —t_avg

16 14 12 10 8 6 4 '

J

i

> < > '

0

10 12 14 16 18 20 ♦ Е min АЕ шах ®Е avg

Рис. 1. Зависимость продолжительности ра- Рис. 2. Зависимость количества эффектив-боты алгоритма от размерности ных стратегий от размерности

группы Оп для задачи Ш2](Т,тР). группы Оп для задачи Ш2|(Т,тР).

Задача Ш2г(Ь,Т,5Р). Найти полную совокупность Е эффективных по Парето оценок в трехкритериальной проблеме минимизации пройденного процессором расстояния, общего времени работы процессора и величины суммарного штрафа по всем объектам множества Оп:

^{кЛр\кЛР)'кЛР)}- (30)

Задача Ш72(Ь,Т,шР). Найти полную совокупность Е эффективных по Парето оценок в трехкритериальной проблеме минимизации пройденного процессором расстояния, общего времени работы процессора и величины максимального из индивидуальных штрафов по всем объектам множества Оп:

™™{к!.{р)'кт{р)>ктр{р)}- (31)

Задача Ш22(Т,8Р). Найти полную совокупность Е эффективных по Парето оценок в бикритериальной проблеме минимизации общего времени работы процессора и величины суммарного штрафа по всем объектам множества Оп:

™${кЛр)>кАР)}- (32)

Задача Ш72(Т,шР). Найти полную совокупность Е эффективных по Парето оценок в бикритериальной проблеме минимизации общего времени работы процессора и величины максимального из индивидуальных штрафов по всем объектам множества Оп:

^{^(Р).^/0)}- (33)

Для решения задачи (30) в п. 3.2.2 рассмотрена модификация на многокритериальный случай алгоритма, описанного в п. 2.2.3. Там же представлены необходимые модификации данного алгоритма для решения задач (31)-(33).

В п. 3.2.3 приводится пример решения задачи Ш7г(Ь,Т,5Р), а также результаты вычислительных экспериментов, демонстрирующие: а) зависимость продолжительности решения и количества эффективных стратегий для задач п. 3.2.1 от размерности группы Оп; б) среднюю длительность отработки решающего алгоритма в зависимости от параметра к для задач разной размерности (в частности, такие зависимости для задачи 1 БЕгСЦТ^Р) представлены на рисунке 3).

В п. 3.3.1 § 3.3 для модели Ш2з записываются постановки многокритериальных задач.

Задача Ш2з(Ь,Т,зР). Найти полную совокупность Е эффективных по Парето оценок в трехкритериальной проблеме минимизации пройденного процессором расстояния, общего времени работы процессора и величины суммарного штрафа по всем объектам множества Оп:

т1з{КЛр)>Кт{р)>КАр)}- (34)

от параметра к для задачи I ЭггСЦТ.вР) при различных значениях п.

Задача Ш2з(Ь,Т,тР). Найти полную совокупность Е эффективных по Парето оценок в трехкритериальной проблеме минимизации пройденного процессором расстояния, общего времени работы процессора и величины максимального из индивидуальных штрафов по всем объектам множества Оп:

\р)-кЛР)}- (35)

Задача Ш2з(Т,зР). Найти полную совокупность Е эффективных по Парето оценок в бикритериальной проблеме минимизации общего времени работы процессора и величины суммарного штрафа по всем объектам множества Оп:

(36)

Задача Ш2з(Т,тР). Найти полную совокупность Е эффективных по Парето оценок в бикритериальной проблеме минимизации общего времени работы процессора и величины максимального из индивидуальных штрафов по всем объектам множества Оп:

(37)

Рекуррентные соотношения динамического программирования, решающие задачи (34)-(37), выводятся в п. 3.3.2. Для записи соотношений, решающих задачу (34), вводятся обозначения: Е( V, г) - совокупность эффективных оценок в ситуации, где процессор должен обслужить совокупность объектов с индексами из V, а затем объект , / г V; М - множество трехмерных векторов; Ч1 ] .(М) - функция, которая преобразует каждый вектор из Мпо следующему

правилу: + з11,1]1,с + где = шах [Ь + уи, г^ + т,. Решаю-

щие соотношения имеют следующий вид:

£({0},/) = (.?„„/„ «?,(?,)), Г,- = тах(у0,.,/-) + тп геЛГ; (38)

Я(К,/) = еГг|у[^.Д£(К\{у},у))]|; (39)

£ = eff • (40)

lae.V J

В п. 3.3.3 доказываются утверждения о А^Р-трудности всех поставленных в п. 3.3.1 задач.

В п. 3.3.4 рассматривается пример решения задачи 1DZ3(L,T,sP) и приводятся результаты вычислительных экспериментов для многокритериальных задач 1DZ3(T,sP), lDZ3(T,mP), 1DZ3(L,T,sP) и lDZ3(L,T,mP).

В п. 3.4.1 § 3.4 записываются постановки многокритериальных задач для модели 2DZ3.

Задача 2DZ3(L,T,sP). Найти полную совокупность Е эффективных по Парето оценок в трехкритериальной проблеме минимизации пройденного процессором расстояния, общего времени работы процессора и величины суммарного штрафа по всем объектам множества Оп :

mi 4{Kl{P),Kt{p),KsP{P)}- (41)

Задача 2DZ3(L,T,mP). Найти полную совокупность Еэффективных по Парето оценок в трехкритериальной проблеме минимизации пройденного процессором расстояния, общего времени работы процессора и величины максимального из индивидуальных штрафов по всем объектам множества Оп :

min{KL(p),KT(p),KmP(p)}- (42)

Задача 2DZ3(T,sP). Найти полную совокупность Е эффективных по Парето оценок в бикритериальной проблеме минимизации общего времени работы процессора и величины суммарного штрафа по всем объектам множества Оп :

(43)

РЧ'Я,

Задача 2DZ3(T,mP). Найти полную совокупность Е эффективных по Парето оценок в бикритериальной проблеме минимизации общего времени работы процессора и величины максимального из индивидуальных штрафов по всем объектам множества Оп :

тт{Кт(р)ЛтР{р)) - (44)

/?еЛ3

Рекуррентные соотношения на основе принципа динамического программирования для многокритериальных задач (41)-(44) записываются в п. 3.4.2.

В п. 3.4.3 приведен иллюстрирующий пример решения задачи 2DZj(L,T,sP).

В четвертой главе (Алгоритмы синтеза субоптимальных стратегий обслуживания [2, 3, 11, 16]) излагаются построенные на основе идеологии эво-люционно-генетических вычислений процедуры решения задач, сформулированных в рамках моделей 1DZ3 и 2DZ3.

§ 4.1 посвящен вопросу оценивания отклонения квазипаретовского множества оценок Е*, полученного путем использования генетического алго-

д(£,£*) = тах

100, %. (46)

ритма, от паретовского множества оценок Е, полученного в результате использования концепции динамического программирования. При этом полагается, что наборы значений критериев оценки работы процессора представляются как декартовы координаты точек евклидового пространства. Через \ЛВ\ обозначается расстояние между точками А и В (в /и-мерном случае):

\АВ\ = ^(Ь1-а1)2+(Ь2-а2)2+... + (Ьт-ат)2 . (45)

Для записи формул отклонения вводятся следующие обозначения: рп / = 1,|я|, qJ, у = 1,|.Е*| — элементы множеств Е и Е' соответственно, в общем случае |£| ^ |£*|; точка О имеет нулевые координаты; ау§(Я) - операция взятия среднего значения из множества чисел Н. В диссертации отклонение Д определяется следующим образом:

м ,

Существует другой подход к оцениванию отклонения4. Следующая формула является модификацией этого подхода:

'1;(М) '■"»■*■ <47>

I

В вычислительных экспериментах (§ 4.4) используются обе указанные формулы.

В § 4.2 описана обобщенная структура эволюционно-генетического алгоритма (п. 4.2.1) и представлены методы учета условия однократности обслуживания объектов при скрещивании отдельных хромосом из популяции (п. 4.2.2).

В § 4.3 представлены конкретные реализации генетического алгоритма (на основе обобщенной структуры, описанной в § 4.2) для решения однокри-териальных (п. 4.3.1) и многокритериальных (п. 4.3.2) задач в рамках моделей Ю23 п20г3.

В § 4.4 приведена сравнительная характеристика построенных эволюци-онно-генетических алгоритмов и метода динамического программирования. Показана зависимость величин отклонений от ключевых параметров генетических алгоритмов. Результаты экспериментов для задачи Ш2з(Ь,Т,тР) представлены на рисунках 4-6; здесь дополнительно принимаются обозначения: БР - метод динамического программирования; ОА - генетический алгоритм для

4 Дуничкина, H.A. Анализ и алгоритмы решения бикритериальных задач управления обслуживанием стационарных объектов тоЫ!е-процессорами [Текст]: дис. канд. физ.-мат. наук.: 05.13.01 / Дуничкина Надежда Александровна. - Нижний Новгород, 2012 - 163 с.

многокритериальных задач; (1еУтах - максимальное отклонение квазипаретов-ского множества оценок от эффективного множества, вычисляемое по формуле (46); <1еу — среднее отклонение, вычисляемое по формуле (47).

Рис. 4. Зависимость средней длительно- Рис. 5. Зависимость среднего и максималь-сти (с) отработки алгоритмов ОР и вА от ного отклонений (%) от размерности

размерности группы Оп для задачи группы 0„ для задачи Шгз(Ь,Т,шР).

lPZ3(L,T,mP).

9 8 7 6 5

i L i k i A GA_E_avg ♦ DP E avg

J L J L i k

^ 2 1 0 L

10 12 14 16 18 20

Рис. 6. Зависимость среднего количества стратегий, синтезируемых

алгоритмами DP и GA, от размерности группы Оп для задачи lDZ3(L,T,mP).

В пятой главе (Программный комплекс поддержки диспетчерского управления обслуживанием рассредоточенных объектов перемещающимся процессором [19]) приводится обоснование выбора языка программирования Python (§ 5.1), описывается программный комплекс (§ 5.2) синтеза оптимальных и субоптимальных стратегий обслуживания пространственно рассредоточенных стационарных объектов перемещающимся процессором - излагаются его назначение и функциональные возможности (п. 5.2.1), программная архитектура (п. 5.2.2) и типовая схема использования лицом, принимающим решения (п. 5.2.3).

В заключении изложены основные научные и практические результаты диссертационной работы.

Приложения содержат описание условий проведения выполненных вычислительных экспериментов, документы о внедрении результатов диссертационной работы и свидетельство о государственной регистрации программы для ЭВМ.

Основные результаты и выводы

Автором получены следующие научно-технические результаты.

1. Построены обобщенные теоретические модели одностадийного обслуживания группы пространственно рассредоточенных стационарных объектов перемещающимся процессором; в моделях учитываются возможные ограничения на траектории движения процессора, а также предписанные объектам ранние сроки начала обслуживания.

2. В рамках моделей п. 1 сформулированы однокритериальные и многокритериальные задачи синтеза оптимальных стратегий обслуживания.

3. Получены результаты оценки вычислительной сложности двурей-совых однокритериальных и обобщенных многокритериальных задач.

4. Для однокритериальных задач п. 2 на основе идеологии динамического программирования разработаны алгоритмы синтеза оптимальных стратегий обслуживания.

5. Для решения многокритериальных задач п. 2 в условиях концепции Парето применяется принцип динамического программирования в его многокритериальном обобщении, что позволяет строить полные совокупности эффективных оценок с одновременным обеспечением возможности синтеза по любой из таких оценок порождающей её стратегии обслуживания.

6. Для решения задач п. 2 больших размерностей разработаны базирующиеся на концепции эволюционно-генетических вычислений алгоритмы синтеза субоптимальных стратегий обслуживания.

7. Разработан программный комплекс, реализующий синтез оптимальных и субоптимальных решений для полного набора поставленных задач.

Итогом системного анализа изучаемой проблематики и выполненных теоретических исследований является разработка новых моделей и семейства алгоритмов, предназначенных для решения прикладных задач синтеза стратегий обслуживания группы пространственно рассредоточенных стационарных объектов.

Полученные в диссертационной работе результаты отличаются от известных учетом в моделях ранних сроков начала обслуживания и специфических ограничений на допустимые траектории движения процессора, введением в рассмотрение новых критериев оценки качества стратегий (общее время работы процессора, длина пройденного процессором пути, суммарное время простоев процессора), а также рассмотрением в рамках концепции Парето многокритериальных задач с двумя и тремя независимыми критериями, комбинации которых позволяют более точно оценивать состояния транс-портно-технологических систем.

Применение разработанных в диссертации теоретических моделей и решающих алгоритмов, а также созданного на их базе программного комплекса, позволяет повысить эффективность диспетчерского управления обслуживанием систем на внутреннем водном транспорте.

Статьи в рецензируемых изданиях, рекомендованных ВАК

1. Пушкин, A.M. Модель обслуживания стационарных объектов перемещающимся процессором с возможностью возвратов [Текст] / A.M. Пушкин // Научно-технический вестник Поволжья. - № 5. - 2014. - С. 288-292.

2. Пушкин, A.M. Алгоритмы синтеза стратегий в трехкритериаль-ной задаче однопроцессорного обслуживания группировки стационарных объектов [Электронный ресурс] / A.M. Пушкин, Д.И. Коган, Ю.С. Федо-сенко // Инженерный вестник Дона. - 2015. - № 3. - Режим доступа: http://ivdon.ru/ru/magazine/archive/n3y2015/3083.

3. Пушкин, A.M. Обобщенная модель синтеза стратегий обслуживания группы стационарных объектов с возможностью возвратов [Электронный ресурс] / A.M. Пушкин // Интернет-журнал «Науковедение». - Том 7. — № 4. -2015. - Режим доступа: http://naukovedenie.ru/PDF/46TVN415.pdf.

Другие статьи и материалы конференций

4. Дуничкина, H.A. Об одной модели обслуживания стационарных объектов перемещающимся в одномерной рабочей зоне процессором [Текст] / H.A. Дуничкина, Д.И. Коган, A.M. Пушкин, Ю.С. Федосенко // Труды XII Всероссийского совещания по проблемам управления, ИПУ РАН, М., 2014. -С. 5044-5052.

5. Дуничкина, H.A. Модель и синтез стратегий обслуживания стационарных объектов перемещающимся в одномерной зоне процессором [Текст] / H.A. Дуничкина, Д.И. Коган, A.M. Пушкин, Ю.С. Федосенко // Танаевские чтения: доклады Шестой Международной научной конференции (27-28 марта 2014 г., Минск). - Минск: ОИПИ HAH Беларуси, 2014. - С. 44-48.

6. Дуничкина, H.A. Задача обслуживания тоЫ1е-процессором группировки стационарных объектов с учетом сроков их готовности [Текст] / H.A. Дуничкина, Д.И. Коган, A.M. Пушкин, Ю.С. Федосенко // Сборник материалов XX международной научно-технической конференции «Информационные системы и технологии - ИСТ-2014». Нижний Новгород, Нижегородский технический университет им. P.E. Алексеева, 2014. — С. 311-312.

7. Коган, Д.И. Об одной задаче обслуживания стационарных объектов перемещающимся процессором [Текст] / Д.И. Коган, A.M. Пушкин // Новые информационные технологии: Сборник трудов XVI Всероссийской научно-технической конференции (Москва, 17-19 апреля 2013 г.) / Под ред.

B.В. Никонова, А.Г. Шмелевой. - М.: МГУПИ, 2013. - С. 56-59.

8. Коган, Д.И. Информационно-алгоритмическое обеспечение выбора вариантов обслуживания стационарных объектов перемещающимся процессором [Текст] / Д.И. Коган, A.M. Пушкин // Вестник Московского государственного университета приборостроения и информатики. Выпуск №50. Серия «Приборостроение и информационные технологии». - Москва, 2014. -

C. 62-70.

9. Коган, Д.И. Алгоритм синтеза стратегий обслуживания mobile-процессором стационарных объектов в одномерной рабочей зоне [Текст] / Д.И. Коган, A.M. Пушкин, H.A. Дуничкина, Ю.С. Федосенко // Актуальные проблемы приборостроения, информатики и социально-экономических наук. Сборник трудов научно-практической конференции, серия: «Информационные технологии, математическое моделирование». - Москва, 2014. - С. 74-81.

10. Коган, Д.И. Обобщенная задача обслуживания стационарных объектов в одномерной рабочей зоне [Текст] / Д.И. Коган, A.M. Пушкин, Ю.С. Федосенко // Сборник научных трудов: материалы Международной научно-технической конференции «Информатика и технологии. Инновационные технологии в промышленности и информатике» Института высоких технологий МГУПИ. Выпуск I (XXI); под редакцией д.т.н. проф. Кондратенко B.C. -М.: ИВТ МГУПИ, 2015.-С. 127-131.

11. Коган, Д.И. Информационно-алгоритмическое обеспечение синтеза стратегий обслуживания группировки стационарных объектов в одномерной рабочей зоне [Текст] / Д.И. Коган, A.M. Пушкин, Ю.С. Федосенко // Вестник Волжской государственной академии водного транспорта. - Вып. 44. -Н. Новгород: Изд-во ФГБОУ ВО «ВГУВТ», 2015. - С. 116-123.

12. Пушкин, А.М. Информационно-алгор1ггмическое обеспечение простейшей задачи синтеза расписаний обслуживания стационарных объектов [Текст] / A.M. Пушкин // Вестник молодых ученых Московского государственного университета приборостроения и информатики. - Вып. 11. - 2012. - С. 47-52.

13. Пушкин, A.M. Об одной задаче обслуживания перемещаемым процессором системы стационарных объектов [Текст] / A.M. Пушкин // Сборник материалов XIX международной научно-технической конференции «Информационные системы и технологии —ИСТ-2013». Нижний Новгород, Нижегородский технический университет им. P.E. Алексеева, 2013. - С. 319.

14. Пушкин, A.M. Об одной модели обслуживания стационарных объектов перемещающимся процессором [Текст] / A.M. Пушкин // Актуальные проблемы приборостроения, информатики и социально-экономических наук, Сборник трудов научно-практической конференции, серия: «Информационные технологии, математическое моделирование». - Москва, 2014. - С. 98-104.

15. Пушкин, A.M. О моделях и алгоритме синтеза стратегий обслуживания системы стационарных объектов [Текст] / A.M. Пушкин // Труды 17-го международного научно-промышленного форума «Великие реки - 2015». Материалы научно-методической конференции профессорско-преподавательского состава, аспирантов, специалистов и студентов «Проблемы использования и инновационного развития внутренних водных путей в бассейнах великих рек». Том 1. - Н. Новгород: изд-во ФГБОУ ВО «ВГАВТ», 2015. - С. 61-64.

16. Пушкин, A.M. Информационно-алгоритмические средства оптимизации обслуживания производственных точек одномерной рабочей зоны [Текст] / A.M. Пушкин // Сборник материалов XXI международной научно-технической конференции «Информационные системы и технологии —

ИСТ-2015». Нижний Новгород, Нижегородский технический университет им. P.E. Алексеева, 2015. - С. 267-268.

17. Dunichkina, N. Servicing stationary objects in a linear working zone of a mobile processor: scheduling problem in the case of non-zero ready dates [Text] / N. Dunichkina, Yu. Fedosenko, D. Kogan, A. Pushkin // ECCO XXVII -CO 2014 Joint Conference, 27th Conference of the European Chapter on Combinatorial Optimization, Technische Universität München, Department of Mathematics, May lst-3rd, 2014, pp. 60-61.

18. Kogan, D.I. Modified Tanker Maintenance Task for Stationary Objects [Text] / D.I. Kogan, A.M. Pushkin // International scientific-practical Conference «Information Control Systems and Technologies», Odessa, 2013, pp. 88-90.

Свидетельство о регистрации программы для ЭВМ

19. Пушкин, A.M. Программа синтеза Парето-оптимальных стратегий обслуживания пространственно рассредоточенных стационарных объектов с учетом ряда критериев оценки качества работы процессора [Текст] / A.M. Пушкин // Свидетельство о государственной регистрации программы для ЭВМ № 2015619032. Зарегистрировано в реестре программ для ЭВМ Федеральной службы по интеллектуальной собственности, патентам и товарным знакам РФ от 21 августа 2015 г.

Формат 60 х 84 Хб • Гарнитура «Тайме». Ризография. Усл. печ. л. 1,0. Уч.-изд. л. 1,0. Тираж 100 экз. Заказ 169.

Издательско-полиграфический комплекс ФГБОУ ВО «ВГУВТ»

603950, Нижний Новгород, ул. Нестерова, 5