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

 

ОП ИСАНИЕ

ИЗЬ6РЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советски к

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

Республик

< >813437 (61) Дополнительное к авт. свид-ву— (22) Заявлено 04.07.77 (21) 2503987/18-24 с присоединением заявки №вЂ” (23) Приоритет— (51) М. К .

G 06 F 15/20

G 06 J 1/00

Гевудлрствеевй кемнтет

СССР ю делам лзабретенил и вткрытвй (53) УДК 681.322 (088.8) Опубликовано 15.03.81. Бюллетень № 10

Дата опубликования описания 25.03.81 (72) А вторы изобретения

В. А. Добрыдень и В. П. Кольцов .

i

f

Харьковский институт радиоэлектроники и Харьковский инженерностроительный институт (71) Заявители (54) ВЫЧИСЛИТЕЛЬНОЕ УСТРОЛСТВО ДЛЯ ПОИСКА

ОПТИМАЛЬНОГО РЕШЕНИЯ ЗАДАЧИ ОДНОМЕРНОГО РАСКРОЯ

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

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

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

Указанные устройства позволяют минимизировать длину листового материала, из 20 которого выкраиваются образцы различной конфигурации.

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

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

Материал слитка может быть реализован (продан) только в виде заготовок, а именно: заготовкой первого сорта считается часть слитка, заключенная между двумя его поперечными сечениями, удовлетворяющая двум условиям: — длина части не меньше определенной величины, не равной нулю, — часть состоит только из материала первого сорта.

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

25 зо

35 ковой пилы. Любая часть слитка, удовлетворяющая первому условию х жет быть реализована как заготовка второго сорта; если же это условие не выполняется, часть идет в брак (для удобства терминологии и обозначений будем называть ее в этом случае заготовкой нулевого сорта).

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

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

Это устройство не реализует алгоритм поиска оптимального варианта размещения резов (оптимального решения) без прямого перебора вариантов, что снижает его эффективность.

Цель изобретения — повышение эффективности путем сокращения числа перебираемых вариантов.

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

55 чены соответственно к управляющим входам блоков коммутации.

На фиг. 1 представлена схема устройства; на фиг. 2 — алгоритм поиска оптимального варианта раскроя; на фиг. 3 приведено схематическое изображение объекта (монокристалла), подлежащего раскрою.

Устройство содержит блок 1 ввода, блоки 2 и 3 коммутации, первую группу резисторов 4, 5, 6, вторую группу резисторов 7 — 9, операционные усилители 10, 11, блок 12 сравнения, элементы И 13 — 16, дешифратор

17, счетчик 18 импульсов, блок 19 управления, регистр 20, логический блок 21 формирования сигналов, вход 22 и выход 23 устройства.

Блок 1 ввода позволяет устанавливать на первых своих четырех выходах постоянные стабильные отрицательные напряжения, пропорциональные величинам а, 8, L u h (см. фиг. 2 и 3). Установка этих напряжений может осуществляться вручную — оператором, либо автоматически — по сигналам от устройства, измеряющего указанные величины. На пятом выходе блока 1 ввода поддерживается фиксированное отрицательное напряжение. Операционные усилители

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

Выходной потенциальный сигнал блока 12 сравнения имеет два уровня — нулевой и единичный. Единичный сигнал присутствует на выходе в том и только в том случае, если входное напряжение, поступающее на вход блока 12 с выхода операционного усилителя 10; строго меньше напряжения, поступающего на другой вход с выхода операционного усилителя 11. Счетчик 18 импульсов представляет собой обычный накапливающий счетчик, имеющий не менее 10 различных состояний, т. е. может быть выполнен как одна декада десятичного счетчика (4 триггера). Он имеет потенциальные разрядные выходы, импульс, подаваемый на его управляющий вход, устанавливает счетчик в нулевое состояние. Блок 9 управления имеет три импульсных выхода и два импульсных входа «пуск» и «стоп». В исходном состоянии блока импульсы на всех

его выходах отсутствуют. После подачи импульса на вход 22 (импульс «пуск» подается оператором с помощью пусковой кнопки или внешней системой автоматического управления) блок начинает генерировать на первом выходе последовательность импульсов с периодом Т. Эти же импульсы появляются на втором и третьем выходах. Импульс, поступающий на 2-ой вход («стоп») блока управления, возвращает блок в исходное состояние. Входы логического блока 21, соединенные с выходами счетчика 18 импульсов и регистра 20 являются потенциальными, а вход, соединенный с 3-м выходом блока 19 управления — импульсным. Сигналы на вы813437

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

Nl-резы не производить, весь слиток реализовать как заготовку первого сорта;

N2-резы не производить, весь слиток реализовать как заготовку второго сорта; ав 22, ав. 20, ав 00 — произвести 2 реза в точках а и в; первая и вторая цифры указывают сорт заготовок, получающихся, соответственно, из левой и правой отрезаемых частей слитка (его средняя часть будет заготовкой первого сорта); а2, a0 — произвести один рез в точке а, цифра указывает сорт Заготовки, получающейся из левой части слитка (вторая, правая его часть будет заготовкой первого сорт );

h — произвести один рез в точке h, левая часть при этом — заготовка второго сорта, правая — первого;

ah — произвести два реза — в точках 4 а и L — h, оба отрезаемых конца слитка являются заготовками второго сорта, а середина — заготовкой первого сорта;

hb — произвести два реза — в точках

h и b, левая часть при этом — заготовка второго сорта, средняя — первого, правая — 4 нулевого;

hh — произвести два реза — в точках

h u L — h, середина слитка является при этом заготовкой первого сорта, а две остальных части — второго.

Предполагается, что слитки сориенти5 рованы так, что а Э 1.— b, это легко обеспечить, например, на этапе измерения величин а, Ь, L перед раскроем слитков.

Устройство работает следующим образом.

В исходном состоянии счетчик 18 импуль-5 сов и регистр 20 установлены в нулевое состояние, а блок 19 управления находится в состоянии «Стоп», т. е. на его выходах импульсы отсутствуют. На соответствующих ходах блока 21 формируются при поступлении импульса на его вход с выхода блока 19 управления. Кодирование решений, а также управляющих сигналов блоков 2 и 3 коммутации, обеспечивающих требуемые соединения, может быть выбрано любым в зависимости от конкретных используемых элементов и других обстоятельств. Выход устройства может быть подключен к индикатору оптимального решения, если решение выполняется оператором, либо непосредственнок к управляющим входам исполнительных устройств автоматической системы оптимального раскроя.

В прямоугольниках блок-схемы алгоритма (фиг. 2) записаны проверяемые условия, а в овалах — условные обозначения принимаемых решений, знак «+» означает выполнение, а знак «-» — невыполнение соответствующего условия; принимаемые решения обозначены следующим образом: выходах блока ввода 1 устанавливаются напряжения, пропорциональные величинам, характеризующим монокристалл, подлежащий раскрою, а также фиксированное напряжение. Принцип действия состоит в автоматическом вычислении с помощью операционных усилителей правой и левой частей неравенств, фигурирующих в алгориме, представленном на фиг. 2, и в провер ке их выполнения согласно алгоритму до тех пор, пока не будет найдено оптимальное решение. При этом очередное условие, подлежащее проверке, выбирается автоматически в зависимости от результатов предшествующих проверок в соответствии с алгоритмом (фиг. 2). При нулевом состоянии

15 счетчика 18 и регистра 20 блок 2 коммутации соеди"яет вход операционного усилителя 10 через резистор с третьим выходом блока 1 ввода, а блок коммутации 3 соединяет вход операционного усилителя 11

20 через резистор с четвертым выходом блока

11 ввода. Если оказывается, что L

«пуск» блока управления 19 (на вход 22 вручную от пусковой кнопки или от внешнеЗо го управляющего устройства) . Получив пусковой импульс, блок управления формирует управляющий импульс сначала на 1-ом выходе, затем — на 2-ом выходе, затем— на 3-ем своем выходе. Импульс с первого выхода фиксирует в первом разряде регистЗ5 ра 20 памяти результат первого условия алгоритма (фиг. 2). Действительно, если это условие выполняется, импульс с выхода блока 19 управления проходит через открытый элемент И 13, а также через единственный открытый элемент И, соединенный выходом со входом первого разряда регистра 20, устанавливая его в единичное состояние.

Если условие не выполняется, то первый разряд регистра 20 остается в нулевом состоянии. Спустя некоторое время появляется

5 импульс на 2-м выходе блока 19 управления, увеличивая содержимое счетчика 18 на единицу. В результате воздействия этих двух импульсов практически одновременно изменяется (если условие выполняется) кодовая комбинация, поступающая на входы логического блока 21 с выходов регистра

20 и кодовая комбинация на выходах счетчика импульсов 18. Спустя необходимое для этого время появляется импульс на третьем выходе блока 19 управления. Если условие

5 было выполнено, т. е. оптимальным вариантом раскроя является вариант NO, на выходе устройства будет сформирована соответствующая кодовая комбинация, а на выходе логического блока 21, соединенном со 2-м

813437 входом (входом «стоп») блока 19 управления будет сформирован импульс, возвращающий его (а также регистр 29 и счетчик импульсов 18) в исходное состояни; выполнение алгоритма поиска на этом закончено.

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

b (a+h результат проверки заносится во второй разряд регистра 20 (на счетчике 18 при этом установлена единица). Если следую- 15 щее условие выполнено, то оптимальным решением является N2, на выходе устройства формируется сигнал, кодирующий это решение, а импульс, формирующийся при этом на втором выходе блока 21, возвращает устройство в исходное состояние.

Дальше работа схемы продолжается совершенно аналогично и проверяются условия алгоритма, представленного на фиг. 2.

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

Таким образом; хотя число различных неравенств, проверка которых может потребоваться при отыскании оптимального решения, равно 16, поиск заканчивается не более чем через десять «шагов» (тактов). Имен- 4О но.поэтому число разрядов регистра 20 памяти выбрано равным десяти, а счетчик 18 можно выполнять четырехразрядным. Выполнение резисторов 4 — 9 регулируемыми (с линейной шкалой проводимости) позволяет 4 легко и просто перестраивать устройство в случае изменения цен.

Устройство обеспечивает автоматизацию поиска оптимального варианта раскроя, реализация которого заметно повысит эффективность раскроя, кроме того автоматизация So приводит к повышению производительности оборудования, реализующего раскрой.

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

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

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

1. Патент США № 3596068, кл. 235 — 150, кл. G 06 F 15/00, 1971.

2. Авторское свидетельство СССР № 347761, кл. G 06 F 15/46, 1972.

3. Авторское свидетельство СССР № 497606, кл. G 06 J 1/00, G 06 F 1з/20.

1971 (прототип).

813437 г.! ь Й Ь ь

uz.J

Составитель А.геренов

Заказ 346/62

Редактор Воловик Техред А. Бойкас К орректор . Бутяга

В. Б

Тираж 745 Подписное

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

113035, Москва, )K — 35, Раушская наб., д. 4/5

Филиал ППП «Патент>, г. Ужгород, ул. Проектная, 4