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

Союз Советски кСоциалистическиеРеспублик ОП ИСАНИЕИЗОБРЕТЕН ИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ и 902021(51)М. Кл. а об г 1 у 20 с присоединением заявки МВеударстеенныЯ кемнтет СССР но денем нзебретеннЯ и отнрнтнЯ(23)Приоритет Опубликовано 30.0182; Бюллетень М 4 Дата опубликования описания 30 .0 1.82(71) Заявите арьковскии СТРОЙСТВО ДЛЯ ПОИСКА ОПТИИАЛЬНОГ ЕШЕНИЯ ЗАДАЧИ ОДНОМЕРНОГО РАСКРО близким к предла тройство, которое ода, блоксравнен является жит блок одеф лок Формирования ическ налов Изобретение относится к вычислительной технике и может быть использовано при автоматизации раскроя полупроводниковых монокристаллов на заготов"ки двух сортов, а также для оптималь"ного решения задачи одномерного раскроя других материалов, если алгоритмпоиска оптимального решения относится к классу алгоритмов, допускающихреализацию с помощью устройства.тоИзвестно устройство для раскроя,содержащее блоки сравнения, установки масштабов, генератор тактовых импульсов, элементы И, блок ввода, счетчик, блок выбора корней коэффициентов, блок вывода, блок умножения 11.Однако данное устройство использует большое число перебираемых вариантов, что снижает его эффективность,Наиболее гаемому масштабные резисторы, элемент И, бло.ки коммутации, операционные усилители, регистр и формирователь импульсов управления, первый вход которогосоединен со входом устройства, пятьвыходов блока ввода через последовательно соединенные первый блок коммутации, первую группу масштабных резисторов и первый операционный усилитель подключены к первому входублока сравнения. Первый, второй, третий и четвертый выходы блока вводачерез последовательно соединенныевторой блок коммутации, вторую гФуппу масштабных резисторов и второй операционный усилитель подключены ко второму входу блока сравнения, выходкоторого соединен с первым входомэлемента И, входы логического блокаформирования сигналов соединены с выходами регистра и с третьим выходомформирователя импульсов управления,первый выход логического блока формирования сигналов подключен к выходу3 90202устройства, второй выход соединен суправляющим входом регистра и со вторым входом формирователя импульсовуправления, а управляющие выходы подключены соответственно к управляющимвходам блоков коммутации 12 ,Недостатком известного устройстваявляется относительная сложность егосхемы, точнее - ее управляющей части,включающей десять элементов И и счет Очик, причем как выходы счетчика, таки выходы регистра памяти являютсявходами логического блока формирования сигналов, который при столь большом числе входов оказывается весьмагромоздким,Цель изобретения - упрощение устройства,Поставленная цель достигается тем, что устройство, содержащее блок ввода параметров, блок сравнения, блоки коммутации, шифратор, аналоговые сумматоры, элемент И и генератор тактовых импульсов, первый вход которого соединен с управляющим входом устройства, пять выходов блока ввода пара" метров через последовательно соеди" ненные первый блок коммутации и первый аналоговый сумматор подключены к первому входу блока сравнения, первый, второй, третий и четвертый выходы блока ввода параметров через последовательно соединенные второй блок коммутации и второй аналоговый сумматор подключены ко второму входу33 блока сравнения, выход которого соединен с первым входом элемента И, второй вход которого подключен к первому выходу генератора тактовых импуль- . сов, второй выход которого соединен с управляющим входом шифратора, пер.-. вый выход котброго является выходом устройства, второй выход соединен с вторым входом генератора тактовых43 импульсов, третий и четвертый выходы шифратора подключены к управляющим входам соответственно первого и второго блоков коммутации, содержит регистр сдвига, выходы которого соединены соответственно,с входами шифратора, вход сдвига - соединен с третьим выходом генератора тактовых импульсов, первый и второй входы регистра сдвига соединены соответственно с выходом элемента И и вторым выходом шифратора.На фиг. 1 представлена блок-схема устройства; на фиг, 2 - алгоритм 1 4поиска, реализуемый устройством; наФиг. 3 - объект, подлежащий раскрою.В состав схемы устройства входятблок ввода 1 параметров, блоки 2 и 3коммутации, группа масштабных резисторов 4,56, группа масштабныхрезисторови 89, операционные усилители 10 и 11. На операционных усилителях и масштабных резисторах выполнены аналоговые сумматоры,блок 12 сравнения, элемент И 13, генератор 14 тактовых импульсов, регистр 15 сдвига, шифратор 16 и вход 17устройства.Блок ввода 1 позволяет устанавливать на первых своих четырех выходахпостоянные стабильные отрицательныенапряжения, пропорциональные исход-ным данным решаемой задачи раскроя.Установка этих напряжений может осуществляться вручную - оператором,либо автоматически - по сигналам отустройства, измеряющего соответствующие величины.Операционные усилители 10 и 11 выполнены суммирующими, Выходной сигнал блока 12 сравнения имеет двв уровня, а именно нулевой и единичный, еди- .ничный сигнал присутствует на его выходе только тогда, когда напряжение,поступающее на первый вход блока 12с выхода первого операционного усилителя 1 О, строго меньше напряжения,поступающего на второй его вход свыхода второго операционного усилителя 11,Генератор 14 тактовых импульсов имеет три импульсных выхода и два входа "Пуск" и "Стоп". В исходном состоянии импульсы на выходах генератора 14 отсутствуют. После подачи импульса на вход он начинает генерировать на выходе, соединенном со входом сдвига регистра 15, последовательность импульсов с периодом Т.Эти же импульсы, задержанные на время Т/2 и 2 Т/3, появляются соответственно на других его выходах. Импульс, поступающий на второй вход (вход "Стоп")генератора 14 с выхода шифратора 16, возвращает его в исходное состояние.Регистр 15 выполнен сдвиговым, чис. ло его разрядов на единицу больше максимального числа условий алгоритма, которые требуется проверить для отыскания оптимального решения. Сдвиг содержимого регистра осуществляется5 9020 подачей импульсов йа вход сдвига. Импульс, поступивший на вход регистра 15 со второго выхода шифратора 16, устанавливает его в исходное состояние, в котором первый разряд содержит еди ницу, а все остальные - нули. единичный вход первого разряда регистра соединен с выходом элемента И 13, Иначе говоря, исходным является состояние 00001, сдвиг осуществляет в ся влево т,е. после каждого сдвига первый разряд оказывается в нулевом состоянии, причем после К сдвигов К+1-й разряд будет находиться в еди-. ничном состоянии, а все разряды ле вее его - в нулевом.Входы шифратора 16, соединенные с выходами регистра 15,являются потенциальными, а вход, соединенный с выходом генератора 11 - импульсным. 20 Сигналы на выходах шифратора 16 формируются при поступлении на его вход импульса с выхода генератора 1 ч. Колирование решений, а также управляющих сигналов блоков 2 и 3 коммутации, 25 обеспечивающих требуемые соединения, может быть выбрано любым - в зависимости от используемых элементов и других обстоятельств.Выход устройства может быть под- зо ключен к индикатору оптимального решения, если решения выполняются оператором, либо непосредственно к управляющим входам исполнительных устройств автоматической системы оптимального З 5 раскроя. В прямоугольниках блок-схемы алгоритма (фиг. 2) записаны проверяемые условия, а в окружностях - условные обозначения принимаемых решений. Знак "+" означает выполнение, а знак .- невыполнение соответствующего условия. Принимаемые решения обозначены следующим образом:МО - реэы не производить, весь монокристалл (слиток)реализовать как заготовку нулевого сорта (брак)1М 1 - резы не производить, весь слиток реализовать как заготовку первого сорта;М 2 - резы не производить, весь слиток реализовать как заготовку второго сорта;ав 22,ав 20, ав 00 - произвести резы в точках а и в, первая и вторая цифры указывают сорт заготовки, получающейся соответственно из левой и правой частей слитка (его средняя часть 2 6всегда будет при этом заготовкой первого сорта)1а 2,а 0 - произвести рез в точке а,цифра указывает сорт заготовки, получающейся из левой части слитка(правая его часть всегда при этом будетзаготовкой первого сорта)Ь - произвести рез в точке Клевая часть при этом - заготовка второго сорта, правая - первого,аЙ - произвести резы в точках аи 1.-Ь, оба отрезаемых конца слиткаявляются заготовками второго сорта,а середина - заготовкой первого сорта,йЬ - произвести ревы в точках йи Ь, левая часть,ври этом заготовкавторого сорта, правая - нулевого,средняя - первого;ЬЬ - произвести резы в точках Ьи =6, середина слитка является приэтом заготовкой первого сорта, а двеостальные части - второго. Предполагается, что слитки сориентированы так, что ать.-Ь, и это легкообеспечить, например, на этапе измерения величина а, Ь, 1. перед раскроем слитков.В исходном состоянии генератор 1 Ьнаходится в состоянии "Стоп", т.е.на его выходах импульсы отсутствуют.Первый разряд регистра 15 установленв единичное состояние, остальные разряды - в нулевое, На соответствующихвыходах блока ввода 1 устанавливаютсянапряжения, пропорциональные величинам,характеризующим объект, подлежащийраскрою.Принцип действия устройства состоит в автоматическом вычислении с помощью операционных усилителей 10 и11 левой и правой частей неравенств,фигурирующих в алгоритме, представ"ленном на фиг2, и в проверке ихвыполнения, согласно алгоритму до техпор, пока не будет найдено оптимальное решение. При этом очередное подлежащее проверке условие выбираетсяавтоматически в зависимости от результатов предшествующих проверок в соответствии с алгоритмом. При укаэанномисходном состоянии регистра 15 всевыходы блока 2 и 3 коммутации заземлены,Запуск устройства осуществляетсяподачей импульса на вход 17 устройства. Импульс с выхода генератора 11сдвигает содержимое регистра 15 на7 90202один разряд (т.е, регистр переходитв состояние 00010, освобождая первый разряд для приема результата проверки первого условия алгоритма)Приновом состоянии регистра, т.е. приновой кодовой комбинации на входахшифратора 16, блок 2 коммутации соединяет вход операционного усилителя 10. через резистор с третьим выходом блока ввода 1, а блок 3 коммута оции соединяет вход операционного усилителя 11 через резистор с четвертымвыходом блока ввода 1,Если оказывается, что 1 (первоенеравенство алгоритма), на выходе 15блока 12 сравнения появляется единичный сигнал, т,е, элемент И 13. открывается, и импульс выхода генератора 14 проходит через него, устанавливая первый разряд регистра 15 в единичное состояние, т.ефиксируя внем положительный результат проверкипервого условия. Если условие не выполняется, первый разряд регистра 15остается в нулевом состоянии, 25Если первое условие выполняется,то с приходом импульса с выхода генератора 14 на выходе устройства фор"мируется соответствующая кодовая комбинация, а на выходе шифратора 16,соединенном со вторым входом (входом "Стоп" ) генератора 14, формируется импульс, возвращающий генератор 14, а также регистр 15 в исходное состояние, и выполнение алгорит 35ма на этом заканчивается,Если же первое условие не выполняется, то импульсы на выходе устройства не появляются, генератор продолжает свою работу, и второй импульсс его выхода снова сдвигает содержимое регистра 15, которое принимаетвид 000 100. При данной входнойкодовой комбинации шифратор 16 обеспечивает соединение входов и выходовблоков 2 и 3 коммутации, необходимоедля проверки очередного неравенстваалгоритма. Если оно выполняется, то, аналогично предыдущему, импульс выхода генератора 14 заносит единицу в первый разряд регистра 15, а импульс с другого выхода генератора 14 формирует на выходе устройства код оптимального в данном случае решения М 2, а также импульс на выходе шифратора 16, возвращающий генератор 14 и регистр 15 в исходное состояние, Если второе условие не выполняется, работа устройства продолжается совершенно аналогично, обеспечивая про. верку условий согласно алгоритму, представленному на фиг, 2 до нахождения оптимального решения.фиксированное напряжение на пятом выходе блока ввода 1 выбирается равным единице (в соответствующем масштабе), благодаря чему подключение резистора к этому выходу обеспечивает на выходе операционного усилителя требуемое напряжение. Операционный усилитель 1 О вычисляет левые части неравенств, а операционный уси" литель 11 - правые.Как видно из фиг, 2, поиск может потребовать проверки максимум десяти условий, ввиду чего число разрядов регистра 15 в этом случае (т.е, при реализации именно этого алгоритма) равно 11. При этом в разряде, номер которого на единицу больше номера проверяемого условия, всегда содержится единица, таким образом, положение, первой единицы (слева направо в кодовой комбинации, содержащейся в регистре, однозначно определяет номер проверяемого условия.Выполнение резисторов 4 - 9 регулируемыми позволяет легко и просто пепестраивать устройство при изменении величин Со, С, С , СФормула изобретенияУстройство для поиска оптимально- . го решения задачи одномерного раскроя, содержащее блок ввода параметров, блок сравнения, блоки коммутации, шифратор, аналоговые сумматоры, элемент И и генератор тактовых импульсов, первый вход которого соединен с управляющим входом устройства, пять выходов блока ввода параметров. через последовательно соединенные первый блок коммутации и первый ана" логовый сумматор подключены к первому входу блока сравнения, первый, второй, третий и четвертый выходы блока ввода параметров через последовательно соединенные второй блок коммутации и второй аналоговый сумматор подключены ко второму входу блока сравнения, выход которого соединен с первым входом элемента И, второй вход которого подключен к первому выходу генератора тактовых импульсов,9 90202 второй .выход которого соединен с уп" равляющим входом шифратора, первый выход которого является выходом устройства, второй выход соединен свторым входом генератора тактовых 3 импульсов, третий и четвертый выходы шифратора подключены к управляющим входам соответственно первого и второго блоков коммутации, о т л и ч аю щ е е с я тем, что, с целью упро- тв щения, оно содержит регистр сдвига, выходы которого соединены соответственно с входами шифратора, вход сдви 10га - соединен с третьим выходом генератора тактовых импульсов, первыйи второй входы регистра сдвига соеди"иены соответственно с выходом элемента И и вторым выходом шифратора.Источние информации,принятые во вйимание при экспертизе1. Авторское свидетельство СССРИ 497606, кл. С 06 3 1/ООуС ОЬ .Г 35/20 1971.2. Авторское свидетельство СССРпо ваяеке И 2503987/24,кл. С 06 Г 1 У 20, 1977 (прототип).902021 Составитель Л.Жеренов Техред А.Бабинец Ко ректор Г.Назар актор Н.Ковалев Заказ 12385/5 ПП "Патент", г.ужгород, ул,Проектная, 4 ил 9 Тираж 731 ПодписноеИИПИ Государственного комитета СССРпо делам изобретений и открытий3035, Москва, Е, Рауаскав наб., д. 4/5