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

(51)5 С 06 Е 15/20 ГОСУДАРСТВЕНН ПО ИЗОБРЕТЕНИЯ ПРИ ГКНТ СССР НОМИОТКРЫТ Т 2 (54) УСТРОЙСТВО ДЛЯ РЕБЕ РАСКРОЯ МАТЕРИАЛА (57) Изобретение относит вычислительной техники и использовано для решения мального раскроя материа рию непревышения наперед допустимого остатка. Цел ния является повышение б-24 ин, П,В. Ильин. 8.8)свидетС 06 Еидетел ельство ССС 15/20, 198 ство СССР 15/20, 31. ержит элеОПИСАНИЕ ИК АВТОРСКОМУ СВИ(21) 4340474/2 (22) 03,11,87 (46) 07.01.90. (72) А.Ю. Вере и И.Н. Маркова (53) 681.333(08 (56) Авторское Иф 1247888, кл.Авторское св В 1478223, кл. БРЕТЕНИЯ 87. устройства. Устройствося к области може г быть задачи опти ла по крите- заданного ью изобрете- ыстродействия1534468 мент И 1, группу из Т счетчиков 2, где , Т в , количество типов кусков раскроен. ного материала, группу из Т блоков 3 памяти, информационные выходы 4 устройства, группы из Т элементов И 5,6, элемент И 7, группу из Т элементов 8 задержки, группу иэ Т регистров 9, регистр 10, две группы триггеров 11, 12, группу из Т коммутаторов 13, бло Оки 14, 15 сравнения, накапливающий Изобретение относится к вычислительной технике и может быть использовано для решения задачи оптимального раскроя материала по критериюнепревышения наперед заданного допустимого остатка.Цель изобретения " повышение быстродействия устройства.На чертеже представлена функцио- .нальная схема устройства.Устройство содержит элемент И 1,группу счетчиков 2, группу блоков 3 па"мяти, информационные выходы 4 устройства, первую группу элементов И 5, вторуюгруппу элементов И Ь, элемент И /, 30группу элементов 8 задержки, группурегистров 9, регистр 10, первую группу триггеров 11, вторую группу триггеров 12, группу коммутаторов 13,блоки 14 и 15 сравнения, накапливающий сумматор 16, группу селекторов17, выхоц 18 признака отсутствиярешения, выход 19 признака окончаниярешения, группу блоков 20 вычислениятекущего количества раскроенного 40материала, блок 21 элементов ИК ивход 22 устройства.Устройство работает следующим образом,Пусть требуется решить задачу раскроя материала, Задано; Ь - общаядлина материала; 1; - требуемые длины кусков; ; - потребное число 1о " допустимая величина отходов,Найти а; - целое (ь. = 1,п), 50такое, что01, -а,1;В.сПричем при1; ;Ь кусков 55фтребуется больше, чем имеется материала, так как только при этом условии задача имеет смысл; невыполненсумматор 16, группу из Т селекторов17, выход 18 признака отсутствия решения, выход 19 признака окончаниярешения, группу из Т блоков 20 вычисления количества раскроенного материала и блок 21 элементов ИЛИ. Цельизобретения достигается изменениемпоследовательности перебора комбинаций раскладки кусков по длине ма"териала. 1 ил. ный план (а;( И;) будет выполнен на следующих кусках.В основу достижения поставленной цели положена следующая идея. Для оценки пригодности каждой комбинации А в качестве решения задачи (1) необходимо сформировать очередную комбинацию А , вычислить сумму а,;,- определить величину о и сравнить ее с допустимой величинойРассмотрим обычный последовательный процесс формирования комбинаций А при п = 3,= 4, М5,4: ,/ 0 1 2 3 4 5 6 7.29 30 3145а, 0 1 2 3 4 О 1 24 О 14а 0 0 О 0 0 1 1 15 0 05а О 0 0 0 0 0 0 00 1 14Очевидно, что для вычисления 3 при переходе от= 1 до4 на каждом шаге иэ величины Ь достаточно вычитать 1 однако, при переходе от 4-й к 5-й комбинации и других переходах, когда происходит переполнение какой" либо из величин а;, величину 3 приходится вычислять заново. Однако, если изменить порядок следования комбинаций А , то каждый шаг будет требовать выйолнения только одной операции сложения, Действительно, рассмотрим следующий процесс: А / 0 1 2 3 4 5 6 7 8 9 10 11 12а, О 1 2 3 4 4 3 2 1 0 О2а 0 0 0 0 0 1 1 1 1 1 2 2 2..аз 00000000000 0 0 При таком способе чередования комбинаций на каждом шаге изменяется на единицу значение только одной величины а;, при этом для формирования 3 достаточно выполнить одну операцию сложения или вычитания (в зависимости от того, в какую сторону из+1, +5 а.11 - 1 -1 Такой принцип формирования комбинаций 10 кот позволяет достаточно быстро решать с с задачи (1) даже при значительных ве- нал личинах И;. Р,Перед началом работы триггеры 11 сви и 12 и счетчики 2 обнулены, т. е. 15 элементы И 5 закрыты, элементы И 6 фор открыты, на адресных входах блоков явл 3 памяти установлен код адреса нуле- дач вой ячейки; в 1-е блоки 3 памяти по лен адресам 0 и И; записаны единицы, а 20 по остальные ячейки обнулены; в 1-х ре- вхо гистрах 9 записаны величины 1 в етс регистре 10 записана величина 3 , в нов сумматоре 16 записана величина 1. в с (цепи сброса и начальной установки 26 ре перечисленных элементов не показаны). вле Для определенности положим, что ям прохождении второго импульса поду 22 описанный процесс повторяя. В результате на выходах 4 устаится код А = 2, О, О, который- Глучае, если полученная в суммато 16 величина 3 = 1. - 1, - 1 Удотворяет перечисленным трем условиявляется решением задачи. В противном случае аналогичный процессповторится и по прохождении третье Го импульсаЧетвертый импульс обеспечит вычисление в сумматоре 16 величины 3= 1 - 1, - 1, - 1, - 1,. Допустим,однако, что и код А 4 = 4, О, 0не является решением поставленнойзадачи. Поскольку в четвертой ячейке блока 3 памяти записана единица,четвертый импульс, пройдя через элемент 8 задержки на вход признака 40 чтения блока 3 памяти, считает единицу на вход триггера 11, триггер11 перейдет в противоположное состояние, что вызовет открытие элемента. И 5, закрытие элемента И 6 и переход 4 В триггера 12 в противоположное состояние, В свою очередь триггер 12 вызовет срабатывание коммутатора 13, чтообеспечит поступление очередных тактовых импульсов на вычитающий ("-1")вход счетчика 2, Выходной сигнал триггера 12 поступит на управляющий входселектора 17, что обеспечит отключениеобратных и подключение прямых выходов регистра 9 к выходам селектора17, который отключен от сумматора 16до прихода сигнала с элемента И 6.Пятый импульс по входу 22 через открытый элемент И 5 поступит на первый вход открытого элемента И 6 блои = 3 И = 4 И = 5 Ю = 4,ф 4Й ф ЪПервый импульс с входа 22 устройства через открытый элемент Й 6 блока 20 будет подан коммутатором 13 на суммирующий вход счетчика 2, в результате чего на его выходе установится код адреса первой ячейки блока 3 памяти. Поскольку эта ячейка обнулена, то этот же импульс, поступив через элемент 8 задержки на вход признака чтения блока 3 памяти, считает ноль на вход триггера 11, т.е. состояние триггера 11 не изменится. Тот же импульс поступит на вход подключения селектора 17, благодаря чему содержимое 1 первого регистра 9 будет подано в обратном коде на вход слагаемого накапливающего сумматора 16, где образуется величина Ь - 1, = 3 по окончании тактового импульса на входе 22 (по его заднему Фронту). После этого начинается проверка пригодности 6 полученного решения. Многоразрядное сравнение 3, с 30 организовать технически сложно, поэтому эта проверка проводится следующим образом.Блок 14 выдает единичный сигнал,. если в сумматоре 16 в старших разрядах - нули. Младшие разряды сумматора 16 в блоке 15 сравнения сравниваются с 3 , поступающим с регистра 10. На5меняется а;). ПоследовательныйФормирования 1; имеет вид:. 3 - ь - , - ), - , - , - , + ,выходе блока 15 сравнения появляется единичный сигнал в том случае, если содержимое младших разрядов сумматора 16 меньше 30 пЕсли оба перечисленных условия выполнены, то на выходе элемента И 1 появляется единичный сигнал, который поступает на входэлемента И /, на второй входорого подается знаковый разряд умматора 16. Таким образом, сигна выходе 19 появляется, еслидетельствует о том, что код А = 1, О, 0, установившийся на инмационных выходах 4. устройства, яется решением поставленной заи. Если хотя бы одно из перечисных условий не выполняется, тока 20, благодаря чему в нем произойдут процессы, аналогичные описанным. В результате на выходах 4 устройства формируется кол Ау - 4, 1, О. Этот , же импульс поступит на вход подключения соответствующего селектора 17, в результате чего содержимое 1 А сост" ветствующего регистра 9 поступит в обратном коде на вход сумматора 16, 10 и по окончании тактового сигнала величина 5 си Ь - 1 - 1, - 1, - 1, - 1 будет в него записана, В случае равенства нулю старших разрядов сумматора 16, а также выполнения условийоА О и 33 А появится сигнал наОвыходе 19 устройства, который будет свидетельствовать, что код А з = я4, 1, О 1 является решеиием задачи. В любом случае пятый тактовый импульс 20 н блоке 20 поступит через элемент 8 задержки на вход чтения блока 3 памяти и, поскольку содержимое счетчика 2 по пятому импульсу не изменилось, прочтет опять из четнертой ячейки блока 3 памяти единицу, которая поступит на счетный вход триггера 11. Триггер 11 перейдет из единичного в нулевое состояние, в результате чего закроется элемент И 5, откроется элемент И б 30 и первом блоке 20, Триггер 12 останется н прежнем состоянии.В дальнейшем, если сформированный кол Азщ 4, 1, 011 ие явился, решеяи ем задачи, очередной (шестой) импульс 35 поступит через открытый элемент И 6 первого блока 20 и коммутатор 13 на вычитающий вход первого счетчика 2, в результате чего на его выходе установится адрес третьей ячейки блока памяти. Этот же шестой импульс после прохождения через элемент 8 задержки считает ноль из третьей ячейки, т.е. триггер 11 останется в прежнем состоянии. На выходах 4 установится код Аб =453, 1, О , а по окончании тактового сигнала н сумматоре 16 образуется величина 3-,- Ь - 1 - 1, - 1, - 1, -1, +1,.Далее, по прохождении седьмого им пульса будет прочитан ноль из второйячейки блока 3 памяти первого блока20, на выходных шинах 4 установится код А - 10 р 1, 0 р в сУмматоРе 16образуется величина 8 = Ь - 1, - 1 - 551,- 1," 1 + 1 + 1,; по прохождениивосьмого импульса установится код Лб= 1 р 1, 01, в сумматоре 16 образуется величина 3 = 1 - 1 - 1 - 1- 1,1+ 1+ 1,+ 1 Но прохождении девятого импульса счетчик 2 первого блока 20 обнулится, на выходах 4 установится код А= 10 р 1, Оеар в сУмматоРе 16 образуется величина= Ь - 11-1 -1 - 1+1+1 + + 1, + 1 Ь - 1. Девятый тактовый импульс после задержки на элементе 8 прочтет единицу из нулевой ячейки блока 3 памяти на вход триггера 11, что вызовет его переход в противопо" ложное состояние, открытие элемента И 5, закрытие элемента И б, переход триггера 12 в противоположное состояние. Благодаря этому по прохождении десятого импульса установится код А о = Ор 2, О), а в сумматоре 1 б образуегся величинами, = 1, - 1 - 1 В дальнейшем работа устройства протекает в соответствии с описанным алгоритмом, Если вплоть до прохождения 104-го импульса решение так и не будет найдено, то при прохождении 105- го импульса появится сигнал на выходе 18 устройства, который свидетельствует о том, что при заданных исходных данных решить задачу невозможно.Формула изобретенияУстройство для решения задачи раскроя материала, содержащее Т блоков памяти, где Т - количество типов кусков раскроенного материала, группу из Т счетчиков, накапливающий сумматор, два блока сравнения, два элемента И, регистр и две группы элементов И, причем информационный выход К-го счетчика группы (К шк 1, Т) является К-м информационным выходом устройства и подключен к адресному входу К-го блока памяти группы, выход К-го элемента И первой группы (К 1 Т) подключен к входу (К+1)-го элемента И той же группы, выход регистра подключен к первому информа" ционному входу первого блока сравнения, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, устройства, в него введены группа из Т элементов задержки, две группы из Т триггеров, группа из Т коммутаторов, группа из Т регистров, группа из Т селекторов и блок элементов ИЛИ,.причем тактовый вход устройства подключен к входу первого элемента задержки группы, к первому вхо1534468 Составитель А, МишинТехред М,Дидык Корректор И. Муска Редактор Н. Тупица Заказ 42 Тираж 555 ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР113035, Москва, Ж, Раушская наб., д, 4/5 Производственно-издательский комбинат "Патент", г.ужгород, ул, Гагарина,101 ду первого элемента И первой группы, к первому входу первого элемента И второй группы и к тактовому входу накапливающего сумматора выход знаЭ5 кового разряда которого подключен к первому входу первого элемента И, выход которого является выходом признака окончания решения устройства, выход К-го элемента И первой группы (КТ) подключен к входу К-го элемента задержки группы и к первому входу К-го элемента И второй группы, выход Т-го элемента И первой группы является признаком отсутствия реше" ния устройства, выход К-го элемента задержки группы подключен к входу признака чтения К-го блока памяти группы, выход которого подключен к счетному входу К-го триггера первой группы, инверсный выход которого подключен к счетному входу К-го триггера второй группы и к второму входу К-го элемента И второй группы, выход которого подключен к входу включения 25 К-го селектора группы и к информационному входу К-го коммутатора груп- . пы, первый информационный выход которого подключен к суммирующему входу К-го счетчика группы, вычитающий вход которого подключен к второму информационному входу К-го коммутатора группы, управляющий вход которого подключен к выходу К-го триггера группы и к управляющему входу К-го селектора группы, прямой выход К-го триггера первой группы подключен к второму входу К-го элемента И первой группы, выход К-го регистра группы подключен к информационному входу К-го селектора группы, выход которого подключен к К-му входу блока элементов ИЛИ, выход которого подключен к входу слагаемого накапливающего сумматора, выход группы младших разрядов которого подключен к второму информационному входу первого блока сравнения, выход признака больше которого подключен к первому входу второго элемента И, выход которого подключен к второму входу первого элемента И, , выход группы младших разрядов накапливающего сумматора подключен к информационному входу второго блока сравнения, выход признака равенства которого подключен к второму входу второго элемента И.