Устройство для оптимизации раскроя материала Советский патент 1989 года по МПК G06F17/00 

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

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

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

Устройство содержит счетчики 1 и 2, блоки 3 и 4 памяти, блоки 5 умножения, блок 6 вычитания, блоки 7 и 8 сравнения, элементы И 9-11, элемент ИЛИ 12, элементы НГ 13-15, блоки 16

переноса, тактовый вход 17 устройства, вход 18 задания длины материала устройства, входы 19 задания длин заготовок устройства, информационные выходы 20 устройства, выход 21 признака окончания решения устройства, выход 22 признака отсутствия решения устройства и выход 23 величины остатка материала.

На фиг. 2 показаны первый 24 и второй 25 входы блока 16, первый 26, второй 27 и четвертый 28 выходы блока 16, четвертый 29 и второй 30 входы блока 16, третий выход 31 блока 16 и пятый вход 32 бпока 16, элементы И 33 и 34, элемент НЕ 35, элементы И

36-38, элементы ИЛИ 39 и АО и элемент НЕ 4 1.

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

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

Найти niin SL, 1 1 , ... ,k при ((n,l, ,}+,... ,+п,1 к) О, где п,- - целое, ,6N,;tO

J L Ј (5Lji,anC;(I)

L, li,Ni - заданные величины.

Такая задача возникает при необхоли oL 0. Этот сигнал проходит элемент И 9, так как на второй вход последнего через элемент НЕ 15 подает- ся нулевое значение тактового сигнала, и разрешает блоку 8 сравнения сравнение JL с Ь,«ек поступающее со счетчика 2. Если oL.dLmeK, то единичный сигнал на выходе 22 свидетельствует об окончании поиска, коды на выходах 20 - искомые значения rij , a информация на выходе 23 показывает, при каком значении oLmei( это решение1 получено. По приходу положительного

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

I=1,...K, где N_I-целое, 0≤N_I≤N_I

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

L_I-длина заготовки

N_I-количество заготовок I-го типа

K-количество типов заготовок. Такая задача возникает при необходимости раскроя с минимальными остатками материала длины L на заготовки, длины которых L_I и потребляемое количество каждого типа N_I. Задача решается методом перебора комбинаций раскроя, но для повышения быстродействия комбинации, для которых δL*980, исключаются из анализа. 1 з.п. ф-лы, 2 ил.

димости раскроя с минимальными остат- 15 Фронта тактового импульса запрегаает

ками материала длины L на заготовки, длины которых 1-i и потребляемое количество каждого тина , k количество типов заготовок,

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

N minfNjL/l l ,

так как решение задачи (1-) не может быть нулевым кодом на всех счетчиках 1. В счетчике 2 записан код минимального значения ОЦшо с которого имеет смысл начинать поиск. Блоки 3 памяти обнулены за исключением ячеек с адре- сом N,, в которых записаны единицы. В блок 4 памяти единица записана по адресу, соответствующему $LAWкс. Ка вход 18 блока 6 вычитания подано значение L.

Работа устройства происходит под действием тактовых сигналов, поступающих с входа 17. Каждый шаг поиска

. R этом случае очередной тактовый сигнал в соответствии с предложенным алгоритмом формирования

записано Ni, ,...,г.Первый (г+1)-й счетчик 1, срдержимое которого отлично от , должен быть увеличен на

решения выполняется в два этапа. На первом этапе (по нулевому уровню так- 40 Ai Д°лжен миновать, не изменяя сотового сигнала па входе 17) произво- держимого, все счетчики 1, в которых днтся сценка полученной комбинации и подготовка к второму этапу формирования следующей комбинации, который происходит при единичном уровне, сигна-45 6ДИНИЦУ ла на входе 17., При этом тактовый сигнал

Рассмотрим первый этап. Пусть на счетчиках 1 сформирована некоторая кодовая комбинация А4(п|,п,...,Пц).

50

Коды п( поступают аз блоки 5 умноже- , откуда величины njl-i поступают

ния,

на блок 6 вычитания. Па его выходе получают значение OL, которое поступает на блоки 7 и 8 сравнения. Нулевое значение тактового сигнала, поступая через элемент НЕ 14 на вход блока 7 сравнения, разрешает сравнение L с нулем. Сигнал на выходе блока 7 сравнения равен единице, ес55

должен пройти, не изменяя содержимого, все счетчики 1 (,..,г), которые обнулены, сбросить первый (г+1)-й ненулевой счетчик и увеличить на единицу содержимое следующего (г+2)-го. При выполнении последнего действия может возникнуть ситуация, когда . в результате чего возникает еще один вариант

, . В этом случае необходимо сбросить все счетчики i r+2,...,t, в которых оказалось N$ , ,...,t, и увеличить на единицу

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

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

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

. R этом случае очередной тактовый сигнал в соответствии с предложенным алгоритмом формирования

Ai Д°лжен миновать, не изменяя содержимого, все счетчики 1, в которых 6ДИНИЦУ , При этом тактовый сигнал

записано Ni, ,...,г.Первый (г+1)-й счетчик 1, срдержимое которого отлично от , должен быть увеличен на

Ai Д°лжен миновать, не изменяя содержимого, все счетчики 1, в которых 6ДИНИЦУ , При этом тактовый сигнал

0

5

должен пройти, не изменяя содержимого, все счетчики 1 (,..,г), которые обнулены, сбросить первый (г+1)-й ненулевой счетчик и увеличить на единицу содержимое следующего (г+2)-го. При выполнении последнего действия может возникнуть ситуация, когда . в результате чего возникает еще один вариант

, . В этом случае необходимо сбросить все счетчики i r+2,...,t, в которых оказалось N$ , ,...,t, и увеличить на единицу

в котором nt.(NtH.

Укачанные варианты организации перебора комбинаций реализуются блоком 16 переноса.

На втором этапе работы устройства тактовый сигнал на входе 17 в зависимости от сигнала на выходе блока 7 сравнения проходит либо через элемент И 11 (при oL 0), либо элемент ИЛИ 12 (при-сУь 0). В последнем случае он поступает на вход 24 первого блока 16 переноса. Если в первом счетчике I записан код N,то единичный сигнал с выхода блока 3 памяти поступает на вход 29 блока 16 переноса. В результате этого с элемента И 33 единичный сигнал поступает на выход 26 блока 16 переноса и распространяется между блоками 16 переноса с выхода 26 предыдущего на вход 24 последующего до тех пор, пока не встретится (г+1)-й счетчик 1, содержимое которого меньше N. В этом i случае нулевой сигнал с входа 29 (г+1)-го блока переноса закрывает элемент И 33 и открывает элемент И 36, В результате тактовый сигнал с входа 24, пройдя элементы ИПИ 40 и И 36, поступает на выход 31 и увеличивает на единицу содержимое (г+1)-г счетчика 1.

ПриоЬ 0 тактовый сигнал с элемета И 1 1 поступает на вход 25 первого блока 16 переноса, а код со счетчика 1 - на входы 30 блока 16 переноса. Если этот код нулевой, то он через элемент НЕ 35 разрешает прохождение тактового сигнала с входа 25 блока 16 переноса через элемент И 34 на выход 27. Таким образом, сигнал переноса следует от одного блока 16 переноса к следующему. Достигнув (г+1)-г счетчика 1 с ненулевым содержимым, сигнал с входа 25 одноименного блока 16 переноса проходит через элемент И 37 и ИЛИ 39 на выход 28. По этому сигналу сбрасывается (г+1)-й счетчик 1 и подается сигнал переноса на вход 32 следующего (г+2)-го блока 16 переноса. Если в следующем (г+2)-м счетчике 1 записано N, то единичный сигнал с входа 29 открывает элемент И 38 и пропускает сигнал с входа 32 через элемент ИЛИ 39 на выход 28 этого блока 16 переноса, а от него - на вход 32 следующего блока 16-переноса и т.д.

ка 1 (в котором Nj, 1 , сигнал с входа 32 (t+I)-ro блока 16 переноса не может пройти элемент И 38, так как на входе 29 нуль. В этом случае сигнал через элементы ИЛИ 40 и И 36 поступает на выход 31 этого блока 16 переноса и увеличивает на единицу содержимое (t+l)-ro счетчика 1.

Появление сигнала на выходе 26 последнего К-го блока 16 переноса означает, что во всех счетчиках 1 записаны NJ , i l,...,k, а решение не наи5 дено. В этом случае необходимо увеличить о IJ|rie , подав сигнал с выхода 26 К-го блока 16 переноса через элемент И 10 на счетный вход счетчика 2. Единичный сигнал на выходе 28 последнео го К-го блока 16 переноса свидетельствует о том, что все комбинации А1, подлежащие анализу, рассмотрены, причем последняя комбинация имеет вид: 0,0, . . . 0,NpNJ4.(,. t . ,NK, для которой

5 оказалось, что .

Ка следующем шаге тактовый сигнал с входа 25 первого блока 16 переноса проходит на выход 27 и сбрасывает счетчики 1. В этом случае сигнал с

0 выхода 28 К -го блока 16 переноса через элемент И 10 увеличивает . на счетчике 2, а также поступает на установочный вход первого счетчика 1 для записи в него начального кода

5 N

В дальнейшем процесс перебора

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

5

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

0 К блоков переноса, где К - количество типов заготовок, группу из К блоков памяти,, группу из К счетчиков, группу из К блоков умножения, блок вычитания, два блока сравнения, два

5 элемента И, два элемента НЕ, элемент ИЛИ, счетчик и блок памяти, причем- тактовый вход устройства подключен к входам первого и второго элементов НЕ и к первому входу первого элемен71А

та И, выход первого элемента НЕ подключен к входу опроса перш го блока сранения, выход первого элемента И подключен к первому входу первого блока переноса, вход задания длины заготовки М-го типа устройства (М 1,. . ., К) подключен к входу первого сомножителя М-ro блока умножения группы, первый-выход М-го блока пере- носа группы () подключен к первому входу (М-Н)-го блока переноса группы, первый выход К-ro блока переноса группы подключен к первому нхо ду элемента ИЛИ, выход которого под- ключей к суммирующему входу счетчика, выход которого является выходом величины остатка материала устройства и подключен к первому информационному входу второго блока сравне- ния и к адресному входу блока памяти, выход которого является выходом признака отсутствия решения устройства, выход счетчика группы является М-м информационным выходом устройства и подключен к второму входу М-го блока переноса, к адресному входу М-го блока памяти и к входу второго сомножителя М-го блока умножения группы, выход которого подклю- чен к входу М-го вычитаемого блока вычитания, вход задания длины материала устройства подключен к входу уменьшаемого блока вычитания, выход которого подключен к второму информа ционному входу второго блока сравнения и к информационному входу первого блока сравнения, выход которого подключен к второму входу первого элемента И и к первому входу второго элемента И, выход которого подключен к входу опроса второго блока сравнения, выход которого является выходом признака окончания решения устройства,

отличающееся тем,

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

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

8

0 5 0 с 0

5

0

.

входу первого блока переноса группы, второй выход М-го блока переноса (М#К) группы подключен к третьему входу (М+1)-го блока переноса группы, выход М-го блока памяти группы подключен к четвертому входу К-го блока переноса группы, третий выход которого подключен к суммирующему входу М-го счетчика группы, четвертый выход М-го блока переноса группы () подключен к входу установки в О М-го счетчика группы и к пятому входу (М+1)-го блока переноса группы, четвертый выход К-го блока переноса группы подключен к входу установки в О К-го счетчика группы, к второму входу элемента ИЛИ и к установочному входу первого счетчика группы.

чЗ-1

Ч

Iflj /7

Фиг/

К

jf

i. | ЛУ

31

А

Я

Фй.г