Программа предназначена для оптимизации раскроя профиля и других длинномерных материалов (брус, бревно, труба, подоконник).
Использован алгоритм "плотной укладки", то есть взятое изделие укладывается на самый короткий остаток заготовки, на который она помещается. Если никуда не помещается, берется новая заготовка. Задачей оптимизации является нахождение последовательности изделий, при которой будет использовано меньше заготовок и будет больше длина деловых обрезков. На первом такте, изделия размещаются на хлыстах в случайном порядке. Возникает "начальная популяция". В процессе решения, популяция мутирует и размножается, неудачные экземпляры погибают, а лучшие продолжают эволюцию. Всё, как в животном и растительном мире + искусственный отбор.
Живое демо на сайте
Пример ниже - не статическая картинка, а работоспособное веб - приложение.
Вы можете запустить раскрой профиля кнопкой Старт
, задать свои размеры изделий и заготовок, изменить настройки оптимизации и оценить решение.
Конечно, оптимизатор в браузере работает медленнее, чем нативная программа, но позволяет бесплатно получить пригодные для работы результаты без необходимости что либо скачивать и устанавливать на компьютер.
Преимущества
- Окнософт:cutting обеспечивает карты распила высокого качества. Многочисленные внедрения подтверждают реальный коэффициент обрези не более 1% при оптимизации партий от 30 контуров (~120 отрезков)
- Для чтения исходных данных и записи результатов раскроя, программа использует простые форматы текстовых файлов, что упрощает интеграцию с учетными системами, внедренными у заказчика
- При необходимости, раскрой может выполняться под Linux или OS X в браузере или Node.js с передачей параметров через url, web-socket или объекты javascript
Алгоритмы линейного оптимизатора
В окнософт:каттинге использован генетический алгоритм. Суть его вот в чем:
Назовем каждое распределение изделий по хлыстам решением. Определим целевую функцию, позволяющую сравнивать качество решений. Сформируем несколько произвольных решений, назовем их поколением. Определим правила получения следующего поколения. Экземпляры с лучшей целевой функцией передают большую часть своего "генофонда", это наш "искусственный отбор". Теперь остается предоставить систему самой себе, пусть мутирует и оптимизирует результаты раскроя
В процессе разработки испытывался метод "Монте-Карло", когда наши "экземпляры" являются случайными и не зависят друг от друга и "Муравьиные алгоритмы"(ACO- ant colony optimisation). Все методы показали себя вполне работоспособным, но генетический алгоритм оказался чуть более эффективным
Варианты поставки
Есть два варианта поставки модуля раскроя Окнософт:cutting - в составе комплексного решения Управление позаказным производствм и в виде отдельного исполняемого файла. Взаимодействие с раскройной программой при первом сценарии, полностью скрыто от пользователя. Оператор работает со стандартными документами 1С:
- На основании заказов покупателей формируется план производства
- На основании плана - сменные задания со списком продукции и необходимых материалов
- Внутри задания на производство происходит оптимизация раскроя
- В процессе оптимизации, программа забирает из незавершенного производства деловую обрезь и помещает в ячеистый склад вновь образовавшиеся деловые обрезки
- Сменное задание умеет печатать бланки раскроя при ручном производстве или формировать файлы для станков с ЧПУ
- Так же, из сменного задания печатаются этикетки для отрезаемых изделий и схемы раскладки в телеги и пирамиды
- На основании заданий на производство формируются требования - накладные для передачи материалов в цех с учетом потребности и нормоупаковок
Программный интерфейс (API линейного раскроя)
Файл входных данных - setup.ini, помещается в папку с исполняемым файлом.
Файлы выходных данных - result.txt, resultproduct.txt и resultstick.txt - формируются в той же папке.
Скачать файлы с демо-данными Окнософт:cutting можно по ссылке в конце страницы. В файлх используются следующие теги:
- Outputvariant - структура выходного файла файла. Возможные значения: tab, oknosoft, по умолчанию oknosoft
- В варианте "oknosoft", формируются файлы resultproduct.txt и resultstick.txt с информацией о размещении изделий на заготовках и образовавшейся обрези
- В варианте "tab" выводятся пять значений, разделенных символами "tab": длина изделия, номер хлыста, длина хлыста, номер реза и остаток заготовки
- Algorithm - используемый алгоритм. Возможные значения: random, conservative, genetic, по умолчанию genetic
- Random- случайный перебор вариантов
- Conservative- экземпляры следующей итерации происходят от одного "родителя"
- Genetic- от двух родителей
- Variation - изменчивость, параметр алгоритмов "conservative" и "genetic". Чем выше, тем меньше потомство "похоже" на родителей. По умолчанию 1.
- Generations - количество итераций алгоритма, по умолчанию 40000
- Persons - количество "экземпляров" в "популяции", количество решений используемых в одной итерации. В алгоритме "random" просто делается generations*persons итераций с одним экземпляром(решением)
- KnifeWidth - ширина пилы
- StickLength - длина нового хлыста
- Products - длина изделия
- Scraps - длина обрезка, используемого в раскрое
- Wrongsnipmin – минимальная длина «плохого» образка
- Wrongsnipmax – максимальная длина «плохого» обрезка
В результатах оптимизации не будет обрезков с длиной между Wrongsnipmin и Wrongsnipmax
Парный раскрой
Используется при подготовке данных для станков, поддерживающих парный распил. В этом случае, в станок помещают сразу два хлыста профиля и за один такт отрезания, образуется два одинаковых полуфабриката
Задача парного раскроя решается группировкой данных перед их передачей в программу оптимизации и последующего дублирования результатов раскроя на пары изделий и заготовок. При работе раскроя внутри УПзП, система учитывает свойства номенклатуры и использует одиночный или парный раскрой в зависимости от возможностей отрезных станков
Раскрой большого числа изделий
С одной стороны, для достижения высокого качества оптимизации, на вход программы должно поступать значительное количество изделий разной длины, чтобы оптимизатору было "что сортировать". С другой, при очень больших партиях, снижается вероятность нахождения максимума при фиксированном числе итераций перебора. Эксперименты показали, что оптимальной является партия в 60 – 120 заготовок (что соответствует такту производства 30-60 изделий при парном раскрое). Если необходимо оптимизировать более 120 заготовок, лучших результатов можно добиться, разделив задачу на N частей и выполнив последовательные оптимизации для каждой части. Обработка формирования пачек заданий на производство умеет группировать продукции по видам профиля и подбирать в сменные задания изделия с максимальной дисперсией, избавляя оператора от рутинной работы по составлению производственных документов
Скачать примеры раскроя и документацию
- Демо карт одинарного и двойного распила: 60.01 Листы раскроя
- Документация и примеры файлов:
Экономичный линейный раскрой материалов (раскрой погонажа) актуален для многих отраслей производства и в строительстве. Это — распил бревен и досок в деревообработке, резка прутков, арматурных стержней, уголков, швеллеров, труб, двутавров на заготовки...
В производстве металлоконструкций и машиностроении, поперечный раскрой рулонов с бумагой и тканью в целлюлозной и легкой промышленности.
Не смотря на кажущуюся простоту, решение задач линейного раскроя является весьма не легким, но стоящим делом. Внедрение научного подхода к раскрою погонажных материалов позволяет снизить расходы на них иногда более чем на 10%! Дочитайте статью до конца и убедитесь в правоте этих слов.
Рассматриваемая тема относится к задачам линейного программирования. Для решения таких задач ученые в последние 70 лет придумали несколько различных методов.
Метод индексов Л.В. Канторовича и В.А. Залгаллера при определенном навыке позволяет «вручную» без использования вычислительной техники эффектно выполнять линейный раскрой. Любопытным читателям рекомендую с этим методом ознакомиться, прочитав книгу вышеназванных авторов «Рациональный раскрой промышленных материалов».
Симплекс-метод, основанный на идеях Л.В. Канторовича, был описан и детально разработан рядом ученых из США в середине 20 века. Надстройка MS Excel «Поиск решения» (Solver) использует этот алгоритм. Именно с помощью этого метода и Excel мы будем в этой статье решать задачу линейного раскроя.
Позже появились и получили развитие генетический, жадный и муравьиный алгоритмы. Однако, ограничимся их перечислением и перейдем к делу, не забираясь в дебри теорий (хотя там, «в дебрях», очень интересно).
Включим Excel и на простом примере порезки металлических стержней на детали познакомимся с одним из способов решения практических задач линейного раскроя. Часто математики эту задачу называют «задачей о распиле».
Исходные данные для примера я не стал придумывать, а взял из статьи Покровского М.А. «Минимизация неизбежных потерь материалов в промышленном производстве при их раскрое на штучные заготовки» опубликованной в №5 (май 2015) электронного научно-технического журнала «Инженерный вестник» издаваемого ФГБОУ ВПО «МГТУ им. Н.Э. Баумана» (ссылка: engbul . bmstu . ru / doc /775784. html ).
Цель, которую я преследовал – сравнить полученные результаты решения задачи.
Пример решения задачи линейного раскроя в MS Excel.
Договоримся, что:
1. Заготовки – это исходный материал в виде прутков, полос, стержней и т.д. одинаковой длины.
2. Детали – это элементы, которые необходимо получить, разрезав исходные заготовки на части.
3. Ширина пила, реза, руба принята равной нулю.
Условие задачи:
Для комплектации одного из заказов заготовительный участок должен порубить на комбинированных ножницах из одинаковых прутков-заготовок длиной 1500 мм три типоразмера деталей:
151 штуку длиной 330 мм
206 штук длиной 270 мм
163 штуки длиной 190 мм
Требуется найти оптимальный план раскроя, использующий минимальное количество материала и дающий, соответственно, минимальное количество отходов.
Исходные данные:
1. Длину исходных заготовок L з в миллиметрах записываем в объединенную ячейку
D3E3F3: 1500
2. Присваиваем номера i всем типоразмерам деталей, начиная от самой длинной и заканчивая самой короткой в ячейках
D4; E4; F4: 1; 2; 3
3. Длины деталей L д i в миллиметрах пишем в
D5; E5; F5: 330; 270; 190
4. Количество деталей N д i в штуках заносим в
D6; E6; F6: 151; 206; 163
5. Приступаем к очень важному этапу – заполнению вариантов раскроев.
Необходимо запомнить и понять 2 принципа выполнения этой работы .
1. Длины отходов должны быть меньше самой маленькой детали (0< Lo j < L д min ).
2. «Укладку» деталей в заготовку начинаем с самых больших деталей и с самого большого их количества, последовательно двигаясь в сторону уменьшения.
Если какого-нибудь типоразмера деталей в варианте раскроя нет, то ячейку оставляем пустой, ноль писать не будем для облегчения визуального восприятия таблицы.
Вариант раскроя №1:
Попытка выкроить из одной заготовки 5 деталей №1 невозможна, поэтому пишем в ячейку
Добавить в раскрой деталь №2 или деталь №3 также невозможно, поэтому оставляем пустыми ячейки
Вариант раскроя №2:
Уменьшаем на 1 от предыдущего варианта количество деталей №1 и записываем в
Пробуем добавить 2 детали №2 – не получается, поэтому дополняем в
Остается возможность дополнить раскрой деталью №3. Заносим в
Придерживаясь озвученных принципов, заполняем по аналогии все возможные в данном случае 18 вариантов раскроев.
Сделав пару-тройку таблиц вариантов раскроев самостоятельно, вы уясните логику действий и будете тратить считанные минуты на эту работу.
Если при раскрое не выполняется первый принцип, то ячейка с длиной отхода автоматически окрашивается в красный цвет. Условное форматирование, примененное к ячейкам G7…G24, наглядно поможет вам в этой работе.
В ячейках H7…H24 ничего не пишем! Они используются для вывода результата решения!
Подготовка к решению:
* В ячейках G7…G24 вычисляются длины отходов (обрезков), остающиеся в результате выполнения раскроев, по формуле
Lo j = L з — Σ (L д i * N д ij )
6. Количество деталей каждого типоразмера, изготовленных по всем примененным вариантам раскроя, будут подсчитываться в ячейках D26, E26 и F26 по формуле
N д i расч = Σ (N д ij * N з j )
Количество деталей в найденном в конце решения плане раскроя должно полностью соответствовать заданному количеству деталей!
7. Необходимое число заготовок для выполнения оптимального плана раскроя будет определяться в объединенной ячейке D27E27F27 по формуле
N з расч = ΣNз j
8. Общая длина всех заготовок, необходимых чтобы выполнить линейный раскрой всех деталей будет подсчитываться в объединенной ячейке D28E28F28 по формуле
L з Σ = L з * N з расч
9. Общая длина всех отходов, получаемых при выполнении найденного плана раскроя, будет считаться в объединенной ячейке D29E29F29 по формуле
L о Σ = Σ (L о j * N з j )
10. Доля отходов, полученных при выполнении оптимального плана линейного раскроя от общего количества использованного материала, будет вычисляться в объединенной ячейке D30E30F30 по формуле
Ωo = Lо Σ /Lз Σ
Решение:
Подготовка завершена, определены 18 вариантов наиболее оптимальных раскроев одной заготовки на детали и вписаны все необходимые формулы. Теперь предстоит решить главную задачу: определить оптимальный план раскроя – сколько заготовок, и по каким вариантам раскроев резать , чтобы в итоге получить все необходимые детали в нужном количестве при минимуме отходов.
1. Выбираем в главном меню «Сервис» - «Поиск решения…».
2. В появившемся одноименном окне «Поиск решения» производим настройки.
2.1. Назначаем целевой функцией общую длину отходов Lо Σ и вводим ссылку в окно целевой ячейки.
2.2. Устанавливаем переключатель «Равной:» в положение «минимальному значению».
2.3. Указываем ячейки с переменными Nз j в окне «Изменяя ячейки».
2.4. Вводим ограничения в одноименное окно. В качестве условий указываем необходимость равенства заданного Nд i и расчетного Nд iрасч количества деталей, а так же на переменные Nз j – расчетное количество заготовок по вариантам раскроев – накладываем ограничение: это должны быть целые числа.
3. Нажимаем кнопку «Параметры» и в выпавшем окне «Параметры поиска решения» выполняем настройки так, как показано на следующем скриншоте. Закрываем окно кнопкой «ОК».
4. В окне «Поиск решения» нажимаем кнопку «Выполнить» и ждем, пока Excel найдет решение. Это может длиться несколько минут.
5. После сохранения найденного решения кнопкой «ОК», результаты отобразятся в ячейках H7...H24 на листе Excel.
На следующей картинке показан найденный оптимальный линейный раскройный план.
Что в итоге?
Линейный раскрой в Excel заготовок для задач подобных рассмотренной в этой статье выполняется описанным выше методом за 10-15 минут! «Вручную», не зная метод индексов Канторовича, за такое время решения не найдешь.
Запустив «Поиск решения» несколько раз при разных параметрах поиска, удалось найти 5 различных планов рубки заготовок. Все 5 планов требуют одинаковое число заготовок – 93 и дают отходов всего 2,21%!!! Эти планы почти на 6% лучше, чем план, рассчитанный Покровским и более чем на 10% экономичнее «Традиционного» плана (смотри ссылку на первоисточник в первой части статьи). Очень достойный результат достигнут быстро и без применения дорогостоящих программ.
Следует заметить, что надстройка Excel Solver («Поиск решения»), использующая симплекс-метод при решении задач линейного программирования, может работать не более чем с 200 переменными. В приложении к рассмотренной нами задаче линейного раскроя это означает, что количество раскроев не может превышать 200 вариантов. Для простых задач этого достаточно. Для более сложных задач следует попробовать применить «смесь» «жадного» алгоритма и симплексного метода Solver, отобрав из полного списка раскроев не более 200 самых экономичных. Далее запасаемся терпением и добиваемся результатов. Можно попытаться разбить сложную задачу на несколько простых, но «уровень оптимальности» найденного решения будет при этом, скорее всего, ниже.
Может быть, рассмотренный вариант решения вопросов линейного раскроя и не «высший пилотаж», но однозначно шаг вперед по сравнению с «традиционным» подходом на многих производствах.
Использование надстройки MS Excel «Поиск решения» (Solver) было на блоге уже однажды рассмотрено в статье . Думаю, что этот замечательный инструмент достоин пристального внимания и еще не раз поможет изящно и быстро решить ряд новых нетривиальных задач.
P.S. Ссылки на лучшие из бесплатных программ линейного раскроя, найденных мной в Сети:
http://stroymaterial-buy.ru/raschet/70-raskroy-lineynih-izdeliy.html
http://forum-okna.ru/index.php?app=core&module=attach§ion=attach &attach_id=7508
http://forum.dwg.ru/attachment.php?attachmentid=114501&d=13823277 74
http://www.planetcalc.ru/917/
Программы по последним двум ссылкам реализуют жадные эвристики и выполняют линейный раскрой в задаче из статьи, используя аж целых 103 заготовки. Применение жадных алгоритмов оправдано в случаях необходимости снижения общего времени операции резки при слишком большом количестве вариантов раскроев в более оптимальных планах.
Ниже статьи в блоке «Отзывы» можете написать свои комментарии, уважаемые читатели.
см. Модели линейного программирования для решения задач раскроя .Пример №1 . Продукция бумажной фирмы выпускается в виде бумажных рулонов стандартной ширины - по 2 метра. По специальным заказам потребителей фирма поставляет рулоны и других размеров, для чего производится разрезание стандартных рулонов. Типичные заказы на рулоны нестандартных размеров приведены в табл.
Требуется найти такие сочетания различных вариантов разрезания стандартных рулонов, чтобы поступившие заказы полностью удовлетворить с минимальными потерями (отходами).
Рассмотрим все возможные варианты раскроя стандартного рулона, соответствующие данные приведем в табл.
| Ширина рулона(м) | Варианты раскроя рулона | Минимальное количество рулонов | |||||
| 1 | 2 | 3 | 4 | 5 | 6 | ||
| 0,5 | 0 | 2 | 2 | 4 | 1 | 0 | 150 |
| 0,7 | 1 | 1 | 0 | 0 | 2 | 0 | 200 |
| 0,9 | 1 | 0 | 1 | 0 | 0 | 2 | 300 |
| Отходы в м | 0,4 | 0,3 | 0,1 | 0 | 0,1 | 0,2 | - |
Определим переменные:
X j - количество стандартных рулонов, разрезаемых по варианту j, j =1, 2, 3,4,5, 6 .
Ограничения непосредственно связаны с требованием обеспечить изготовление требуемого количества нестандартных рулонов. Используя данные табл., получим:
2Х 2 + 2 Х 3 + 4 Х 4 + Х 5 = 150 - количество рулонов шириной 0,5 м,
X 1 + Х 2 + 2 Х 5 = 200 - количество рулонов шириной 0,7 м,
X 1 + Х 3 + 2 Х 6 =300 - количество рулонов шириной 0,9 м.
Выражение для суммарной величины потерь бумаги (отходы) (в м) имеет вид
0,4Х 1 + 0,3 Х 2 + 0,1 Х 3 + 0,1 Х 5 + 0,2 Х 6 .
Таким образом, математическая модель в общем виде имеет вид
min f(x) = 0,4 X 1 + 0,3Х 2 + 0,1Х 3 + 0,1Х 5 + 0,2Х 6 .
при ограничениях:
2Х 2 + 2 Х 3 + 4 Х 4 + Х 5 = 150
Х 2 + Х 2 + 2 Х 5 = 200
Х 2 + Х 3 + 2 Х 6 = 300
Задача о раскрое материалов
Данная задача состоит в разработке такого плана, который обеспечивает необходимый комплект изделий при минимальных отходах (по длине, площади, массе, стоимости и др.) при раскрое материалов или обеспечивает максимальное число комплектов изделий. Пример №2 . Требуется разработать оптимальный план раскроя стандартных листов стали, обеспечивая выход планового числа заготовок разного вида при минимальных суммарных отходах, если известно, что из партии листовой стали необходимо нарезать четыре вида различных заготовок в количестве b i (i = 1, 2,…,4) штук. Лист стали стандартных размеров может быть раскроен четырьмя способами. Каждому возможному способу раскроя соответствует карта раскроя. Из карт раскроя известен выход заготовок в штуках разных видов a ij (i = 1, 2,…4; j = 1,2,…,4), а также площадь отходов c j (j = 1, 2,…,n) при раскрое одного листа стали по j-му способу раскроя. Какое количество листов стали необходимо раскроить тем или иным способом, чтобы отходы были минимальными?Таблица 3
Виды | План-задание по количеству заготовок (b 1) | Выход заготовок (шт) разных видов |
|||
| 1 | 2 | 3 | 4 | ||
| 1 | 240 | 1 | 4 | 0 | 1 |
| 2 | 200 | 1 | 0 | 4 | 0 |
| 3 | 120 | 1 | 0 | 0 | 3 |
| 4 | 140 | 1 | 1 | 0 | 3 |
| Площадь отходов, м 2 (c j) | 1,4 | 0,1 | 2,1 | 0,1 | |
Составим экономико-математическую модель задачи. Обозначим через x j – количество исходного материала (листов стали), которые необходимо раскроить по одному из способов j . Ограничения в задаче должны соответствовать плановому выходу заготовок различных видов. Целевая функция сводиться к нахождению минимума отходов при раскрое
F=1,4·x 1 +0,1·x 2 +2,1·x 3 +0,1·x 4 →(min)..
Ограничения по выходу заготовок i-го вида по всем j способам раскроя:
Пример №3
. На раскрой (распил, обработку) поступает материал одного образца в количестве a единиц. Требуется изготовить из него l разных комплектующих изделий в количествах, пропорциональных числам b 1 , b 2 ,…,b l (условие комплектности). Каждая единица материала может быть раскроена n различными способами, причем использование i -го способа (i = 1, 2,…,n) дает a ik единиц k-го изделия (k = 1, 2,…,l). Необходимо найти план раскроя, обеспечивающий максимальное число комплектов.
Составим экономико-математическую модель задачи.
Обозначим через x i – число единиц материала, раскраиваемых i-ым способом, и x – число изготавливаемых комплектов изделий. Тогда целевая функция сводиться к нахождению
F=x→(max),
при ограничениях: по общему количеству материала равного сумме его единиц, раскраиваемых различными способами; по требованию комплектности и не отрицательности переменных.
Пример №4
. На предприятии имеются бревна длиной L м, которые необходимо разрезать на заготовки длиной l 1 , l 2 , l 3 м в количестве p 1 , p 2 , p 3 соответственно.
Необходимо составить оптимальный план раскройки материала, который обеспечивает минимальные отходы, при условии выполнения плана по выходу заготовок. Исходные данные приведены в таблице.
| Задача | Длина | Размеры заготовок, м | Количество заготовок, шт. | ||||
| l 1 | l 2 | l 3 | p 1 | p 2 | p 3 | ||
| 68 | 6,5 | 2,1 | 2,3 | 1,4 | 600 | 720 | 900 |
Решение: Сначала составим математическую модель нашей задачи. Возможные варианты раскроя и отходы при каждом из них запишем в виде таблицы.
| Длина заготовки | Варианты раскроя | Количество заготовок | ||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | ||
| 2,1 | 3 | 2 | 2 | 1 | 1 | 0 | 0 | 600 |
| 2,3 | 0 | 1 | 0 | 1 | 0 | 2 | 1 | 720 |
| 1,4 | 0 | 0 | 1 | 1 | 3 | 1 | 3 | 900 |
| Остаток, м | 0,2 | 0 | 0,9 | 0,7 | 0,2 | 0,5 | 0 | |
Обозначим через x i количество бревен, разрезанных по i-му варианту (i=1..7). Тогда суммарный остаток отходов запишется в виде линейной функции:
Z = 0,2x 1 + 0x 2 + 0,9x 3 + 0,7x 4 + 0,2x 5 + 0,5x 6 + 0x 7
При этом должны выполняться условия выполнения плана по количеству заготовок, т.е.
3x 1 + 2x 2 + 2x 3 + x 4 + x 5 = 600
x 2 + x 4 + 2x 6 + x 7 = 720
x 3 + x 4 + 3x 5 + x 6 + 3x 7 = 900
Таким образом, для решения поставленной задачи необходимо найти minZ при ограничениях. Поскольку minZ = -max(-Z(x)), то вместо задачи минимизации функции будем решать задачу максимизации функции:
Z = -(0,2x 1 + 0x 2 + 0,9x 3 + 0,7x 4 + 0,2x 5 + 0,5x 6 + 0x 7)
Пример №5
. Для пошива одного изделия требуется выкроить из ткани 6 деталей. На швейной фабрике были разработаны два варианта раскройки ткани. В таблице (расположенной ниже) приведены характеристики вариантов раскроя 10 м 2 ткани комплектность, т.е. количество деталей определенного вида, которые необходимы для пошива одного изделия. Ежемесячный запас ткани для пошива изделий данного типа составляет 405 м 2 . В ближайший вечер планируется сшить 90 изделий.
Построить математическую модель задачи, позволяющий в ближайший месяц выполнить план по пошиву с минимальным количеством отходов.
Таблица - Характеристики вариантов раскроя отрезков ткани по 10м 2
| Вариант раскроя | Количество деталей, шт./отрез | Отходы, м 2 /отрез | |||||
| 1 | 2 | 3 | 4 | 5 | 6 | ||
| 1 | 60 | 0 | 90 | 40 | 70 | 90 | 0,5 |
| 2 | 80 | 35 | 20 | 78 | 15 | 0 | 0,35 |
| Комплектность, шт./изделие | 1 | 2 | 2 | 2 | 2 | 2 | |
Математическая постановка задачи
Переменные задачи
В данной задаче искомые величины явно не указаны, но сказано, что должен быть выполнен ежемесячный план по пошиву 90 изделий. Для пошива 90 изделий в месяц требуется раскроить строго определенное количество деталей. Крой производится из отрезков ткани по 10 м 2 двумя различными способами, которое позволяют получить различное число деталей. Поскольку заранее неизвестно, сколько ткани будет раскраиваться первым способом и сколько - вторым, то в качестве искомых величин можно задать количество отрезков ткани по 10м 2 , раскроенных каждым из способов:
x 1 - количество отрезков ткани по 10м 2 , раскроенных первым способом в течении месяца, [отрез./мес.];
x 2 - количество отрезков ткани по 10м 2 , раскроенных первым способом в течении месяца, [отрез./мес.];
Целевая функция
Целью решения задачи является выполнение плана при минимальном количестве отходов. Поскольку количество изделий строго запланировано (90 шт./мес.), то этот параметр не описывает ЦФ, а относится к ограничению, невыполнение которого означает, что задача не решена. А критерием эффективности выполнение плана служит параметр «количество отходов», который необходимо свести к минимуму. Поскольку при раскрое одного отреза (10м 2) ткани по 1-му варианту получается 0,5м 2 отходов, а по 2-му варианту - 0,35м 2 (см. таблицу 1), то общее количество отходов при крое (ЦФ) имеет вид
L(x) = 0.5x 1 + 0.35x 2 = min,
Ограничения
Количество раскроев ткани различными способами ограничивается следующими условиями:
- Должен быть выполнен план по пошиву изделий, другими словами, общее количество выкроенных деталей должно быть таким, чтобы из него можно было пошить 90 изделий в месяц, а именно: 1-го вида должно быть как минимум 90 и деталей остальных видов - как минимум по 180 (см. комплектность в таблицу).
- Расход ткани не должен превышать месячного запаса на складе;
- Количество отрезков раскроенной ткани не может быть отрицательным.
(Общее количество деталей №1 выкроенных по всем вариантам)≥ (90 штук);
(Общее количество деталей №2 выкроенных по всем вариантам) ≥ (180 штук);
(Общее количество деталей №6 выкроенных по всем вариантам) ≥ (180 штук);
Математически эти ограничения записываются в виде
:
60x 1 + 80x 2 ≥90;
35x 2 ≥180;
90x 1 + 20x 2 ≥180;
40x 1 + 78x 2 ≥180;
70x 1 + 15x 2 ≥180;
90x 1 ≥180;
Ограничение по расходу ткани имеет следующие формы записи:
Содержательную
(общее количество ткани, раскроенной за месяц)≤ (405м 2)
Математическую
x 1 +x 2 ≤405/10
Не отрицательность количества раскроенных отрезков задается в виде
x 1 ≥ 0, x 2 ≥ 0
Таким образом, математическая модель задачи имеет вид
L(x) = 0.5x 1 + 0.35x 2 = min [м 2 отх./мес.],
60x 1 + 80x 2 ≥90;
35x 2 ≥180;
90x 1 + 20x 2 ≥180;
40x 1 + 78x 2 ≥180;
70x 1 + 15x 2 ≥180;
90x 1 ≥180;
x 1 +x 2 ≤40,5
x 1 ≥ 0, x 2 ≥ 0
Пример №6 . Имеется 69 труб для отопительной сети по 1070 см каждая. Их необходимо разрезать на трубы по 130, 150 и 310 см. Найти такой вариант раскроя поступивших труб, при котором отходы были бы минимальными.
Этап 1. Определяем варианты оптимального распила труб.
| Варианты раскроя | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| 310 | 3 | 2 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| 150 | 0 | 3 | 2 | 1 | 0 | 3 | 2 | 1 | 0 | 3 | 2 | 1 | 0 |
| 130 | 1 | 0 | 1 | 2 | 3 | 2 | 3 | 4 | 5 | 4 | 5 | 7 | 8 |
| Остатки | 10 | 0 | 20 | 40 | 60 | 50 | 70 | 90 | 110 | 100 | 120 | 10 | 30 |
Этап 2.
Составим экономико-математическую модель задачи. Обозначим через x j - количество труб, которые необходимо распилить по одному из способов j. Целевая функция сводиться к нахождению минимума отходов при распиле:
10x 1 + 20x 3 + 40x 4 + 60x 5 + 50x 6 + 70x 7 + 90x 8 + 110x 9 + 100x 10 + 120x 11 + 10x 12 + 30x 13 → min
x 1 + x 3 + x 4 + x 5 + x 6 + x 7 + x 8 + x 9 + x 10 + x 11 + x 12 + x 13 = 69
Ответ: необходимо использовать только второй вариант распила (нулевые отходы)
В нашем прайсе представлены три продукта, связанных общей темой сортировки и оптимизации:
- Программа линейного раскроя профиля и длинномерных материалов
- Программа двумерного раскроя стекла, сэндвичей, ДСП и прочих листовых материалов
- Программа оптимизации маршрута для решения логистических задач
Поставка модулей раскроя возможна как в составе комплексного решения Окнософт: Управление позаказным производством, так и в виде отдельных программ. При вызове раскройных программ из 1С, не требуется импорт – экспорт данных в промежуточные файлы. Пользователь работает в стандартном интерфейсе, а все тонкости взаимодействия 1С с внешними оптимизаторами выполняют обработки заполнения табличных частей. Для целей учета складских остатков, деловой обрези и материалов в производстве, используются стандартные документы и регистры типовых конфигураций 1С.
Линейный раскрой (профиль, труба, бревно)
Обеспечивает подтвержденный инвентаризациями процент обрези <1%. Ряд клиентов приобрели наши алгоритмы для замены программ оптимизации, поставлявшихся производителями отрезных станков. В программе использован алгоритм плотной укладки и генетический алгоритм поиска решения. На вход поступают данные о количестве и размерах изделий и деловых отходов. На выходе формируются карты раскроя с указанием тележек и ячеек. При необходимости, формируются файлы для обрабатывающих центров, станков с ЧПУ и этикетки с подробной информацией об отрезаемой заготовке и примыкающих элементах.
Живое демо на сайте
Пример ниже - не статическая картинка, а работоспособное веб - приложение.
Вы можете запустить раскрой профиля кнопкой Старт
, задать свои размеры изделий и заготовок, изменить настройки оптимизации и оценить решение.
Конечно, оптимизатор в браузере работает медленнее, чем нативная программа, но позволяет бесплатно получить пригодные для работы результаты без необходимости что либо скачивать и устанавливать на компьютер.
| 20000 р. | |
Раскрой стекла и листовых материалов
Формирует карты раскроя высочайшего качества. Обеспечивает процент экономии материала, близкий к теоретическому пределу. На 10-12% превосходит популярные программы Opty-Way, MaxCut, PerfectCut, Cutting и др. по таким показателям, как площадь неделовых остатков, общая площадь раскраиваемого материала и количество использованных целых листов
Все алгоритмы двумерного раскроя разработаны в ООО «Программы раскроя», г. Новосибирск, разработчик: Шиляев Владимир Генрихович. "Окнософт" является официальным дилером разработчика и по сублицензионному договору имеет право, как продавать программу в виде отдельного продукта, так и использовать в составе наших разработок
| 40000 р. | |
Зачем оптимизировать раскрой в программе?
Многие заказчики говорят: "У меня работает хороший напиловщик. Он прекрасно кроит стекло и профиль в голове. В мусор попадают только треугольники."
Чаще всего, это правда. Вместе с тем, одной из задач руководителя, является организация предсказуемого процесса, стабильность которого не зависит от гениальности исполнителей. Программная оптимизация распила на основании плана производства - одна из мер, приближающая к этой цели.
Если предположить, что человек может перебрать в голове комбинаций больше, чем компьютер за тот же отрезок времени, получаемый при автоматическом раскрое коэффициент обрези ~1%, выгладит привлекательнее, чем неконтролируемый и неуправляемый 1%, который может обеспечить Гений. Перекладвыание задач оптимизации на программу, может высвободить дополнительное время (1-2 часа в день), которые он потратит с пользой для бизнеса.
На самом деле, ситуация с обрезью на большинстве предприятий хуже. В спецификации закладывают коэффициенты порядка 4-7% и если цех отработает с обрезью 3-5%, это считается хорошим результатом. Снижение реального коэффициента обрези на 3-5% - это 30-50 тысяч рублей, сэкономленных на каждом миллионе, потраченном на материалы. А еще, это даст возможность не закладывать в плановую себестоимость лишние рубли и предложить покупателю более выгодные цены.
Задача оптимального расходования материалов состоит из нескольких частей
Складской учет мерных материалов
В зависимости от особенностей бизнеса, клиенты используют несколько схем учета материалов:
- На основании плана производства формируются требования - накладные с указанием продукции. Выдача дополнительных материалов (не хватило) отражается отдельными документами. Указание продукции в этих документах - желательно, но не является необходимым условием. В этом случае, в цех выдаются только те материалы, которые есть в спецификациях выпускаемой сегодня продукции и только в нужном количестве. Недостатком данного подхода можно назвать необходимость оформлять больше документов и отсутствие запаса материалов на участках (может, это достоинство?)
- Требования - накладные формируются асинхронно, без привязки к плану производства на основании заявок мастеров. Такой подход позволяет получить "живой склад" при минимальных операторских затратах кладовщика, но не защищает от перерасхода материалов. Вся ответственность за соответствие расхода спецификациям, лежит в этом случае на мастерах и рабочих. План-фактный анализ себестоимости, покажет отклонения, но может оказаться поздно
Учет деловой обрези
Возможен в сценарии, при которм требования - накладные формируются на основании плана производства. Остатки деловой обрези на начало раскроя берутся из специального регистра и могут быть скорректированы оператором в соответствии с реальными остатками. При проведении задания на производство, данные о количестве материалов, которое необходимо получить со склада, помещаются в требования - накладные, а данные об образовавшейся деловой обрези складываются обратно в регистр.
Взаимодействие исполнителей
Принимая решение об использовании оптимизатора раскроя, необходимо учесть:
- При автоматическом раскрое невозможно организовать сварку (сборку) изделий "из - под пилы", так как отрезки, относящиеся к одному изделию будут "разбросаны" по всей карте оптимизации
- Удлинняется цикл производства, требуется организовать пул для хранения заготовок. Компромиссом является раскрой партиями по 30 - 50 изделий. При этом достигаются высокие показатели обрези и получается равномерная загрузка участков сварки и фурнитуры
- Снижается оперативность, с которой цех может отреагировать на изменения плана. Если менеджеру нужно вклинить в сегодняшний план новое изделие, это ухудшит результаты оптимизации
