Это проблема минимального набора?

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

Мне представлен список «рецептов» (Ri), которые необходимо выполнить в указанном порядке для выполнения заданной задачи. Каждый рецепт состоит из списка частей (Pj), необходимых для его выполнения. Рецепт обычно требует до 3 или 4 частей, но может потребоваться и 16. Примерный список рецептов может выглядеть так:

• R1 = {P1}
• R2 = {P4}
• R3 = {P2 , P3, P4}
• R4 = {P1, P4}
• R5 = {P1, P2, P2} // Обратите внимание, что может потребоваться более 1 данной части. (Здесь P2)
• R6 = {P2, P3}
• R7 = {P3, P3}
• R8 = {P1} // Обратите внимание, что рецепты могут повторяться в списке. (То же, что и R1)

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

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

Происходит итерация процесса выполнения. следующим образом:

• Следующий рецепт в списке представлен набору машин.
• На каждой машине, одна из его доступных программ выбирается для производства одной из деталей, требуемых по этому рецепту, или, если это не требуется для этого рецепта, она устанавливается в "автономный режим".
• "Кривошип" вращается, и каждая машина ( который не был "отключен") выплевывает одну деталь.
• Объединение деталей, полученных одним поворотом рукоятки, соответствует рецепту. Порядок не имеет значения, например, выполнение рецепта {P1, P2, P3} совпадает с выполнением рецепта {P1, P3, P2}.

Машины работают мгновенно, параллельно и имеют неограниченное количество сырья, поэтому нет ресурсные или временные / календарные ограничения. Размер k группы машин должен быть, по крайней мере, равен количеству элементов в самом длинном рецепте и, таким образом, иметь примерно такой же диапазон (обычно 3-4, возможно, до 16), что и длина рецепта, указанная выше. Итак, в приведенном выше примере k = 3 (определяется размером R3 и R5) кажется разумным выбором.

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

На данный момент я считаю это проблемой unicost, т. Е. Каждой программе требуется один и тот же объем памяти, хотя я Мне нравится гибкость, позволяющая добавлять весовые коэффициенты для каждой программы в будущем. В приведенном выше примере, учитывая все рецепты, P1 встречается не более одного раза, P2 встречается не более двух раз (в R5), P3 встречается не более двух раз (в R7), а P4 встречается не более одного раза, поэтому в идеале я хотел бы достичь конфигурация, которая соответствует этому - только одна машина сконфигурирована для производства P1, две машины сконфигурированы для производства P2, две машины сконфигурированы для производства P3 и одна машина сконфигурирована для производства P4. Одна возможная минимальная конфигурация для приведенного выше примера с использованием размера банка станков k = 3:

• M1 запрограммирован на производство P1 или P3
• M2 запрограммирован на производство P2 или P3
• M3 запрограммирован для производства P2 или P4

Поскольку здесь нет ограничений типа «работа цех», Моя интуиция подсказывает мне, что это должно сводиться к проблеме набора-покрытия - что-то вроде минимальной проблемы единого набора-покрытия, обнаруживаемой при проектировании цифровых систем. Но я не могу адаптировать мои (правда, ограниченные) знания об этих алгоритмах к этому сценарию. Может ли кто-нибудь подтвердить или опровергнуть осуществимость этого подхода и в любом случае указать мне на некоторые полезные алгоритмы? Я ищу что-то, что можно интегрировать в существующий фрагмент кода, в отличие от чего-то предварительно упакованного, например, Berkeley's Espresso.

Спасибо!