Оптимизатор порезки длинномеров (OptimaCut 2.0.0.17)

Обновления:

2021-04-22:
Наконец-то получил разрешение правообладателя на безоплатное распространение Оптимизатора.
В связи с этим, в разделе "Файлы для скачивания" выложил дистрибутив Оптимизатора и его исходные коды.
Также, добавил раздел "Альтернативные решения", в котором рассмотрел найденную на просторах ИНета альтернативу.
И Содержание добавил, чтоб было проще ориентироваться в статье.

Содержание

Проблематика задачи

Тот, кто выполняет порезку длинномеров (например, карнизов, профилей, труб, досок, рельсов и т.п.), наверняка сталкивается с проблемой отходов порезки. Если процесс порезки никак не оптимизирован, рано или поздно на складе начинает скапливаться огромное количество «обрезков», которые никуда нельзя применить. А выбросить их жалко, потому что они стоят денег.

Наиболее распространенным выходом из такой ситуации является разнесение себестоимости выбрасываемых «обрезков» на стоимость выпускаемых длин. Но в условиях жесткой конкуренции, в которые сегодня попадает большинство организаций, такой подход приводит к уменьшению конкурентоспособности и гибели предприятия. Возникает вопрос: «Можно ли как-нибудь применить современные технологии для уменьшения количества «обрезков», чтобы не приходилось повышать стоимость выпускаемой продукции?».

Оказалось, что можно. И как показал уже более, чем 10-летний опыт эксплуатации, данная разработка прекрасно справляется с этой задачей.

Краткое описание

Подробное описание возможностей компоненты и руководство по ее использованию можно найти в прикрепленных файлах.
Здесь же приведу некоторую вводную информацию, чтобы не качая файлов, можно было получить общее представление о том, что из себя представляет Оптимизатор.

Назначение

Оптимизатор порезки длинномеров (далее Оптимизатор) является библиотекой COM объектов (библиотека OptimaCut2), позволяющих выполнять расчет оптимальной порезки длинномеров, и предназначен для оптимизации процесса порезки длинномерных материалов. Целью оптимизации является поиск такой последовательности порезки, при которой остается минимальное количество «неходовых» длин.

Оптимизатор может выполнять порезку в двух режимах:

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

Пример

Чтобы лучше понять суть оптимизации рассмотрим пример. Имеется две трубы длиной 500см и 420см. Необходимо отрезать 300см. Можно эти 300см отрезать от 500см, и тогда останется 200см. А можно эти 300см отрезать от 420см, и тогда останется 120см. Известно, что длина 200см хорошо продается, в то время как длину 120см никто не покупает (ее придется либо дальше резать, либо вообще выбросить как отход). В этом случае оптимизатор предложит отрезать 300см от 500см (хотя на первый взгляд, кажется, что лучше порезать более короткий материал).

Естественно, Оптимизатор позволяет оптимизировать и более сложные случаи.

Системные требования

Оптимизатор работает под управлением операционных систем семейства Win32 и может быть интегрирован с любым программным обеспечением, поддерживающим работу с COM через COM-интерфейсы, либо в режиме OLE Automation. Существенных ограничений на аппаратные ресурсы компьютера оптимизатор не имеет. Но в связи с выполнением программой множества математических операций, скорость расчета порезки, и вероятность нахождения оптимального варианта в режиме порезки по таймеру, напрямую зависит от мощности процессора. Также для комфортной работы необходимо не менее 300МБ СВОБОДНОЙ оперативной памяти.

История возникновения и немного об авторах

Началась эта история , когда директор одной компании, пожелавшей остаться неназванной, Сергей Юрьевич, обратился в компанию 1С-Франчайзи, где я в то время работал, с просьбой помочь в решении задачи оптимизации порезки длинномеров.

Поиск на рынке готовых решений результатов не принес. Как и не принес результатов поиск в Интернете описаний методик решения подобных задач. Было такое ощущение, что до нас никто ничего подобного не делал. И даже не пытался делать. Во всяком случае, не афишировал свою деятельность.

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

Сергей Юрьевич согласился проинвестировать наши научные изыскания на эту тему, и я получил месяц времени на получение ответа на вопрос: сможем ли мы решить поставленную задачу?

Первым, как оказалось, достаточно важным шагом в решении задачи, было определение терминов и понятий, которыми оперирует Оптимизатор. Такие понятия, как Состояние склада, Задача порезки, Список материалов, Операции порезки, Приоритеты длин, оказались достаточно удачными и помогли в решении задачи. Собственно, задача свелась к формулировке: "Перебрать все возможные варианты порезки, и из получившихся в итоге состояний склада выбрать наиболее оптимальное".
Отдельную сложность и важность заключала в себе подзадача определения критериев оптимальности состояния склада, и сравнения разных состояний склада между собой. Но и она была решена.

Итак, результатом данной деятельности был набор прототипов (консольных exe-файлов), у которых Задача порезки была прошита прямо в коде, а результаты (с сообщениями о проделанных вычислениях) выводились в консоль.
Прототипы, для небольших задач порезки ("отрезать три изделия из четырех материалов", "отрезать четыре изделия из шести материалов", "отрезать пять изделий из шести материалов") работали относительно шустро, и давали похожие на правду результаты. Но с ростом сложности задачи порезки, экспоненциально росло и время ее решения, и объем используемой для решения памяти. Например, прототип для задачи "отрезать десять изделий из десяти материалов" выедал доступные для 32-битных консольных приложений 2 Гигабайта памяти, и валился с ошибкой.

Встала задача, простите за тавтологию, оптимизации Оптимизатора.

Мне на помощь пришел работающий со мной мой коллега, одногрупник по институту, и Друг по жизни - Агибалов Валерий (он же Valar). Он прекрасно дополнял меня на проектах, т.к. моя любовь к стройным, но не всегда жизнеспособным, теориям, компенсировалась его строгой практичностью.
И вот мы вдвоем, к , выдали первый релиз Оптимизатора, который был консольным exe-файлом, принимающим через параметры командной строки имя текстового файла с описанием Задачи порезки, и возвращающим результат расчета в текстовый файл, имя которого тоже указывалось в параметрах командной строки. При этом, он за вполне приемлемое время решал задачи оптимизации порезки, близкие к реальным задачам, возникающим на тот момент в работе компании заказчика.

С этой версией Оптимизатора компания прожила 2 года (до ). К тому времени, я уже успел вкусить все прелести "вольных хлебов", и волею судьбы оказался штатным сотрудником этой компании. Компания же за это время успела немного подрасти, и существующая версия Оптимизатора уже была узким местом в процессе обработки заказов клиентов.

Встала задача дальнейшего ускорения Оптимизатора.

Собственно, очевидным решением задачи была более тесная интеграция Оптимизатора с базой 1С, и уход от обмена текстовыми файлами, который сам по себе занимал много времени.
Именно так и появилась идея реализовать Оптимизатор в виде AddIn-компоненты для 1С:Предприятие 7.7.
Эта деятельность заняла у меня несколько месяцев плотной работы, и в вышел первый релиз нового Оптимизатора, который уже носил имя OptimaCut (версии 1.6.0.0). В процессе этой работы, были не просто перенесены в каркас AddIn-компоненты существующие алгоритмы, но и проведена работа по существенной их оптимизации, что дало еще больший прирост скорости расчета.

Далее, в течение 2006-го года, были точечные доработки Оптимизатора, связанные с исправлением выявленных ошибок и дальнейшей оптимизацией по скорости. Так в в мир вышла версия 1.6.0.1. В - версия 1.6.0.2. А в - версия 1.6.0.3.

Далее компания пришла в своем развитии к необходимости перехода на платформу 1С:Предприятие 8.0. Естественно, встал вопрос адаптации Оптимизатора под новую платформу. Очевидным было просто переписать Оптимизатор в виде AddIn-компоненты для 1С:Предприятие 8.0. Но понимание того, что при следующем обновлении платформы нужно будет снова переписывать Оптимизатор, подтолкнуло к слегка неожиданному для нас, но вполне размуному (с этого и надо было начинать) решению. А именно - сделать Оптимизатор в виде COM-компоненты. И пусть при этом немного потерять в скорости взаимодействия базы с Оптимизатором (за счет менее тесной интеграции с 1С), зато приобрести гибкость и мобильность за счет получения возможности интегрировать Оптимизатор в любые системы (хоть в Excel). При этом потеря скорости была незначительной, т.к. AddIn, по сути своей, были теми же COM-компонентами, которые просто немного более тесно интегрированы в 1С:Предприятие.
COM-технология к тому времени уже была достаточно хорошо проверена временем. К тому же на ней столько всего было реализовано в Windows, что было очевидно, что Microsoft откажется от нее очень не скоро. И как показало время (с тех пор прошло больше 10 лет), мы сделали правильный выбор.

Пару месяцев интенсивного изучения книги по разработке COM-компонент, с преломлением получаемых знаний к задаче написания нового Оптимизатора, привели к появлению в первого релиза COM-компоненты (OptimaCut версия 2.0.0.01), реализующей COM-объекты OptimaCut2.ХХХ. Далее, в течение месяца шла обкатка и тестирование новой компоненты на живой базе. Исправление обнаруженных ошибок и дальнейшая оптимизация (в том числе кэширование уже рассмотреных операций порезки), завершились выходом в версии 2.0.0.16.

Эта версия прожила в эксплуатации год, и была подключена к внедренной на тот момент конфигурации на базе платформы 1С:Предприятие 8.0. Я тогда в компании уже не работал. Но связь с ними держал. Поэтому когда, занимающийся тогда у них поддержкой 1С, Омелянчук Павел обнаружил и исправил в Оптимизаторе ошибку очистки памяти, он прислал исправление мне, чтобы я пересобрал и выпустил новую версию Оптимизатора. Что я и сделал.
Так, в в мир вышел крайний релиз Оптимизатора (версия 2.0.0.17), который используется в компании и по .

Альтернативные решения

Как я уже писал выше, на тот момент на рынке не было совершенно никаких альтернативных решений.
При подготовке этой статьи мне стало интересно - появилось ли за прошедшее время что-то на рынке по данной теме?
И я нашел весьма интересное, как на мой взгляд решение: Окнософт:cutting - Программа линейного раскроя
Особенно оно интересно тем, что оно использует "Генетический алгоритм", который я видел как путь дальнейшего совершенствования Оптимизатора (если бы передо мной поставили такую задачу).

Из того, что я понял, из описания на их сайте, в Окнософт:cutting нет такого понятия, как приоритеты длин. Соответственно, это решение не позволяет учитывать тот факт, что обрезки 10 и 20 см могут очень хорошо продаваться (например, на образцы), обрезки в диапазоне от 30 до 110 см практически вообще не продаются, длины 120, 140 и 200 см - являются "стандартными" и очень хорошо продаются, а длины 130, 150-190 см продаются плохо (но из них можно изготовить хорошо продающиеся длины - соответственно их приоритет выше, чем у длин от 30 до 110 см).
В этом плане - OptimaCut значительно лучше.

Также заметил, что Окнософт:cutting не замечает возможности взять из материалов уже готовое изделие без всяких отпиливаний.
А OptimaCut прекрасно справляется с этой задачей.

С другой стороны, Окнософт:cutting позволяет учитывать ширину распила, чего не умеет делать OptimaCut.

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

В-общем, если бы эти два продукта скрестить, то получился бы практически идеальный оптимизатор порезки длинномеров. А так - прийдется выбирать - какие возможности оптимизатора более востребованы именно в Вашей деятельности.

Файлы для скачивания

Документация, позволяющая получить представление о возможностях Оптимизатора:
Описание возможностей.doc (83 КБ)
Справочное руководство.doc (642 КБ)

Архив с дистрибутивом Оптимизатора (здесь же можно найти и лицензионное соглашение):
OptimaCut2_Distribution.7z (334 КБ)

Архив папки проекта на MS Visual Studio (С++) 2008:
OptimaCut2.7z (3 МБ)

Для разработчиков, которые захотят доработать или модифицировать Оптимизатор, может оказаться полезным следующий документ:
Руководство разработчика.doc (106 КБ)

Для выполнения модульного тестирования объектов Оптимизатора прикладываю архив с обработками для соответствующих версий 1С, а также с эксель-файлом, где на VBA написаны юнит-тесты:
TestOptimaCut2.7z (63 КБ)