Два участка подряд: в каком порядке запускать задания

Назовите цель: закончить весь набор раньше

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

Эту длительность от начала работы до завершения последнего задания называют makespan. Она отличается от среднего ожидания заказа, суммы опозданий и момента готовности отдельного срочного клиента. В учебном материале Cambridge эти цели разделены, а правило Джонсона отнесено к двум последовательным машинам и минимизации makespan. Cambridge: machine-level scheduling, слайды 145–151.

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

Границы учебной модели

Все задания и материалы готовы в момент 0. Каждый ресурс выполняет не более одного задания одновременно. Порядок операций для любой работы одинаков: сначала M1, затем M2. Операции не прерываются, их длительности известны и постоянны.

Выбранный порядок заданий одинаков на обоих участках. Подготовка выполнена, зависимых переналадок нет, передача не добавляет времени. Между участками есть достаточное место ожидания: готовое задание освобождает M1, даже когда M2 занят. Блокировка первого участка из-за занятого второго исключена.

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

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

Три задания и два времени для каждого

Все числа условные и выражены в минутах. Обозначения A, B и C относятся к заданиям, а M1 и M2 — к ресурсам.

• A требует 2 минуты на M1 и 7 на M2.
• B требует 6 минут на M1 и 3 на M2.
• C требует 5 минут на M1 и 4 на M2.

Первый участок загружен суммарно на 2 + 6 + 5 = 13 минут, второй на 7 + 3 + 4 = 14. Общий объём работы равен 27 ресурсным минутам. Но это не календарная длительность всего набора: часть работы разных участков может перекрываться.

Для любого заданного порядка M1 начинает следующую работу после своей предыдущей. Начало на M2 равно более позднему из двух моментов: это задание готово после M1 и M2 освободился от предыдущего. Затем к началу прибавляется время второй операции.

Нельзя запустить задание на M2 только потому, что M2 свободен, пока оно ещё обрабатывается на M1. И нельзя запустить готовое задание, когда второй ресурс занят. Обе проверки входят в одну строку расписания.

Что происходит в порядке A, B, C

На M1 получаем интервалы A: 0–2, B: 2–8, C: 8–13.

A приходит на M2 в момент 2 и занимает его до 9. B готово после M1 на 8, но M2 свободен только на 9: B обрабатывается с 9 до 12. C будет готово на 13, поэтому второй участок после B ждёт одну минуту и выполняет C с 13 до 17.

Итог: весь набор завершён на минуте 17. Второй участок не работает в начале 0–2 и между заданиями 12–13; его 14 минут обработки вместе с этими тремя минутами ожидания дают 17.

Суммы нагрузки на каждом участке правильные, но сами по себе не показывали этот разрыв. Расписание объясняет, когда второй ресурс остаётся без доступной работы, хотя первое звено ещё занято.

Правило Джонсона даёт A, C, B

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

Здесь минимальное время 2 относится к A на M1, поэтому A ставим первым. Среди оставшихся минимум 3 относится к B на M2, поэтому B ставим последним. C занимает середину. Получается A, C, B. Этот пошаговый вариант правила показан в учебных слайдах Cambridge; равных минимумов в нашем примере нет.

На M1: A 0–2, C 2–7, B 7–13. На M2: A 2–9, C 9–13, B 13–16. Второй участок после начала на 2 работает без промежуточного ожидания, а весь набор заканчивается на 16.

Обработка по-прежнему занимает 13 и 14 ресурсных минут. Мы не ускорили операции и не сократили обязательную работу: изменили сочетание готовности и занятости. Выигрыш одной календарной минуты относительно A, B, C не является автоматической денежной экономией.

Проверьте все шесть порядков и нижнюю границу

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

• A, B, C: 17.
• A, C, B: 16.
• B, A, C: 20.
• B, C, A: 22.
• C, A, B: 19.
• C, B, A: 21.

Дополнительно докажем, что закончить раньше 16 при наших условиях нельзя. Второму ресурсу нужны 14 минут работы. Первое задание не может поступить на него раньше минимальной первой операции, то есть раньше минуты 2. Следовательно, завершение не раньше 2 + 14 = 16.

Есть и вторая проверка: M1 должен выполнить все 13 минут работы. Последнее завершённое им задание затем ещё требует как минимум 3 минуты на M2. Поэтому общая готовность также не раньше 13 + 3 = 16. Ожидание могло бы увеличить эти границы, но не уменьшить.

A, C, B достигает 16, значит, в данной модели результат действительно оптимален. В нашем наборе он единственный лучший среди шести порядков. Не переносите эту уникальность на любые исходные времена: у другой задачи могут быть несколько оптимальных очередей.

Срочный срок отдельного задания меняет решение

Добавим новое обязательство: B должно завершиться на M2 не позднее минуты 12. В прежнем лучшем порядке A, C, B оно готово только на 16, поэтому этот вариант больше недопустим. Короткий makespan не оправдывает нарушение принятого срока.

Порядок A, B, C даёт B на 12 и весь набор на 17. Он выполняет новое условие, хотя общий конец на одну минуту позднее прежнего свободного оптимума. Остальные допустимые по сроку B порядки из полного перебора, B, A, C и B, C, A, завершают весь набор на 20 и 22.

Значит, при добавленном сроке B выбран A, B, C с завершением 17. Это результат проверки изменённой маленькой задачи, а не утверждение, что стандартное правило Джонсона оптимизирует произвольные сроки клиентов.

Если на участке уже начато задание, его нельзя переставить задним числом. Сохраните фактическое состояние обоих ресурсов и готовность промежуточных работ, затем пересчитывайте разрешённый остаток. Модель «всё готово и оба ресурса свободны на 0» уже не описывает такую ситуацию.

Данные для выпуска проверяемого плана

Для каждого задания нужны идентификатор, две подтверждённые длительности, маршрут M1 → M2, момент готовности и обязательные сроки. Для ресурсов — календарь и независимость исполнителей. Отдельно сохраняйте реальные передачи, буфер, подготовку и ограничения прерывания; нулевое время должно быть допущением с основанием, а не заменой неизвестного.

Результат содержит порядок, начало и конец каждой операции, ожидание перед M2, общий момент завершения и нарушения условий. Не выдавайте окончание M1 за готовый выпуск после обоих участков. Расчёт передаточных частей понадобится отдельно, если фактически разрешён частичный переход партии.

Для производства SABSUS и BOM обсудите исходные операции и утверждённый календарь. Хранение нужных ограничений, расчёт расписания и автоматический оптимизатор подтверждаются отдельно в выбранной конфигурации.

1. A, B, C воспроизводит M2: 2–9, 9–12, 13–17.
2. A, C, B воспроизводит M2: 2–9, 9–13, 13–16.
3. Начало каждой второй операции не раньше готовности и освобождения ресурса.
4. Ни одно задание не потеряно и не обработано дважды.
5. Все шесть порядков дают 17, 16, 20, 22, 19 и 21.
6. Нижние границы дают 16, а допустимый план достигает их.
7. Обязательный срок B = 12 исключает прежний порядок A, C, B.
8. Фактический старт, нехватка места или общий исполнитель требуют новой модели.

Источники и область применения

• Della Croce, Schau: Revisiting Johnson’s rule, версия 4 от 7 января 2026, раздел 1.
• Cambridge Judge Business School: Operations Management, machine-level scheduling, слайды 145–151.

Источники проверены 11 октября 2026 года. Времена, задания, полный перебор и дополнительный срок являются оригинальным учебным примером. Расчёт не устанавливает допустимость рабочего метода и не является обещанием срока для реального заказа без проверки исходных условий.