Распределение бункерных накопителей в производственных линиях с использованием эволюционного моделирования тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат наук Сигаев Вячеслав Сергеевич

• Сигаев Вячеслав Сергеевич
• кандидат наук
• 2019

Оглавление диссертации кандидат наук Сигаев Вячеслав Сергеевич

Введение

Глава 1. Свойства модели производственной линии с

промежуточными бункерными накопителями

1.1 Производственная линия и её математическая модель

1.2 Оценка производительности линии

1.3 Задачи распределения бункерных накопителей

1.4 Вычислительная сложность распределения бункерных накопителей

1.5 Исследование свойств локальных оптимумов

Глава 2. Эволюционные алгоритмы для задачи

распределения бункерных накопителей в

производственной линии

2.1 Эволюционные алгоритмы решения многокритериальной задачи распределения бункерных накопителей

2.1.1 Индикатор гиперобъема и эволюционный алгоритм

на его основе

2.1.2 Модификация эволюционного многокритериального алгоритма

2.1.3 Вычислительный эксперимент

2.2 Эволюционные алгоритмы решения однокритериальной задачи распределения бункерных накопителей

2.2.1 Генетический алгоритм

2.2.2 Алгоритм поиска с запретами

2.2.3 Вычислительный эксперимент

Стр.

2.3 Задача распределения заказов для сети аптек региона

2.3.1 Математическая модель

2.3.2 Генетический алгоритм

2.3.3 Вычислительный эксперимент

Глава 3. Гибридный алгоритм для задачи распределения

бункерных накопителей

3.1 Основные обозначения и предположения

3.2 Гибридный алгоритм

3.2.1 Алгоритм ветвей и границ

3.2.2 Оценка точности алгоритма ветвей и границ

3.3 Вычислительный эксперимент

Глава 4. Комплексы программ

4.1 Библиотека классов Решателя

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

4.3 Комплекс программ для решения задачи распределения заказов для сети аптек региона

Заключение

Список литературы

Список рисунков

Список таблиц

Приложение А. Акты внедрения результатов

диссертационной работы

Введение диссертации (часть автореферата) на тему «Распределение бункерных накопителей в производственных линиях с использованием эволюционного моделирования»

Введение

Диссертация посвящена распределению бункерных накопителей в производственных линиях с использованием эволюционного моделирования. Задача распределения бункерных накопителей возникает при проектировании производственных систем, таких как автоматические линии, гибкие производственные системы или автоматизированные сборочные линии, в которых детали или полуфабрикаты перемещаются от одной единицы оборудования (ЕО) к другой с помощью некоторого транспортного механизма. Наличие бункеров (ёмкостей) для складирования между ЕО позволяет снизить влияние отказов, а также случайных изменений длительности операций, на соседние ЕО и повысить среднюю производительность линии. Однако установка бункеров связана с дополнительными капитальными затратами и увеличением числа складируемых деталей.

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

В задаче распределения бункерных накопителей требуется оптимально распределить объёмы бункеров между единицами оборудования с учетом выбранных критериев эффективности для производственной линии. Базовыми критериями при этом являются: максимизация средней производительности линии в стационарном режиме работы, минимизация капитальных затрат на установку бункерных устройств и стоимости хранения деталей в них.

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

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

Большая часть работ (см., например, [29; 37; 52]) в литературе по задаче распределения бункерных накопителей связана с однокритериаль-ными постановками. В других работах, таких как [28; 36], рассматривалось более одного критерия, но с использованием их взвешенной суммы. Практическая значимость решения задачи распределения бункерных накопителей при проектировании производственных линий продемонстрирована в работах Владзиевского, Мееркова, Долгого, Gershwin, Ancelin, Semeri, Li и др.

см., например, [4; 9; 38; 57]. Существенный экономический эффект от внедрения методов решения таких задач на автозаводах PSA Peugeot Citroën показан в работе Patchong A., Lemoine Т. и Kern G. [61].

Линии без бункеров и линии с неограниченным размером бункеров точно описаны аналитическими моделями. Однако, в случае, если размеры бункеров конечны, оценка производительности линии становится более сложной [20]. Большинство разрешимых аналитических моделей в этом случае разработано только для линий двух или, в некоторых случаях, трех ЕО [34]. Поэтому для моделирования работы таких линий используются методы аппроксимации, основанные на декомпозиции, агрегировании или методы имитационного моделирования. В связи с этим для задачи размещения бункерных накопителей для линий с большим количеством ЕО активно разрабатываются подходы, основанные на эвристических принципах, в частности метод эволюционного моделирования.

Метод эволюционного моделирования основан на использовании упрощенных имитационных моделей эволюционных процессов из живой

природы для построения математических объектов с искомыми свойствами. Такими математическими объектами могут быть модели реальных объектов, максимально приближенные к известному образцу по своим свойствам [2; 27], или новые математические конструкции, обеспечивающие эффективное функционирование тех или иных систем реального мира [14]. Разрабатываемые в рамках данного подхода эволюционные алгоритмы применяются для решения задач машинного обучения, комбинаторной и непрерывной оптимизации в областях анализа данных, проектирования и управления, поддержки принятия решений и др. Намечается и обратный перенос научных знаний из теории эволюционных вычислений в биологию [48]. Инструментами эволюционного моделирования являются генетические алгоритмы, эволюционные стратегии, эволюционное программирование, имитационное моделирование, цепи Маркова и др.

Классический генетический алгоритм предложен J. Holland [53]. В этом алгоритме приспособленность особей к условиям «окружающей среды» выражается некоторой монотонной функцией от значения целевой функции задачи. Чем выше качество допустимого решения, понимаемое как значение целевой функции, тем выше его приспособленность. Популяция развивается за счет отбора родительских особей с помощью оператора пропорциональной селекции и применения к ним случайных операторов, имитирующих мутацию генов и рекомбинацию родительских генотипов (кроссинговер). В различных вариантах генетических алгоритмов используются разные операторы селекции, при этом особи с большим значением приспособленности в среднем получают большее число потомков в следующем поколении.

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

Для достижения указанной цели определены следующие задачи исследования:

1. Исследование моделей производственных линий с промежуточными бункерами.

2. Разработка и анализ эволюционных алгоритмов для задачи распределения бункерных накопителей.

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

Объект исследования процессы распределения бункерных накопителей в производственных линиях.

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

Методология и методы исследования: методы математического моделирования, методы дискретной оптимизации, рандомизированные алгоритмы, методы математической статистики, проведение вычислительного эксперимента, объектно-ориентированное программирование.

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

1. Сложностные и структурные свойства оптимизационных моделей распределения бункерных накопителей в производственных линиях.

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

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

4. Комплекс программ, реализующий алгоритмы эволюционного моделирования для проведения вычислительного эксперимента.

Научная новизна:

1. Установлена вычислительная сложность задачи распределения бункерных накопителей и показано, что множество локальных оптимумов во многих рассмотренных задачах состоит из кластеров, удалённых друг от друга, что не было известно ранее. Обнаружена симметрия множества локальных оптимумов задачи распределения бункерных накопителей в случае приближённого вычисления целевой функции с использованием метода агрегирования линии [12].

2. В отличие от известного ранее алгоритма БЕМО [56], предложенная его модификация для аппроксимации множества Парето задачи распределения бункерных накопителей учитывает кластерную структуру локальных оптимумов задачи и предотвращает локализацию популяции в сравнительно небольшом подмножестве пространства решений.

3. Разработанный генетический алгоритм для задачи распределения бункерных накопителей стал одним из первых эволюционных алгоритмов решения этой задачи [39].

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

Теоретическое значение работы состоит в следующем:

— выявлена кластерная структура множества локальных оптимумов и причины её возникновения;

— для линий простой структуры доказана NP-трудность задачи распределения бункерных накопителей;

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

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

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

Внедрение результатов работы. Результаты диссертационной работы использованы в ОИПИ HAH Беларуси при выполнении работ в международном проекте INTAS 03-51-5501 и совместном проекте БРФФИ и СОРАН «Комбинаторные модели и методы теории расписаний и их приложения в системах поддержки принятия решений», а также внедрены в учебный процесс Омского государственного университета им. Ф.М. Достоевского в составе лекционного курса «Эволюционные алгоритмы».

На основании разработанного генетического алгоритма предложен алгоритм для задачи распределения заказов для сети аптек региона, вошедший в программный комплекс «Центр единого заказа», внедренный на предприятии ООО «Западно-Сибирская фармацевтическая компания».

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

— Международный семинар «Discrete Optimization Methods in Scheduling and Computer-Aided Design» (Беларусь, Минск, 2000);

— Международная конференция «Joint Meeting of IEMS and ICC&IE» (USA, Florida, 2001);

— 12-я Байкальская международная школа-семинар «Методы оптимизации и их приложения» (Россия, Иркутск, 2001);

— Международный семинар «Discrète Optimization Methods in Production and Logistics» (Россия, Омск, 2004);

— Первая международная Азиатская школа-семинар «Проблемы оптимизации сложных систем» (Россия, Новосибирск, 2005);

— III Всероссийская научная молодёжная конференция «Под знаком £» (Россия, Омск, 2005);

— 14-й Всероссийская конференция «Математическое программирование и приложения» (Россия, Екатеринбург, 2011).

— Всероссийская конференция «Проблемы оптимизации и экономические приложения» (Россия, Омск, 2003, 2012, 2015);

— VII Международная конференция «Проблемы оптимизации и их приложения» (Россия, Омск, 2018);

Кроме того, автор неоднократно выступал с докладами на семинарах в Омском филиале Института математики им. С.Л. Соболева СО РАН.

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

Публикации. Основные результаты по теме диссертации изложены в 15 печатных работах, 5 из которых в рецензируемых изданиях, индексируемых Web of Science или Scopns, среди них одна статья в журнале из списка ВАК.

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

Объем и структура работы. Диссертация состоит из введения, четырёх глав, заключения и приложения. Полный объём диссертации составляет 123 страницы, включая 35 рисунков и 37 таблиц. Список литературы содержит 72 наименования.

и

Глава 1. Свойства модели производственной линии с промежуточными бункерными накопителями

В данной главе рассматривается задача распределения бункерных накопителей в производственной линии. Даётся обзор алгоритмов оценки производительности линий. Описаны ранее использованные подходы для решения данной задачи. Представлены доказательства NP-трудно-сти и псевдополииомиальной разрешимости задачи поиска фронта Парето для задачи распределения бункерных накопителей для линий простой структуры. Описан факт симметрии множества локальных оптимумов при использовании алгоритма агрегирования и показана кластеризации локальных оптимумов.

В п. 1.1 рассматривается производственная линия последовательно-параллельной структуры для задачи распределения бункерных накопителей. Описана математическая модель производственной линии.

В п. 1.2 рассматриваются различные оценки производительности некоторых моделей производственных линий. Излагается метод расчета средней производительности линии на основе эвристики агрегирования, предложенный A.B. Долгим [8]. Представлены основные достоинства и недостатки данного подхода.

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

В п. 1.4 представлено доказательство NP-трудности задачи распределения бункерных накопителей.

В п. 1.5 проведено экспериментальное исследование свойств локальных оптимумов задачи распределения бункерных накопителей на основе тезиса «центрального массива».

Результаты первой главы опубликованы в [7; 21; 22; 25; 45; 46].

1.1 Производственная линия и её математическая модель

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

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

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

Структура линии представляет собой ориентированный последовательно-параллельный [19] граф С (см. рисунок 1.1), где вершины Во,... ,Бп+\ отвечают бункерным устройствам, а дуги ЕО\,... ,ЕОт соот-

ветствуют единицам оборудования. Каждая дуга направлена от вершины входного бункера соответствующей ЕО к вершине выходного и возможны кратные дуги, т. е. параллельно работающие ЕО с общими бункерами. Единственная вершина Б0, не имеющая входящих дуг, соответствует входному бункеру линии, а единственная вершина Бте+1 без выходящих дуг -выходному. Каждой вершине Б^ приписано максимальное число вмещаемых деталей Ь^ в бункер ^причем Ь0 = Ьп+1 = то.

Рисунок 1.1: Пример линии последовательно-параллельной структуры.

Любая ЕО может находиться в состояниях «работа», «отказ» (идет восстановление ЕО после её поломки), «блокировка» (невозможно передать обработанную деталь на следующую операцию) и «простой» (отсутствие деталей на входе ЕО). Согласно сделанным выше предположениям, ЕО, связанные с бункером на входе системы, не могут находиться в состоянии «простой», а ЕО, связанные бункером на выходе системы, не могут находиться в состоянии «блокировка».

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

равновероятно (появившаяся деталь загружается на эту ЕО для обработ-

Каждая дуга ЕОг граф а С характеризуется тройкой параметров (Т?, ТР, и г) € [1,го)2 х М, оде N - множество натуральных чисел. Находясь в состоянии «работа», ЕО с номером % имеет постоянное время обработки детали иг € N ^ = 1,...,ш. Отказы и восстановления различных ЕО происходят независимо, и время наработки на отказ, так же как и время восстановления ЕО, имеет экспоненциальное распределение. Для каждой ЕО Т? € [1,го) - среднее время наработки на отказ, а Тг € [1,го) - среднее время восстановления. Если ЕО с номером г исправна, а её входной бункер ] не пуст и бункер ]' на её выходе неполон (т.е. она не находится в состоянии «отказ», «блокировка» или «простой»), то каждые иг единиц времени данная ЕО пополняет бункер ]' одной деталью и извлекает одну деталь из бункера В состояниях «блокировка» и «простой» ЕО не отказывает. В состояниях «отказ», «блокировка» и «простой» ЕО не вносит изменений в заполненность её входного и выходного бункеров. В момент отказа обработка текущей детали прерывается, а после восстановления продолжается до завершения. Время обработки детали после восстановления равно оставшемуся времени обработки в момент отказа.

Производственные линии описанного типа рассматривались в [8; 9; 12; 16; 20; 30; 34; 47] и других работах.

1.2 Оценка производительности линии

При проектировании производственных линий нередко требуется оценить их производительность, и если линии без бункеров и линии с бесконечным размером бункеров точно описаны аналитическими моделями [34], то, в случае, когда бункеры конечны, оценка производительности линии ста-

новится намного более сложной. Большинство разрешимых аналитически моделей в этом случае разработано только для линий двух или, в некоторых случаях, трех ЕО.

Существуют два типа моделей данного класса. Первый предполагает, что количество деталей описывается дискретной величиной (дискретные модели), второй аппроксимирует эту величину некоторой вещественной переменной и предполагает поток деталей непрерывным (дискретно-непрерывные модели). В дискретной модели, предложенной Soyster A.L. и Toof D.I. [64], предполагается, что отказы оборудования подчиняются закону Бернулли, а время восстановления постоянно и равно длительности технологических операций. Дискретная модель с более реалистичными гипотезами впервые предложена Okamnra К. и Yamashina Н. [60]. В данной модели предполагается экспоненциальное распределение времени безотказной работы и восстановления. Получены асимптотические соотношения для такой марковской модели и численный алгоритм их анализа.

Линии с двумя ЕО и конечным бункером между ними, для которых были получены аналитические результаты, можно разделить на три группы [49]:

1) время обработки детали на станке случайная величина и ЕО не выходят из строя. В этой категории большинство публикаций связано с моделями, где время обработки детали имеет экспоненциальное распределение;

2) детерминированное время обработки детали, но случайное по моменту возникновения поломки ЕО. Во второй категории основная часть работ написана для моделей с геометрическим распределением времени восстановления и поломки;

3) время обработки детали и момент возникновения поломки ЕО случайная величина. Предполагается экспоненциальное распределение времени восстановления и поломки.

В работах Gershwin S.В. и Schor J.E. [49] была получена модель для трёх ЕО и двух бункеров между ними. Однако, данные модели слишком сложны для практического использования.

Дискретно-непрерывные модели позволяют получить более простые аналитические решения. Данные модели впервые были предложены Влад-зиевским А.П. и Zimmern В [71]. В работах Владзиевского А.П. использованы следующие допущения:

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

2) моменты случайных отказов образуют простейший поток (простейший поток образуют также моменты восстановлений);

3) текущая величина запаса изделий в бункере условно считается непрерывной;

4) занятость наладчиков устранением отказов на одном станке не изменяет условий обслуживания другого;

5) оба станка не могут одновременно находиться в неработоспособном состоянии;

6) время цикла обработки деталей (длительность операций) для обоих станков одинакова;

7) станок в состоянии простоя не отказывает.

Допущения 5) и 6) являются очень сильными ограничениями, они были сняты в работах Левина А.А., Пасько Н.И. [16] и, позднее, Dubois D., Forestier J.P. [47]. Подобные же исследования проводились Buzacott J.A. [34].

Рассмотрим марковскую модель линии с п промежуточными бункерами и m станками. Состояния в данной модели описываются набором параметров (ai,... ,ат,х1,... ,хп,у1,... ,ут,). Здесь a = 0, если ЕО с номером i находится в состоянии «отказ», и a = 1 иначе. Значение Xj G {0,1,... ,hj} определяет количество деталей в бункере j. Величина

Уг € {0,1,... ,и{} - число единиц времени, уже затраченных на обработку имеющейся детали на ЕО с номером г. Значение у^ равно нулю, если ЕО находится в состоянии «простой». Когда ЕО находится в состоянии «блокировка», значение у{ не меняется и остается равным Ui. Множество всех состояний есть 5 = {0,1}т х П"=1{0,1,... } х П^=1{0,1,...

Рассматриваемая система описывается цепью Маркова М с дискретным временем и множеством состояний Б. С ненулевой вероятностью за иг(т + Ь]) переходов из любого состояния достигается со-

стояние (0,... ,0), в котором все бункеры пусты, в обработке нет ни одной детали и все машины находятся в состоянии «отказ». Из свойств марковских цепей (см., например, [13], гл. V, § 2) вытекает следующее

Предложение 1. Цепь Маркова М имеет стационарное распределение п, к которому сходится распределение вероятностей состояний линии при £ ^ то из любого начального состояния.

Средняя производительность линии в стационарном режиме есть Хл-а-=(ь-ь +1) где суммирование идет по множеству дуг, входящих в

вершину Ьп+1) а - множество состояний системы, в которых а = 1 и Уг = иг.

Опишем упрощенную марковскую модель производственной линии в случае двух последовательных ЕО, предложенную в [47], а также правила агрегирования для пар последовательных и параллельных ЕО, позволяющие использовать эту модель для линий с параллельно-последовательной структурой произвольной сложности.

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

Интенсивность отказов г-й ЕО равна Л^ = 1/Тр, интенсивность восстановления есть щ = 1 /Tf. Скорость обработки дет алей наг-й ЕО обозначим через Ci, Ci = 1/Ut.

Пусть h - это объем бункера между ЕО. Рассматриваются два типа состояний: множество внутренних состояний

Smt = {(аьа2,ж) : 01,02 е {0,1}, х е (0,h)}

и множество граничных состояний

Sfr = {(а1,а2,х) : а1,а2 е {0,1}, х е {0,h}}.

Пусть булевы случайные величины Ai соответствуют значениям а, a вещественная случайная величина X - количеству деталей в бункере. Обозначим вероятности состояний из Sjr в момент t через Раьа2(0,t) := Р{(А1,А2,Х) = (о^о2,0) в момент времени ¿} и Роъо2(h,t) := Р{(А1,А2,Х) = (o1,o2,h) в момент времени t}. Обозначим через Fa' ,а' (ж,£) вероятность того, что в момент времени t случайная величина (А1 ,А2,Х) равна (о1,о2,ж/), где х' < х7 и предположим, что существуют производные fai,a2 (x,t) = dFai,aa (x,t)/dx.

Стационарное распределение марковского процесса, моделирующего рассматриваемую систему, описывается предельными значениями:

Р01,02 (0) = lim Р«^ (0ДРаь(Х2 (h) = lim Р«^ (h,t),

t—TO t—TO

f0-1,02 (x) = lim /01,02 (X,t).

t—>-TO

При этом внутренние состояния связаны системой уравнений Колмогорова [47]

0 = Л1/ю(ж) + Л2/01 (х) - (Щ1 + ^2)foo(x), (1.1)

- С2= Л1/11С-) + V2f00(x) - (щ + Л2)/01(Ж), (1.2)

д f (х)

С1 —10— = Л2У11 (х) + Щ1/0с(ж) - (Л1 + ^2)fw(x), (1.3)

(Ci - C2)Ц1^ = /01(ж) + Ц2/10(ж) - (Al + Л2)/ii(x), (1.4)

а системы уравнений для граничных состояний зависят от соотношения с1 и с2.

Для случая а)с1 < с2:

P0l(h) = Роо(^) = Pn(h) = 0, (1.5)

= Л 2Pn(h) + C1/10(h), (1.6)

М-1^01 (0) = Л1Рп(0) + С2/01(0), (1.7)

(Л1 + Л2- )РП(0) = ^А(0) + (С2 - С1)/п(0), (1.8) С-2

C2Í10(0) = Л2Рц(0), (1.9)

/01(h) = 0. (1.10)

Для случая б)с1 > с2:

Список литературы диссертационного исследования кандидат наук Сигаев Вячеслав Сергеевич, 2019 год

Список литературы

Печатные издания на русском языке

1. Белоус В.В., Грошев C.B., Карпенко А.П., Шибитов И.А. Программные системы для оценки качества Парето-аипроксимации в задаче многокритериальной оптимизации. Обзор // Наука и образование: ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". 2014. № 77. С. 300 320.

2. Вукатова И.Л. Эволюционное моделирование и его приложения. М.: Наука, 1979. 231 с.

3. Вдовин И.В., Сигаев B.C., Рядовой В.Г. DRUGMODULE // ФИПС. 2008. 9 янв. № 2008610028.

4. Владзиевский А.П., Белоусов А.П. Основы автоматизации и механизации технологических процессов в машиностроении. М.: Издателвство «Высшая школа», 1966. 353 с.

5. Гончаров E.H., Кочетов Ю.А. Вероятностный поиск с запретами для дискретных задач безусловной оптимизации // Дискретнвхй анализ и исследование операций. 2002. 9(2). С. 13 30. (2-я сер.)

6. Гэри М., Джонсон Д. Ввхчислителвнвхе машинвх и труднорешаемвхе задачи. М.: Мир, 1982. 416 с.

7. Долгий А.Б., Еремеев. А. В., Сигаев B.C. Анализ задачи многокритериальной оптимизации емкости бункеров в производственной линии // Автомат, и телемех. 2017. Т. 78, ввхп. 7. С. 125 140.

8. Долгий А.Б. Моделирование автоматизированнвхх технологических комплексах с исполвзованнвхх параметризованнвхх сетей Петри // Радиотехнический институт. 1991. Деп. в Бел. НИИНТТИ 9.12.91 №1007-Б91.

9. Долгий А. Б. Система моделей для разработки и исследования автоматизированного производства : диссертация ... кандидата технических наук : 05.13.01 / АН БССР. Ин-т техн. кибернетики / Долгий А.Б. Минск, 1990. 231 с.

10.Долгий А.Б., Ерем,еев A.B., Колоколов A.A., Сигаев B.C. Оптимизация размещения бункерных устройств в автоматических линиях // Труды XII Байкальской международной конференции «Методы оптимизации и их приложения». Т. 1. 2001. С. 138 143.

11. Долгий А.Б., Еремеев A.B., Колоколов A.A., Сигаев B.C. О некоторых эвристических алгоритмах размещения бункерных накопителей // Труды Всероссийской конференции «Проблемы оптимизации и экономические приложения». Омск. С. 85.

12. Долгий А.Б., Свирин Ю.П. Модели оценки вероятностной производительности автоматизированных технологических комплексов // Вести АН Беларуси. 1995. № 1. С. 59 67.

13. Дуб Дж.Л. Вероятностные процессы. М.: ИИЛ, 1956. 609 с.

14. Емельянов В.В., Курейчик В.В., Курейчик В.М. Теория и практика эволюционного моделирования. М.:ФИЗМАТЛИТ, 2003. 431 с.

15. Крамер Г. Математические методы статистики. М.: Мир, 1975. 648 с.

16. Левин A.A., Пасько Н.И. Расчет производительности автоматических линий // Станки и инструмент. 1969. № 8. С. 8 10.

17. Перепелица В.А. Многокритериальные модели и методы для задач дискретной оптимизации на графах. LAP LAMBERT Academic Publication, 2013. 330 с.

18. Сачков В.Н. Введение в комбинаторные методы дискретной математики. М.: Наука, 1982. 384 с.

19. Свами М., Тхуласиралшн К. Графы, сети и алгоритмы. М.: Мир, 1984. 455 с.

20. Севастьянов Б.А. Задача о влиянии емкости бункеров на среднее время простоя автоматической линии станков // Теория вероятностей и ее применения. 1962. Т. 7, № 2. С. 438 447.

21. Сигаев B.C. Исследование свойств локалвнвхх оптимумов задачи размещения буфернвхх накопителей // Трудвх III Всероссийской научной молодежной конференции «Под знаком £». — Омск, 2005. — С. 39^44.

22. Сигаев B.C. О свойствах локалвнвхх оптимумов задачи размещения буфернвхх накопителей // Вестник Омского университета. Омск, 2006. Т. 2. С. 32 34.

23. Сигаев В. С. Задача размещения заказов для сети аптек региона // Трудвх IV Всероссийской конференции «Проблемвх оптимизации и экономические приложения». Омск, 2009. С. 244.

24. Сигаев B.C. Задача размещения заказов для сети аптек региона и ее приближенное решение // Проблемвх информатики. Новосибирск, 2011. 1(9). С. И 19.

25. Сигаев B.C. Анализ многокритериальной задачи размещения буфернвхх накопителей в производственной линии // Трудвх VI Международной конференции «Проблемвх оптимизации и экономические приложения». Омск, 2015. С. 189.

26. Сигаев B.C. Гибриднвхй алгоритм для задачи распределения бун-кернвхх накопителей // ФАП СО РАН. 2019. 29 марта. PR19002.

27. Фогель Л., Оуэне А., Уолш М. Искусственный интеллект и эволюционное моделирование. М.: Мир, 1969. 230 с.

Печатные издания на английском языке

28. Abdul-Kader W. Capacity improvement of an unreliable production line an analytical approach // Comput. Oper. Res. - 2006. Vol. 33. -

P. 1695 - 1712.

29. Altiparmak A., Bugak A., Dengiz B. Optimization of buffer sizes in assembly systems using intelligent techniques // Proceedings of the 2002 Winter Simulation Conference. - 2002. - P. 1157- 1162.

30. Ancelin B., S emery A. Calcul de la productivité d'une ligne integrée de fabrication // RAIRO Automatiq., Productiq. Informatiq. Industrielle. -1987. - Vol. 21. P. 209 - 238.

31. Boese K.D., Kahng A.B., Muddu, S. A new adaptive multi-start technique for combinatorial global optimizations // Oper. Res. Lett. - 1994. Vol. 16, no. 2. - P. 101 - 114.

32. BoMer F. The Multiobjective Shortest Path Problem Is NP-Hard, or Is It? // Evolutionary Multi-Criterion Optimization. - Cham : Springer International Publishing, 2017. - P. 77-87.

33. Brockhoff D., Friedrich T., Neumann F. Analyzing hypervolume indicator based algorithms // Parallel Probl. Solving from Nature - PPSN X: 10th Int. - Berlin, 2008. - Vol. 5199. - P. 651 660.

34. Buzacott J.A., Shanthikwnar J.G. Stochastic Models of Manufacturing Systems. - Prentice Hall, New Jersey, 1993. - 553 p.

35. Coillard P., ProtJi J.M. Effet des stocks tampons dans une fabrication en ligne // Revue belge de Statistique, d'Informatique et de Recherche Opérationnelle. - 1984. Vol. 24 (2). - P. 3 27.

36. Cruz F.R.B., Van Woensel T., Smith .J.M. Buffer and throughput trade-offs in M/G/l/K queuing networks: A bicriteria approach // Int. J. Product. Econom. - 2010. - Vol. 125. P. 224 - 234.

37. D'Souza K., Khator S. System reconfiguration to avoid deadlocks in automated manufacturing systems // Comput. Indust. Engin. - 1997. Vol. 32. - P. 445 -465.

38. Dallery Y., Gershwin S.B. Manufacturing flow line systems: a review of models and analytical results // Queueing Syst. - 1992. - Vol. 12, no. 1/2. -P. 3 - 94.

39. Demir L, Tunali S, Eliiyi D T. The state of the art on buffer allocation problem: A comprehensive survey // Journal of Intelligent Manufacturing. -2014. - Vol. 25(3). P. 371 - 392.

40. Dolgui A., Eremeev A., Kolokolov A., Sigaev V. A Genetic Algorithm for Buffer Allocation in Production Line with Unreliable Machines // Proceedings of the International Workshop «Discrete Optimization Methods in Scheduling and Computer-Aided Design». - Minsk, 2000. - P. 26 - 31.

41. Dolgui A., Eremeev A., Kolokolov A., Sigaev V. Optimization of buffer allocation in production line // Joint Meeting of IEMS and ICC&IE. - Cocoa Beach Florida USA, 2001. P. 534 - 540.

42. Dolgui A., Eremeev A., Kolokolov A., Sigaev V. A genetic algorithm for the allocation of buffer storage capacities in a production line with unreliable machines // Journal of Mathematical Modelling and Algorithms. - 2002. -Vol. 1. P. 89 104.

43. Dolgui A., Eremeev A., Sigaev V. Hybrid Branch and Bound Algorithm for Buffer Space Allocation in Tandem Production Lines // Proceedings of The Second Intenational Workshop «Proceedings of Discrete Optimization Methods in Production and Logistics». - Omsk, 2004. - P. 39 - 44.

44. Dolgui A., Eremeev A.V., Sigaev V.S. HBBA: hybrid algorithm for buffer allocation in tandem production lines // Journal of Intelligent Manufacturing. - 2007. - Vol. 18, no. 3. - P. 411 - 420.

45. Dolgui A.B., Eremeev A.V., Kovalyov M.Y., Sigaev V.S. Complexity of buffer capacity allocation problems for production lines with unreliable machines // Journal of Mathematical Modelling and Algorithms in Operations Research. 2013. - Vol. 12. - R 155 - 165.

46. Dolgui A.B., Eremeev A.V., Kovalyov M.Y., Sigaev V.S. Complexity of bi-objective buffer allocation problem in systems with simple structure // Communications in Computer and Information Science. 2018. - Vol. 871. -P. 278 - 287.

47. Dubois Dn ForestAer J.P. Productive et en-cours moyens d'un ensemble de deux machines separees par une zone de stockage // RAIRO Automatique. -1982. - Vol. 16, no. 12. P. 105 - 132.

48. Eremeev A., Spirov A. Estimates from evolutionary algorithms theory applied to gene design // Proceedings of the 11th International Multiconference "Bioinformatics of Genome Regulation and Structure\Systems Biology", IEEE. - 2018. - P. 33 - 38.

49. Gershwin S.B., Schor J.E. Efficient Algorithms for Buffer Space Allocation. Annals of Operations Research // Annals of Operations Research. -2000. - Vol. 93. P. 117-144.

50. Glasserman P., Yao D. Structured buffer-allocation problems // Discrete Event Dynamic Systems. - 1996. - Jan. Vol. 6, no. 1. - P. 9 - 41.

51. Glover Fn Laguna M. Tabu Search. - Dordrecht: Kluwer Acad. Publ., 1997.

52. Hamada M., Martz H., Berg E., Koehler A. Optimizing the product-based avaibility of a buffered industrial process // Reliabilit. Engin. Syst. Safety. - 2006. - Vol. 91. - P. 1039 - 1048.

53. Holland .J.H. Adaptation in natural and artificial systems. - MIT Press Cambridge, MA, USA, 1992. - 211 p.

54. .Jafari M.A., Shanthikumar J.G. Determination of optimal buffer storage capacities and optimal allocation in multistage automatic transfer lines // HE Transactions. - 1989. - Vol. 21, no. 2. - P. 130 - 135.

55. Kirkpatrick S., Gelatt C.D., Vecchi Optimization by simulated annealing // Science 220. - 1983. - P. 671 - 680.

56. Laumanns M., Thiele L.. Zitzler E., Welzl E., Deb I(. Running time analysis of a multi-objective evolutionary algorithm on a simple discrete optimization problem // Parallel Probl. Solving From Nature. Berlin, 2002. -Vol. 2439. - P. 44 - 53.

57. Li J., Meerkov S. Production Systems Engineering. - Springer US, 2009. - 666 p.

58. Mann H.B., Whitney D.R. On a test of whether one of two random variables is stochastically larger than the other // Annals of Mathematical Statistics. - 1947. - No. 18. P. 50 - 60.

59. Martello S., Toth P. Knapsack Problems : Algorithms and Computer Implementations. - Willey, 1990.

60. Okamura I(, Yamashina H. Analysis of the Effect of Buffer storage Capacity in Transfer Line Systems // ARE Transactions. - 1977. Vol. 9, no. 2. - P. 127- 135.

61. Patchong A., Lemoine T., Kern G. Improving car body production at PSA Peugeot Citroen // Interfaces. 2003. - Vol. 33, no. 1. - P. 36 -49.

62. Reeves C.R. Genetic Algorithms for the Operations Researcher // INFORMS Journal on Computing. - 1997. - Vol. 9, no. 3. - P. 231 - 250.

63. Serafini P. Some Considerations about Computational Complexity for Multi Objective Combinatorial Problems // Recent Advances and Historical Development of Vector Optimization / ed. by J. Jahn, W. Krabs. - Berlin, Heidelberg : Springer Berlin Heidelberg, 1987. P. 222 - 232.

64. S oyster A.L., Toof D.I. Some comparative and design aspects of fixed cycle production systems // Naval Res. Logist. Quart. - 1976. Vol. 23, no. 3. - R 437- 454.

65. Spinellis D., Papadopoulos G. Stochastic algorithms for buffer allocation in reliable production lines // Mathematical Problems in Engineering. -2000. - Vol. 5. - P. 441 - 458.

66. Tempelmeier H. Practical considerations in the optimization of flow production systems // Int. J. Product. Res. - 2003. - Vol. 41, no. 1.

P. 149 - 170.

67. Terracol C., David R. Performance d'une ligne composée de machines et de stocks intermédiaires // RAIRO Automatiq., Productiq. Informatiq. Industrielle. - 1987. - Vol. 21. - P. 239 - 262.

68. Vouros G.A., Papadopoulos H. T. Buffer allocation in unreliable production lines using a knowledge based system // Computers Ops. Res. - 1998. -Vol. 25, no. 12. - P. 883 - 891.

69. Warburton A. Approximation of Pareto optima in multiple-objective shortestpath problems // Operations Research. 1987. - Vol. 35(1). -P. 70 - 79.

70. Yamashita H., Altiok T. Buffer capacity allocation for a desired throughput in production lines // HE Transactions. - 1998. - Vol.30. - P. 883 - 891.

71. Zimmern B. Etudes de la propagation des arrêts aléatoires dans les chaines de production // Review Statististical Applications. - 1956. Vol. 4. P. 85 104.

72. Zitzler E., Brockhoff D., Thiele L. The hypervolume indicator revisited: On the design of Pareto-compliant indicators via weighted integration // Conf. Evolut. Multi-Criter. Optim. (EMO 2007). - Berlin, 2007. - Vol. 4403.

P. 862 - 876.

Список рисунков

1.1 Пример линии последовательно-параллельной структуры. ... 13

1.2 Аппроксимационные марковские модели для двух последователвнвк ЕО для случаев a)ci < с2, б)с\ > С2, в)с\ = с2. 20

1.3 Аппроксимационная марковская моделв для двух параллельных ЕО......................................................20

1.4 Пример работы эвристики агрегирования..........................21

1.5 Схема линии AS7....................................................26

1.6 Схема линии AS8 ....................................................26

1.7 Линия простой структурвх ..........................................30

1.8 Структура локалвнвхх оптимумов задачи анб......................42

1.9 Структура локалвнвхх оптимумов задачи Ьп5.1....................42

1.10 Значения целевой функции на множестве D для задачи t.l . . . 43

2.1 Число найденнвхх точек из F' в процессе работвх алгоритмов. Задача Р0..............................................................50

2.2 Относительная величина хтшеробъема ............................51

2.3 Полученные популяции алгоритмов SEMO и SEMO • для

задачи AS6............................................................52

2.4 Сравнение ГАвг с ГА на задаче ASI..................................70

2.5 Сравнение ГАвг с ГА на задаче AS2..................................70

2.6 Сравнение ГАвг с ГА на задаче AS6..................................70

2.7 Сравнение ГАвг с ГА на задаче AS7..................................71

2.8 Сравнение ГАвг с ГА на задаче AS8..................................71

2.9 Сравнение алгоритмов локальной корректировки решений. ... 73

2.10 Погрешность для различных размеров популяции..................82

2.11 Погрешность для различных размеров турнира....................83

2.12 Погрешность для различных вероятностей кроссинговера. ... 83

2.13 Погрешность для различных вероятностей мутации................84

3.1 Схема гибридного алгоритма........................................87

3.2 Значения величинв1 Яе1 для серий С5 : 20 ... С5 : 55..............95

3.3 Значения величинв1 Де/ для серий W8 : 5 ... W8 : 25..............95

4.1 Входной файл для комплекса программ............................99

4.2 Компонентная архитектура системы электронных торгов. ... 102

4.3 Окно приложения «Бп^МосШе»..................103

4.4 иМЬ диаграмма классов задач......................................105

4.5 ИМЬ диаграмма классов решателя................................106

А.1 Акт внедрения результатов диссертационной работы стр.1 ... 120

А.2 Акт внедрения результатов диссертационной работы стр.2 ... 121

А.З Акт внедрения результатов диссертационной работы в ОмГУ . 122

А. 4 Акт внедрения результатов диссертационной работы в Б ГУ . . 123

Список таблиц

1 Список серий..........................................................25

2 Параметры задачи ASI..............................................26

3 Параметры задач AS2 и AS6........................................27

4 Параметры задач AS7 и AS8........................................27

5 Параметры задач BN5.1 и BN5.2....................................28

6 Параметры задач BN5.3 и BN5.4....................................28

7 Параметры задач BN5.5 и BN5.6....................................28

8 Параметры задач BN5.7 и BN5.8....................................28

9 Параметры задач BN5.9 и ВN5.10..................................29

10 Параметры задач VP6.9 и VP6.10..................................29

11 Параметры задач VP7.9 и VP7.10..................................29

12 Результаты многократного запуска локального поиска для

серии as. 1 - as.6........................................................39

13 Результаты многократного запуска локального поиска для

серии vp6.9 - vp6.10..................................................39

14 Результаты многократного запуска локального поиска для

серии vp7.9 - vp7.10..................................................39

15 Результаты многократного запуска локального поиска для

серии Ьп5.1 - Ьп5.10..................................................40

16 Результаты вычислений корреляций для серий as и vp6..........40

17 Результаты вычислений корреляций для серий Ьп и vp7 .... 41

18 Размерности задач и число вычисленных пробных решений за

1 час....................................................................51

19 Аппроксимация множества Парето задачи ASI....................54

20 Аппроксимация множества Парето задачи AS2....................55

21 Аппроксимация множества Парето задачи AS7....................55

22 Аппроксимация множества Парето задачи AS6....................56

23 Аппроксимация множества Парето задачи AS8....................56

24 Результаты экспериментов ГА и ГАЖ для серии as.l-as.8 .... 69

25 Результаты экспериментов ГАпп и ГАвг для серии as.l-as.8 ... 69

26 Результаты экспериментов ГА и ГАпп для серии bn5.l-bn5.10 . . 72

27 Результаты экспериментов ГАЖ и ГАвг для серии bn5.l-bn5.10 . 72

28 Результаты экспериментов ГА и ГАЖ для серии vp6.9-vp6.10 . . 72

29 Результаты экспериментов ГАвг и ГАпп для серии vp6.9-vp6.10 . 73

30 Результаты экспериментов ГА и ГАЖ для серии vp7.9-vp7.10 . . 73

31 Результаты экспериментов ГАвг и ГАпп для серии vp7.9-vp7.10 . 73

32 Сгенерированные серии задач........................................91

33 Время работы алгоритма полного перебора и гибридного .... 93

34 Список абстрактных классов..........................................97

35 Список базовых классов..............................................98

36 Список классов для решения задачи распределения бункерных накопителей ..........................................................98

37 Список классов для решения задачи распределения заявок для сети аптек..............................................................101

Приложение А Акты внедрения результатов диссертационной работы

«Утверждаю» директор ООО «ЗападноСибирская фармацевтическая

ания» И.В. Вдовин

АКТ

ВНЕДРЕНИЯ РЕЗУЛЬТАТОВ ДИССЕРТАЦИОННОЙ РАБОТЫ

Сигаева Вячеслава Сергеевича

нэ предприятии ООО «Западно-Сибирская фармацевтическая компания» (ООО «ЗапСибфарм»)

Настоящий акт составлен комиссией в составе директора ООО «ЗапСибфарм» Вдовин а И. В. и заместителя директора Бружеса ВВ. в том, что на вышеназванном предприятии была осуществлена производственная апробация разработанного Сигаевым Вячеславом Сергеевичем программного комплекса при консультации к ф. - м.н Еремеева A.B.

Указанный комплекс «Центр единого заказа» является частью программного обеспечения по автоматизации предприятия и позволяет эффективно распределять заказы отдельных центральных районных аптек Омской области и их филиалов между несколькими оптовыми поставщиками в соответствии с требованиями обеих сторон. Основным назначением ПО «Центр единого заказа» является проведение электронных торгов. Внедрение комплекса, разработанного Сигаевым B.C., помимо основной задачи распределения заказов, Рисунок А.1: Акт внедрения результатов диссертационной работы стр.1

обеспечило их выполнение в поставленные сроки.

Результаты диссертационной работы приняты к внедрению на предприятии ООО «Западно-Сибирская фармацевтическая компания» г. Омска.

Комиссия считает что предлагаемая Сигаевым В С система для распределения заказов может быть использована на предприятиях подобного типа.

Представители комиссии:

Рисунок А.2: Акт внедрения результатов диссертационной работы стр.2

Вдовин И.В,

Бружес В.В.

О?.

Рисунок А.З: Акт внедрения результатов диссертационной работы в

ОмГУ

УТВЕРЖДАЮ

Генеральный директор ОИПИ HAH Беларуси, ч л.-корр. IJ£H Беларуси

А.В.Тузиков

«

0» 2019 г.

АКТ

о внедрении результатов диссертационного нсследовавня B.C. Сигаева «Распределение бункераых накопителей в производственных линиях с использованием эволюционного моделирования»

Настоящий акт подтверждает внедрение результатов диссертационной

работы Сигаева Вячеслава Сергеевича «Распределение бункерных

накопителен в производственных линиях с использованием эволюционного

моделирования>>, выполненной в Омском филиале Института математики

им. С.Л. Соболева СО РАН (Омск, Россия) и представлен и ой на соискание

ученой степени кандидата технических наук по специальности 05 13 L8

«Математическое Моделирование, численные методы и комплексы программ».

Полученные в указанной работе сложностные свойства оптимизационных моделей распределения бункерных накопителей в производственных линиях и эволюционные алгоритмы оптимизации объемов бункерных накопителей использованы в Объединенном институте проблем информатики Национальной академии наук Беларуси (ОИПИ HAH Беларуси) при выполнении следующих работ:

* международный проект INTAS 03-51-5501 (2004-2006); - совместный проект Белорусскою республиканского фонда фундаментальных исследований и Сибирского отделения Российской академии наук «Комбинаторные модели н методы теории расписаний и их приложения в системах поддержки принятия решений» (2015-2017}- подготовка аспирантов по специальности 05.13.18 - «Математическое моделирование, численные методы и комплексы программ»

Заместитель генерального директора

по научной работе, чл.чюрр ^

HAH Беларуси . ^ МЛ. Ковалев

Рисунок А.4: Акт внедрения результатов диссертационной работы в БГУ