В продолжение вчерашней записи.
Если чуть изменить задачу, то можно обойтись двукратным решением задачи линейного программирования (или это ее частный случай - транспортная задача? не помню).
Меняем задачу так: Проверить выполнимость плана. Если не выполним, то скомплектовать плавки, максимизируя общую массу отлитого; если план выполним, то добавляем к нему план следующей недели и комплектуем плавки так, чтобы был полностью выполнен план текущей недели и еще отлито что-то из следующего плана, по-прежнему максимизируем массу отлитого.
Т.е. исходим из того, что оборудование должно быть загружено максимально. Для нашего завода это разумная посылка - заказов много и проблема их выполнить все в срок. Еще тут предполагается, что мы планируем критичное оборудование, т.е. узкое место именно здесь, увеличение производительности здесь не создаст проблем на остальных участках. В общем, голдраттовская "теория ограничений" на практике.
Формальная постановка задачи и алгоритм чуть меняются:
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 ведь разные. Но они определяются типом печи, которых у нас всего три, так что подойдет простой перебор. Или узнать в цеху их соображения - равномерность загрузки печей? Наоборот, неравномерность - чтобы не прогревать лишний раз печь (первая плавка в день требует больше энергии)?
В общем, остается узнать (или придумать) алгоритм, который решал бы систему линейных неравенств в целых числах.
Кстати, если план заведомо невыполним, то этот алгоритм не работает; тогда задача меняется: скомплектовать плавки так, чтобы выпустить максимум продукции по весу. Классическая задача линейного программирования :-)
пятница, 26 февраля 2010 г.
Поехали!
Меня зовут Тимур Василенко, живу в Пензе, работаю на заводе "МашСталь" директором по IT. Завод металлургический, выпускает черное и цветное литье под заказ, а я занимаюсь автоматизацией этого производства - от бухгалтерии до маркетинговой подготовки производства. Этот блог и посвящен моей работе - что делаю, как делаю, идеи и т.п.
Скажу сразу - бухгалтерия и производственное планирование/диспетчирование у нас сделаны на 1С:7.7. Причины такого выбора:
1. Исторические - сначала фирма занималась только металлоломом, там все было автоматизировано на 1С. Потом с появлением литейных цехов постепенно система наращивалась и дописывалась - эволюционировала, в общем;
2. Специфические - металлургическое производство весьма специфично, так что стандартных решений (типа MRP II для машиностроительного производства) нет или они стоят столько, что заводу на те же деньги можно купить новую производственную линию. С другой стороны, эта специфика не связана с большой сложностью, так что слабые вычислительные возможности 1С вполне достаточны для возникающих задач;
3. Персональные - имеющийся персонал знает 1С, так что хоть со стороны освоенности инструмента нет проблем.
В общем, на чем-то другом можно было бы сделать и круче, но 1С для этой задачи достаточно, и будет достаточно еще несколько лет.
На первых порах буду писать о двух проектах:
Создание документации на базе Wiki-движка. Автоматизировано уже много бизнес-процессов, часть из них достаточно редкие (но сложные). Пользователи забывают - вот решил сделать документацию. Пишу, обдумываю.
Маркетинговая подготовка производства. Это весь тот этап, который от заявки клиента "не могли бы вы изготовить мне вот такую штуку?" до заключения договора на изготовление этой самой штуки. Это не функционал CRM, тут не отношения с клиентом важны, а процедура оценки заявки (сможем ли изготовить и сколько это будет стоить), коммерческий отдел тут по краям процесса, основное - технологи и производство. Систем управления этим процессом я не встречал, так что буду изобретать свое. Концептуально обдумал, практически начнем воплощать через три недели.
Ну и еще одна тема - алгоритмы производственного планирования в привязке к нашему производству.
Скажу сразу - бухгалтерия и производственное планирование/диспетчирование у нас сделаны на 1С:7.7. Причины такого выбора:
1. Исторические - сначала фирма занималась только металлоломом, там все было автоматизировано на 1С. Потом с появлением литейных цехов постепенно система наращивалась и дописывалась - эволюционировала, в общем;
2. Специфические - металлургическое производство весьма специфично, так что стандартных решений (типа MRP II для машиностроительного производства) нет или они стоят столько, что заводу на те же деньги можно купить новую производственную линию. С другой стороны, эта специфика не связана с большой сложностью, так что слабые вычислительные возможности 1С вполне достаточны для возникающих задач;
3. Персональные - имеющийся персонал знает 1С, так что хоть со стороны освоенности инструмента нет проблем.
В общем, на чем-то другом можно было бы сделать и круче, но 1С для этой задачи достаточно, и будет достаточно еще несколько лет.
На первых порах буду писать о двух проектах:
Создание документации на базе Wiki-движка. Автоматизировано уже много бизнес-процессов, часть из них достаточно редкие (но сложные). Пользователи забывают - вот решил сделать документацию. Пишу, обдумываю.
Маркетинговая подготовка производства. Это весь тот этап, который от заявки клиента "не могли бы вы изготовить мне вот такую штуку?" до заключения договора на изготовление этой самой штуки. Это не функционал CRM, тут не отношения с клиентом важны, а процедура оценки заявки (сможем ли изготовить и сколько это будет стоить), коммерческий отдел тут по краям процесса, основное - технологи и производство. Систем управления этим процессом я не встречал, так что буду изобретать свое. Концептуально обдумал, практически начнем воплощать через три недели.
Ну и еще одна тема - алгоритмы производственного планирования в привязке к нашему производству.
Подписаться на:
Сообщения (Atom)