Проблемы с расписанием 101

автор Адам Кехо

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

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

(Или нет, но надеюсь, что это так.)

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

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

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

Причина появления этой области исследований (похоже, как и многих других исследований операций) в том, что даже простейшие задачи планирования допускают большое количество возможных решений. Задача планирования, в которой одна машина обрабатывает 10 заданий, содержит 10! (или около 3,6 миллиона) возможных заказов на работу. Даже в этих очень простых случаях перечисление часто не удается, а это означает, что в любой практической ситуации необходимо использовать альтернативные методы. (Вы можете узнать больше о проблемах перечисления в исследовании операций в нашей статье Opex 101 о проблемах маршрутизации транспортных средств.)

Как и любая другая проблема OR, формулировка задачи планирования включает в себя постановку цели. Это может отличаться в зависимости от приоритетов бизнеса или организации. Обычно целью является минимизация затрат, но «стоимость» в контексте планирования обычно является некоторой мерой, связанной со временем. (Однако конкретная минимизируемая метрика может отличаться.)

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

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

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

Один из вариантов - сформулировать это как программу со смешанными целыми числами:

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

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

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

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

Если вы хотите, чтобы мы затронули тему в рамках Opex 101 , сообщите нам об этом в комментариях ниже!

_________________________________________________________________

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