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

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

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

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

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

Блок 1 задания исходных данных предназначен для задания напряжений, пропорциональных затратам, необходимым для вып ол нения 1-й операции j-ro вида работ (i-1, m, j 1, n) и содержит (mX п) по- тенциометров S,-/, i 1, m, j 1, n и полюсов 6,/, i 1, m, j 1, n, являющихся выходами блока.

Блок 2 управления предназначен для фиксирования определяемого распределения операций по исполнителям и управления работой блоками устройства. Блок 2 содержит(п-1)т субблоков управления 7,/,

i , m, j 2, n, (n-1) т-входовых элементов И Si j 2, п и аналого-импульсных преобразователей 9,, j 2, п, {п-1)-входовый элемент ИЛИ 10, ключ 11, транспарант 12, выключатель 13,кнопочный, выключатель 14, полюса; 15,-, 16, 17,-/, , fh, , 18, 19,-j , ш, , п.

Блок 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, гп.

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

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

0

5

закрепленных за ним ранее операций назначается операция, требующая минимальных затрат из еще незакрепленных операций данного вида работ. При этом операции каждого вида работ должны быть предварительно упорядочены по t// так, что , где t// - время, необходимое для выполнения i-й операции j-ro вида работ. Перед работой подвижные контакты потенциометров 5//, i 1, m, j 1, п блока 1 устанавливаются в положения, которым соот ветствуют выходные напряжения, пропорцио- нальные значениям t//, i 1, m, j П П- Работа устройства начинается включением выключателя 14 блока 2. При этом на2 пряжение от шины питания через его замыкающие контакты поступает на выход 16, разомкнутую исполнительную цепь ключа 11 и первый вход субблока управления. С выхода 16 блока 2 напряжение поступает на вход 22 блока 3, а с него - на управляю0 щую цепь ключа 21. Исполнительные цепи ключа 21 соединяют выходы сумматоров 20/, i 1, ш, на входах которых есть напряжение с соответствующих потенциометров 5//, i 1, m с выходами 23/, i 1, m, блока 3, соединенными с выходами 31,, i 1, m блока 4. Все триггеры 28/, i I, ш, блока 4 находятся в нулевом состоянии и исполнительные цепи ключей 26/, i 1, m замкнуты, обеспечивая поступление на входы операционных усилителей 25/, i 1, m напряжений,

Q пропорциональных t/ , i 1, m.

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

Q входах элемента 34 субблока 7i2 есть сигнал высокого уровня, то импульс через замкнутую исполнительную цепь ключа 37 субблока 7|2 поступает на вход установки в единицу триггера 38ш только этого субблока управления. Триггер 38„, субблока 7|2 переходит в

5 единичное состояние, и сигнал высокого уровня с его прямого выхода поступает на один из входов элемента ИЛИ 36 и управляющую цепь ключа 39,,,. Ключ 39„, срабаты0

5

вает и напряжение с подвижного контакта потенциометра 5i2 блока 1 поступает на одни из входов группы входов 24,,, блока 3, имитируя этим назначение первой операции второго вида работ т-му исполнителю. С выхода элемента 36 субблока сигнал поступает на вход инвентора 39 и первый выход этого субблока. Сигнал высокого уровня на выходе инвертора 39 субблока 7i2 сменяется на сигнал низкого уровня, далее снимается сигнал высокого уровня с одного из входов элемента 34 и с управляющей цепи ключа 37.

Исполнительные цепи ключа 37 субблока 7io размыкаются и исключают дальнейшее участие в работе устройства субблока . С первого выхода этого субблока сигнал высокого уровня поступает на первый вход субблока 72-2. а с него на один из входов элемента 34 этого субблока. С выхода 34 сигнал поступает на управляющую цепь ключа 37 и его исполнительные цепи замыкаются, готовя тем самым прием следующего импульса от блока 4 субблоком 722 управления. К этому моменту времени сигнал с элемента 30,„ задержки блока 4 поступит на управляющую цепь ключа 26,,,. Исполнительная цепь последнего размыкается и отключает вход операционного усилителя 25,,, от входного полюса 31т. На этом шаг работы устройства завершается и последующие (т-1) шагов осуществляются аналогично рассмотренному. В конце п-го шага рещения отключается от входного полюса блока 4 последний операционный усилитель, но присутствуют сигналы высокого уровня на всех входах элемента 82 и сигнал с его выхода поступает на вход аналого-импульсного преобразователя 92. И.мпульс с его выхода поступает на один из входов элемента 10 и далее - через выход 18 блока 2 и вход 32 блока 4 на входы установки в «О триггеров 28,, i 1, m этого блока Триггеры переходят в нулевое состояние и снимается сигнал высокого уровня с управляющих цепей ключей 26,, i 1, m. Исполнительные цепи последних вновь подключают входы операционных усилителей 25,-, i l,m к входам блока и устройство начинает первый щаг решения второго этапа. По завершении последнего т-го щага последнего (п-1)-го этапа решения сигнал высокого уровня с выхода субблока 7ш„ поступает на управляющую цепь ключа 11 и его исполнительная цепь соединяет с источником напряжения транспарант 12, загорание которого сигнализирует об окончании рещения. Номера триггеров 38,, i 1, m субблоков 7,/ управления, 1 1, т, j 2, п, находящихся в единичном состоянии, однозначно определяют назначение операций рассматриваемых видов работ за исполнителями.

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

0

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

Аналогично с использованием устройства может быть решена и задача распределения неделимых работ. При этом потенциометры 5ij, j 1, n устанавливаются в состояние, которому соответствуют напряжения на их выходах, пропорциональные tj, j 1, п, где t./- время на выполнение j-ro вида работы, а остальные потенциометры устанавливаются в одинаковое состояние, при котором выходное напряжение пропорционально Tj maxti. Результаты решения при этом определяются по состоянию триггеров , m субблоков 7,,, j 2, п, управления.

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

0 Устройство для peцJeния задачи оптимальной загрузки сборочной линии, содержащее блок выбора максимума суммарных затрат, содержащий т операционных усилителей, вход каждого i-ro (,..m, m - чисr ло исполнителей, п - число работ) операционного усилителя соединен с первым выводом токозадающего резистора и с резистором обратной связи, второй вывод которого соединен с анодом шунтирующего диода, катод которого соединен с выходом

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

5 устройства за счет рещения задачи оптимизации распределения неделимых работ и работ, состоящих из независимых операций, в него введены блок задания исходных данных, блок сумматоров, блок управления, в блок выбора максимума суммарных зат0

рат введены m триггеров, т элементов задержки, т преобразователей аналог - импульс и т входных ключей, информационные выходы которых соединены с соответствующими токозадающими резисторами блока выбора максимума суммарных зат- рат, управляющие входы входных ключей соединены с выходами соответствующих элементов задержки, входы которых соединены с прямыми выходами соответствующих триггеров и с входами соответствующих преобQ разователей аналог- импульс, входы установки в «О всех триггеров соединены с управляющим входом блока выбора максимума суммарных затрат, а вход установки в «1 каждого из т триггеров соединен с выходом соответствующего ключа, информа5 ционный вход каждого из которых соединен с входом первого положительного потенциала устройства, а выходы преобразователей аналог-импульс соединены с второй

группой m входов блока управления, содержащего матрицу mx(n-1) субблоков управления, (п-1) т-входовых элементов И, п - 1 преобразователей аналог-импульс, (п-1)-входовый элемент ИЛИ, ключ, транспарант, кнопочный выключатель и выключатель, каждый //-и субблок управления матрицы (; 1,...,ш; / 2,..., п) содержит двухвходовый элемент И, инвертор, т-входо- вый ключ, m триггеров, т ключей и т-входорицы объединены и являются т-входами второй группы блока управления, первый выход (/-го субблока управления матрицы соединен с первым входом субблока управления (/+1)-й строки этого же столбца матрицы и с соответствующим входом У-го т-входо- вого элемента И блока управления, первый выход mj-ro субблока управления соединен с первым входом субблока управления первой строки (/-(-1)-го столбца матрицы и

вый элемент ИЛИ, выход которого соеди- 10 с соответствующим входом j-ro m-входового

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

ды группы всех субблоков управления мат-

рицы объединены и являются т-входами второй группы блока управления, первый выход (/-го субблока управления матрицы соединен с первым входом субблока управления (/+1)-й строки этого же столбца матрицы и с соответствующим входом У-го т-входо- вого элемента И блока управления, первый выход mj-ro субблока управления соединен с первым входом субблока управления первой строки (/-(-1)-го столбца матрицы и

с соответствующим входом j-ro m-входового

0

5

0

лог-импульс, выходы которых соединены с соответствующими входами (п-1)-входо- вого элемента ИЛИ блока управления, выход которого является вторым выходом блока управления, тХ (-1) входы первой группы блока управления соединены с тХ X(л - 1) выходами первой группы блока задания исходных данных,который состоит из матрицы тХ п потенциометров, первые неподвижные контакты всех потенциометров матрицы соединены с третьим входом положите.аьного потенциала устройства, а вторые - с входом нулевого потенциала устройства, подвижные контакты потенциометров /-го столбца (/ 2,...,п) матрицы являются тХ («-1) выходами пер0

затрат.

вой группы блока задания исходных данных, подвижные контакты потенциометров первого столбца матрицы потенциометров соединены с соответствующими входами группы блока сумматоров, который состоит из тп- входовых сумматоров, тХ п резисторов и т-входового ключа, входы./(-го сумматора (К 1, т) соединены,-через резисторы с соответствующими входйми-группы тХ доц блока сумматоров, выходы всех сумматоров соединены с соответствующими информационными входами ключа блока сумматоров, управляющий- вход ключа соединен с первым выходом блока управления, второй выход которого соединен с управляющим входом блока выбора максимума суммарных затрат, X (п-1) выходы группы блока уп 1авления соединены с соответствующими входами группы блока сумматоров, выходы ключа которого соединены с входами соответствующих входных ключей блока выбора максимума суммарных

5

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