Задача: На производстве для монтажа электрических цепей выпускаемой продукции применяются контактные колодки типа LTA. Контактные колодки поставляются в виде линеек по 12 контактов в каждой. В изделиях же применяются колодки с разным числом контактов (от 2 до 12), которые получают путем отрезания нужного числа контактов от 12 контактной полоски прямо на складе предприятия. Колодки LTA имеют специальную конструкцию, рассчитанную на разрезание. Отрезать нужную часть колодки можно даже ножом. В каждом изделии применяются десятки колодок разной длины. Требуется создать программу рассчитывающую оптимальный раскрой разъемов на все изделия месячного плана. Входной информацией для программы является список всех колодок каждого размера, необходимых для изготовления всех изделий по текущему плану с указанием требуемого количества колодок каждого размера. На выходе программа должна выдать план оптимального раскроя. Имеется в виду, что программа должна определить, как разрезать двенадцатиконтактные планки так, что бы на план ушло минимально возможное количество исходных планок и отходы при разрезании были бы минимальными.

Задача была поставлена и решена для реального производства. В данной статье приводится описание разработанного для этой цели алгоритма. Кроме того, на сайте вы можете загрузить и испытать в работе действующую программу, выполненную в виде внешнего отчета для 1С. Файл отчета вы можете открыть в конфигураторе для просмотра и изучения. Ссылку для скачивания отчета вы можете найти здесь: скачать.

Вообще то, задача оптимального раскроя - сложная математическая задача и в общем виде пока не решена. Но для данного конкретного случая удалось найти достаточно простой алгоритм, который было не трудно воплотить в жизнь. Было решено применить алгоритм перебора. Но для того, что бы максимально сократить количество отходов при раскрое подбор было решено делать в два этапа. На первом этапе было введено понятие "Идеальный раскрой". Под идеальным раскроем понимается схема раскроя одной 12 контактной колодки на набор более мелких при котором все полученные части полностью пойдут на план. Для того, что бы этот подбор был возможен сначала был составлен список всех возможных вариантов идеального раскроя. На первом этапе программа выбирает из списка по очереди каждый такой вариант и проверяет, можно ли его применить исходя из плана. Если можно, то определяется сколько раз можно применить выбранный раскрой. Затем в выходной список раскроев записывается этот вариант и количество его применений, а из плана вычитается все уже полученные таким образом наборы колодок. И подбор продолжается снова уже с другим вариантом идеального раскроя. Если очередной идеальный раскрой применить не возможно, он пропускается. Первый этап подбора заканчивается тогда, когда будут перебраны все варианты из списка "Идеальных".

Для записи вариантов идеального раскроя применяются строки состоящие из цифр, означающих размер отрезаемой колодки. Цифры записываются через символ "+" и без пробелов. Ниже приводится фрагмент этого списка. Полный список вы можете увидеть, загрузив пример обработки "Оптимальный раскрой колодок" ( скачать) и открыв ее в конфигураторе.

Список составлялся по определенному алгоритму, начиная с вариантов минимального разрезания. Первоначально он выглядел не так, как вы видите на картинке. Порядок следования вариантов был другой. Для того, что бы гарантированно перебрать все варианты идеального раскроя при составлении списка я исходил из размеров первого отрезаемого куска. Размеры этого куска постепенно уменьшаются от варианта к варианту от максимально возможного до минимального. Поэтому первым вариантом стал вариант, когда колодка вообще не разрезается. Следующий вариант включает в себя колодку на один контакт короче максимального (11 контактов). Такой вариант, очевидно, всего один (11+1). Следующий вариант имеет размер первого отрезаемого куска 10 контактов. Возможны два варианта раскроя в которых размер первого куска равен 10. Это 10+2, 10+1+1. Следующий вариант раскроя - это вариант с размером первого отрезаемого куска 9. Тут возможны три варианта раскроя: 9+3, 9+2+1, 9+1+1+1. Именно в таком порядке я их и располагаю. То есть сначала варианты в которых дополнительные куски имеют максимально возможный размер, а в конце варианты с самыми мелкими кусками. Далее идут пять вариантов в которых первый отрезаемый кусок имеет размер 8. Это 8+4, 8+3+1, 8+2+2, 8+2+1+1 и 8+1+1+1+1. Таким же образом по той же схеме составляем и остальные варианты раскроя.

7+5, 7+4+1, 7+3+2, 7+3+1+1, 7+2+2+1, 7+2+1+1+1, 7+1+1+1+1+1.
6+6, 6+5+1, 6+4+2, 6+4+1+1, 6+3+3, 6+3+2+1, 6+3+1+1+1, 6+2+2+2, 6+2+2+1+1, 6+2+1+1+1+1, 6+1+1+1+1+1+1.

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

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

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

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

Как видно из рисунка, результат расчета - это таблица из пяти колонок. В первой колонке указывается тип разъема (в нашем случае тип не указывается). Во втором столбце - вариант раскроя 12 контактной колодки на части. В третьей колонке указывается количество данного варианта раскроя на план. В следующих двух столбцах указывается количество отходов, которые останутся при раскрое по данному варианту. В графе "Ост разм" указывается размер отхода, а в графе "Ост кво" - количество таких "обрезков".