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

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

Цель изобретения - повышение быстродействия устройства.

На чертеже представлена функцио-. нальная схема устройства.

Устройство содержит элемент И 1, группу счетчиков 2, группу блоков 3 памяти, информационные выходы 4 устройства, первую группу элементов И 5, вторую группу элементов И 6, элемент И /, группу элементов 8 задержки, группу регистров 9, регистр 10, первую группу триггеров 11, вторую группу триггеров 12, группу коммутаторов 13, блоки 14 и 15 сравнения, накапливаю- щий сумматор 16, группу селекторов 17, выход 18 признака отсутствия решения, выход 19 признака окончания решения, группу блоков 20 вычисления текущего количества раскроенного материала, блок 21 элементов ИЛИ и вход 22 устройства.

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

Пусть требуется решить задачу рас- кроя материала. Задано: L - общая длина материала; 1; - требуемые длины кусков; N; - потребное число 1 ; ft - допустимая величина отходов.

Найти а; - целое (i 1,...n),

такое, что

и 06L- ail;60. (1)

W1

Причем при

кусков

требуется больше, чем имеется материала, так как только при этом условии задача имеет смысл; невыполненный план ( N;) будет выполнен на следующих кусках.

В основу достижения поставленной цели положена следующая идея. Для оценки пригодности каждой комбинации А; в качестве решения задачи (1) необходимо сформировать очередную

п комбинацию А; , вычислить сумму а.С;.

J ,.

определить величину fr: и сравнить ее с допустимой величиной 8,.

Рассмотрим обычный последовательный процесс формирования комбинаций

А при п

3, N, 4, N4 5, N.

4:

Л /jО1234 5 6 7...29 30 31...145

а,01234 0 1 2...4 О 1...4

аг00000 1 1 1...5 0 0...5

а5ООООО О О О...О 1 1...4

Очевидно, что для вычисления 8; при переходе от j « 1 до j 4 на каждом шаге из величины L достаточно вычитать 1,, однако, при переходе от 4-й к 5-й комбинации и других переходах, когда происходит переполнение какой- либо из величин а:, величину oj приходится вычислять заново. Однако, если изменить порядок следования комбинаций А-, то каждый шаг будет требовать выполнения только одной операции сложения. Действительно, рассмотрим следующий процесс: A /j 01 23456789 10 11 12...

а, 01234432100 1 2...

а, 00000111112 2 2...

а 00000000000 О О...

При таком способе чередования комбинаций на каждом шаге изменяется на единицу значение только одной величины а;-, при этом для формирования $j достаточно выполнить одну операцию сложения или вычитания (в зависимости от того, в какую сторону изменяется а). Последовательный процесс формирования uj имеет вид:

J -L -1, - 1, 14- 1, -

. - j

f

+ 1 , + 1 4 +,

выходе блока 15 сравнения появляется единичный сигнал в том случае, если содержимое младших разрядов сумматора 16 меньше 6 доп Если оба перечисленных условия выполнены, то на выходе элемента И 1 появляется единичный

I LI-L -LI-LI-.., . , сигнал, который поступает на вход

элемента И 7, на второй вход Такой принцип формирования комбинаций Q которого подается знаковый разряд

&,

V 1

Si 1, - 12 - 1, - 1, позволяет достаточно быстро решать задачи (1) даже при значительных величинах N;.

Перед началом работы триггеры 11 и 12 и счетчики 2 обнулены, т. е. элементы И 5 закрыты, элементы И 6 открыты, на адресных входах блоков 3 памяти установлен код адреса нулевой ячейки; в i-e блоки 3 памяти по адресам О и N, записаны единицы, а остальные ячейки обнулены; в 1-х регистрах 9 записаны величины 1, ; в регистре 10 записана величина S.on; в сумматоре 16 записана величина L (цепи сброса и начальной установки перечисленных элементов не тказаны). Для определенности положим, что

п 3; N.

4; Na 5; N

а ъ

Первый импульс с входа 22 устройства через открытый элемент И 6 блока 20 будет подан коммутатором 13 на суммирующий вход счетчика 2, в результате чего на его выходе установится код адреса первой ячейки блока 3 памяти. Поскольку эта ячейка обнулена, то этот же импульс, поступив через элемент 8 задержки на вход признака чтения блока 3 памяти, считает ноль на вход триггера 11, т.е. состояние триггера 11 не изменится. Тот же импульс поступит на вход подключения селектора 17, благодаря чему содержимое lf первого регистра 9 будет подано в обратном коде на вход слагаемого накапливающего сумматора 16, где образуется величина L - 1, 0,, по окончании тактового импульса на входе 22 (по его заднему фронту). После

с сумматора 16. Таким образом, CHI- нал на выходе 19 появляется, если

&i °&&,«лд, ра,Р 8лоД& стр 0, что свидетельствует о том, что код А

5 Г О 0), установившийся на ин- форм ционных выходах 4 устройства, является решением поставленной задачи. Если хотя бы одно из перечисленных условий не выполняется, то

о по прохождении второго импульса по входу 22 описанный процесс повторяется. В результате на выходах 4 установится код Аг {2, 0, 0}, который в случае, если полученная в суммато5 ре 16 величина 82 L - 1, - 1 удовлетворяет перечисленным трем условиям, является решением задачи. В противном случае аналогичный процесс повторится и по прохождении третье0 го импульса.

Четвертый импульс обеспечит вычисление в сумматоре 16 величины 64. L - 1, - 1, - 1 - 1, . Допустим, однако, что и код А4 , О, 0 не является решением поставленной задачи. Поскольку в четвертой ячейке блока 3 памяти записана единица, четвертый импульс, пройдя через элемент 8 задержки на вход признака

5

чтения блока 3 памяти, считает единицу на вход триггера 11, триггер 11 перейдет в противоположное состояние, что вызовет открытие элемента И 5, закрытие элемента И 6 и переход

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

Изобретение относится к области вычислительной техники и может быть использовано для решения задачи оптимального раскроя материала по критерию непревышения наперед заданного допустимого остатка. Целью изобретения является повышение быстродействия устройства. Устройство содержит элемент И 1, группу из T счетчиков 2, где T - количество типов кусков раскроенного материала, группу из T блоков 3 памяти, информационные выходы 4 устройства, группы из T элементов И 5, 6, элемент И 7, группу из T элементов 8 задержки, группу из T регистров 9, регистр 10, две группы триггеров 11,12, группу из T коммутаторов 13, блоки 14, 15 сравнения, накапливающий сумматор 16, группу из T селекторов 17, выход 18 признака отсутствия решения, выход 19 признака окончания решения, группу из T блоков 20 вычисления количества раскроенного материала и блок 21 элементов ИЛИ. Цель изобретения достигается изменением последовательности перебора комбинаций раскладки кусков по длине материала. 1 ил.

этого начинается проверка пригодности gg вход счетчика 2. Выходной сигнал триг- полученного решения. Многоразрядное гера 12 поступит на управляющий вход

селектора 17, что обеспечит отключение обратных и подключение прямых выходов регистра 9 к выходам селектора 17, который отключен от сумматора 16

сравнение S, с о ог, организовать технически сложно, поэтому эта проверка проводится следующим образом.

Блок 14 выдает единичный сигнал, gg если в сумматоре 16 в старших разрядах - нули. Младшие разряды сумматора 16 в блоке 15 сравнения сравниваются

.8

о«г

поступающим с регистра 10. На л

до прихода сигнала с элемента И 6. Пятый импульс по входу 22 через открытый элемент И 5 поступит на первый вход открытого элемента И 6 блодо прихода сигнала с элемента И 6. Пятый импульс по входу 22 через открытый элемент И 5 поступит на первый вход открытого элемента И 6 блока 20, благодаря чему в нем произойдут процессы, аналогичные описанным. В результате на выходах 4 устройства формируется код Ау |4, 1, , Этот же импульс поступит на вход подключения соответствующего селектора 17, результате чего содержимое 1г соответствующего регистра 9 поступит в обратном коде на вход сумматора 16, и по окончании тактового сигнала величина $5 L-1, -1, -1, будет в него записана. В случае равенства нулю старших разрядов сумматора 16, а также выполнения услопоявится сигнал на

ч+

1,+

ю

15

вий&5 0 и 85 SAon выходе 19 устройства, который будет свидетельствовать, что код А 5 ГА, 1, 0 является решением задачи. В любом случае пятый тактовый импульс 20 в блоке 20 поступит через элемент 8 задержки на вход чтения блока 3 памяти и, поскольку содержимое счетчика 2 по пятому импульсу не изменилось, прочтет опять из четвертой ячейки- блока -5 3 памяти единицу, которая поступит на счетный вход триггера 11. Триггер 11 перейдет из единичного в нулевое состояние, в результате чего закроется элемент И 5, откроется элемент И 6 30 и первом блоке 20. Триггер 12 останется в прежнем состоянии.

В дальнейшем, если сформированный

не явился % решеникод А5 4, 1, 0}

ем задачи, очередной (шестой) импульс 35 ков памяти, где Т - количество

1,+ X, Но прохождении того импульса счетчик 2 первого 20 обнулится, на выходах 4 уста код АО о, 1, 0, в сумматор образуется величина Ј 9 L - - 1 , - 1, - 1 - 12 + 1 + 1(

+ 1« + 1 L - Ig. Девятый та импульс после задержки на элем 8 прочтет единицу из нулевой я блока 3 памяти на вход триггер что вызовет его переход в прот ложное состояние, открытие эле И 5, закрытие элемента И 6, пе триггера 12 в противоположное ние. Благодаря этому по прохож десятого импульса установится A (Q 0, 2, 0), а в сумматоре разуется величина в L - 1г - В дальнейшем работа устройства кает в соответствии с описанны ритмом. Если вплоть до прохожд 104-го импульса решение так и дет найдено, то при прохождени го импульса появится сигнал на де 18 устройства, который свид ствует о том, что при заданных ходных данных решить задачу не можно .

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

Устройство для решения зада раскроя материала, содержащее Т

поступит через открытый элемент И 6 первого блока 20 и коммутатор 13 на вычитающий вход первого счетчика 2, в результате чего на его выходе установится адрес третьей ячейки блока па-до мяти. Этот же шестой импульс после прохождения через элемент 8 задержки считает ноль из третьей ячейки, т.е„ триггер 11 останется в прежнем состоянии. На выходах 4 установится код А6 45

-Гз, 1, 0, а по окончании тактового сигнала в сумматоре 16 образуется величина 1, - 1, - 1, - 1, -lt + 1,.

Далее, по прохождении седьмого им- 50 пульса будет прочитан ноль из второй ячейки блока 3 памяти первого блока 20, на выходных шинах 4 установится код AT - О, 1, , в сумматоре 16 образуется величина Ј5 1

-1,- 1,- 1г+ 1,+ 1, ; по прохождении восьмого импульса установится код

55

1, 0, в сумматоре 16 образуется величина б8 L - 1,- 1,- 1,ke

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

ч+

1,+

5

0 50

5 ков памяти, где Т - количество

1,+ X, Но прохождении девятого импульса счетчик 2 первого блока 20 обнулится, на выходах 4 установится код АО о, 1, 0, в сумматоре 16 образуется величина Ј 9 L - 1 - - 1 , - 1, - 1 - 12 + 1 + 1( +

+ 1« + 1 L - Ig. Девятый тактовый импульс после задержки на элементе 8 прочтет единицу из нулевой ячейки блока 3 памяти на вход триггера 11, что вызовет его переход в противоположное состояние, открытие элемента И 5, закрытие элемента И 6, переход триггера 12 в противоположное состояние. Благодаря этому по прохождении десятого импульса установится код A (Q 0, 2, 0), а в сумматоре 16 образуется величина в L - 1г - 1. В дальнейшем работа устройства протекает в соответствии с описанным алгоритмом. Если вплоть до прохождения 104-го импульса решение так и не будет найдено, то при прохождении 105- го импульса появится сигнал на выходе 18 устройства, который свидетельствует о том, что при заданных исходных данных решить задачу невозможно .

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

Устройство для решения задачи раскроя материала, содержащее Т бло5 ков памяти, где Т - количество

о 5

0

5

типов

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

Составитель А. Мишин Техред М.Дидык

Заказ 42

Тираж 555

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж-35, Раушская наб., д. 4/5

ду К-го счетчика группы, вычитающий вход которого подключен к второму информационному входу К-го коммутатора группы, управляющий вход которого подключен к выходу К-го триггера группы и к управляющему входу К-го селектора группы, прямой выход К-го триггера первой группы подключен к второму входу К-го элемента И первой группы, выход К-го регистра группы подключен к информационному входу К-го селектора группы, выход которого подключен к К-му входу блока элементов 5 ИЛИ, выход которого подключен к входу слагаемого накапливающего сумматора, выход группы младших разрядов которого подключен к второму информационному входу первого блока сравне- 0 ния, выход признака больше которого подключен к первому входу второго элемента И, выход которого подключен к второму входу первого элемента И, выход группы младших разрядов накапливающего сумматора подключен к информационному входу второго блока сравнения, выход признака равенства которого подключен к второму входу второго элемента И.

5

Корректор И. Муска

Подписное