Устройство для оптимизации раскроя материала

 

Изобретение относится к области вычислительной техники и может быть использовано для решения целочисленных задач математического программирования. Целью изобретения является повышение быстродействия устройства за счет исключения перебора заведомо непригодных комбинаций. Решаемая устройством задача формируется следующим образом. Найти MIN SL при SL = L-ΣN<SB POS="POST">I</SB>L<SB POS="POST">I</SB>≥0

I=1,...K, где N<SB POS="POST">I</SB>-целое, 0≤N<SB POS="POST">I</SB>≤N<SB POS="POST">I</SB>

L-длина материала

L<SB POS="POST">I</SB>-длина заготовки

N<SB POS="POST">I</SB>-количество заготовок I-го типа

K-количество типов заготовок. Такая задача возникает при необходимости раскроя с минимальными остатками материала длины L на заготовки, длины которых L<SB POS="POST">I</SB> и потребляемое количество каждого типа N<SB POS="POST">I</SB>. Задача решается методом перебора комбинаций раскроя, но для повышения быстродействия комбинации, для которых δL*980, исключаются из анализа. 1 з.п. ф-лы, 2 ил.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (5l) 4 С 06 F 15/20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

5,f:.0!Ã:!!," 1

ПАТЕ;i„

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (21) 4219958/24-24 (22) 31, 03, 87 (46) 07.05 ° 89. Бюл. № 17 (72) А,10,Веревкин, П,В,Ильин и И.H.Ìàðêoâà (53) 681.333(088,8) (56) Авторское свидетельство СССР № 1180925, кл. G 06 F 15/20, 1984.

Авторское свидетельство СССР № 1247888, кл. G 06 F 15/20, 1986. (54) УСТРОЙСТВО ДЛЯ ОПТИМИЗАЦИИ РАСКРОЯ МАТЕРИАЛА (57) Изобретение относится к области вычислительной техники и может быть использовано для решения целочисленных задач математического программирования. Целью изобретения является повышение быстродействия устройства за счет исключения перебора эаведоИзобретение относится к вычислительной технике и может быть использовано для решения целочисленных задач математического программирования °

Целью изобретения является повышение быстродействия устройства эа счет исключения перебора заведомо непригодных комбинаций.

На фиг. представлена функциональная схема устройства; на фиг,2 функциональная схема блока переноса.

Устройство содержит счетчики 1 и

2, блоки 3 и 4 памяти, блоки 5 умножения, блок 6 вычитания, блоки 7 и 8 сравнения, элементы И 9 — 11, элемент

ИЛИ !2, элементы НЕ 13-15, блоки 16

„„SU„„1478223 А1 мо непригодных комбинаций. Решаемая устройством задача формируется следующим образом. Найти min8I. при

К

81.=Ь- n1>0; i 1 ... k, где и !=4 целое, 0(n; < $ L — длина материала; 1; — длина заготовки; М; — количество заготовок -ro типа; количество типов заготовок. Такая задача возникает при необходимости раскроя с минимальными остатками материала длины L на заготовки, длины которых 1; и потребляемое количест-во каждого типа N; . Задача решается методом перебора комбинаций раскроя, но для повышения быстродействия комбинации, для которых 8L (О, исключаются из анализа. 1 з.п. ф-лы, 2 ил. переноса, тактовый вход 17 устройства, вход 18 задания длины. материала устройства, входы 19 задания длин заготовок устройства, информационные выходы. 20 устройства, выход 21 признака окончания решения устройства, выход 22 признака отсутствия решения устройства и выход 23 величины остатка материала, На фиг, 2 показаны первый 24 и второй 25 входы блока 16, первый 26, второй 27 и четвертый 28 выходы блока

16, четвертый 29 и второй 30 входы блока 16, третий выход 31 блока 16 и пятый вход 32 блока 16, элементы И

33 и 34, элемент HE 35, элементы И

1478223

36-38, элементы ИЗ(И 39 и 40 и элемент HI . 41.

Устройство работает следующим образом.

Пусть требуется решить транспортную задачу типа:

Найти min 8L, 1=!,...,k прп 8I,=L (п, 1< +п,1, +,...,+п,1„,) -., О, где п; — цело е, О. и; < М.;;

Д L Й р«>к (1)

L, 1,,N, — заданные Båën÷èíû.

Такая задача возникает при необходимости раскроя с минимальными остат- 15 ками материала длины I. ня заготовки, длины которых 1, и потребляемое количество каждого типа 11, k — количество типов заготонок, В исходном состоянии все счетчики 20

1 обнулены за исключением первого, н котором установлен код

H, =mini#, и Д, так кяк решение задачи (1.) не может 25 быть нулевым кодом на всех счетчиках

1. В счетчике 2 записан код минимального значения 81.FW((, с которого имеет смысл начинать поиск. Блоки 3 памяти обнулены за исключением ячеек с адре- 30 сом N„, в которых записаны единицы, В блок 4 памяти единица записана по адресу, соответствующему 8LF, „„Èà вход 18 блока 6 вычитания подано значение L.

Работа устройства происходит под действием тактовых сигналов, поступающих с входа 17 ° Каждый шаг поиска решения выполняется в дна этапа, На перном этапе (по нулевому уровню так- gg тового сигнала на входе 17) производится оценка полученной комбинации и подготовка к второму этапу формирования следующей комбинации, который происходит при единичном уровне сигна-д ла на входе 17.

Рассмотрим первый этап ° Пусть на счетчиках 1 сформирована некоторая кодовая комбинация A,=(n,,ï,...,n <), Коды n поступают .."я блоки > умножед ния, откуда величины п11, поступают на блок 6 вычитания, Ня его выходе получают значение 8Ь, которое поступает на блоки 7 и 8 сравнения, Нулевое значение тактового сигнала, поступая через элемент HE 14 на вход блока 7 сравнения, разрешает сравнение 8L с нулем. Сигнал на выходе блока 7 сравнения равен единице, если о Ь > О. Этот сигнал проходит элемент И 9, так как на второй вход последнего через элемент HE 15 подает- ся нулевое значение тактового сигна- . ла, и разрешает блоку 8 сравнения сравнение о f, с clЬ „е,, поступающее со счетчика 2. Если д1. Й»>ек, то единичный сигнал ня выходе 22 свидетельствует об окончании поиска, коды на выходах 20 — искомые значения и, а

1 информация ня выходе ?3 показывает, при каком значении дЬщ „ это решение получено, Ilo приходу положительного фронта тактового импульса запрещается операция сравнения в блоках 7 и

8, а результаты прошедшего сравнения сохраняются до прихода следующего разрешающего сигнала, Кроме того, происходит считывание информации из блоков Зи 4 памяти по адресам, хранящимся в соответствующих счетчиках 1 и 2. Считанная информация

"1 или "0" в зависимости от выполнения равенства и =N, запоминается н блоках 3 и 4 памяти до прихода переднего фронта следующего тактового сигнала.

Способ формирования следующей кодовой комбинации А„, на нтором этапе в значительной степени зависит от результатон сравнения на первом этапе, в частности от выходного сигнала блока 7 сравнения. В связи с этим возможны следующие варианты: о1, > О, В этом случае очередной тактовый сигнал н соответствии с предложенным алгоритмом формирования

А,„ должен миновать, не изменяя содержимого, нсе четчики 1, в которых записано N;, i=1...,,г.Первый (г+1)-й счетчик 1, содержимое кдторого отлич но от N>, должен быть увеличен на единицу," о Ь <О, При этом тактовый сигнал должен пройти, не изменяя содержимого, все счетчики 1 (i=1...,r), которые обнулены, сбросить первый (г+1)-й ненулевой счетчик и увеличить на единицу содержимое следующего (r+2)-го.

При выполнении последнего действия мо>хет возникнуть ситуация, когда

n>+ =N,> в результате чего возникает еще один вариант

BI.(О, n>,<=Nq,g. В этом случае необходимо сбросить все счетчики i

=r+2..., t, и которых оказалось N<

1=г+2,...,с, и увеличить на единицу

1478223 содержимое того (t+1)-го счетчика 1, в котором и<. сН, Указанные влриянты организации перебора комбинаций реализуются блоком

16 переносл.

Ня втором этапе работы устройства тактовый сигнал на входе 17 в зависимости от сигнала ня выходе блока

7 сравнения проходит либо через элемент И 11 (при 8Lс О), либо элемент

ИЛИ 12 (при BL > О) . В последнем случае он поступает на вход 24 первого блока 16 переноса. Если в первом счетчике 1 записан код N то единичный сигнал с выхода блока 3 памяти поступает на вход 29 блока 16 переноса. В результате этого с элемента

И 33 единичный сигнал поступает ня ныход 26 блока 16 переноса и распространяется между блоками 16 переноса с выхода 26 предыдущего на вход 24 последующего до тех пор, пока не встретится (r+1)-й счетчик 1, содержимое которого меньше М . . В этом

25 случае нулевой сигнал с входа 29 (r+1)-ro блока переноса закрывает элемент И 33 и открывает элемент

И 36, В результате тактовый сигнал с входа 24, пройдя элементы ИЛИ 40 и

И 36, поступает нл выход 31 и увеличивает ня единицу содержимое (г+1)-ro счетчика 1, При 8L (О тактовый сигнал с элемента И 11 постунает на нход 25 первого блока 16 перенося, а код со счетчика

1 — на нходы 30 блока 16 переноса.

Если этот код нулевой, то он через элемент НЕ 35 разрешает прохождение тактового сигнала с входа 25 блока 4р

16 переноса через элемент И 34 на выхрд 27, Таким образом, сигнал переноса следует от одного блока 16 переноса к следующему. Достигнув (г+1)-ro счетчика 1 с ненулевым содержимым, сигнал с входа 25 одноименного блока

16 переноса проходит через элемент

И 37 и ИЛИ 39 на выход 28, По этому сигналу сбрасывается (г+1)-й счетчик

1 и подается сигнал переноса на вход

32 следующего (r+2)-го блока 16 переноса, Если в следующем (г+2)-м счетчике 1 записано N то единичный сигнал с входа 29 открывает элемент

И 38 и пропускает сигнал с входа 32 через элемент ИЛИ 39 на выход ?8 этого блока 16 переноса, а от него — на вход 32 следующего блока .16 .переноса и т.д.

Наконец, достигнуп (t+ )-го счетчика 1 (в котором n!„«N<, ), сигнал с входа 32 (t+1)-го блока 16 перенося не может пройти элемент И 38, так как на нходе ?9 нуль. В этом случае сигнал через элементы ИЛИ 40 и И 36 поступает на выход 31 этого блока 16 переноса и увеличивает на единицу содержимое (t+1)-rn счетчика 1.

Появление сигнала на выходе 26 последнего К вЂ” го блока 16 переноса означает, что но всех счетчиках 1 злписаны И1, i=1. ..k, л решение не найдено. Б этом случае необходимо увеличить Ь.щ!,, подав сигнал с ныходя 26

К-ro блока 16 переноса через элемент

И 10 на счетный вход счетчика 2 ° Единичный сигнал на выходе 28 последнего К-го блока 16 переноса свидетельствует о том, что все комбинации A подлежащие анализу, рассмотрены, причем последняя комбинация имеет вид:

0,0,. ° .О,N1,И;,!,...,Н, для которой оказалось, что Ь.с О, Ня следующем шаге тактовый сигнал с входа 25 первого блока 16 переноса проходит нл выход 27 и сбрасывает счетчики 1. В этом случае сигнал с выхода 28 К-го блока 16 переноса через элемент И 10 увеличивает 8I. << на счетчике 2, а также поступает на установочный вход первого счетчика ! для записи в него начального кода

N "", В дальнейшем процесс перебора комбинаций понторяется, но уже с новым значением Й.щ . Поиск прекращается по получении сигнала с блока 8 сравнения (решение найдено) либо по сигналу с выхода 21 блока 4 памяти, который свидетельствует о том, что

8I,

Формула изобретения

1. Устройство для оптимизации раскроя материала, содержащее группу из

К блоков переноса, где К вЂ” количество типов заготовок, группу из К блоков памяти группу из К счетчиков, группу из К блоков умножения, блок вычитания, два. блока сравнения, два элемента И, два элемента НЕ, элемент

ИЛИ, счетчик и блок памяти, причем ° тактовый вход устройства подключен к входам первого и второго элементов

НЕ и к первому входу первого элемен1478223 та И, выход тзертзого элемента III, поцклн>чеп к тзходу опроса нертзт;з о блока сранения, выход первого элемента И подключен к первому входу первого

5 блока переноса, вход задатптя ллиньт заготовки М-го типа устройства (М=I,...,К) подключен к входу первогo сомножзттеля М-го блока умножения группы, первый тзыход М-го блока пере- 10 носа группы (K) ттодтслтзчен к первому входу (M+ I )-го блока переноса группы, первый выход К-го блока переноса группы подключен к первому входу элеметтта И11И. вьзход котоРого под- 15 ключен к суммттрутощез.зу входу счетчика, выход которого является выходом величины остатка материала устройства и подклзочен к первому информационному входу тзторого блока сравнения и к адресному входу блока памяти, выход которого является выходом признака отсутствия решения устройства, выход М-ro счетчика группы является М-м информационным выходом 25 устройства и подключен к второму входу М-го блока переноса, к адресному входу М-го блока памяти и к входу второго сомножителя М-го блока умножения группы, выход которого подклю- 39 чен к входу М-го вычитаемогo блока вычитания, вход задания длиттьз материала устройства подключен к входу уменьшаемого блока вычитания, выход

KoToporÎ подключен к Второму информа" ционному входу второго блока сравнения и к информационному входу первого блока сравнения, выход которого подключен к второму входу первого элемента И и к первому входу второго 4р элемента И, выход которого подключен к входу опроса второго блока сравнения, выход которого является выходом признака окончания решения устройства, о т л и ч а ю щ е е с я тем, 45 что,с целью повышения быстродействия устройства за счет исключения пере— бора заведомо непригодных комбинаций, в него введены третий элемент

НЕ и третий элемент И, причем тактовый вход устройства подключен к nepl вому входу третьего элемента И и к входам признаков чтения всех блоков памяти групгы, выход первого блока сравнения подключен к входу третьего элемента Ш ., выход которого подключен к второму входу третьего элемента И, выход которого подключен к третьему входу первого блока переноса груптты, второй выход М-го блока переноса (МФК) группы подключен к третьему входу (M+I)-го блока переноса группы„ выход М-ro блока памяти группы подключен к четвертому входу М-ro блока переноса группы, третий выход которого подклточен к суммирующему входу

М-го счетчика группы, четвертый выход M-го блока переноса группы (МФК) подключен к входу установки в 0"

М-ro счетчика группы и к пятому входу (М+1)-го блока переноса группы, четвертый выход К-го блока переноса группы подключен к входу установки в 0" I<-го счетчика группы, к второму входу элемента ИЛИ и к установочному входу первого счетчика группы.

2. c oHo Bo no z, 1, о т л и а ю щ е е с я тем, что блок переноса содержит пять элементов И, два элемента ИЛИ и два элемента НЕ, причем первый вход блока переноса подключен к первому входу первого элемента ИЛИ и к первому входу первого элемента И, выход которого является первым выходом блока переноса, второй вход блока переноса подключен к входу первого элемента НЕ, выход которого подключен к первому входу второго элемента И, выход которого является вторым выходом блока переноса, третий вход блока переноса подключен к второму входу второго элемента И и к первому входу третьего элемента И, четвертый вход блока переноса подключен к первому входу четвертого элемента И, к второму входу первого элемента И и к входу второго элемента

II1.", выход которого подключен к первому входу пятого элемента И, выход которого является третьим выходом блока переноса, пятый вход которого подключен к второму входу первого элемента ИЛИ и к второму входу четвертого элемента И, выход которого подключен к первому входу второго элемента ИЛИ, выход третьего элемента И подключен к второму входу второго элемента ИЛИ, выход которого является четвертым выходом блока переноса, выход первого элемента ИЛИ подключен к второму входу пятого эле мента И, второй вход блока переноса подключен к второму входу третьего элемента ИЛИ, 1478223

Составитель А,Мишин

Редактор И.йулла Техред Л.Сердюкова КорректорА.Обручар

Заказ 2365/49 Тираж 669 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина,101