В продолжение вчерашней записи.
Если чуть изменить задачу, то можно обойтись двукратным решением задачи линейного программирования (или это ее частный случай - транспортная задача? не помню).
Меняем задачу так: Проверить выполнимость плана. Если не выполним, то скомплектовать плавки, максимизируя общую массу отлитого; если план выполним, то добавляем к нему план следующей недели и комплектуем плавки так, чтобы был полностью выполнен план текущей недели и еще отлито что-то из следующего плана, по-прежнему максимизируем массу отлитого.
Т.е. исходим из того, что оборудование должно быть загружено максимально. Для нашего завода это разумная посылка - заказов много и проблема их выполнить все в срок. Еще тут предполагается, что мы планируем критичное оборудование, т.е. узкое место именно здесь, увеличение производительности здесь не создаст проблем на остальных участках. В общем, голдраттовская "теория ограничений" на практике.
Формальная постановка задачи и алгоритм чуть меняются:
1. Проверка выполнимости плана:
(Сумма по j) Xij <= Ai - текущий план как ограничение
(Сумма по i) Mi*Xij < Cj - верхнее ограничение массы плавки (нижнее аналогично)
Целевая функция: (Сумма по i и j) Mi*Xij -> max - максимизируем общую массу отлитого.
2. Опорное решение элементарно: все Xij=0
3. Решаем транспортную задачу, получаем оптимальное решение.
4. Если план выполним, то первая группа ограничений реализуется как равенство: (Сумма по j) Xij = Ai
Если это не соблюдено, то план невыполним и полученное решение это тот максимум, который мы можем сделать из плана текущей недели.
5. Если план выполним, то увеличиваем систему: добавляем в нее план следующей недели, но отдельными позициями (т.е. "отливка А" из плана текущей недели и "отливка А" из плана следующей недели - это две разные позиции, хотя физически они одинаковые).
6. Ограничения для плана текущей и плана следующей недели различаются: для текущей недели берем равенства, для следующей недели - неравенства. Целевая функция такая же (с учетом того, что переменных в ней больше).
7. Решение, полученное на предыдущем этапе, является опорным для новой задачи (новые переменные мы приравниваем 0).
8. Решаем транспортную задачу с практически удвоенным числом переменных и находим оптимальную комплектацию плавок.
Финальные замечания:
а) Эта задача так красиво выглядит для одной марки стали - для нескольких марок сначала придется поделить количество плавок между марками стали, а затем оптимизировать эти группы отдельно. Реально стоит сначала выделить редкие стали (всякую там нержавейку) и минимизировать число плавок там - не больше пяти в неделю, это можно и перебором. Остается разобраться с двумя наиболее популярными марками стали.
б) Постановка задачи молчаливо предполагает, что все печи работают независимо, т.е. общее максимальное количество плавок есть сумма максимумов по всем печам. Реально это может быть не так - одновременно плавки на двух крупных печах может не потянуть силовой кабель, так что и тут возможны переборные вариации.
суббота, 10 апреля 2010 г.
пятница, 9 апреля 2010 г.
Формализация задачи планирования
Сейчас начал автоматизировать создание сменных заданий в сталелитейном цехе. Задача комплектации плавок. Неформально она описывается так:
Имеется недельный план - сколько каких отливок надо отлить, каждая отливка имеет расчетный вес и марку стали. В печи плавится сталь (сколько-то тонн) и надо скомплектовать плавки. Цель - выпустить все и при этом за минимальное количество плавок.
Аналогичная задача на цветном и электрошлаковом литье, но там вопрос не в плавках, а в термообработке - комплектация садки. Там задача минимизации числа садок вообще в чистом виде - расход энергии от массы садки не зависит, все определяется режимом термообработки.
Вот вчера понял, как формализовать задачу, описать ее математически:
1. Рассматриваем марки стали отдельно - редкие случаи, когда излишек выплавленной "хорошей" стали заливаем вместо "обычной", не рассматриваем. То есть рассмотрим задачу для одной марки стали.
2. План состоит из n наименований отливок, для i-й отливки масса одной шт. Mi, количество по плану Ai
3. Пусть у нас есть несколько печей и масса плавки имеет две границы - нижнюю и верхнюю (для термообработки нижнюю границу можем считать 0). Для каждой печи мы знаем максимальное количество плавок, которое можно сделать за неделю (т.е. планируемый период). Дальше отвлечемся от печей и рассматриваем плавки - то, что хотим скомплектовать. Верхнее ограничение массы j-й плавки = Cj (зависит от печи - сначала по первой печи все возможные плавки, потом по второй и т.д.)
4. Пусть Xij это количество деталей i в плавке j. Тогда можем записать нужные нам уравнения:
(Сумма по j) Xij = Ai - условие выполнения плана
(Сумма по i) Mi*Xij < Cj - верхнее ограничение массы плавки (нижнее аналогично)
5. Цель - решить эту систему в неотрицательных целых числах. Оптимальная цель - минимизировать при этом количество плавок.
6. Т.е. алгоритм такой: проверяем, совместна ли исходная система и имеет ли она решение в неотрицательных целых числах. Решение, кстати, и будет комплектацией плавок, т.е. потом остается только раскидать плавки по дням и сменам, и voila!
7. Но перед этим надо оптимизировать решение, т.е. если система совместна, то выкидываем одну плавку и смотрим, имеет ли она решение теперь - если да, то оно лучше первого. Конечно, тут проблема, какую плавку выкинуть - Cj ведь разные. Но они определяются типом печи, которых у нас всего три, так что подойдет простой перебор. Или узнать в цеху их соображения - равномерность загрузки печей? Наоборот, неравномерность - чтобы не прогревать лишний раз печь (первая плавка в день требует больше энергии)?
В общем, остается узнать (или придумать) алгоритм, который решал бы систему линейных неравенств в целых числах.
Кстати, если план заведомо невыполним, то этот алгоритм не работает; тогда задача меняется: скомплектовать плавки так, чтобы выпустить максимум продукции по весу. Классическая задача линейного программирования :-)
Имеется недельный план - сколько каких отливок надо отлить, каждая отливка имеет расчетный вес и марку стали. В печи плавится сталь (сколько-то тонн) и надо скомплектовать плавки. Цель - выпустить все и при этом за минимальное количество плавок.
Аналогичная задача на цветном и электрошлаковом литье, но там вопрос не в плавках, а в термообработке - комплектация садки. Там задача минимизации числа садок вообще в чистом виде - расход энергии от массы садки не зависит, все определяется режимом термообработки.
Вот вчера понял, как формализовать задачу, описать ее математически:
1. Рассматриваем марки стали отдельно - редкие случаи, когда излишек выплавленной "хорошей" стали заливаем вместо "обычной", не рассматриваем. То есть рассмотрим задачу для одной марки стали.
2. План состоит из n наименований отливок, для i-й отливки масса одной шт. Mi, количество по плану Ai
3. Пусть у нас есть несколько печей и масса плавки имеет две границы - нижнюю и верхнюю (для термообработки нижнюю границу можем считать 0). Для каждой печи мы знаем максимальное количество плавок, которое можно сделать за неделю (т.е. планируемый период). Дальше отвлечемся от печей и рассматриваем плавки - то, что хотим скомплектовать. Верхнее ограничение массы j-й плавки = Cj (зависит от печи - сначала по первой печи все возможные плавки, потом по второй и т.д.)
4. Пусть Xij это количество деталей i в плавке j. Тогда можем записать нужные нам уравнения:
(Сумма по j) Xij = Ai - условие выполнения плана
(Сумма по i) Mi*Xij < Cj - верхнее ограничение массы плавки (нижнее аналогично)
5. Цель - решить эту систему в неотрицательных целых числах. Оптимальная цель - минимизировать при этом количество плавок.
6. Т.е. алгоритм такой: проверяем, совместна ли исходная система и имеет ли она решение в неотрицательных целых числах. Решение, кстати, и будет комплектацией плавок, т.е. потом остается только раскидать плавки по дням и сменам, и voila!
7. Но перед этим надо оптимизировать решение, т.е. если система совместна, то выкидываем одну плавку и смотрим, имеет ли она решение теперь - если да, то оно лучше первого. Конечно, тут проблема, какую плавку выкинуть - Cj ведь разные. Но они определяются типом печи, которых у нас всего три, так что подойдет простой перебор. Или узнать в цеху их соображения - равномерность загрузки печей? Наоборот, неравномерность - чтобы не прогревать лишний раз печь (первая плавка в день требует больше энергии)?
В общем, остается узнать (или придумать) алгоритм, который решал бы систему линейных неравенств в целых числах.
Кстати, если план заведомо невыполним, то этот алгоритм не работает; тогда задача меняется: скомплектовать плавки так, чтобы выпустить максимум продукции по весу. Классическая задача линейного программирования :-)
Подписаться на:
Сообщения (Atom)