Правило Джонсона: порядок работ на двух станках

Правило Джонсона помогает найти очередность работ, при которой вся партия проходит два станка за минимальное общее время. Каждая работа сначала выполняется на первом станке, затем на втором; продолжительность операций известна. В интерактивном примере ниже можно изменить время одной работы и увидеть, как перестраиваются очередь и интервалы на станках. Затем разберём алгоритм, расчёт и границы его применения.
Какую задачу решает правило Джонсона
Представим участок, где детали сначала обрабатывают на станке 1, а потом на станке 2. Каждый станок в один момент занят не более чем одной деталью. Пока вторая деталь обрабатывается на первом станке, первая уже может находиться на втором. Поэтому складывать все времена операций подряд нельзя: часть работ идёт параллельно.
Цель - минимизировать общее время завершения партии : промежуток от начала расписания в момент ноль до окончания последней работы на втором станке. Это показатель всего набора заказов, а не среднее время ожидания отдельной детали и не сумма сроков их завершения.
С. М. Джонсон описал решение этой задачи в работе 1954 года. Правило относится к теории расписаний: оно выбирает порядок операций при ограниченных ресурсах. Сходная идея зависимости задач встречается в сетевом планировании, хотя там исследуют сеть предшествований и критический путь, а здесь - очередь на двух станках.
При каких условиях правило оптимально
Для стандартной двухстаночной модели предполагают следующее:
- все работы доступны к моменту ноль и проходят станки в одном направлении: сначала первый, затем второй;
- каждый станок выполняет не более одной операции за раз; одна работа тоже не может одновременно занимать оба станка;
- длительности известны заранее, не зависят от порядка и не прерываются;
- станки доступны на протяжении расписания, перенос между ними не требует времени, а промежуточное хранение не ограничено;
- используется одна и та же очередь на обоих станках, а критерий - именно .
Если подготовку можно заранее включить в фиксированную длительность операции и она не зависит от предыдущего заказа, её учитывают в таблице времени. Когда переналадка меняется вместе с последовательностью, простое правило уже не гарантирует оптимум. То же относится к поломкам, разным датам готовности и ограниченной ёмкости буфера: модель придётся уточнять.
Практическое расписание может иметь и другие цели: например, вовремя отгрузить срочный заказ. Оптимальный по план не обязательно минимизирует просрочку. Как и при оценке сменности оборудования, важно сначала определить показатель: загрузка оборудования и момент завершения партии отвечают на разные вопросы.
Алгоритм: минимум в начало или в конец
Обозначим время работы на первом станке через , на втором - через . Выпишите все ещё не распределённые времена и повторяйте процедуру:
- Найдите наименьшее время среди обоих столбцов оставшихся работ.
- Если оно стоит в столбце первого станка, поместите соответствующую работу на самое раннее свободное место очереди.
- Если минимум относится ко второму станку, поместите работу на самое позднее свободное место.
- Исключите работу целиком из дальнейшего поиска и повторите шаги до заполнения очереди.
Когда минимумов несколько, можно выбрать любой из них; из-за равенства иногда получается несколько оптимальных очередей. Важно каждый раз сравнивать времена только оставшихся работ и занимать крайнее свободное место. Станки не выбирают отдельные очереди: найденная последовательность общая.
Интуитивно короткую первую операцию выгодно запустить раньше, чтобы второй станок скорее получил работу. Короткую вторую операцию удобно оставить ближе к концу, чтобы она меньше задержала завершение партии. Это объясняет направление выбора, но гарантия оптимальности относится к перечисленным условиям модели, а не к любому производственному процессу.
Пример: четыре работы на двух станках
Пусть время задано в минутах. Все числа - учебные, а не измерения реального участка.
| Работа | Станок 1, | Станок 2, |
|---|---|---|
| А | 2 | 6 |
| Б | 5 | 3 |
| В | 4 | 7 |
| Г | 6 | 1 |
Сначала минимум равен 1 у работы Г на втором станке: она занимает последнее место. Из оставшихся минимум равен 2 у А на первом станке: ставим её первой. Затем минимум 3 у Б на втором станке: она занимает последнее из свободных мест, перед Г. В оставшуюся позицию попадает В. Итак, очередь - А → В → Б → Г.
Посчитаем интервалы. Первый станок начинает следующую работу сразу после предыдущей. Второй приступает к очередной детали только тогда, когда она готова после первого станка и когда сам второй станок освободился.
| Работа | Станок 1: начало–конец | Станок 2: начало–конец |
|---|---|---|
| А | 0–2 | 2–8 |
| В | 2–6 | 8–15 |
| Б | 6–11 | 15–18 |
| Г | 11–17 | 18–19 |

Второй станок ждёт первую деталь с нуля до второй минуты; затем он занят до конца партии. Следовательно, минут. Для сравнения, в обратном порядке Г → Б → В → А последний заказ заканчивается на 28-й минуте. Экономия относительно этого конкретного порядка составляет 9 минут; правило не утверждает, что всякая другая очередь обязательно хуже.
Как проверить диаграмму и вычисления
Для работы на позиции обозначим моменты окончания операций через и . Положим . Тогда для выбранной очереди:
Максимум во второй формуле обеспечивает оба ограничения: деталь уже готова, а станок свободен. Например, В покидает первый станок в момент 6, но второй занят работой А до момента 8. Поэтому В начинается на втором станке в 8 и заканчивается в 15. Б готова в 11, но ждёт до 15; Г готова в 17 и ждёт до 18.
Проверка по диаграмме состоит из трёх вопросов. Нет ли пересечений операций на одном станке? Начинается ли каждая вторая операция после первой? Совпадают ли длительности прямоугольников с исходной таблицей? Если все ответы положительны, расписание допустимо; правило Джонсона дополнительно обосновывает оптимальность его общего времени в данной модели.
Длительность обработки одной партии отличается от мощности участка или выпуска за смену: перевод времени в производственные показатели требует дополнительных допущений. При работе с ресурсами полезно также различать физический выпуск и его изменение, как в статье о предельном продукте труда.
Почему порядок имеет значение
Хотя сумма операций на каждом станке фиксирована, простои второго станка между ними зависят от очереди. Если следующая деталь ещё не вышла с первого станка, второй простаивает. При этом сокращение всех простоев первого станка не является отдельным шагом алгоритма: в нашем расписании он последовательно выполняет все четыре операции за 17 минут.
Есть и нижняя граница для примера: второму станку требуется минут чистой работы, а получить первую деталь раньше второй минуты он не может. Поэтому любое расписание закончится не раньше 19-й минуты. Найденный план достигает этой границы, что независимо подтверждает его оптимальность именно для этих исходных чисел. В других задачах такая простая граница может не достигаться; тогда не следует объявлять её ответом без построения расписания.
Задача выбора порядка - пример оптимизации по дискретным вариантам. Перебор всех очередей быстро растёт с числом работ, поэтому специальное правило полезно именно там, где выполняются его условия. О различии между задачей поиска и проверкой готового решения рассказывает материал о классах P и NP.
Частые ошибки
- Искать минимум в каждой строке, а затем сразу сортировать без разделения сторон. На каждом шаге нужен общий минимум среди всех оставшихся операций; номер станка определяет край очереди.
- Вычёркивать только одну ячейку. После размещения работа исключается вместе с обоими временами, иначе она попадёт в очередь дважды.
- Начинать вторую операцию сразу после первой. Нужно дождаться и освобождения второго станка: для В в примере это 8-я минута, а не 6-я.
- Считать, что оптимальная очередь единственна. При равных временах и даже без них другие очереди тоже могут дать тот же .
- Применять результат к другому критерию без проверки. Минимум общего срока не означает минимум просрочки, стоимости или среднего ожидания.
FAQ
Можно ли применять правило к трём станкам? Не напрямую ко всем задачам. Для некоторых специальных условий трёхстаночную задачу сводят к двухстаночной с фиктивными временами; без проверки этих условий гарантия отсутствует.
Что делать при равных минимумах? Выбрать любой из них и продолжить по той же процедуре. Полученная очередь оптимальна для стандартной модели, хотя конкретный порядок может отличаться от ответа в учебнике.
Нужно ли второму станку ждать завершения всей партии на первом? Нет. Как только отдельная работа закончена на первом станке и второй свободен, она может перейти на него. Это перекрытие операций и отражает диаграмма.
Коротко
Правило Джонсона строит оптимальную по общему времени очередь для двух последовательных станков: минимум первого столбца ставят в начало свободной части очереди, минимум второго - в конец. После выбора порядка моменты окончания проверяют через максимум готовности детали и освобождения станка. В рассмотренном примере очередь А → В → Б → Г завершает партию за 19 минут.
Читайте также

ABC-анализ запасов: расчёт и пример
ABC-анализ запасов по стоимости годового расхода: формулы, пример с накопленными долями, правило границ групп A, B и C и применение результатов на складе.

Абсолютное преимущество Смита: пример и расчёт
Абсолютное преимущество Смита простыми словами: как сравнить затраты труда, рассчитать выигрыш от специализации и отличить его от сравнительного преимущества Рикардо.

Аддитивная факторная модель: формула и пример расчёта
Аддитивная факторная модель в экономике: как разложить показатель на слагаемые, рассчитать вклад каждого изменения и проверить результат на примере прибыли.

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

Анализ чувствительности инвестиционного проекта
Как провести анализ чувствительности инвестиционного проекта: расчёт NPV, сравнение факторов, порог выручки и ограничения однофакторной модели на числовом примере.

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