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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

„„SU„„1336042

А1 д11 4 G 06 б 7/122

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

H ABTOPCHOMV СВИДЕТЕЛЬСТВУ

;р

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

flO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 4053935/24-24 (22) 09.04.86 (46) 07.09.87. Бюл. № 33 (72) О. Г. Алексеев, В. Ю. Мержанов и Н. И. Ячкула (53) 681.333 (088.8) (56) Васильев В. В. и др. Решения задач оптимального планирования на электронных моделях.— К.: Наукова думка, с. 36 — 38.

Авторское свидетельство СССР № 714421, кл. G 06 G 7/48, 1980. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧИ ОПТИМАЛЬНОЙ ЗАГРУЗКИ СБОРОЧНОЙ ЛИНИИ (57) Изобретение относится к области вычислительной техники и может быть использовано для решения задачи, состоящей в распределении между m исполнителями п работ, каждая из которых может быть разбита на

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

1336042

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

1 - — "-m независимых операций, минимизирующих максимальные среди всех исполнителей суммарные затраты.

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

На чертеже представлена блок-схема устройства.

Устройство для решения задачи оптимальной загрузки сборочной линии содержит блок 1 задания исходных данных, блок 2 управления, блок 3 сумматоров и блок 4 выбора максимума суммарных затрат.

Блок 1 задания исходных данных предназначен для задания напряжений, пропорциональных затратам, необходимым для выполнения i-й операции j-го вида работ (i-l, m, j= 1, и) и содержит гп) и) потенциометпов 5;;, i= 1, m, j= 1, и и полюсов

6„, i= 1, m, j= 1, п, являющихся выходами блока.

Блок 2 управления предназначен для фиксирования определяемого распределения операций по исполнителям и управления работой блоками устройства. Блок 2 содержит (n — 1) m субблоков управления 7„, i= 1, m, j= 2, и, (и — 1) m-входовых элементов И 8„j= 2, и и аналого-импульсных преобразователей 9„ j= 2, и, (и†1)-входовый элемент ИЛИ 10, ключ 11, транспарант 12, выключатель 13,кнопочный, выключатель 14, полюса: 15;, 16, 17;;, 1=Г, m, j=2, и, 18, 19;;

i=1, m, j=2, и.

Блок 3 сумматоров предназначен для определения суммарных затрат. необходимых

j-му исполнителю для выполнения закрепленных за ним до данного шага решения операций рассматриваемых видов работ.

Блок 3 содержит сумматоры 20„j= 1, m, ключ 21, выход 22, выходы 23;, j= 1, m, группы п входов 24;, i= 1, m.

Блок 4 выбора максимума суммарных затрат предназначен для определения исполнителя, суммарные затраты на выполнение закрепленных за ним операций у которого максимальны. Блок 4 содержит операционные усилители 25;, ключи 26;, 27;, триггеры

28;, аналог-импульсные преобразователи 29;, элементы 30; задержки, i= 1, m, а также входы 31;, i= 1, m, 32 и входы 33;, i= 1, m.

Субблоки 7;;, i=1, m, j= 2, и управления одинаковы и каждый содержит двухвходовой элемент И 34, инвертор 35, m-входовый элемент ИЛИ 36, ключи 37, триггеры 38„

i= 1, m, ключи 39;, i=- 1, m.

Работа устройства основана на алгоритме, в соответствии с которым исполнителю с максимальными затратами на выполнение

5 !

О !

55 закрепленных за ним ранее операций назначается операция, требующая минимальных затрат из еще незакрепленных операций данного вида работ. При этом операции каждого вида работ должны быть предварительно упорядочены по t;; так, что t;;(t»( (1,;(1„„, где 1;; — время, необходимое для выполнения i-й операции j-го вида работ.

Перед работой подвижные контакты потенциометров 5;;, l= 1, m, 1= блока 1 устанавливаются в положения, которым соот ветствуют выходные напряжения, пропорциональные значениям t;;, i= 1, m, j= 1, п.

Работа устройства начинаетея включением выключателя 14 блока 2. При этом напряжение от шины питания через его замыкающие контакты поступает на выход 6, разомкнутую исполнительную цепь ключа 11 и первый вход субблока 71 управления. С выхода 16 блока 2 напряжение поступает на вход 22 блока 3, а с него — на управляющую цепь ключа 21. Исполнительные цепи ключа 21 соединяют выходы сумматоров 20;, i= 1, m, на входах которых есть напряжение с соответствующих потенциометров 5;,, i= 1, m с выходами 23;, i= 1, m, блока 3, соединенными с выходами 31;, i= 1, m блока

4. Все триггеры 28;, i= 1, m, блока 4 находятся в нулевом состоянии и исполнительные цепи ключей 26;, i= 1, m замкнуты, обеспечивая поступление на входы операционных усилителей 25;, i= 1, m напряжений, пропорциональных t, ь i= 1, m.

Т. е. первоначально происходит закрепление i-й операции первого вида работ за

i-м исполнителем сборочной линии. В блоке

4 происходит выбор максимума и на первом шаге, в соответствии с предварительным упорядочением элементов t;,, i= 1, m, j= 1, и, максимальным будет сигнал на входе операционного усилителя 25,„. Сигнал с его выхода через ключевой диод поступает на управляющую цепь ключа 27„,. Исполнительная цепь ключа 27„, замыкается, и напряжение от источника напряжения через нее поступает на вход установки в единицу триггера 28„,. Триггер переходит в единичное состояние и сигнал высокого уровня с его прямого выхода поступает на элемент 30„, задержки и аналого-импульсный преобразователь 29„,. Импульс с преобразователя 29,„ через выход ЗЗ„, блока 4 поступает на входы

15 блока 2, а с него — на соответствующий вход группы входов всех субблоков управления. Однако, так как только на обоих входах элемента 34 субблока 71 есть сигнал высокого уровня, то импульс через замкнутую исполнительную цепь ключа 37 субблока

7i поступает на вход установки в единицу триггера 38., только этого субблока управления. Триггер 38., субблока 7i переходит в единичное состояние, и сигнал высокого уровня с его прямого выхода поступает на один из входов элемента ИЛИ 36 и управляющую цепь ключа 39„,. Ключ 39„, срабаты1336042 вает и напряжение с подвижного контакта потенциометра 51 блока 1 поступает на один из входов группы входов 24„, блока 3, имитируя этим назначение первой операции второго вида работ m-му исполнителю. С выхода элемента 36 субблока 7i сигнал поступает на вход инвентора 39 и первый выход этого субблока. Сигнал высокого уровня на выходе инвертора 39 субблока 712 сменяется на сигнал низкого уровня, далее снимается сигнал высокого уровня с одного из входов элемента 34 и с управляющей цепи ключа 37.

Исполнительные цепи ключа 37 субблока

7 размыкаются и исключают дальнейшее участие в работе устройства субблока 7 .

С первого выхода этого субблока сигнал высокого уровня поступает на первый вход субблока 72 . а с него на один из входов элемента 34 этого субблока. С выхода 34 сигнал поступает на управляющую цепь ключа 37 и его исполнительные цепи замыкаются, готовя тем самым прием следующего импульса 20 от блока 4 субблоком 7>г управления. К этому моменту времени сигнал с элемента 30,„задержки блока 4 поступит на управляющую цепь ключа 26„,. Исполнительная цепь последнего размыкается и отключает вход операционного усилителя 25„, от входного полюса 31„,. На этом шаг работы устройства завершается и последующие (m — 1) шагов осуществляются аналогично рассмотренному

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

8 и сигнал с его выхода поступает на вход аналого-импульсного преобразователя 9 .

Импульс с его выхода поступает на один из входов элемента 10 и далее — через выход

18 блока 2 и вход 32 блока 4 на входы установки в «О» триггеров 28;, i= 1, m этого блока

Триггеры переходят в нулевое состояние и снимается сигнал высокого уровня с управляющих цепей ключей 26;, i= 1, m. Исполнительные цепи последних вновь подключают 40 входы операционных усилителей 25;, i= l,è к входам блока и устройство начинает первый шаг решения второго этапа. По завершении последнего m-го шага последнего (п — 1) -го этапа решения сигнал высокого уровня с выхода субблока 7 „поступает на управляющую цепь ключа 11 и его исполнительная цепь соединяет с источником напряжения транспарант 12, загорание которого сигнализирует об окончании решения.

Номера триггеров 38;, i= 1, m субблоков

7;; управления, i= 1, m, j= 2, п, находящихся в единичном состоянии, однозначно определяют назначение операций рассматриваемых видов работ за исполнителями.

Для возврата схемы в исходное необходимо выключить выключатель 14 блока 2 и 55 кратковременно нажать выключатель 13 кнопочный этого блока. При этом напряжение питания через замкнутые контакты выключателя кнопочного поступает на Bx()ды установки в ноль триггеров всех схбблоков управления, возвращая нх в исходное положение.

Аналогично с использованием устройства может быть решена и задача распределения неделимых забот. При этом потенциометры 5ij, j= 1, и устанавливаются в состояние, которому соответствуют напряжения на их выходах, пропорциональные

t,, j= 1, и, где t< — время на выполнение j-го вида работы, а остальные потенциометры устанавливаются в одинаковое состояние, при котором выходное напряжение пропорционально Т,) mast,, Результаты решения при этом определяются по состоянию триггеров 38„1=1, i77 cy66,7oêoâ 7„, j= 2, и, управления.

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

Устройство для решения задачи оптимальной загрузки сборочной линни, содержащее блок выбора максимума суммарных затрат, содержащий m операционных усилителей, вход каждого i-го (i=1,..rn, m — чис70 исполнителей. а — число работ) операционного усилителя соединен с первым выводом токозадаюгцего резистора и с резистором обратной связи, второй выво7 которого соединен с анодом шунтирующего диода, катод которого соединен с выходом операционного усилителя и с катодом ключевого диода, анод которого соединен с управляющим входом соответствующего ключа, аноды всех шунтирующих диодов объединены, отличающееся тем, что, с целью расширения функциона 7bnblx возможностей устройства за счет решения задачи оптимизации распределения неделимых работ и работ, состоящих из независимых операций, в него введены блок задания исходных данных, блок сумматоров, блок управления, в блок выбора максимума суммарных затрат введены m триггеров, m элементов задержки, m преобразователей аналог импульс и m входных ключей, информационные выходы которых соединены с соответствующими токозадаюгцими резисторами блока выбора максимума суммарных затрат, управляющие входы входных ключей соединены с выходами соответствующих элементов задержки, входы которых соединены с прямыми выходами соответствующих TpHtгеров и с входами соответствующих преобразователей аналог — импульс, входы установки в «О» всех триггеров соединены с управляющим входом блока выбора максиму. ма суммарных затрат, а вход установки в «!» каждого из т триггеров соединен с вы: одом соответствующего ключа, информационный вход каждого из которых соединен с входом первого положительного потенциала устройства, а выходы преобразователей аналог-импульс соединены с второй

1336042

5 группой m входов блока управления, содержащего матрицу m X (n — 1) субблоков управления, (и — 1) m-входовых элементов И, и — 1 преобразователей аналог-импульс, (и — -1)-входовый элемент ИЛИ, ключ, транспарант, кнопочный выключатель и выключатель, каждый ij-й субблок управления матрицы (i= l,...,m; j= 2,..., и) содержит двухвходовый элемент И, инвертор, т-входовый ключ, m триггеров, m ключей и т-входовый элемент ИЛИ, выход которого соединен с входом инвертора и является первым выходом !(-го субблока управления матрицы, выход инвертора соединен с первым входом двухвходового элемента И, второй вход которого является первым входом ij-го субблока управления матрицы, выход двухвходового элемента И соединен с управляющим входом m-входового ключа, m информационных входов которого являются m входами группы ij-го субблока управления матрицы, т выходов т-входового ключа соединены с входами установки в

«1» соответствуюгцих триггеров, входы установки в «О» всех триггеров соединены с вторым входом /1-го субблока управления матрицы, прямые выходы триггеров соединены с соответствующими входами т-входового элемента ИЛИ и с управляющими входами соответствующих ключей, информационные выходы которых являются выходами группы ij-го субблока управления матрицы, информационные входы всех ключей соединены с третьим входом ij-го субблока управления матрицы блока управления, первый вход субблока управления первой строки (i= 1) второго столбца (j= 2) матрицы блока управления соединен с информационным входом ключа блока управления, выход которого соединен с первым выводом транспаранта, второй вывод которого соединен с входом нулевого потенциала устройства, информационный вход ключа блока управления соединен с первым выходом блока управления и выходом выключателя, вход которого соединен с входом второго положительного потенциала устройства и с входом кнопочного выключателя, выход которого соединен с вторыми входами всех субблоков управления матрицы блока управления, третьи входы всех субблоков управления матрицы являются первой группой mX (n-1) входов блока управления, К-е выходы (К=1, ...,m) всех субблоков управления 1 -го столбца матрицы соединны с К-м выходом j-й группы

mX (n — 1) выходов блока управления, m-входы группы всех субблоков управления мат5

1О

50 рицы объединены и являются m-входами BTQрой группы блока управления, первый выход ц -го субблока управления матрицы соединен с первым входом субблока управления (i+1)-й строки этого же столбца матрицы и с соответствующим входом j-го т-входового элемента И блока управления, первый выход mj-го субблока управления соединен с первым входом субблока управления первой строки (j+1)-го столбца матрицы и с соответствующим входом j-го m-входового элемента И, первый выход mn-го субблока управления матрицы соединен с соответствующим входом и-го т- входового элемента И и с управляющим входом ключа блока управления, выходы m-входовых элементов И блока управления соединены с входами соответствующих преобразователей аналог-импульс, выходы которых соединены с соответствующими входами (и — 1) -входового элемента ИЛИ блока управления, выход которого является вторым выходом блока управления, mX (n — 1) входы первой группы блока управления соединены с mX

)((и — 1) выходами первой группы блока задания исходных данных, который состоит из матрицы mX n потенциометров, первые неподвижные контакты всех потенциометров матрицы соединены с третьим входом положительного потенциала устройства, а вторые — с входом нулевого потенциала устройства, подвижные контакты потенциометров j-го столбца (j= 2,...,n) матрицы являются mX (n — 1) выходами первой группы блока задания исходных данных, подвижные контакты потенциометров первого столбца матрицы потенциометров соединены с соответствующими входами группы блока сумматоров, который состоит из mnвходовых сумматоров, mX n резисторов и

m-входового ключа, входы К-го сумматора (К= 1, т) соединены:через резисторы с соответствующими входами-группы mX n входоц блока сумматоров, выходы всех сумматоров соединены с соответствующими информационными входами ключа блока сумматоров, управляющий. вход ключа соединен с первым выходом блока управления, второй выход которого соединен с управляюгцим входом блока выбора максимума суммарных затрат, X (и — 1) выходы группы блока управления соединены с соответствующими входами группы блока сумматоров, выходы ключа которого соединены с входами соответствующих входных ключей блока выбора максимума суммарных затрат.

l336042

Составитель С. Кошелев

Редактор С. Патрушейа Техред И. Верее Корректор М. немчик

Заказ 3805/46 Тираж 672 Подписное

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

113035, Москва, 7К вЂ” 35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4