Устройство для выбора вариантов распределения мест между исполнителями Советский патент 1986 года по МПК G06F15/173 

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

Цель изобретения - повьппение эффективности устройства путем опти- мального назначения для максимально То числа исполнителей.

На фиг. 1 представлена схема устройства; на фиг. 2 - схема блока регистровой памяти; на фиг. 3 - схема узла коммутации; на фиг. 4 - схема решающего блока; на фиг, 5 - схема блока буферной памяти.

Устройство содержит распределите 1 импульсов, элемент И 2, элементы ИЛИ 4 и 3, элемент И 5, блок 6 регистровой памяти, решающий блок 7, блок 8 буферной памяти, выходы 9 и 10 распределителя импульсов, тактовый вход 11 устройства, выходы 12 и 13 распределителя импульсов, вход 4 пуска устройства, триггеры 15, группы 16 элементов ИЛИ, группы J7- 19 элементов И, группы 20 и 21 элементов ИЛИ, элемент ИЛИ 22, связи 23-30 входрв и выходов устройства, триггер 31 , элементы И 32 и 33, элемент ИЛИ 34, матрица 35 узлов коммутации, группы 36 и 37 элементов И, элемент ЗАПРЕТ 38, элемент И 39, группы 40 триггеров, группы 41 элементов И, элемент ИЛИ 42, группы 43 триггеров, группы 44 элементов ЗАПРЕТ , группы 45 и 46 элементов И, элемент ШШ 47, связи 48-50 входов и выходов устройства, триггеры 51, группы 52 и 53 элементов ИЛИ и элементы И 54.

Принцип работы устройства основа на следующем.

Первоначально выбирается то из мест, которое удовлетворяет наименьшее число исполнителей. Далее сопоставляются все исполнители, для которых пригодно вьщеленное место. Среди этих исполнителей выделяется тот, который имеет наименьшее число удовлетворяющих его мест. Введенный таким образом исполнитель назначается на выбранное место. Место оказывается занятым, исполнитель считается получившим это место. Поэтому и место и исполнитель исключаются из дальнейшего рассмотрения. Таким образом число еще не занятых мест

5

0

5

,и число исполнителей еще не получивших место уменьшилось на единицу. Далее процедура повторяется до тех пор, пока или все исполнители получают удовлетворяющие их места, или таких мест на всех не хватает.

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

Каж,цый регистр блока 6 (число регистров равно числу исполнителей М) содержит триггеры 15, число которых равно количеству мест N, на кото- pbfe может быть назначен исполнитель. Изложение .работы устройства ведется для случая , т.е. когда имеется три исполнителя и три места. Соответственно этому устройство содержит три регистра и по три триггера в ре- гистре. Доход h ( , М, , N) , получаемый т-м исполнителем при его назначении на п-е место по условию принимает значение Ьл, (-Удовлетворительно) или значение (Неудовлетворительно) .

Перед началом работы устройства в триггеры блока 6 записываются значения чисел h.

В каждый триггер

0

5

0

5

5

0

первого регистра записывается число hyjj (доход при назначении первого исполнителя на j-e место), в каждый тригг€1р второго регистра записывается число hg- (доход при назначении второго исполнителя на j-e место), . в каждый триггер третьего регистра записывается число (доход при назначении третьего исполнителя j-e место).

Б исходном состоянии все триггеры 40 и триггеры 43 блока 7, а также триггеры 51 блока 8 имеют нулевое состояние (обнуляются перед началом работы устройства), распределитель 1 устройства находится в исходном состоянии. при котором единичный сигнал снимается с его выхода 13.

Работа устройства начинается с подачи единичного сигнала на вход 14 устройства.

Если все числа h; (,...,М; - j l,.,,.,N) равны нулю, то при любом назначении исполнителей на места суммарный доход равен нулю. В этом случае с выходов всех элементов ИЛИ 21 и, следовательно, с выхода элемента ИЛИ 22 блока 6 снимается нулевой сигнал, который через выход 29 блока 6 поступает на вход элемента И 2 устройства и запрещает

.

поступление импульсов с тактового входа 11 на остальные узлы устройства. Нулевой сигнал на выходе 29 блока 6 свидетельствует о том, что этом случае работа устройства за- кончена. При этом все триггеры блок

8остаются в нулевом состоянии, что свидетельствует о том, что йи один исполнитель не может получить место

с удовлетворительньм (единичным) доходом.

Если хотя бы одно число h;: не равно нулю, на выходе 29 блока 6 воникает единичный сигнал. При подаче на вход 14 устройства единичного сигнала тактовые импульсы с входа 11 начнут проходить через элемент И 2 устройства.

Поскольку в исходном состоянии устройства единичный сигнал снима- ется с выхода 13 распределителя 1, ои поступает через элемент ИЛИ 4 устройства на вход элемента И 5. Поэтому первый тактовый импульс через элемент И 22 поступает на вход 23 блока 6. Единичный сигнал с входа 23 блока 6 поступает на входы всех элементов И 7 и 18. С выходов этих элементов сигналы поступают на блок 7. Это приводит к тому, что на входах узлов 35 блока 7 . (инверсный и прямой входы триггеров 31 этих узлов появляются напряжения совпадающие с напряжениями инверсного и прямого выходов соответ- ствующих им триггеров 15 (т.е. имеющих те же индексы i, j) блока 6. Единичный сигнал с тактового входа 11 устройства поступает на тактовые входы всех узлов 35 (тактовые входы триггеров 31). Это приводит к записи содержимого триггеров 15 блока 6 в триггеры 31 соответствующих им узлов 35 блока 7.

Единичный сигнал с выхода элемен- та И 5 устройства поступает также через элемент ИЛИ 3 на вход распределителя 1 и переводит его в следующее состояние, так что к моменту прихода второго тактового импульса еди- ничный сигнал уже снимается с выхода

9распределителя 1. Если для некоторого места хотя бы один из триггеров блока 6 имеет единичное состояние,

то единичный сигнал через элен|ент ИЛИ 21 и выход 27 блока 6 поступает на вход соответствующего элемента И 36 блока 7.

2554

Так как единичное напряжение снимается теперь с выхода 9 распределителя 1 , очередные тактовые импульсы с входа 11 устройства начинаю проходить через элемент И 36 блока 7 на управляющий вход узла 35. В противном случае элемент И 36 закрыт и тактовые импульсы на управляющий вход узла 35 не поступают. Если в триггер 31 узла 35 записана единица, то с его нулевого выхода снимается нулевой сигнал, запрещающий прохождение тактового импульса через элемент И 33 на выход узла 35. В этом случае тактовый импульс поступает через элемент ИЛИ 34 на нулевой вход триггера 3 и переводит его своим задним фронтом в нулевое состояние, что разрешает прохождение следущего тактового импульса через элемен И 33.

Таким образом, если триггер 31 имеет единичное состояние, то узел 35 осуществляет функцию задержки прохождения импульса на один такт. Для фиксированного j-ro места совокупность узлов 35 осуществляет задержку прохождения тактовых импульсов с выхода элемента И 36 на стольк тактов, сколько единиц записано в триггерах 31 узлов 35. Если суммарное количество единиц записанных в триггерах 31 узлов 35„ , 352, , , отлично от нуля и меньще или авно количеству единиц,записанных в триг.герах 31 узлов 35,, , 35 35, а также меньще или равно количеству единиц в триггерах 31 узлов , 35j5, 35-, то тактовый импульс, прошедший по пути: вход модуля 35( - выход модуля элемент 42 ИЛИ - выход 49 блока 7 - элемент ИЛИ 3 устройства,- поступает на распределитель 1 и переводит его в следующее состояние 12. Одновременно тактовый импульс, пройдя на единичный вход триггера 40 в блоке 7, вызывает единичньд сигнал на его выходе.

Совпадение единичных сигналов на входах элемента И 41 (поскольку в рассматриваемом случае на первом входе 27 блока 7 присутствует единичный сигнал) вызьгоает единичный сигнал на первом выходе 26.

Одновременно тактовый импульс на выходе узла 35 закрывает соответствующий элемент ЗАПРЕТ, что запрещает прохождение тактового импульса

с выхода элемента ИЛИ 42 через элементы ЗАПРЕТ 38 и элементы И 39 на единичные входы остальных триггеров 40 в случае, если в триггерах 31 уз- лов , ЗЗгг , 35,25 либо узлов 35,, , ЗЗ, , записано такое количество единиц, как в триггерах 31 узлов 35 fl , 352, , Jt

Если количество единиц в триггера 31 узлов 35,2 , , 35,2 отлично от нуля и меньше, чем количество единиц в триггерах 31 узлов 35, , ЗЗ) , 33 а также меньше или равно количеству единиц в триггерах 31 узлов 33 , 352, 35,, то тактовый импульс быстрее приходит по пути: вход узла 35/12 вход узла . и поступает на вход элемента И 39. Поскольку на выходе узла 35 , тактовый импульс отсутству ет, то первый элемент ЗАПРЕТ 38 открыт . Поэтому тактовый импульс с выхода узла проходит через элемент ИЛИ 42 и элемент ЗАПРЕТ и поступает на вход элемента И 39. Совпадение единичных сигналов на его входах приводит к записи единицы во второй триггер 40, а на втором выходе 26 появляется единичный сигнал. Тактовый импульс с выхода узла через элемент РШИ 42, выход 49 блока 7 поступает через элемент ИЛИ 3 на вход распределителя 1 и переводит его в следуютцее состояние 12.

Если число единиц в триггерах 31 узлов 35, 332J , 33 j равно числу единиц в триггерах 31 узлов 35, 352, 33 2; О тактовый импульс на единичньш вход триггера 40 не про- хрдит; так как элемент И 39 закрыт, поскольку закрыт второй элемент ЗАПРЕТ 38 ,т .е . единичный сигнал появляется только на втором выходе 26 блока 1 . Аналогично, если минимальным (но отличным от нуля) оказывается число единиц в триггерах 31 узлов 33, , 35, , 35 а, единичный сигнал появляется только на третьем выходе 26 блока 7. .

Предположим, что единичный сиг- нал возникает на первом, вь гходе 26 блока 7, т.е. некоторый исполнитель назначен на первое место.

Определение номера этого исполнителя происходит следующим образом.

Так как единичный сигнал, снимаемый теперь с выхода 12 распределителя 1 , через элемент ИЛИ 4 устройства

поступает на вход элемента И 5, очередной тактовьм имгГульс с входа I 1 устройства через элементы И 2 и 5 поступает на вход блока 6 и через элемент ИЛИ 3 ка вход распределителя 15 так что по окончании тактового импульса распределитель переходит в следующее состояние. Единичный сигнал на входе 23 блока 6 приводит к записи содержимого триггеров 15 блока 6 в триггеры 3 соответствующих узлов 35. Единичный сигнал с первого выхода 26 блока 7 поступает на входы элементов И 19 блока 6. Если в соответствующий триггер 15 записана единица (hj,l), то совпадение единичных сигналов на входах соответствующего элемента И 19 вызывает единичньш сигнал на входе элемента ИЛИ 20 и выходе 28 блока 6. Это приводит к тому, что тактовые импульсы с входа 11 устройства начинают проходить через элемент И 37 блока 7, т.е. i-й исполнитель исключается из рассмотрения при назначении исполнителей на первое место. Логика работы блока 7 при подаче единичного сигнала на его вход с выхода 10 распределителя 1 идентична логике р аботы при подаче единичного сигнала на его вход с выхода 9 распределителя 1.

При этом роль элементов 36-42 выполняют элементы 37, 44, 45 43, 46 и 47 соответственно.

Таким образом, через некоторое количество тактов на выходе элемента ШШ 47 блока 7 появляется тактовый импульс, который через выход 50 блока 7, соединенный с входом элемента 3 ИЛИ устройства, и элемент 3 ИПР устройства поступает на вход распределителя 1 и переводит его в. следующее состояние 13, а на одном из выходов 48 появится единичный сигнсШ, Пусть для определенности eдин rчньш сигнал возникает на первом выходе 48 блока 7. Тогда совпа- дение единичных сигналов на выходах соответствующ€;го элемента И 54 блока 8 вызьшает единштый сигнал на его выходе, что приводит к записи единицы в триггер 51, т.е. первый, исполнитель назначен на первое место. Единичный сигнал с выхода этого триггера 31 через элемент ИЛИ 32 поступает на выход 24 блока 8 и через элемент ИЛИ 53 на выход 25 блока 8. Единичный сигнал через вход 24 блока 6 и элементы ИЛИ 16 поступает на входы триггеров 5 первой группы и обнуляет их содержимое. Нулевые сигналы на входах первого элемента ИЛИ 20 вызывают нулевой сигнал на первом выходе 28 блока 6, который закрывает первый элемент И 37 блока 7, т.е. первый исполнитель исключен из дальнейшего рассмотрения. Кроме того,нулевой сигнал на первом входе 28 блока 7 вызывает нулевой сигнал на выходе первого элемента И 46 и на первом выходе 48 блока 7, что исключает возможность записи единицы в триггеры 51.

Аналогично единичный сигнал на входе 25 блока 6 обнуляет содержимое триггеров 15, а на первом входе 27 блока 7 появляется нулевой сигнал, который закрывает элемент И 36 блока 7, т.е. первое место исключается из дальнейшего рассмотрения.

Нулевой сигнал на первом входе 27 блока 7 вызывает нулевой сигнал на выходе первого элемента И 41 и первом выходе 26 блока 7, что исключает возможность записи единиць в триггеры 51 в дальнейшем.

Если теперь все триггеры 15 находятся в нулевом состоянии, то нулевые с игналы на выходах элементов ИЛИ 21 блока 6 вызывают нулевой сигнал на выходе 29 блока 6, который поступает на. элемент И 2 устройства, так что очередной тактовый импульс не проходит через элемент И 2 и распределитель 1 остается в положении 13, как и устройство в исходном состоянии. Нулевой сигнал на выходе 29 блока 6 свидетельствует об окончании работы устройства, так как ни один- из оставшихся исполнителей не может быть назначен на место с единичным доходом. Если хотя бы один из триггеров 15 блока 6 имеет единичное состояние, то на выходе 29 блока 6 присутствует единичный сигнал и устройство повторяет процедуру-чназначения .

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

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

Устройство для выбора вариантов распределения мест между исполнителями, содержащее блок регистровой п 1мяти, распределитель импульсов, элементы И и ИЛИ, отличающееся, тем, что, с целью повышения эффективности за счет обеспечения оптимального назначения для максимального числа исполнителей, в него введены блок буферной памяти и решающий блок, включающий матрицу узлов коммутации, группы элементов И, ИЛИ, ЗАПРЕТ, группы триггеров и элементы ИЛИ, причем стробирующие входы узлов коммутации соединены с тактовым входом устройства, первый и второй информационные входы каждог узла коммутации соединены с первой и второй группами информационных выходов блока растровой памяти, первый управляющий вход каждого узла коммутации последующего столбца каждой строки матрицы соединен с первым выходом соответствующего узла коммутации предыдущего столбца соответствующей строки матрицы, а второй управляющий вход каждого последующего узла коммутации каждого столбца мат- .рицы подключен к второму выходу пре- дьщущего узла коммутации того же столбца матрицы, первые управляющие входы узлов коммут.ации первого столбца матрицы соединены соответственно с выходами элементов И первой группы первые и вторые входы которых подключены соответственно к первому, выходу распределителя имцульсов и к тактовому входу устройства, третьи входы элементов И первой группы соединены соответственно с выходами признаков номеров занятых разрядов блока регистровой памяти, вторые управляющие входы узлов коммутации первой строки соединены соответственно с выходами элементов И второй группы, первые и вторые входы которых подключены соответственно к второму выходу распределителя импульсов и

к тактовому входу устройства, третьи входы элементов И второй группы соединены соответственно с выходами признаков номеров занятых ячеек блока регистровой памяти, первые выходы узлов коммутаций последнего столбца, кроме узла коммутации последней строки, подключены соответственно к управляющим входам элементов ЗАПРЕТ первой группы, первые выходы узлов коммутации последнего столбца матрицы соединены соответственно с входами первого элемента ИЛИ решающего блока, выход которого соединен с первым входом первого элемента ИЛИ устройства и информационным входом первого элемента ЗАПРЕТ первой группы, выход каждого предыдущего элемента ЗАПРЕТ первЬй группы соединен с информационным входом каждого последующего элемента ЗАПРЕТ первой грур- пы, выходы элементов ЗАПРЕТ первой группы соединены соответственно с первыми входами элементов И третьей группы, первый выход узла коммутации первой строки последнего столбца матрицы соединен с единичным входом первого триггера первой группы, единичные входы триггеров первой группы, начиная с второго, подключены соответственно к выходам элементов И третьей группы, вторые входы которых соединены соответственно с первыми выходами узлов коммутации последнего столбца матрицы, начиная с второй строки, единичные выходы триггеров первой группы соединены соответственно с первыми входами элементов И четвертой группы, вторые входы которых соединены соответственно с выходами признаков номеров занятых разрядов блока регистровой памяти, выходы элементов И четвертой группы соединены с первым входом считывания блока регистровой памяти, вторые выходы узлов коммутации последней строки матрицы, кроме узла коммутации первого столбца последней строки соединены соответственно с управляющими входами элементов ЗАПРЕТ второй группы, начиная с первого элемента, вторые выходы узлов коммутации последней строки матрицы -соединены соответственно с входами вто0

5

0

.)

0

5

0

5

рог.о элемента ШШ решающего блока, выходы которого подключены к второму входу первого элемента ИЛИ устройства и к информационному входу последнего элемента ЗАПРЕТ второй группы решающего блока, информационный вход каждого предыдущего элемента ЗАПРЕТ второй группы соединен с выходом последующего элемента ЗАПРЕТ второй группы, выходы элементов ЗАПРЕТ, второй группы подключены соответственно к первым входам элементов И пятой группы, единичный вход последнего триггера второй группы соединен с вторым выходом узла коммутации последнего столбца последней строки матрицы, вторые выходы узлов коммутации последней строки матрицы, кроме узла коммутации последней строки последнего столбца,, соединены соответственно с вторыми входами элементов И пятой группы, выходы которых подключены соответственно к единичным входам триггеров второй группы, единичные выходы которых соединены соответственно с первыми входами элементов И шестой группы, вторые входы которых соединены соответств.енно с выходами признаков номеров занятых ячеек блока регистровой памяти, а выходы подключены соответственно к второму входу записи блока буферной памяти, выходы признаков номеров занятых ячеек и выходы признаков номеров занятых разрядов которого подключены соответственно к установочным входам блока регистровой памяти, второй вход считывания ко- торого и третий вход первого элемента ИЛИ устройства соединены. с выходом первого элемента И, выход признака окончания блока регистровой памяти, вход пуска и тактовый вход устройства соединены соответственно с входами второго элемента И -устройства, ВЫХ.ОД которого и выход второго элемент-а ИЛИ устройства соединены соответственно с входами первого элемента И, входы второго элемента Irlfffl устройства соединены соот- ветственно с третьим и четвертым выходами распределителя импульсов, вход которого соединен с выходом первого элемента ИЛИ устройства. О(/г. 7

3f

133

2

.27

фиг. 2

Фи1. 3

я

Изобретение относится к вычислительной технике и может быть ис,пользовано для принятия решения о наилучшем назначении исполнителя на определенные работы. Целью изобретения является повышение эффективности за счет обеспечения оптимального назначения для максимального числа исполнителей. Устройство содержит блок регистровой памяти, распределитель импульсов, элементы И, ИЛИ, блок буферной памяти и решающий блок, тактовый вход которого соединен с тактовым входом устройства, выходы подключены к входам блока регистровой памяти и блока буферной памяти, а управляющие и информационные входы соединены с соответствующ1тми выходами блока регистровой памяти, выход второго элемента И через первый элемент И и первый элемент ИЛИ соединен со входом распределителя, два выхода которого через второй элемент ИЖ подключены к второму входу первого элемента И, выход которого соединен с входом счй- тьшания блока регистровой памяти, а два других выхода распределителя соединены .с входами решающего блока, входы второго элемента И соединены соответственно с тактовым входом и входом пуска устройства, блок- регистровой памяти соединен.с блоком буферной памяти Решающий блок выполнен с применением групп элементов И, ИЛИ, двух групп триггеров и двух групп элементов запрета, двух элементов ИЛИ и матригда.узлов коммутации, каждый из которых позволяет осуществлять задержку прохождения входных импульсов на один такт. Блок регистровой памяти и блок буферной памяти выполнены на триггерах с элементами И, ИЛИ для записи и считывания информации. 5 ил. с «е СЛ С L ND 4 N5 сл 01

2S

Zif

Составитель A, Жаренов Редактор Л. Пчелинская Техред В.Кадар Корректор А, Обручар

Заказ 3601/45Тираж 671Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раутлскаи наб. , д, 4/5

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