Сравнительный анализ эвристических методов планирования потока

Введение в расписание Flow Shop

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

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

Общие эвристические методы

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

Правила приоритетного отвода

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

Правила приоритета чрезвычайно быстры (]O(n log n) и просты в реализации, что делает их пригодными для планирования в реальном времени.Однако они редко вырабатывают оптимальные решения и могут плохо работать на больших или сложных экземплярах.

Ближайший сосед (NEH)

Эвристика NEH (Nawaz, Enscore, & Ham) является одним из наиболее эффективных конструктивных методов минимизации расхода. Она работает в два этапа:

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

Сила NEH заключается в его способности быстро генерировать высококачественные решения. Он часто используется в качестве эталона и отправной точки для эвристики улучшения. Сложность - это O 3 ] для m машин и n рабочих мест, но она может быть ускорена с использованием структур данных. Существуют многочисленные варианты, такие как NEH с правилами тай-брейка (например, предпочтение рабочих мест с меньшим временем простоя).

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

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

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

Имитируемое отжиг (SA)

Имитируемое отжигание имитирует физический процесс отжига, где материал нагревается, а затем медленно охлаждается для уменьшения дефектов. В планировании SA начинает с исходного раствора (часто от NEH) и итеративно генерирует соседний раствор с помощью небольших возмущений (например, своп или вставка). Новое решение всегда принимается, если оно улучшает размазывающее усилие; в противном случае оно может быть принято с вероятностью, которая зависит от температурного параметра и величины ухудшения. Температура уменьшается с течением времени в соответствии с графиком охлаждения (например, геометрическое охлаждение: ]T T 0 * α k .

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

Поиск Табу (TS)

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

TS предлагает хороший баланс между разведкой и эксплуатацией. Он часто производит высококачественные решения с умеренным вычислительным временем. Варианты включают реактивный поиск табу (динамическая корректировка размера списка табу) и гибридный TS с другими эвристиками. Простая реализация TS для магазина потоков обычно использует своп или вставки ходов и срок службы табу 10-20 итераций.

Другие эвристические методы

Помимо классики, для планирования потоковых магазинов было разработано несколько других эвристик:

  • Оптимизация колонии муравьев (ACO): Модели кормового поведения муравьев. Искусственные муравьи строят решения путем вероятностного выбора последовательности заданий на основе феромонных следов и эвристической информации (например, времени обработки). Феромоны обновляются для усиления хороших решений.
  • Оптимизация теплоты частиц (PSO): Использует популяцию частиц, которые перемещаются через пространство решения, регулируя свои позиции на основе личных и глобальных лучших позиций.Хотя изначально для непрерывных задач существуют дискретные варианты для планирования перестановок.
  • Итерированный локальный поиск (ILS): Применяет локальный поиск (например, самый крутой спуск) от стартового решения, затем возмущает локальный оптимум для создания новой отправной точки, повторяясь несколько раз.
  • Переменный поиск по соседству (VNS): Систематически меняет структуры окрестностей во время поиска, чтобы избежать локального оптимума.

Сравнительный анализ

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

Качество решения

Приоритетные правила и простая конструктивная эвристика обычно достигают пробелов в 10-20% выше оптимального или наиболее известного решения. NEH работает намного лучше, часто в пределах 3-5% от оптимального. Метаэвристика (GA, SA, TS) может достигать пробелов 0-1% при достаточном времени выполнения. Среди метаэвристики TS и гибридные GA, как правило, более последовательны в разных размерах проблемы, в то время как SA может потребовать тщательной настройки, чтобы соответствовать их производительности. ACO и PSO также могут достигать конкурентных результатов, но менее установлены, чем более традиционные подходы.

вычислительное время

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

хладнокровие

Надежность относится к согласованности качества решения в различных экземплярах проблемы. NEH очень надежен для минимизации пространства. GA и SA могут быть чувствительны к параметрам; плохо настроенный GA может преждевременно сходиться или не исследовать. Производительность TS менее чувствительна к параметрам, чем SA, хотя размер списка табу имеет значение. Гибридная эвристика, которая сочетает в себе конструктивное (NEH) с улучшением (TS или SA), как правило, наиболее надежна.

Метрики производительности

При оценке эвристики используется несколько метрик:

  • Makespan (Cmax]: Общее время от начала первой работы до завершения последней работы на последней машине.
  • Общее время выполнения работ : Сумма времени выполнения всех работ. Минимизация времени выполнения работ сокращает количество рабочих мест.
  • Максимальная задержка : Наихудший случай задержки относительно сроков, часто используемый в клиентоориентированных средах.
  • Количество рабочих мест Тарди : Количество рабочих мест, которые заканчиваются после их срока годности.
  • Время простоя: Общее время простоя машины; минимизация его увеличивает использование машины.

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

Гибридные подходы и последние достижения

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

  • NEH + Локальный поиск: Используйте NEH для создания хорошего исходного решения, а затем применяйте смоделированный отжиг или поиск в табу для улучшения.
  • Генетический алгоритм + локальный поиск (Меметический алгоритм): Применяйте локальный поиск к каждому потомству перед вводом в популяцию, обеспечивая хорошую конвергенцию.
  • Адаптивный контроль параметров : Настройка параметров GA или SA во время выполнения на основе поведения поиска (например, повторное отжиг температуры, адаптивные скорости мутаций).
  • Интеграция машинного обучения: Модели регрессии поездов или агенты обучения подкрепления для прогнозирования хороших ходов или выбора эвристики динамически. Например, использование нейронных сетей для руководства позициями вставки в конструктивной эвристике.

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

Выбор правильной эвристики

Выбор эвристики для планирования потока зависит от нескольких практических факторов:

  • Размер и сложность задачи: Для малых и средних экземпляров (10–50 рабочих мест, до 20 машин) точные методы могут быть осуществимы, но если нет, NEH или простая метаэвристика, такая как TS, хорошо работают.
  • Требования к качеству раствора: Если практически оптимальные решения являются обязательными (например, при производстве с высокой пропускной способностью), то оправдан гибридный GA или TS с более длительным временем выполнения.
  • Доступные вычислительные ресурсы: Облачные вычисления или мощные рабочие станции позволяют использовать более вычислительно интенсивные методы, такие как GA с большой популяцией.
  • Усилия по внедрению : Правила приоритета и NEH тривиальны для кодирования. SA и TS требуют умеренных усилий; GA более сложна, но хорошо документирована. ACO и PSO требуют дополнительных вариантов дизайна для дискретных проблем.
  • Динамические среды: Некоторые производственные системы сталкиваются с новыми рабочими местами, прибывающими с течением времени (онлайн-планирование). Простые правила отправки предпочтительны в таких настройках из-за их скорости и адаптивности.

Многие исследователи используют бенчмаркинг для сравнения производительности Taillard flow shop benchmark или OR-Library instances.

Заключение

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

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

Для дальнейшего чтения см. всеобъемлющий обзор по Framinan et al. (2015) по эвристике планирования потока магазинов и классический текст по Pinedo (2016) по теории планирования и алгоритмам.