Эвристика смещения узких мест - Shifting bottleneck heuristic

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

Использует

Последовательность машин и пример времени обработки

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

Процедура

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

Первый график

Исходный рисунок

Первый шаг - нарисовать ограничения приоритета в графической форме, называемой графиком (см. Рисунок исходного чертежа). Каждое задание начинается с «источника», который мы обозначим на графике буквой U. Каждое задание завершится «стоком» заданий, который мы обозначим на графике буквой V. Каждая строка узлов в графе представляет собой задание. Каждый узел на графике представляет задачу, которая является частью задания, второе число подтверждает выполняемое задание, а первое число указывает, какая машина используется для этой задачи. На этом этапе начальное время выполнения каждого задания должно быть рассчитано путем сложения времени обработки, которое задание занимает на каждой из машин (или строк). После того, как время выполнения каждого задания было рассчитано, время изготовления системы определяется на основе самого длительного времени выполнения любого отдельного задания. Это предполагает отсутствие конфликтов ресурсов и дает время изготовления 22.

Первая итерация

Машина 1

Итерация 1

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

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

Вторая итерация

Итерация 2

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

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

Дальнейшие итерации

Итерация 3

Этот процесс повторяется до тех пор, пока не будут учтены все машины или пока максимальная задержка не станет равна нулю на всех соответствующих оставшихся машинах. Каждый раз, когда процесс повторяется, он считается итерацией, и все дизъюнктивные ограничения могут быть нанесены на схему работы и машины. В нашем примере следующая итерация предоставила нам нулевое значение максимальной задержки на машинах 3 и 4, поэтому их оптимальные последовательности могут быть включены в чертеж (см. Итерацию 3).

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

Смотрите также

внешняя ссылка

Процедура смещения узких мест для мастерских с параллельными станками