Устройство для поиска оптимального решения задачи одномерного раскроя Советский патент 1982 года по МПК G06G7/122 

Изобретение относится к вычислитель ной технике и может быть использовано при автоматизации раскроя полупроводниковых монокристаллов на заготовки двух сортов, а также для оптимального решения задачи одномерного раскроя других материалов, если алгоритм поиска оптимального решения относится к классу алгоритмов, допускающих реализацию с помощью устройства. Известно устройство для раскроя, содержащее блоки сравнения, установки масштабов, генератор тактовых импульсов, элементы И, блок ввода, счет чик, блок выбора корней коэффициентов, блок вывода, блок умножения мТ Однако данное устройство использует большое число перебираемых вариантов, что снижает его эффективность. Наиболее близким к предлагаемому является устройство, которое содержит блок ввода, блок сравнения, логический блок формирования сигналов. масштабные резисторы, элемент И, блоки коммутации, операционные усилители, регистр и формирователь импульсов управления, первый вход которого соединен со входом устройства, пять выходов блока ввода через последовательно соединенные первый блок коммутации, первую группу масштабных резисторов и первый операционный усилитель подключены к первому входу блока сравнения. Первый, второй, тре тий и четвертый выходы блока ввода через последовательно соединенные второй блок коммутации, вторую rffynпу масштабных резисторов и второй операционный усилитель подключены ко второму входу блока сравнения, выход которого соединен с первым входом элемента И, входы логического блока формирования сигналов соединены с выходами регистраи с третьим выходом (|юрмирователя импульсов управления, первый выход логического блока формирования сигналов подключен к выходу 39 устройства, второй выход соединен с управляющим входом регистра и со вто рым входом формирователя импульсов управления, а управлякяцие выходы под ключены соответственно к управлящим входам блоков коммутации 21 . Недостатком известного устройства является относительная сложность его схемы, точнее - ее управляющей части включающей десять элементов И и счет чик, причем как выходы счетчика, так и выходы регистра памяти являются входами логического блока формирова|ния сигналов, который при столь боль шом числе входов оказывается весьма громоздким. Цель изобретения - упрощение устройства. Поставленная цель достигается тем что устройство, содержащее блок ввода параметров, блок сравнения, блоки коммутации, шифратор, аналоговые сум маторы, элемент И и генератор тактовых импульсов, первый вход которого срединен с управляющим входом устрой ства, пять выходов блока ввода параметров через последовательно соединенные первый блок коммутации и первый аналоговый сумматор подключены к первому входу блока сравнения, пер вый, второй, третий и четвертый выходы блока ввода параметров через по ледовательно соединенные второй блок коммутации и второй аналоговый сумматор подключены ко второму входу блока сравнения, выход которого соединен с первым входом элемента И, вто рой вход которого подключен к первому выходу генератора тактовых импуль сов , второй выход которого соединен с управлякмцим входом шифратора, первый выход котброго является выходом устройства, второй выход соединен с вторым входом генератора тактовых импульсов, третий и четвертый выходы шифратора подключены к управляющим входам соответственно первого и второго блоков коммутации, содержит регистр сдвига, выходы которого соединены соответственно .с входами шифратора, вход сдвига - соединен с третьим выходом генератора тактовых импульсов, первый и второй входы регистра сдвига соединены соответственно с выходом элемента И и вторым выходом шифратора. На фиг. 1 представлена блок-схема устройства; на фиг. 2 - алгоритм поиска, реализуемый устройством, на фиг. 3 объект, подлежащий раскрою. В состав схемы устройства входят блок ввода 1 параметров, блоки 2 и 3 коммутации, группа масштабных резисторов 4,5,...,6, группа масштабных резисторов 7 и 8,...,9, операционные усилители 10 и 11. На операционных усилителях и масштабных резисторах выполнены аналоговые сумматоры, ;. блок 12 сравнения, элемент И 13, генератор И тактовых импульсов, регистр 15 сдвига, шифратор 16 и вход 17 устройства. Блок ввода 1 позволяет устанавливать на первых своих четырех выходах постоянные стабильные отрицательные напряжения, пропорциональные исходным данным решаемой задачи раскроя. Установка этих напряжений моиет осуществляться вручную - onepatopoM, либо автоматически - по сигналам от устройства, измеряющего соответствующие величины. Операционные усилители 10 и 11 выполнены суммирующими. Выходной сигнал блока 12 сравнения имеет два уровня, а именно нулевой и единичный. Единичньгй сигнал присутствует на его выходе только тогда, когда напряжение, поступающее на первый вход блока 12 с выхода первого операционного усилителя 10, строго меньше напряжения, поступаадегр на второй его вход с выхода второго операционного усилителя 11. Генератор И тактовых импульсов имеет три импульсных выхода и два входа Пуск и Стоп, В исходном состоянии импульсы на выходах генератора fi отсутствуют. После подачи импульса на вход 6н начинает генерировать на выходе, соединенном со входом сдвига регистра 15 последовательность импульсов с периодом Т. Эти же импульсы, задержанные на время Т/2 и 2Т/3, появляются соответственно на других его выходах. Импульс, поступающий на второй вход (вход Стоп)генератора 14 с выхода шифратора 16, возвращает его в исходное состояние. Регистр 15 выполнен сдвиговым, число его разрядов на единицу больше максимального числа условий алгоритма, которые требуется проверить для отыскания оптимального решения. Сдвиг содержимого регистра осуществляется подачей импульсов fia вход сдвига. Им пульс, поступивший на вход регистра со второго выхода шифратора 16, устанавливает его в исходное состояние в котором первый разряд содержит еди ницу, а все остальные - нули. Единич ный вход первого разряда регистра соединен с выходом элемента И 13. Иначе говоря, исходным является состояние 000...01, сдвиг осуществляется влево т.е. после каждого сдвига первый разряд оказывается в нулевом состоянии, причем после К сдвигов К+1-Й разряд будет находиться в единичном состоянии, а все разряды левее его - в нулевом. Входы шифратора 16, соединенные с выходами регистра 15,являются потенциальными, а вход, соединенный с выходом генератора - импульсным. Сигналы на выходах шифратора 16 формируются при поступлении на его вход импульса с выхода генератора И. Колирование решений, а также управляющих сигналов блоков 2 и 3 коммутации обеспечивающих требуемые соединения может быть выбрано любым - в зависимости от используемых элементов и других обстоятельств. Выход устройства может быть подключен к индикатору оптимального решения, если решения выполняются оператором, либо непосредственно к упра ляющим входам исполнительных устройс автоматической системы оптимального раскроя. В прямоугольниках блЬк-схемы алго ритма (фиг. 2) записаны проверяемые условия, а в окружностях - условные обозначения принимаемых решений. Знак + означает выполнение, а знак невыполнение соответствующего условия. Принимаемые решения обозначены следующим образом: N0 - резы не производить, весь монокристалл (слиток)реализовать как заготовку нулевого сорта (брак); N1 - резы не производить, весь слиток реализовать как заготовку пер вого сорта; Nit - резы не производить, весь слиток реализовать как заготовку вто рого сорта ав22,ав20, авОО - произвести резы в точках айв, первая и вторая цифры указывают сорт заготовки, получаю щейся соответственно из левой и правой частей слитка (его средняя част всегда будет при этом заготовкой первого сорта); а2,аО - произвести рез в точке а, цифра указывает сорт заготовки, получающейся из левой части слитка(пра вая его часть всегда при этом будет заготовкой первого сорта) h - произвести рез в точке h, левая часть при этом - заготовка второго сорта, правая - первого/ ah - произвести резы в точках а и L-h, оба отрезаемых конца слитка являются заготовками второго сорта, а середина - заготовкой первого сортаhb - произвести резы в точках h и Ь, левая часть.при этом заготовка . второго сорта, правая - нулевого, средняя - первого} hh - произвести резы в точках h и , середина слитка является при этом заготовкой первого сорта, а две остальные части - второго. Предполагается, что слитки сориентированы так, что , и это легко обеспечить, например, на этапе измерения величина а, Ь, L перед раскроем слитков. В исходном состоянии генератор 1U находится в состоянии Стоп, т.е. на его выходах импульсы отсутствуют. Первый разряд регистра 15 установлен в единичное состояние, остальные разряды - в нулевое. На соответствующих выходах блока ввода 1 устанавливаются напряжения, пропорциональные величинам, характеризующим объект, подлежащий раскрою. Принцип действия устройства состоит в автоматическом вычислении с помощью операционных усилителей 10 и 11 левой и правой частей неравенств, фигурирующих в алгоритме, представленном на фиг. 2, и в проверке их выполнения, согласно алгоритму до тех пор, пока не будет найдено оптимальное решение. При этом очередное подлежащее проверке условие выбирается автоматически в зависимости от результатов предшествующих проверок в соответствии с алгоритмом. При указанном исходном состоянии регистра 15 все выходы блока 2 и 3 коммутации заземлены. . Запуск устройства осуществляется подачей импульса на вход 17 устройства. Импульс с выхода генератора 1 , сдвигает содержимое регистра 15 на 79 один разряд (т.е. регистр переходит в состояние 00...010, освобождая пер вый разряд для приема результата про верки первого условия алгоритма). Пр новом состоянии регистра, т.е. при новой кодовой комбинации на входах шифратора 1б, блок 2 коммутации соединяет вход операционного усилителя 10.через резистор с третьим выходом блока ввода Г, а блок 3 коммутации соединяет вход операционного уси лителя 11 через резистор с четвертым выходом блока ввода 1. Если оказывается, что (первое неравенство алгоритма), на выходе блока 12 сравнения появляется единич ный сигнал, т.е. элемент И 13 открывается, и импульс выхода генератора 1 проходит через него, устанавли вая первый разряд регистра 15 в единичное состояние, т.е. фиксируя в нем положительный результат проверки первого условия. Если условие не выполняется, первый разряд регистра 15 остается в нулевом состоянии. , Если первое условие выполняется, то с приходом импульса с выхода гене ратора И на выходе устройства формируется соответствующая кодовая комбинация, а на выходе шифратора 16, соединенном со вторым входом (входом Стоп) генератора 1, формируется импульс, возвращающий генератор И, а также регистр 15 в исходное состояние, и выполнение алгоритма на этом заканчивается. Если же первое условие не выполняется, то импульсы на выходе устройст ва не появляются, генератор продолжает свою работу, и второй импульс с его выхода снова сдвигает содержимое регистра 15, которое принимает вид 00...0100. При данной входной кодовой комбинации шифратор 16 обеспечивает соединение входов и выходов блоков 2 и 3 коммутации, необходимое для проверки очередного неравенства алгоритма. Если оно выполняется, то, аналогично предыдущему, импульс выхода генератора 14 заносит единицу в первый разряд регистра 15, а импульс с другого выхода генератора И формирует на выходе устройства код оптимального в данном случае решения N2, а также импульс на выходе шифратора 1б, возвращающий генератор 1 и регистр 15 в исходное состояние. Если второе условие не выполняется, работа устройства продолжается совершенно аналогично, обеспечивая проверку условий согласно алгоритму, представленному на фиг. 2 до нахождения оптимального решения. Фиксированное напряжение на пятом выходе блока ввода 1 выбирается равным единице (в соответствующем масштабе), благодаря чему подключение резистора к этому выходу обеспечивает на выходе операционного усилителя требуемое напряжение. Операционный усилитель 10 вычисляет левые масти неравенств, а операционный усилитель 11 - правые. Как видно из фиг. 2, поиск может потребовать проверки максимум десяти условий, ввиду чего число разрядов регистра 15 в этом случае (т.е. при реализации именно этого алгоритма) равно 11. При этом е разряде, номер которого на единицу больше номера проверяемого условия, всегда содержится единица, таким образом, положение, первой единицы (слева направо) в кодовой комбинации, содержащейся в регистре, однозначно определяет номер проверяемого условия. Выполнение резисторов t - 9 ре гули- руемыми позволяет легко и просто пепестраивать устройство при изменении величин Со, С., С, Ср. Формула изобретения Устройство для поиска оптимально- . го решения задачи одномерного раскроя, содержащее блок ввода параметров, блок сравнения, блоки коммутации, шифратор, аналоговые сумматоры, элемент И и генератор тактовых импульсов, первый вход которого соединен с управляющим входом устройства, пять выходов блока ввода параметров, через последовательно соединенные первый блок коммутации и первый аналоговый сумматор подключены к первому входу блока сравнения, первый, второй, третий и четвертый выходы блока ввода параметров через последовательно соединенные второй блок коммутации и второй аналоговый сумматор подключены ко второму входу блока сравнения, выход которого соединен с первым входом элемента И, второй вход которого подключен к первому выходу генератора тактовых импульсов,

990202

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

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

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

1.Авторское свидетельство СССР (Г kS76Q6, кл. G 06 J 1/00,

6 Об F15/20, 1971.

2.А8Т( свидетельство СССР по заявке ff 2503987/2 1,

кй. G Об F 15/20, 1977 (прототип).