Формализация задачи планирования

Сейчас начал автоматизировать создание сменных заданий в сталелитейном цехе. Задача комплектации плавок. Неформально она описывается так:
Имеется недельный план - сколько каких отливок надо отлить, каждая отливка имеет расчетный вес и марку стали. В печи плавится сталь (сколько-то тонн) и надо скомплектовать плавки. Цель - выпустить все и при этом за минимальное количество плавок.
Аналогичная задача на цветном и электрошлаковом литье, но там вопрос не в плавках, а в термообработке - комплектация садки. Там задача минимизации числа садок вообще в чистом виде - расход энергии от массы садки не зависит, все определяется режимом термообработки.
Вот вчера понял, как формализовать задачу, описать ее математически:

1. Рассматриваем марки стали отдельно - редкие случаи, когда излишек выплавленной "хорошей" стали заливаем вместо "обычной", не рассматриваем. То есть рассмотрим задачу для одной марки стали.

2. План состоит из n наименований отливок, для i-й отливки масса одной шт. M_i, количество по плану A_i

3. Пусть у нас есть несколько печей и масса плавки имеет две границы - нижнюю и верхнюю (для термообработки нижнюю границу можем считать 0). Для каждой печи мы знаем максимальное количество плавок, которое можно сделать за неделю (т.е. планируемый период). Дальше отвлечемся от печей и рассматриваем плавки - то, что хотим скомплектовать. Верхнее ограничение массы j-й плавки = C_j (зависит от печи - сначала по первой печи все возможные плавки, потом по второй и т.д.)

4. Пусть X_ij это количество деталей i в плавке j. Тогда можем записать нужные нам уравнения:
(Сумма по j) X_ij = A_i - условие выполнения плана
(Сумма по i) M_i*X_ij < C_j - верхнее ограничение массы плавки (нижнее аналогично)

5. Цель - решить эту систему в неотрицательных целых числах. Оптимальная цель - минимизировать при этом количество плавок.

6. Т.е. алгоритм такой: проверяем, совместна ли исходная система и имеет ли она решение в неотрицательных целых числах. Решение, кстати, и будет комплектацией плавок, т.е. потом остается только раскидать плавки по дням и сменам, и voila!

7. Но перед этим надо оптимизировать решение, т.е. если система совместна, то выкидываем одну плавку и смотрим, имеет ли она решение теперь - если да, то оно лучше первого. Конечно, тут проблема, какую плавку выкинуть - C_j ведь разные. Но они определяются типом печи, которых у нас всего три, так что подойдет простой перебор. Или узнать в цеху их соображения - равномерность загрузки печей? Наоборот, неравномерность - чтобы не прогревать лишний раз печь (первая плавка в день требует больше энергии)?

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

Кстати, если план заведомо невыполним, то этот алгоритм не работает; тогда задача меняется: скомплектовать плавки так, чтобы выпустить максимум продукции по весу. Классическая задача линейного программирования :-)