Устройство для решения задачи раскроя материала

 

Изобретение относится к области вычислительной техники и может быть использовано для решения задачи оптимального раскроя материала по критерию непревышения наперед заданного допустимого остатка. Целью изобретения является повышение быстродействия устройства. Устройство содержит элемент И 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 ил.

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

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

РЕСПУБЛИН (51)5 G 06 Е 15/20

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

К А BTOPCHOMV СВИДЕТЕЛЬСТВУ

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

f10 ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГКНТ СССР (21) 4340474/24-24 (22) 03.11.87 (46) 07.01.90. Вюл. № 1 (72) А.IO. Веревкин, П.В. Ильин. и И.Н. Маркова (53) 681.333(088.8) (56) Авторское свидетельство СССР № l247888, кл. G 06 F 15/20, 1986.

Авторское свидетельство СССР № l478223, кл. G 06 F 15/20, 31.03.87.

„„SU„„1534468 А 1

2 (54) УСТРОЙСТВО ДПЯ РЕШЕНИЯ ЗАДАЧИ

РАСКРОЯ МАТЕРИАЛА (57) Изобретение относится к области вычислительной техники и може г быть использовано для решения задачи оптимального раскроя материала по критерию непревышения наперед заданного допустимого остатка. Целью изобретения является повышение быстродействия устройства. Устройство содержит эле-!

1534468 мент И 1, группу из Т счетчиков 2, где, Т вЂ, количество типов кусков раскроен. ного материала, группу из Т блоков 3 памяти, информационные выходы 4 устройства, группы из Т элементов И 5,6, элемент И 7, группу из Т элементов

8 задержки, группу иэ Т регистров 9, регистр 10, две группы триггеров i 1, 12, группу из Т коммутаторов 13, бло- 10 ки 14, 15 сравнения, накапливающий

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

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

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

Устройство содержит элемент И 1, группу счетчиков 2, группу блоков 3 па" мяти, информационные выходы 4 устройства, первую группу элементов И 5, вторую группу элементов И Ь, элемент И /, 30 группу элементов 8 задержки, группу регистров 9, регистр 10, первую группу триггеров 11, вторую группу триггеров 12, группу коммутаторов 13, блоки 14 и 15 сравнения, накапливающий сумматор 16, группу селекторов

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

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

Пусть требуется решить задачу рас- 45 кроя материала. Задано; Ь вЂ” общая длина материала; 1; — требуемые длины кусков; N; — потребное число 1;;

0 — допустимая величина отходов.

Найти а; — целое (з. = 1,° ..... n), такое, что и

P I, — а,1; ). !

ã! и

Причем при 1; N;>L кусков 55 ! с! требуется больше, чем имеется материала, так как только при этом условии задача имеет смысл; невыполненсумматор 16 группу из Т селекторов

17, выход 18 признака отсутствия решения, выход 19 признака окончания решения, группу из Т блоков 20 вычисления количества раскроенного материала и блок 21 элементов ИЛИ. Цель изобретения достигается изменением последовательности перебора комбинаций раскладки кусков по длине материала. 1 ил. ный план (а;(N ) будет выполнен на следующих кусках.

В основу достижения поставленной цели положена следующая идея. Для оценки пригодности каждой комбинации

А в качестве решения задачи (1) необходимо сформировать очередную !! комбинацию А, вычислить сумму а;(;, ! определить величину 0 и сравнить . ее с допустимой величиной !!

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

А при п = 3, N< = 4, М 5, N> 4:

/ /j 0 1 2 3 4 5 6 7 ° ° .29 30 31...145 а, 0 1 2 3 4 0 1 2...4 0 1...4 а 0 О О О 0 1 1 1...5 0 0...5 а 0 0 О 0 0 О 0 0...0 1 1...4 ! Ъ

Очевидно, что для вычисления о при переходе от j = 1 до j 4 на каждом шаге иэ величины Ь достаточно вычитать

1,, однако, при переходе от 4-й к

5-й комбинации и других переходах, когда происходит переполнение какой" либо из величин а;, величину 6 приходится вычислять заново. Однако, если изменить порядок следования комбинаций А, то каждый шаг будет требовать выйолнения только одной операции сложения. Действительно, рассмотрим следующий процесс:

А /j О 1 2 3 4 5 6 7 8 9 10 11 12... а, О 1 2 3 4 4 3 2 1 0 О 1 2... а„ О 0 О О 0 1 1 1 1 1 2 2 2. ° . а О 0 0 О О 0 0 0 О О О 0 О...

При таком способе чередования комбинаций на каждом шаге изменяется на единицу значение только одной величины а;, при этом для формирования

3 достаточно выполнить одну операJ цию сложения или вычитания (в зависимости от того, в какую сторону из1534468 меняется а;). Последовательный процесс формирования F; имеет вид: Ь-1, — 1,.-1,— 1,— 1< +1,+y,+, с сумматора 16. Таким образом, сигнал на выходе 19 появляется, если свидетельствует о том, что код А =

= (1, О, 0, установившийся на информационных выходах 4 устройства, является решением поставленной задачи. Если хотя бы одно из перечисленных условий не выполняется, то по прохождении второго импульса по входу 22 описанный процесс повторяется. B результате на выходах 4 установится код А = „2, О, О), который

Г в случае, если полученная в суммато25 ре 16 величина о = Ь вЂ” 1, — 1 удовлетворяет перечисленным трем условиям, является решением задачи. В противном случае аналогичный процесс повторится и по прохождении третье30 ГО импульса

Четвертый импульс обеспечит вычисление в сумматоре 16 величины 8<

= I — 1, — 1, — 1, — 1,. Допустим, однако, что и код А = (4, О, О не является решением поставленной задачи. Поскольку в четвертой ячейке блока 3 памяти записана единица, четвертый импульс, пройдя через элемент 8 задержки на вход признака чтения блока 3 памяти, считает единицу на вход триггера 11, триггер

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

17, который отключен от сумматора 16 до прихода сигнала с элемента И 6.

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

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

16 в блоке 15 сравнения сравниваются с 3» „, поступающим с регистра 10. На „

Такой принцип формирования комбинаций позволяет достаточно быстро решать задачи (1) даже при значительных величинах N;. Перед началом работы триггеры 11 и 12 и счетчики 2 обнулены, т. е. элементы И 5 закрыты, элементы И 6 открыты, на адресных входах блоков

3 памяти установлен код адреса нулевой ячейки; в i-e блоки 3 памяти по адресам О и N записаны единицы, а остальные ячейки обнулены; в i-х регистрах 9 записаны величины 1;; в регистре 10 записана величина 3» „, в сумматоре 16 записана величина Ь (цепи сброса и начальной установки перечисленных элементов не показаны).

Для определенности положим, что и = 3 N = 4 N = 5 N = 4, 4 и 3 выходе блока 15 сравнения появляется единичный сигнал в том случае, если содержимое младших разрядов сумматора 16 меньше3pz Если оба перечисленных условия выполнены, то на выходе элемента И 1 появляется единичный сигнал, который поступает на вход элемента И /, на второй вход которого подается знаковый разряд

1534468 ка 20, благодаря чему в нем произойдут процессы, аналогичные описанным.

В результате на выходах 4 устройства формируется кол Ау - (4, 1, 0 . Этот, же импульс поступит на вход подключения соответствующего селектора 17, в результате чего содержимое 1 сост" ветствующего регистра 9 поступит в обратном коде на вход сумматора 16, 10 и по окончании тактового сигнала вели ина 85 Ь вЂ” 1» — 1, — 1, — 1, — 1э будет в него записана. В случае равенства нулю старших разрядов сум матора 16, а также выполнения условий о «О и 3 < 3А д появится сигнал на

5 выходе 19 устройства, который будет свидетельствовать, что код А з = (4, 1, 0 1 является решеиием задачи.

В любом случае пятый тактовый импульс 20 в блоке 20 поступит через элемент 8 задержки на вход чтения блока 3 памяти и, поскольку содержимое счетчика 2 по пятому импульсу не изменилось, прочтет опять из четвертой ячейки блока

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

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

3, 1, 0, а по окончании тактового сигнала в сумматоре 16 образуется величина 8 .—,- Ь - 1, - 1, — 1, — 1»

1,+1,.

Далее, по прохождении седьмого им- 50 пульса будет прочитан ноль из второй ячейки блока 3 памяти первого блока

20, на выходных шинах 4 установится код АУ - (О, 1, Оеар в сУмматоРе 16 образуется величина 5 — — L — 1, — 1» — 55

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

Лб= (1р 1, 0 1, в сумматоре 16 образуется величина 3 =* L — 1, — 1 — 1<- 1,1z+ 1»+ 14+ 1, . Ио прохождении девятого импульса счетчик 2 первого блока

20 обнулится, на выходах 4 установится код A = (О, 1, О), в сумматоре 16 образуется величина = Ь вЂ” 14

1,— 1, — 1, — 1<+ 1, » 1, +

+ 1, + 1» Ь вЂ” 1 . Девятый тактовый импульс после задержки на элементе

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

И 5, закрытие элемента И б, переход триггера 12 в противоположное состояние. Благодаря этому по прохождении десятого импульса установится код

А о = (О, 2, 01, а в сумматоре 1б образуегся величина3юев Ь вЂ” 1 — 1..

В дальнейшем работа устройства протекает в соответствии с описанным алгоритмом. Если вплоть до прохождения

104-ro импульса решение так и не будет найдено, то при прохождении 105го импульса появится сигнал на выходе 18 устройства, который свидетельствует о том, что при заданных исходных данных решить задачу невозможно, формулаиэобретения

Устройство для решения задачи раскроя материала, содержащее Т блоков памяти, где Т вЂ” количество типов кусков раскроенного материала, группу из Т счетчиков, накапливающий сумматор, два блока сравнения, два элемента И, регистр и две группы элементов И, причем информационный выход К-го счетчика группы (К шк 1,...

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

1534468

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

Техред M.Äèäûê Корректор И Муска

Редактор Н. Тупица

Заказ 42 Тираж 555 Подписное

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

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

Производственно-издательский комбинат "Патент", г.ужгород, ул. Гагарина,101 ду первого элемента И первой группы, к первому входу первого элемента И второй группы и к тактовому входу накапливающего сумматора выход знаЭ

5 кового разряда которого подключен к первому входу первого элемента И, выход которого является выходом признака окончания решения устройства, выход К-го элемента И первой группы (К Р Т) подключен к входу К-го элемента задержки группы и к первому входу К-ro элемента И второй группы, выход Т-ro элемента И первой группы является признаком отсутствия решения устройства, выход К-ro элемента задержки группы подключен к входу признака чтения К-ro блока памяти группы, выход которого подключен к счетному входу К-го триггера первой группы, инверсный выход которого подключен к счетному входу К-го триггера второй группы и к второму входу

К-ro элемента И второй группы, выход которого подключен к входу включения 25

К-го селектора группы и к информационному входу K-го коммутатора груп-пы, первый информационный выход которого .подключен к суммирующему входу К-го счетчика группы, вычитающий вход которого подключен к второму информационному входу К-го коммутатора

1 группы, управляющий вход которого подключен к выходу К-го триггера группы и к управляющему входу К-го селектора группы, прямой выход К-го триггера первой группы подключен к второму входу К-го элемента И первой группы, выход К-го регистра группы подключен к информационному входу К-ro селектора группы, выход которого подключен к К-му входу блока элементов

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