Оптимизация наборов красок при печати. Класс задачи?

[anvano]

Предыстория:
Имеется в наличии около 100 разных красок.
Надо напечатать 50-1000 картинок.
Каждая картинка печатается разным количеством красок от 5 до 30, в среднем 15 (набор красок для каждой картинки заранее известен).
В печатающее устройство можно одновременно залить не более 30 красок (30 баночек там).

Чтобы перезаправить устройство на другой набор оттенков надо потратить прилично времени (слить краску, промыть головки и т.п.)


Задача:
Имея на руках таблицу с перечнем красок для каждой картинки, необходимо оптимизировать количество перезаправок печатающего устройства.
То есть надо за минимальное количество перезаправок распечатать все картинки.
Результатом работы должен быть список красок для каждой перезаправки (палитра).

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

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


Вот пример исходных данных (70 красок, 25 картинок):
http://anvano.ru/images.xlsx
Мой алгоритм:
1) Рекурсивно объединяются наборы красок для картинок, пока объединение не превысит допустимый размер палитры.
2) Все варианты полученных объединений (палитр) запоминаются в некоторый пул.
3) Для каждой полученной палитры из пула определяется , какие картинки этой палитрой можно распечатать.
4) Выбирается одна палитра, покрывающая максимальное количество картинок. Остальной пул отбрасывается.
Получили первую результирующую палитру

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

Для вышеописанного примера данный алгоритм выдаёт, что все 25 картинок можно распечатать четырьмя палитрами:
http://anvano.ru/result.png

Что мне не нравится в алгоритме:
На первом этапе отбирается палитра, покрывающая максимальное количество картинок (в примере - 13). Дальше эти картинки отбрасываются и работа ведётся уже с остатками. В итоге получается (из картинки с результатом):
1 палитра - 13 картинок
2 палитра - 7 картинок
3 палитра - 3 картинки
4 палитра - 2 картинки

А вдруг есть такие палитры, что:
1 палитра - 9 картинок
2 палитра - 8 картинок
3 палитра - 8 картинки
А мой алгоритм даже не пытается такие варианты рассматривать, т.к. первый шаг оптимизации идет по максимальному количеству распечатанных картинок.

Вот, может несколько сумбурно, но попытался изложить свои мысли :)

[ИСН]

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

[anvano]

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

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