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

Союз Соввтскмк

Соцмалмстмческма

Республик

ОП ИСАНИЕ

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ())) 902021 (6l ) Дополнительное к авт. с вид-ву(22)Заявлено 13.06.80 (21) 2941317/18 24 (51)М. Кл.

6 06 F 15/20 с присоединением заявки МВаударстеенны11 кемнтет

СССР но делам нзебретеннй и открытий (23) Приоритет

Опубликовано 30.01 ° 82; Бюллетень М 4

Дата опубликования описания 30 .0 1.82 (53) УДК 681.325.22(088.8) В.А.Добрыдень (72) Автор изобретения (7I ) Заявитель

Харьковский инженерно-строительн (54) УСТРОЙСТВО ДЛЯ ПОИСКА ОПТИМАЛЬНОГО

РЕШЕНИЯ ЗАДАЧИ ОДНОМЕРНОГО РАСКРОЯ

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

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

Однако данное устройство использует большое число перебираемых вариантов, что снижает его эффективность.

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

3 90202 устройства, второй выход соединен с управляющим входом регистра и со вторым входом формирователя импульсов управления, а управляющие выходы подключены соответственно к управляющим входам блоков коммутации (2 ) .

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

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

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

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

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

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

1 4 поиска, реализуемый устройством, на фиг. 3 — объект, подлежащий раскрою.

В состав схемы устройства входят блок ввода 1 параметров, блоки 2 и 3 коммутации, группа масштабных резисторов 4,5,...,6, группа масштабных резисторов 7 и 8,...,9, операционные усилители 10 и 11. На операционных усилителях и масштабных резисторах выполнены аналоговые сумматоры, блок 12 сравнения, элемент И 13, генератор 14 тактовых импульсов, регистр 15 сдвига, шифратор 16 и вход 17 устройства.

Блок ввода 1 позволяет устанавливать на первых своих четырех выходах постоянные стабильные отрицательные напряжения, пропорциональные исход- ным данным решаемой задачи раскроя.

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

Операционные усилители 10 и 11 выполнены суммирующими. Выходной сигнал блока 12 сравнения имеет двв уровня, а именно нулевой и единичный. Еди- . ничный сигнал присутствует на его выходе только тогда, когда напряжение, поступающее на первый вход блока 12 с выхода nepsoro операционного усилителя 10, строго меньше напряжения, поступающего на второй его вход с выхода второго операционного усилителя 11.

Генератор 14 тактовых импульсов имеет три импульсных выхода и два входа "Пуск" и "Стоп". В исходном состоянии импульсы на выходах генератора 14 отсутствуют. После подачи импульса на вход он начинает генерировать на выходе, соединенном со входом сдвига регистра 15, последовательность импульсов с периодом Т.

Эти же импульсы, задержанные на время Т/2 и 2Т/3, появляются соответственно на других его выходах. Импульс, поступающий на второй вход (вход

"Стоп")генератора 14 с выхода шифратора 16, возвращает его в исходное состояние.

Регистр 15 выполнен сдвиговым, число его разрядов на единицу больше максимального числа условий алгоритма, которые требуется проверить для отыскания оптимального решения. Сдвиг содержимого регистра осуществляется

5 9020 подачей импульсов йа вход сдвига. Импульс, поступивший на вход регистра 15 со второго выхода шифратора 16, устанавливает его в исходное состояние, в котором первый разряд содержит еди- 5 ницу, а все остальные - нули. Единичный вход первого разряда регистра соединен с выходом элемента И 13.

Иначе говоря, исходным является состояние 000...01, сдвиг осуществляется влево, т,е. после каждого сдвига первый разряд оказывается в нулевом состоянии, причем после К сдвигов

К+1-й разряд будет находиться в единичном состоянии, а все разряды ле- lS вее его - в нулевом.

Входы шифратора 16, соединенные с выходами регистра 15,являются потенциальными, а вход, соединенный с выходом генератора 14 - импульсным. 20

Сигналы на выходах шифратора 16 формируются при поступлении на его вход импульса с выхода генератора 14. Колирование решений, а также управляющих сигналов блоков 2 и 3 коммутации, >5 обеспечивающих требуемые соединения, может быть выбрано любым - в зависимости от используемых элементов и других обстоятельств.

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

В прямоугольниках блок-схемы алгоритма (фиг. 2) записаны проверяемые условия, а в окружностях - условные обозначения принимаемых решений.

Знак "+" означает выполнение, а знак

""". - невыполнение соответствующего условия. Принимаемые решения обозначены следующим образом:

N0 - реэы не производить, весь монокристалл (слиток)реализовать как заготовку нулевого сорта (брак)

M1 - резы не производить, весь слиток реализовать как заготовку первого сорта, N2 - резы не производить, весь слиток реализовать как заготовку второго сорта; ав22,ав20, ав00 - произвести резы в точках а и в, первая и вторая цифры указывают сорт заготовки, получающейся соответственно из левой и правой частей слитка (его средняя часть

2! 6 всегда будет при этом заготовкой первого сорта)1 а2,а0 — произвести рез в точке а, цифра указывает сорт заготовки, получающейся из левой части слитка(пра вая его часть всегда при этом будет заготовкой первого сорта) произвести рез в точке h, левая часть при этом - заготовка второго сорта, правая — первого, ah — произвести резы в точках а и L hi оба отрезаемых конца слитка являются заготовками второго сорта, а середина — заготовкой первого сорта, hb - произвести ревы в точках h и Ь, левая часть,при этом заготовка второго сорта, правая — нулевого, средняя - первого; произвести резы в точках h и =Ь, середина слитка является при этом заготовкой первого сорта, а две остальные части - второго.

Предполагается, что слитки сориен" тированы так, что ать.-Ь, и это легко обеспечить, например, на этапе измерения величина а, bi L перед раскроем слитков.

В исходном состоянии генератор 14 находится в состоянии "Стоп", т.е. на его выходах импульсы отсутствуют.

Первый разряд регистра 15 установлен в единичное состояние, остальные разряды — в нулевое, На соответствующих выходах блока ввода l устанавливаются напряжения, пропорциональные величинам, характеризующим объект, подлежащий раскрою.

Принцип действия устройства состоит в автоматическом вычислении с помощью операционных усилителей 10 и

11 левой и правой частей неравенств, фигурирующих в алгоритме, представ" ленном на фиг ° 2, и в проверке их выполнения, согласно алгоритму до тех пор, пока не будет найдено оптимальное решение. При этом очередное подлежащее проверке условие выбирается автоматически в зависимости от результатов предшествующих проверок в соответствии с алгоритмом. При укаэанном исходном состоянии регистра 15 все выходы блока 2 и 3 коммутации заземлены.

Запуск устройства осуществляется подачей импульса на вход 17 устройства. Импульс с выхода генератора 14 сдвигает содержимое регистра 15 на

7 90202 один разряд (т.е. регистр переходит в состояние ОО...OIO, освобождая первый разряд для приема результата проверки первого условия алгоритма) ° При новом состоянии регистра, т.е. при новой кодовой комбинации на входах шифратора 16, блок 2 коммутации соединяет вход операционного усилителя 10. через резистор с третьим выходом блока ввода 1, а блок 3 коммутации соединяет вход операционного усилителя 1I через резистор с четвертым выходом блока ввода 1.

Если оказывается, что L< h (первое неравенство алгоритма), на выходе блока 12 сравнения появляется единичный сигнал, т.е. элемент И 13. открывается, и импульс выхода генератора 14 проходит через него, устанавливая первый разряд регистра 15 в единичное состояние, т.е ° фиксируя в нем положительный результат проверки первого условия. Если условие не выполняется, первый разряд регистра 15 остается в нулевом состоянии. 25

Если первое условие выполняется, то с приходом импульса с выхода генератора 14 на выходе устройства формируется соответствующая кодовая комбинация, а на выходе шифратора 16, соединенном со вторым входом (входом "Стоп" ) генератора 14, формируется импульс, возвращающий генератор 14, а также регистр 1 в исходное состояние, и выполнение алгорит35 ма на этом заканчивается.

Если же первое условие не выполняется, то импульсы на выходе устройства не появляются, генератор продолжает свою работу, и второй импульс с его выхода снова сдвигает содержимое регистра 1, которое принимает вид 00...0 100. При данной входной кодовой комбинации шифратор 16 обеспечивает соединение входов и выходов блоков 2 и 3 коммутации, необходимое для проверки очередного неравенства алгоритма.

Если оно выполняется, то, аналогично предыдущему, импульс выхода генератора 14 заносит единицу в первый разряд регистра 15, а импульс с другого выхода генератора 14 формирует на выходе устройства код оптимального в данном случае решения N2, а также импульс на выходе шифратора 16, возвращающий генератор 14 и регистр 15 в исходное состояние. Если второе условие не выполняется, работа устройства продолжается совершенно аналогично, обеспечивая проверку условий согласно алгоритму, представленному на фиг. 2 до нахождения оптимального решения.

Фиксированное напряжение на пятом выходе блока ввода 1 выбирается равным единице (в соответствующем масштабе), благодаря чему подключение резистора к этому выходу обеспечивает на выходе операционного усилителя требуемое напряжение. Операционный усилитель IO вычисляет левые части неравенств, а операционный усилитель 11 — правые.

Как видно из фиг. 2, поиск может потребовать проверки максимум десяти условий, ввиду чего число разрядов регистра 15 в этом случае (т.е, при реализации именно этого алгоритма) равно 11. При этом в разряде, номер которого на единицу больше номера проверяемого условия, всегда содержится единица, таким образом, положение. первой единицы (слева направо в кодовой комбинации, содержащейся в регистре, однозначно определяет номер проверяемого условия.

Выполнение резисторов 4 - 9 регулируемыми позволяет легко и просто пепестраивать устройство при изменении величин Со, С„, С, С

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

Устройство для поиска оптимально- . го решения задачи одномерного раскроя, содержащее блок ввода параметров, блок сравнения, блоки коммутации, шифратор, аналоговые сумматоры, элемент И и генератор тактовых импульсов, первый вход которого соединен с управляющим входом устройства, пять выходов блока ввода параметров через последовательно соединенные первый блок коммутации и первый ана" логовый сумматор подключены к первому входу блока сравнения, первый, второй, третий и четвертый выходы блока ввода параметров через последовательно соединенные второй блок коммутации и второй аналоговый сумматор подключены ко второму входу блока сравнения, выход которого соединен с первым входом элемента И, второй вход которого подключен к первому выходу генератора тактовых импульсов, 9 90202 второй .выход которого соединен с уп" равляющим входом шифратора, первый выход которого является выходом устройства, второй выход соединен с вторым входом генератора тактовых S импульсов, третий и четвертый выходы шифратора подключены к управляющим входам соответственно первого и второго блоков коммутации, о т л и ч аю щ е е с я тем, что, с целью упро- 3В щения, оно содержит регистр сдвига, выходы которого соединены соответственно с входами шифратора, вход сдви10 га - соединен с третьим выходом генератора тактовых импульсов, первый и второй входы регистра сдвига соеди" иены соответственно с выходом элемента И и вторым выходом шифратора.

Источнике информации, принятые во вйимание при экспертизе

3. Авторское свидетельство СССР

N 497606, кл. С 06 J 1/00ф

G 0b .F 15/20, 3971. 2. Авторское свидетельство СССР по ваявке И 25039&7/24, кл. G 06 F 35/20, 1977 (прототип).

902021

Составитель A.Æåðåíîe

Техред A.Бабинец Корректор Г.Назарова

Редактор H. Ковалева филиал ППП "Патент", г.ужгород, ул.Проектная, 4

Заказ 12385/59 Тираж 731 Подписное

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

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