Когда более медленный станок помогает закончить весь набор вовремя

Зафиксируйте одну операцию и общий срок

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

Для учебной проверки задаём условия: все задания и материалы готовы на минуте 0; станки свободны, непрерывно доступны и работают независимо; один станок выполняет одну работу за раз. Прерывания, раздел задания, переналадки, передача, простои, зависимые этапы и общие исполнители отсутствуют. Времена фиксированы. Завершение ровно на минуте 60 считается своевременным.

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

Запишите время для каждой разрешённой пары

Все числа далее вымышлены. A, B и C обозначают целые обязательные задания, M1 и M2 — альтернативные станки. В базовом примере разрешены все шесть сочетаний. Значение в ячейке относится ко всему заданию на конкретном станке.

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

Сравните три назначения, а не среднюю загрузку

Первый вариант выбирает кратчайшую длительность отдельно для A, B и C: всё получает M1. Его интервалы: A 0–20, B 20–50, C 50–90. M2 пуст. Работа составляет 90 станко-минут, последнее завершение приходится на минуту 90. Это минимальная сумма обработки: каждое задание получает свою кратчайшую длительность. Принятый срок нарушен на 30 минут. Деление 90 на два станка не создаёт расписание на 45 минут.

Во втором варианте B назначено на M2: оно занимает 0–50. На M1 остаются A 0–20 и C 20–60. Для B потребовалось 50 вместо 30 минут, поэтому работа выросла до 110 станко-минут. Зато весь набор завершается на 60. Это своевременный результат только при заданных условиях, с нулевым запасом.

Третий вариант переносит A на M2: A 0–40, а на M1 идут B 0–30 и C 30–70. Работа снова равна 110 станко-минутам, однако завершение на 70 означает опоздание на 10 минут. Выбирать между вторым и третьим вариантом по одной сумме работы нельзя: при равных затратах времени на обработку исход обещания различается.

Проверьте все восемь назначений

У трёх заданий по два варианта, всего восемь назначений. Код читается в порядке A, B, C: цифра 1 означает M1, цифра 2 — M2. Для каждого кода складываем длительности выбранных пар отдельно по станкам; при наших условиях размещение подряд от нуля даёт показанное завершение. Все результаты таблицы рассчитаны редакцией.

Только 121 укладывается в 60. Назначение единственное, но порядок на M1 может быть A, C или C, A: оба заканчиваются на 60. Проверка всех 24 расписаний без простоев с разными порядками внутри станков подтверждает тот же минимум. Для этого примера порядок не исправит перегруженное назначение.

Докажите границу и проверьте изменение условий

Предположим, требуется закончить строго раньше 60. C не помещается на M2: ему нужно 70. На M1 оно занимает 40. Вместе с A получилось бы 60, вместе с B — 70. Значит, A и B пришлось бы отправить на M2, где им нужны 40 + 50 = 90. Противоречие. План 121 достигает 60, поэтому для заданной модели граница точная.

Проверьте три независимых изменения, каждый раз возвращая базовые данные. При сроке 59 своевременного назначения нет. Если исключить допуск B на M2, остаются четыре назначения, лучшее завершение равно 70. Если только длительность B на M2 заменить с 50 на 61, лучшее завершение равно 61. Во всех случаях прежняя отметка «к сроку» должна исчезнуть.

Это вывод полного перебора маленького набора. Для большого рабочего плана результат «вариант пока не найден» сам по себе не доказывает невозможность. В нашем примере дополнительные 20 станко-минут также ничего не говорят о денежных расходах: тарифы и затраты здесь не заданы.

Попросите воспроизводимое доказательство

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

• Каждое обязательное задание присутствует ровно один раз. Удаление C ради красивого срока и дублирование A должны отклоняться.
• Интервалы одного станка не перекрываются. Для B на M2 используются именно 50 минут; подстановка 30 из M1 должна обнаруживаться.
• Сравнение сохраняет оба результата с работой 110: конец 60 и конец 70. Оно не заменяется одним показателем загрузки.
• Изменение допуска, длительности или срока запускает новый расчёт с сохранением прежней версии.
• Завершение на минуте 60 при сроке 60 показывает нулевой запас до обещания. Успешный учебный тест не гарантирует реальный срок при отклонениях.

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

Отделите источники модели от учебных чисел

В оригинальной работе Lenstra, Shmoys и Tardos время зависит от пары «задание — машина», а конец набора определяется наибольшей машинной нагрузкой. Выбор быстрейшей машины для каждого задания используется как исходная оценка. CWI: постановка и исходное назначение, страницы 2 и 5.

В официальной схеме Google OR-Tools альтернативе сопоставлены машина и длительность; выбирается ровно одна. Поле latest_end задаёт жёсткую границу отдельно от штрафов за опоздание. Google: описание задачи. Это подтверждает структуру данных, а не возможности конкретной конфигурации SABSUS.

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