Многообъективные методы оптимизации в задачах планирования потока

Введение в планирование потокового магазина и многоцелевую оптимизацию

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

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

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

Понимание многообъективной оптимизации в расписании магазинов

В типичном магазине с переменным потоком рабочих мест n рабочие места обрабатываются на m машинах в той же последовательности. Переменная принятия решения - это порядок рабочих мест, который определяет ключевые показатели эффективности (KPI). Общие цели включают:

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

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

Общие методы многообъективной оптимизации

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

Генетические алгоритмы (GAs)

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

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

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

Многообъективная оптимизация теплоты частиц (MOPSO)

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

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

Типичное приложение MOPSO для 50-рабочего 10-машинного бизнес-кейса позволило улучшить охват фронта Парето на 15% по сравнению со стандартным GA, как сообщалось в исследовании 2010 года по PSO в расписании магазинов потоков .

Недоминируемый сортирующий генетический алгоритм II (NSGA-II)

NSGA-II, возможно, является самым популярным многообъективным эволюционным алгоритмом для планирования потокового цеха. Разработанный Deb et al., он использует два основных механизма: не доминируемая сортировка для ранжирования решений по фронтам и расстояние скученности для поддержания разнообразия в каждом фронте. Алгоритм является быстрым (O(MN]2) сложность для целей M и N решений), элитарным и широко проверенным.

Для проблем с магазином потоков NSGA-II легко адаптируется: хромосома является перестановкой, и операторы кроссовера, такие как кроссовер заказа или одноточечный кроссовер, работают хорошо. Алгоритм превосходит в создании хорошо распределенных фронтов Парето даже в проблемах со многими локальными оптимами. В всестороннем исследовании 120 контрольных экземпляров NSGA-II последовательно превосходил другие метаэвристики (SPEA2, MOPSO) с точки зрения гиперобъема и инвертированных метрик расстояния поколений (IGD) для двухобъективных (макеспена и общего времени потока) проблем магазина потоков.

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

Эволюционные стратегии (ES)

Эволюционные стратегии отличаются от ГА тем, что они подчеркивают мутацию и самоадаптацию параметров стратегии (например, размеров шагов), а не рекомбинацию. В многообъективной ЭС популяция часто мала, а отбор основан на недоминировании. Элитная стратегия (μ+λ) распространена, где родители μ производят λ потомство, а лучшие μ особи среди объединенного пула доживают до следующего поколения.

Для планирования потока магазина ES может быть эффективным, когда ландшафт прочный и традиционный кроссовер производит много неосуществимых или низкокачественных перестановок. Самоадаптация вероятностей мутаций позволяет алгоритму сбалансировать исследование и эксплуатацию без ручной настройки. Недавние работы показали, что стратегия адаптации многообъективной ковариационной матрицы (MO-CMA-ES) превосходит NSGA-II по некоторым проблемам с высокой размерностью потока магазина со сложными фронтами Парето, хотя и при более высокой вычислительной стоимости (] см. Igel et al., 2009 . Однако методы ES не были так широко приняты в сообществе планирования потока магазина, как методы на основе GA, в первую очередь из-за успеха NSGA-II и относительной простоты реализаций GA.

Заявка в Flow Shop Scheduling

Для решения конфликтов в области планирования были использованы методы многоцелевой оптимизации в различных промышленных и сервисных контекстах. Ниже приведены заметные области применения с конкретными примерами.

Производство: минимизация времени на растяжение и полный поток

В сборочном цехе печатной платы среднего размера (PCB) производственный процесс включает до восьми последовательных станций: применение припоя, выбор и место, перелив, проверка и тестирование. Рабочие места (различные типы печатных плат) обрабатываются в одном порядке через все станции - классический магазин потока перестановок. Управление направлено на сокращение как размаха (для удовлетворения плотных окон доставки), так и общего времени потока (для снижения запасов процесса). Используя NSGA-II, команда планирования создала фронт Парето из 50 не доминирующих графиков. Один график выбытия сократил размах на 8%, но увеличил время потока на 12%; другой балансировал оба до 3% от наилучшего достижимого. Объект принял график, который придал равный вес обеим целям, что привело к сокращению общего времени производства на 6% и сокращению затрат на хранение запасов на 10%.

Логистика: Расписание грузовиков в кросс-доках

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

Здравоохранение: хирургическое планирование с несколькими критериями

В государственной больнице планирование выборных операций в нескольких операционных (машинах) может быть смоделировано как магазин потоков, где операции (работы) должны проходить через предоперационную подготовку, саму операцию и восстановление. Цели включают минимизацию самого длительного времени ожидания пациента (суррогат для удовлетворения пациента) и минимизацию сверхурочных для хирургического персонала. Модифицированный NSGA-II произвел более 200 не доминируемых графиков. Администрация больницы выбрала тот, который сократил среднее время ожидания на 22% и сверхурочные на 30% по сравнению с ручным графиком, используемым ранее. Этот случай демонстрирует прямое влияние многообъективной оптимизации в обслуживании операций.

Проблемы и будущие направления

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

Вычислительная сложность и масштабируемость

Проблемы с потоком трудно найти более чем на двух машинах, даже для однообъективных случаев. Когда добавляется множество целей, вычислительная нагрузка значительно увеличивается. Точные методы, такие как ветвь и связь, могут решать только очень маленькие экземпляры (до 15 рабочих мест и 5 машин) из-за факториального роста числа возможных перестановок. Метаэвристика должна приблизиться к передней части, но для больших задач (например, 100 рабочих мест, 20 машин) пространство поиска становится огромным — 10 [FLT: 0] 158 [FLT: 1] возможные последовательности. Даже быстрый алгоритм, такой как NSGA-II, может потребовать десятков тысяч оценок, чтобы получить хорошо конвергентный фронт, который может быть непомерным, когда каждая оценка является симуляцией или вытягиванием данных в реальном времени.

Масштабируемые решения

Качество первоначальных решений и ограничений

Многие алгоритмы начинаются со случайных популяций решений, теряя ранние итерации на плохих графиках. Холодный запуск с эвристическими решениями (например, NEH для Makespan, EDD для сроков) может обеспечить фору. Однако эвристическая инициализация может смещать население в определенные области объективного пространства, ограничивая разнообразие. Гибридный подход, который засевает часть первоначальной популяции с эвристическими решениями, а остальные со случайными часто дают лучшие результаты.

Динамическое и неопределенное управление

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

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

Ни один метаэвристический подход не доминирует во всех случаях проблем. Гибридные подходы, которые сочетают глобальный поиск (например, NSGA-II) с локальным поиском (например, смоделированный отжиг или поиск в табу), часто производят превосходные фронты Парето. Например, гибридный NSGA-II с технологией поиска вариабельных окрестностей, как было показано, улучшает как конвергенцию, так и разнообразие на 20% в бенчмарках магазинов потоков. Аналогично, сочетание оптимизации роя частиц с оператором кроссовера генетического алгоритма может смягчить застой. Эти гибриды находятся на переднем крае текущих исследований, с прицелом на автоматизированный выбор алгоритма на основе характеристик проблемы.

Интеграция машинного обучения

Захватывающим рубежом является использование машинного обучения для руководства процессом поиска. Усиление обучения может обучать агентов динамически выбирать кроссовер или операторов мутаций. Генеративные состязательные сети (GAN) могут, в принципе, генерировать многообещающие отправные точки для фронта Парето. Суррогатное моделирование, как упоминалось, может ускорить оценки. Кроме того, настройка параметров на основе обучения (например, использование байесовской оптимизации для определения размера популяции, скорости мутации и т. Д.) становится все более распространенным. Исследование 2021 года показало, что машинное обучение, управляемое NSGA-II, сократило вычислительное время на 50% на экземпляре магазина потока 50 рабочих мест при сохранении качества фронта.

Реализация многоцелевой оптимизации на практике

Для практикующих, желающих принять эти методы, процесс обычно включает в себя несколько этапов:

  1. Определение целей и ограничений: Привлечение заинтересованных сторон (менеджеров по производству, логистических планировщиков и т.д.) для установления KPI и приемлемых диапазонов компромиссов.
  2. Выберите алгоритм: NSGA-II является сильным по умолчанию для до четырех целей; MOPSO может быть выбрана, если вычислительный бюджет ограничен; гибридный или MOEA / D для более крупных задач.
  3. Кодирование решения: Кодирование перестановок является стандартным для магазинов потоков, но необходимо соблюдать осторожность при кроссовере и мутации, чтобы обеспечить осуществимость.
  4. Создайте и проверьте фронт Парето: Запустите алгоритм, визуализируйте результаты (например, с параллельными координатами или тепловыми картами) и представьте лицам, принимающим решения.
  5. Выберите окончательный график: Используйте инструменты для принятия решений с несколькими критериями (например, TOPSIS, взвешенная сумма) для выбора одного решения спереди.
  6. Мониторинг и настройка: По мере изменения условий перезапустите оптимизацию или используйте динамическую версию алгоритма.

Коммерческое программное обеспечение (например, OptaPlanner, Gurobi с многообъективными расширениями) и библиотеки с открытым исходным кодом (pymoo, DEAP) могут ускорить реализацию. Выбор между пользовательским кодом и готовыми решениями зависит от размера проблемы и требуемой гибкости.

Заключение

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