Вычислительное устройство для поис-ka оптимального решения задачиодномерного раскроя

ОП ИСАНИЕ ИЗОБРЕТЕНИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз Советски кСоциалистическикРеспублик и 813437(51) М. Кл.б 06 Г 15/20 б 06,1 1/00 Гевударстааева кемнтет СССР в деим взфбретенив и вткрытвй(54) ВЫЧИСЛИТЕЛЬНОЕ УСТРОЛСТВО ДЛЯ ПОИСКА ОПТИМАЛЬНОГО РЕШЕНИЯ ЗАДАЧИ ОДНОМЕРНОГО РАСКРОЯИзобретение относится к вычислительной технике и может быть использовано при автоматизации раскроя полупроводниковых монокристаллов на заготовки двух сортов, а также для решения задачи оптимального раскроя других объектов, если алгоритм поиска оптимального варианта раскроя относится к классу алгоритмов, допускающих реализацию с помощью предлагаемого устройства.Известно устройство, содержащее блок преобразования геометрических форм в циф О ровой код, арифметический блок для решения векторных уравнений, графопостроитель, блок ввода данных 1.Известно также устройство, содержащее блок памяти начальных данных, блок ввода данных, арифметический блок, блок учета комбинаций, блок памяти оптимума, блок вывода, сумматор оценок и блок сравнения 2.Указанные устройства позволяют миниМизировать длину листового материала, из 20 которого выкраиваются образцы различной конфигурации.Однако рассмотпенные устройства не позволяют быстро и эффективно решать задачу раскроя полупроводниковых монокристаллов на заготовки двух сортов.Полупроводниковые монокристаллы (вдальнейшем, для краткости, слитки), выращиваемые путем вытягивания из расплава по методу Чохральского и поступающие на раскрой, имеют приблизительно форму кругового цилиндра различной длины. Одной из основных характеристик материала слитка является его удельное объемное электрическое сопротивление, При существующей технологии получения слитков оказывается, что лишь средняя часть слитка, состоит из материала первого сорта, концы же слитка состоят из материала второго сорта.Материал слитка может быть реализован (продан) только в виде заготовок, а именно: заготовкой первого сорта считается часть слитка, заключенная между двумя его поперечными сечениями, удовлетворяющая двум условиям:- длина части не меньше определеннойвеличины, не равной нулю,- часть состоит только из материалапервого сорта.Слиток может быть разделен на частипоперечными резами с помощью тонкой дис 813437ковой пилы. Любая часть слитка, удовлетворяющая первому условию хжет быть реализована как заготовка второго сорта; если же это условие не выполняется, часть идет в брак (для удобства терминологии и обозначений будем называть ее в этом случае заготовкой нулевого сорта).Оптимальным называют раскрой слитка, обеспечивающий максимум прибыли. Известно, что при оптимальном раскрое число реко пять вариантов их возможного размещения.Из известных устройств наиболее близким по технической сущности к данному является вычислительное устройство, содержащее блок ввода, блок сравнения, логический блок формирования сигналов, счетчик импульсов, масштабные резисторы, элементы И 13.Это устройство не реализует алгоритм поиска оптимального варианта размещения резов (оптимального решения) без прямого перебора вариантов, что снижает его эффективность.Цель изобретения - повышение эффективности путем сокращения числа перебираемых вариантов. 15 2 О 25 Поставленная цель достигается тем, что в устройство введены блоки коммутации, операционные усилители, дешифратор, регистр, формирователь импульсов управления, первый вход которого соединен со входом устройства, пять выходов блока ввода через последовательно соединенные первый блок коммутации, первую группу масштабных резисторов и первый операционный усилитель, подключены к первому входу блока зо 35 сравнения, первый, второй, третий и четвертый выходы блока ввода через последовательнэ соединенные второй блок коммутации, вторую группу масштабных резисторов и второй операционный усилитель подключены ко второму входу блока сравнения, выход которого соединен с первым входом первого элемента И, второй вход которого соединен с первым выходом формирователя импульсов управления, второй выход которого подключен ко входу счетчика импульсов, выходы которого через дешифратор подключены к первым входам элементов И, выходы которых подключены соответственно ко входам регистра, вторые входы элементов И соединены с выходом первого элемента И, входы логического блока формирования сигналов соединены соответственно с вы.ходами регистра счетчика импульсов и с третьим выходом формирователя импульсов управления, первый выход логического блока формирования сигналов подключен к выходу устройства, второй выход соединен с управляющими входами регистра и счетчика импульсов и со вторым входом блока управления, управляющие выходы подклю 40 45 50 55 зов не превышает двух, причем имеется тольо чены соответственно к управляющим входам блоков коммутации.На фиг. 1 представлена схема устройства; на фиг. 2 - алгоритм поиска оптимального варианта раскроя; на фиг. 3 приведено схематическое изображение объекта (моно- кристалла), подлежащего раскрою.Устройство содержит блок 1 ввода, блоки 2 и 3 коммутации, первую группу резисторов 4, 5, 6, вторую группу резисторов 7 - 9, операционные усилители 1 О, 11, блок 12 сравнения, элементы И 13 - 16, дешифратор 1, счетчик 18 импульсов, блок 19 управления, регистр 20, логический блок 21 формирования сигналов, вход 22 и выход 23 устройства.Блок 1 ввода позволяет устанавливать на первых своих четырех выходах постоянные стабильные отрицательные напряжения, пропорциональные величинам а, 8, 1. и Й (см. фиг. 2 и 3). Установка этих напряжений может осуществляться вручную - оператором, либо автоматически - по сигналам от устройства, измеряющего указанные величины. На пятом выходе блока 1 ввода поддерживается фиксированное отрицательное напряжение. Операционные усилители 10 и 11 идентичны, они выполнены суммирующими, т. е. в цепь обратной связи усилителя, постоянного тока включен резистор. Выходной потенциальный сигнал блока 12 сравнения имеет два уровня - нулевой и единичный. Единичный сигнал присутствует на выходе в том и только в том случае, если входное напряжение, поступающее на вход блока 12 с выхода операционного усилителя 1 О; строго меньше напряжения, поступающего на другой вход с выхода операционного усилителя 11. Счетчик 18 импульсов представляет собой обычный накапливающий счетчик, имеющий не менее 10 различных состояний, т, е. может быть выполнен как одна декада десятичного счетчика (4 триггера). Он имеет потенциальные разрядные выходы, импульс, подаваемый на его управляющий вход, устанавливает счетчик в нулевое состояние. Блок9 управления имеет три импульсных выхода и два импульсных входа пуск и стоп. В исходном состоянии блока импульсы на всех его выходах отсутствуют. После подачи импульса на вход 22 (импульс пуск подается оператором с помощью пусковой кнопки или внешней системой автоматического управления) блок начинает генерировать на первом выходе последовательность импульсов с периодом Т. Эти же импульсы появляются на втором и третьем выходах. Импульс, поступающий на 2-ой вход (стоп) блока управления, возвращает блок в исходное состояние. Входы логического блока 21, соединенные с выходами счетчика 18 импульсов и регистра 20 являются потенциальными, а вход, соединенный с 3-м выходом блока 19 управления - импульсным. Сигналы на вы813437 ХО-резы не производить, весь слиток реализовать как заготовку нулевого сорта (брак);Ы 1-резы не производить, весь слиток реализовать как заготовку первого сорта;Х 2-резы не производить, весь слиток реализовать как заготовку второго сорта;ав 22, ав. 20, ав 00 - произвести 2 реза в точках а и в; первая и вторая цифры указывают сорт заготовок, получающихся, соответственно, из левой и правой отрезаемых частей слитка (его средняя часть будет заготовкой первого сорта);а 2, аО - произвести один рез в точке а, цифра указывает сорт Заготовки, получающейся из левой части слитка (вторая, правая его часть будет заготовкой первого сорт);Ь - произвести один рез в точке й, левая часть при этом - заготовка второго сорта, правая - первого;ап - произвести два реза - в точках 4 а и 1 - Ь, оба отрезаемых конца слитка являются заготовками второго сорта, а середина - заготовкой первого сорта;ЬЬ - произвести два реза - в точках Ь и Ь, левая часть при этом - заготовка второго сорта, средняя - первого, правая в 4 нулевого;ЬЬ - произвести два реза - в точках Ь и 1 - Ь, середина слитка является при этом заготовкой первого сорта, а две остальных части - второго.Предполагается, что слитки сориенти 5 рованы так, что а 31. - Ь, это легко обеспечить, например, на этапе измерения величин а, Ь, 1. перед раскроем слитков.Устройство работает следующим образом.В исходном состоянии счетчик 18 импульсов и регистр 20 установлены в нулевое состояние, а блок 19 управления находится в состоянии Стоп, т, е. на его выходах импульсы отсутствуют. На соответствующих ходах блока 21 формируются при поступлении импульса на его вход с выхода блока 19 управления. Кодирование решений, а также управляющих сигналов блоков 2 и 3 коммутации, обеспечивающих требуемые соединения, может быть выбрано любым в зависимости от конкретных используемых элементов и других обстоятельств. Выход устройства может быть подключен к индикатору оптимального решения, если решение выполняется оператором, либо непосредственнок к управляющим входам исполнительных устройств автоматической системы оптимального раскроя. В прямоугольниках блок-схемы алгоритма (фиг. 2) записаны проверяемые условия, а в овалах - условные обозначения принимаемых решений, знак + означает выполнение, а знак - - невыполнение соответствующего условия; принимаемые решения обозначены следующим образом: выходах блока ввода 1 устанавливаются напряжения, пропорциональные величинам, характеризующим монокристалл, подлежащий раскрою, а также фиксированное напряжение. Принцип действия состоит в автоматическом вычислении с помощью операционных усилителей правой и левой частей неравенств, фигурирующих в алгориме, представленном на фиг. 2, и в провер ке их выполнения согласно алгоритму до тех пор, пока не будет найдено оптимальное решение. При этом очередное условие, подлежащее проверке, выбирается автоматически в зависимости от результатов предшествующих проверок в соответствии с алгоритмом (фиг. 2) . При нулевом состоянии 15 счетчика 18 и регистра 20 блок 2 коммутации соеди"яет вход операционного усилителя 10 через резистор с третьим выходом блока 1 ввода, а блок коммутации 3 соединяет вход операционного усилителя 11 20через резистор с четвертым выходом блока 11 ввода. Если оказывается, что 1. СЙ (первое неравенство алгоритма), см. фиг. 2), на выходе блока 12 появляется единичный сигнал, т. е. элемент И 13 открывается. Прн нулевом содержимом счетчика 18 возбужден выход дешифратора 17, соединенный с элементом И, выход которого соединен с первым входом регистра 20. Запуск устройства осуществляется подачей импульса на вход пуск блока управления 19 (на вход 22 вручную от пусковой кнопки или от внешне- ЗО го управляющего устройства). Получивпусковой импульс, блок управления формирует управляющий импульс сначала на 1-ом выходе, затем - на 2-ом выходе, затем - на 3-ем своем выходе. Импульс с первого выхода фиксирует в первом разряде регистра 20 памяти результат первого условия алгоритма (фиг. 2). Действительно, если это условие выполняется, импульс с выхода блока 19 управления проходит через открытый элемент И 13, а также через единственный открытый элемент И, соединенный выходом со входом первого разряда регистра 20, устанавливая его в единичное состояние.Если условие не выполняется, то первый разряд регистра 20 остается в нулевом состоянии. Спустя некоторое время появляется 5импульс на 2-м выходе блока 19 управления, увеличивая содержимое счетчика 18 на единицу. В результате воздействия этих двух импульсов практически одновременно изменяется (если условие выполняется) кодовая комбинация, поступающая на входы логического блока 21 с выходов регистра 20 и кодовая комбинация на выходах счетчика импульсов 18. Спустя необходимое для этого время появляется импульс на третьем выходе блока 19 управления. Если условие 5 было выполнено, т. е. оптимальным вариантом раскроя является вариант ХО, на выходе устройства будет сформирована соответствующая кодовая комбинация, а на выходе логического блока 21, соединенном со 2-мвходом (входом стоп) блока 19 управления будет сформирован импульс, возвращающий его (а также регистр 29 и счетчик импульсов 18) в исходное состояни; выполнение алгоритма поиска на этом закончено.Если указанное условие не выполняется, 5 то выходные сигналы блока 21 обеспечивают соответствующее соединение входов и выходов блока коммутации 2 и 3. Блок управления формирует очередную последовательность импульсов на выходах, в результате аналогично описанному выше, проверяется очередное условие алгоритма (фиг. 2)1 з (а+Врезультат проверки заносится во второй разряд регистра 20 (на счетчике 18 при этом установлена единица). Если следую щее условие выполнено, то оптимальным решением является М 2, на выходе устройства формируется сигнал, кодирующий это решение, а импульс, формирующийся при этом на втором выходе блока 21, возвращает устройство в исходное состояние.Дальше работа схемы продолжается совершенно аналогично и проверяются условия алгоритма, представленного на фиг, 2.Фиксированное напряжение выбирается равным 1 (в соответствующем масштабе), 25 благодаря чему подключение резистора к этому напряжению обеспечивает на выходе операционного усилителя требуемое напряжение. Операционный усилитель 10 вычисляет левые части неравенств, а операционный усилитель 11 - правые части неравен- зо ств Время поиска оптимального варианта раскроя оказывается неодинаковым. Как видно из фиг, 2 поиск может закончиться после первой же проверки, либо после второй, третьей, пятой, седьмой, восьмой, девятой или десятой проверок.Таким образом; хотя число различных неравенств, проверка которых может потребоваться при отыскании оптимального решения, равно 16, поиск заканчивается не более чем через десять шагов (тактов). Имен но.поэтому число разрядов регистра 20 памяти выбрано равным десяти, а счетчик 18 можно выполнять четырехразрядным, Выполнение резисторов 4 - 9 регулируемыми (с линейной шкалой проводимости) позволяет 4 легко и просто перестраивать устройство в случае изменения цен.Устройство обеспечивает автоматизацию поиска оптимального варианта раскроя, реализация которого заметно повысит эффек.тивность раскроя, кроме того автоматизация 50 приводит к повышению производительности оборудования, реализующего раскрой. формула изобретенияВычислительное устройство для поиска оптимального решения задачи одномерного раскроя, содержащее блок ввода, блок сравнения, логический блок формирования сигналов, счетчик импульсов, масштабные резисторы, элементы И, отличающееся тем, что с целью повышения эффективности путем сокращения числа перебираемых вариантов, в него введены блоки коммутации, операционные усилители, дешифратор, регистр и формирователь импульсов управления, первый вход которого соединен со входом устройства, пять выходов блока ввода через последовательно соединенные первый блок коммутации, первую группу масштабных резисторов и первый операционный усилитель, подключены к первому входу блока сравнения, первый, второй, третий и четвертый выходы блока ввода через последовательно соединенные второй блок коммутации, вторую группу масштабных резисторов и второй операционный усилитель подключены ко второму входу блока сравнения, выход которого соединен с первым входом первого элемента И, второй вход которого соединен с первым выходом формирователя импульсов управления, второй выход которого подключен ко входу счетчика импульсов, выходы которого через дешифратор подключены к первым входам элементов И, выходы которых подключены соответственно ко входам регистра, вторые входы элементов И соединены с выходом первого элемента И, входы логического. блока формирования сигналов соединены соответственно с выходами регистра счетчика импульсов и с третьим выходом формирователя импульсов управления, первый выход логического блока формирования сигналов подключен к выходу устройства, второй выход - соединен с управляющими входами регистра и счетчика импульсов и со вторым входом блока управления, управляющие выходы подключены соответственно к управляющим входам блоков коммутации.Источники информации,принятые во внимание при экспертизе 1, Патент США. 3596068,кл. 235 - 150, кл. б 06 Г 15/00, 1971.2. Авторское свидетельство СССР347761, кл. 6 06 Г 15/46, 1972,3. Авторское свидетельство СССР497606, кл. 6 06 1 1/00, б 06 Г 15/20,1971 (прототип).813437 г. Риг.д Составитель А.Жерено едактор Воловик Техред А Бойкас аказ 346/62 Тираж 745твенного комитета С ретений и открытий 35, Раушская наб., г. Ужгород, ул. Про д. 4 ктна ВНИИПИ Государс по делам изо 113035, Москва, Ж -илиал ППП Патент, Корректор В. Бутяга ПодписноеССР