Устройство для выбора вариантов распределения мест между исполнителями

 

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

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

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

РЕСПУБЛИК (50 4 С 06 F 15/20

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3824194/24-24 (22) 17.12.84 (46) 30.06.86. Бюл. N -24 (72) О.А. Алексеев, P. Э. Гут и В. B. Егоров (53) 681. 325. 22 (088. 8) (56) Авторское свидетельство СССР

Ф 807310, кл. G Об F 15/20, 1978.

Патент США Ф 38084.10, кл. 235-156, кл. G 06 Р 15/20, 1974 . (54) УСТРОЙСТВО ДЛЯ ВЫБОРА ВАРИАНТОВ

РАСПРЕДЕЛЕНИЯ, МЕСТ МЕЖДУ ИСПОЛНИТЕЛЯМИ (57) Изобретение относится к вычислительной технике и может быть использовано для принятия решения о наилучшем назначении исполнителя на определенные работы. Целью изобретения является повышение эффективности за счет обеспечения оптимального назначения для максимального числа исполнителей, Устройство содержит блок регистровой памяти, распределитель импульсов, элементы И, ИЛИ, блок буферной памяти и решающий блок, тактовый вход которого, соединен с тактовым входом устройства, выходы подключены к входам блока регистровой памяти. и

„„SU„„324125 А 1 блока буферной памяти, а управляющие и информационные входы соединены с соответствующими выходами блока регистровой памяти, выход второго элемента И через первый элемент И и первый элемент ИЛИ соединен со входом распределителя, два выхода которого через второй элемент ИЛИ подключены к второму входу первого элемента И, выход которого соединен с входом считывания блока регистровой памяти, а два других выхода распределителя соединены .с входами решающего блока, входы второго элемента И соединены соответственно с тактовым входом и входом пуска устройства, блок регистровой памяти соединен. с блоком буферной памяти. Решающий блок выполнен с применением групп элементов И, ИЛИ, двух групп триггеров и двух групп элементов запрета, двух элементов ИЛИ и матрицы. узлов коммутации, каждый из которых позволяет осуществлять задержку прохождения входных импульсов на один такт. Блок регистровой памяти и блок буферной памяти выполнены на триггерах с элементами И, ИЛИ для записи и считывания информации. 5 нл.

1241255

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

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

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

Устройство содержит распределитель импульсов, элемент И 2, элементы

ИЛИ 4 и 3, элемент И 5, блок 6 регистровой памяти, решающий блок 7, блок 8 буферной памяти, выходы 9 и

10 распределителя импульсов, тактовый вход 11 устройства, выходы 12 и 13 распределителя импульсов, вход

14 пуска устройства, триггеры 15, группы 16 элементов ИЛИ, группы 1719 элементов И, группы 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.

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

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

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

t0

55.и числа исполнителей еще не получивших место уменьшилось на единицу.

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

Устройство работает следующим образом, Кажцый регистр блока 6 (число регистров равно числу исполнителей

М) содержит триггеры 15, число которых равно количеству мест N на которые может быть назначен исполнитель.

Изложение, работы устройства ведется для случая М=И=З, т.е. когда имеется три исполнителя и три места. Соответственно этому устройство содержит три регистра и по три триггера в регистре. Доход h Ä (m=1, М, п=1, N), получаемый тп-м исполнителем при его назначении на и-е место по условию принимает значение h „=1 ("Удовлетворительно) или значение h 00 ("Неудовлетворительно").

Перед началом работы устройства в триггеры блока 6 записываются зна чения чисел h В каждый триггер первого регистра записывается число h< (доход при назначении первого исполйителя íà j-e место), в каждый триггер второго регистра записывается число h< (доход при назначении второго исполнителя на j е место),. в каждый триггер третьего регистра записывается число h (доход при назначении третьего исполнителя

j-e место) .

В исходном состоянии все триггеры

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

1 устройства находится в исходном состоянии, при котором единичный сигнал снимается с его выхода 13.

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

14 устройства.

Если все числа h, (=1,...,М;

j=l,....,N) равны нулю, то при любом назначении исполнителей на места суммарный доход равен нулю. В этом случае с выходов всех элементов

ИЛИ 21 и, следовательно, с выхода ь элемента ИЛИ 22 блока 6 снимается нулевой сигнал, который через выход

29 блока 6 поступает на вход элемента И 2 устройства и запрещает

1241255

1О

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

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

ИЛИ 21 и выход 27 блока 6 поступает на вход соответствующего элемента

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

8 остаются в нулевом состоянии, что свидетельствует о том, что йи один исполнитель не может получить место с удовлетворительным (единичным) доходом.

Если хотя бы одно число h„" не равно нулю, на выходе 29 блока 6 возникает единичный сигнал. При подаче на вход 14 устройства единичного 5 сигнала тактовые импульсы с входа

11 начнут проходить через элемент

И 2 устройства.

Поскольку в исходном состоянии устройства единичный сигнал снима- 20 ется с выхода 13 распределителя 1, он поступает через элемент ИЛИ 4 устройства на вход элемента И 5.

Поэтому первый тактовый импульс через элемент И 22 поступает на вход

23 блока 6. Единичный сигнал с входа 23 блока 6 поступает на входы всех элементов И 17 и 18. С выходов этих элементов сигналы поступают на блок 7. Это приводит к тому, 30 что на входах узлов 35 блока 7 (инверсньгй и прямой входы триггеров

31 этих узлов) появляются напряжения совпадающие с напряжениями инверсного и прямого выходов соответствующих им триггеров 15 (т.е. имеющих те же индексы i, j) блока 6.

Единичный сигнал с тактового входа

I1 устройства поступает на тактовые входы всех узлов 35 (тактовые входы триггеров 31). Это приводит к записи содержимого триггеров 15 блока 6 в триггеры 31 соответствующих им узлов 35 блока 7.

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

И 33.

Таким образом, если триггер 31 имеет единичное состояние, то узел

35 осуществляет функцию задержки прохождения импульса на один такт. для фиксированного j ãî места совокупность узлов 35 осуществляет за- держку прохождения тактовых импульсов с выхода элемента И 36 на столько тактов, сколько единиц записано в триггерах 31 узлов 35.

Если суммарное количество единиц, записанных в триггерах 31 узлов 35, 35, 35>,, отпично от нуля и меньше или равно количеству единиц, записанных в триггерах 31 узлов 35,, 35zz, 35, а также меньше или равйо количеству единиц в триггерах 31 узлов 35, 35<, 35 », то тактовый импульс, прошедший по пути: вход модуля 35и— выход модуля 35 — элемент 42 ИЛИ— выход 49 блока 7 — элемент ИЛИ 3 устройства, поступает на распределитель

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

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

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

1241255 с выхода элемента ИЛИ 42 через эле менты ЗАПРЕТ 38 и элементы И 39 на единичные входы остальных триггеров

40 в случае, если в триггерах 31 узлов 351, 35, 35, либо узлов

5 35 35 личество единиц, как в триггерах 31 узлов 35 t1 35 zt 35 31

Если количество единиц в триггерах 1О

31 узлов 351<, 35, 35 > отлично от нуля и меньше, чем количество единиц в триггерах 31 узлов 35I» 35,, 35,, а также меньше или равно количеству единиц в триггерах 31 узлов 35, 35, 35, то тактовый импульс быстрее приходит по пути: вход узла 35

ИЛИ 42 и элемент ЗАПРЕТ и поступает на вход элемента И 39. Совпадение единичных сигналов на его входах приводит к записи единицы во второй триггер 40, а на втором выходе 26 появляется единичный сигнал. Так говый импульс с выхода узла 35 через ЗО элемент ИЛИ 42, выход 49 блока 7 поступает через элемент ИЛИ 3 на вход распределителя 1 и переводит его в следующее состояние 12.

Если число единиц в триггерах

3I узлов 35,, 35, 353% равно числу единиц в триггерах 31 узлов 35

3522, 35я, то тактовый импульс на единичный вход триггера 40 не проходит, так как элемент И 39 закрыт, щб поскольку закрыт второй элемент ЗАПРЕТ 38,т. е. единичный сигнал появляется только на втором выходе 26 блока 7.

Аналогично, если минимальным (но отличным от нуля) оказывается число единиц в триггерах 31 узлов 35

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

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

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

Так как единичный сигнал, снимаемый теперь с выхода 12 распределителя 1, через элемент ИЛИ 4 устройства поступает на вход элемента И 5, очередной тактовый импульс с входа 11 устройства через элементы И 2 и 5 поступает на вход блока 6 и через элемент . ЛЛИ 3 на вход распределителя I так что по окончании тактовогО импульса распределитель переходит в следующее состояние. Единичный сигнал на входе 23 блока 6 приводит к записи содержимого триггеров 15 блока 6 в триггеры 31 соответствующих узлов 35. Единичный сигнал с . первого выхода 26 блока 7 поступает на входы элементов И 19 блока 6.

Если в соответствующий триггер 15 записана единица (hl, =!), то совпадение единичных сигналов на входах соответствующего элемента И 19 вызывает единичный сигнал на входе элемента ИЛИ 20 и выходе 28 блока 6.

Это приводит к тому, что тактовые импульсы с входа ll устройства начинают проходить через элемент И 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 появится единичный сигнал. Пусть для определенности единичный сигнал возникает на первом выходе 48 блока 7. Тогда совпа- дение единичных сигналов на выходах соответствующего элемента И 54 блока

8 вызывает единичный сигнал на его выходе, что приводит к записи единицы в триггер 51, т.е ° первый, исполнитель назначен на первое МрсТО

Единичный сигнал с выхода этого триггера 51 через элемент ИЛИ 52 поступает на. выход 24 блока 8 и че! 241255 рез элемент ИЛИ 53 на выход 25 блока

8. Единичный сигнал через вход 24 блока 6 и элементы ИЛИ 16 поступает на входы триггеров 15 первой группы и обнуляет их содержимое. Нулевые сигналы на входах первого элемента

ИЛИ 20 вызывают нулевой сигнал на первом выходе 28 блока 6, который закрывает первый элемент И 37 блока 10 .7, т.е. первый исполнитель исключен из дальнейшего рассмотрения. Кроме того, нулевой сигнал на первом входе

28 блока 7 вызывает нулевой сигнал на выходе первого элемента И 46 и на 15 первом выходе 48 блока 7, что исключает воэможность записи единицы в триггеры 51.

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

7, т.е. первое место исключается из дальнейшего рассмотрения. 25

Нулевой сигнал на первом входе

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

Если теперь все триггеры 15 находятся в нулЕвом состоянии, то нулевые сигналы на выходах элементов ИЛИ

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

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

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

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

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

124!255

1241255 г5

1Риа. f

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

Редактор Л. Пчелинская Техред H.Êàäàð Корректор А. Обручар

Заказ 3601/45 Тираж 671

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

113035, Москва, Ж-35, Раушская наб, ц. 4/5

Подписное

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