Это минимальная проблема прикрытия?

Question

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

Мне представлен список "рецептов" (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), это нормально.

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

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

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

Спасибо!

Answer 1

Это напоминает мне о проблеме раскраски графов, используемой для выделения регистров в компиляторах.

Шаг 1: если та же часть повторяется в рецепте, переименуйте его; например, R5 = {P1, P2, P2'}

Шаг 2: вставьте все части в график с ребрами между частями в одном рецепте

Шаг 3: раскрасьте график так, чтобы два соединенных узла (части) не имели одинаковый цвет

Цвета - это индивидуальность машины для изготовления деталей.

Это неоптимально, потому что переименованные части создают ложные ограничения в других рецептах. Вы можете исправить это с помощью "объединения". Смотри Бриггс.