Skip to content
Назад к результатам поиска

Планирование производственных заказов

Автор метода
Pinedo, M. L.
Год
2016
Тип
Combinatorial scheduling problem
Семейство
Optimization

Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском

Размер шрифта

Что он делает?

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

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

Интуиция метода

Представьте себе небольшой механический цех с 10 станками. Заказ клиента (производственный заказ) состоит из 5 деталей, каждая из которых требует последовательности операций на разных станках: Деталь 1 требует механической обработки на станке A, затем сверления на станке C. Деталь 2 требует сверления на станке B, затем сварки на станке D. Все детали сходятся для окончательной сборки. Задача: составить расписание всех операций так, чтобы минимизировать общее время завершения, не превышая пропускную способность станков, соблюдая при этом последовательность операций для каждой детали. Если вы назначите Деталь 1 на станок A слишком поздно, станок C будет простаивать. Если вы перегрузите станок C, все задержится. Задача планирования производственных заказов отражает эту сложность: при 100 заказах и 20 станках количество возможных расписаний астрономическое, что делает точное решение непрактичным. Вместо этого используются эвристики для быстрого поиска хорошего (не обязательно оптимального) расписания.

История

Задача планирования производственных заказов возникла в 1950-х годах как исследовательская проблема в исследовании операций. Фундаментальная работа Джонсона (1954) оптимально решила двухстанковую задачу; Фишер и Томпсон (1963) создали эталонные задачи, которые используются до сих пор. Задача является NP-трудной (доказано в 1970-х годах), что стимулировало разработку эвристик и метаэвристик. Современные подходы включают программирование ограничений (1990-е–2000-е годы), генетические алгоритмы и гибридные методы. Планирование производственных заказов в настоящее время является зрелой областью с приложениями, выходящими за рамки производства, в облачные вычисления, телекоммуникации и транспорт.

Когда применять

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

Ограничения и замечания

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

Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.

Сильные стороны

  • Учитывает сложные, реалистичные ограничения (предшествование, возможности станков, сроки выполнения), которые простые правила планирования не могут учесть
  • Оптимизирует соответствующие бизнес-показатели (время завершения всех работ, опоздание, загрузка станков), а не произвольные правила
  • Обеспечивает быструю реакцию на сбои; алгоритмы перепланирования могут генерировать пересмотренные планы при поломке станка или поступлении срочного заказа
  • Математическая формулировка позволяет проводить анализ чувствительности и исследовать компромиссы (например, опоздание против времени завершения всех работ)
  • Поддерживается эффективными программными инструментами и зрелыми метаэвристическими алгоритмами

Применение

  • Прецизионный механический цех использует планирование производственных заказов с имитацией отжига для составления расписания более 200 нестандартных деталей на 15 станках с ЧПУ, сокращая время завершения всех работ на 15 процентов и повышая своевременность поставок с 85 процентов до 95 процентов
  • Завод по производству полупроводников применяет планирование на основе ограничений для управления более чем 500 этапами процесса на 50 установках, минимизируя время цикла пластин и сокращая незавершенное производство на 20 процентов
  • Типография использует динамическое планирование производственных заказов для назначения печатных заказов на 8 печатных машин с различными возможностями, оптимизируя смешанный ассортимент заказов (высокообъемные против специализированных) и минимизируя время переналадки
  • Команда планирования больницы внедряет алгоритмы планирования производственных заказов для планирования операционных, координируя работу хирургов, хирургических бригад и оборудования, повышая загрузку операционных с 65 процентов до 82 процентов

Как это работает

Как это работает

1

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

2

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

3

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

4

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

5

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

Частые ошибки

  • Оптимизация по неверному показателю; максимизация загрузки станков может увеличить опоздание заказов, в то время как соблюдение всех сроков выполнения может потребовать значительного времени простоя
  • Игнорирование времени переналадки и смены; расписание, минимизирующее время простоя, но требующее частых, трудоемких переналадок, может быть неоптимальным на практике
  • Чрезмерное доверие эвристическим расписаниям без проверки на реальном поведении цеха; ограничения часто сложнее, чем предполагает модель

Часто задаваемые вопросы

Что такое время завершения всех работ (makespan) и почему оно важно?

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

В чем разница между статическим и динамическим планированием производственных заказов?

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

Какое правило приоритетного назначения следует использовать?

Нет единого доминирующего правила. Кратчайшее время обработки (SPT) минимизирует время завершения всех работ; Ближайший срок выполнения (EDD) минимизирует опоздание; Критическое отношение (CR) балансирует оба показателя. Тестируйте правила на исторических данных или симуляции, чтобы найти наилучшее соответствие приоритетам и ограничениям вашего цеха.

Может ли планирование производственных заказов учитывать навыки работников и перекрестное обучение?

Да, путем расширения модели ресурсов: вместо просто 'Станок A' укажите 'Станок A с Работником 1' или 'Станок A с Работником 2'. Однако это увеличивает сложность задачи; убедитесь, что ваше программное обеспечение для планирования поддерживает ограничения на несколько ресурсов.

Похожие методы

Источники

  1. Pinedo, M. L. (2016). Scheduling: Theory, algorithms, and systems (5th ed.). Cham: Springer.

    Открыть ссылку DOI
    Скопировано.
  2. Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2), 278-285.

    Открыть ссылку DOI
    Скопировано.