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

(50 4 С 06 Р 15/20 ИСАНИЕ ИЗОБРЕТЕНИЯ А ВТОРСНОМУ СВИДЕГЕЛЬСТВУ21) 3824194/222) 17.12,8446 30.06.86. юл. 9 24ев, Р.Э. Г СССР1978. О, 1974.АРИАН ТОВОЛНИТЕ(57) Изобр лительной ние относится к вычис нике и может быть исользовано принятия решения о изобрет ективноальн ого ачения для мак ителей, Устрой егистровой пам мального числво содержит бли, распределиты И, ИЛИ, блоешающий блок, соединен с та испол октель импульсов, элем ферной памяти и к ктовыи вход которо входом устройст к входам блока то выходы подключеныгистровой памяти. и ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ(54) УСТРОЙСТВО ДЛЯ ВЫБОРАРАСПРЕДЕЛЕНИЯ, МЕСТ МЕЖДУ ИСЛЯМИ наилучшем назначении исполнителя определенные работы. Целния является повьппениеза счет обеспечения опт ЯО 124125 А 1 блока буферной памяти, а управляющиеи информационные входы соединены ссоответствующими выходами блока регистровой памяти, выход второго элемента И через первый элемент И ипервый элемент ИЛИ соединен со входомраспределителя, два выхода которогочерез второй элемент ИЛИ подключенык второму входу первого элемента И,выход которого соединен с входом считывания блока регистровой памяти,а два других выхода распределителясоединены .с входами решающего блока,входы второго элемента И соединенысоответственно с тактовым входом и входом пуска устроиства, блок регистровой памяти соединен. с блокомбуферной памяти. Решающий блок выполнен с применением групп элементов И,ИЛИ, двух групп триггеров и двухгрупп элементов запрета, двух элементов ИЛИ и матрицы, узлов коммутации,каждый из которых позволяет осуществлять задержку прохождения входныхимпульсов на один такт. Блок регистровой памяти и блок буферной памятивыполнены на триггерах с элементами И, ИЛИ для записи и считыванияинформации, 5 нл.Изобретение относится к вычислительной технике и может быть использовано для выработки решения о наилучшем назначении исполнителя на работе в различных областях деятельности человека (общества). Цель изобретения - повьппение эффективности устройства путем оптимального назначения для максимального числа исполнителей.На фиг. 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,Принцип работы устройства основанна следующем,Первоначально выбирается то измест, котссрое удовлетворяет наименьшее число исполнителей. Далее сопоставляются все исполнители, длякоторых пригодно выделенное место,Среди этих исполнителей выделяетсятот, который имеет наименьшее числоудовлетворяющих его мест. Введенныйтаким образом исполнитель назначается на выбранное место. Место оказывается занятым, исполнитель считается получившим это место. Поэтомуи место и исполнитель исключаютсяиз дальнейшего рассмотрения. Такимобразом число еще не занятых мест 10 15 20 25 30 35 40 45 50 55.и числа исполнителей еще не получивших место уменьшилось на единицу.Далее процедура повторяется да техпор, пока или все исполнители получают удовлетворяющие их места, илитаких мест на всех не хватает,Устройство работает следующим образом,Кажцый регистр блока б (числорегистров равно числу исполнителейМ) содержит триггеры 15, число которых равно количеству мест И, на которые может быть назначен исполнитель.Изложение, работы устройства ведетсядля случая М=И=З, т.е. когда имеетсятри исполнителя и три места. Соответственно этому устройство содержиттри регистра и по три триггера в регистре. Доход Ь(сп=1, М, п=1, 1),получаемый ш-м исполнителем при егоназначении на и-е место по условиюпринимает значение Ь,=1 ("Удовлетворительно) или значение Ь,=ОО ("Неудовлетворительно" ),Перед началом работы устройствав триггеры блока 6 записываются зна- чения чисел Ь. В каждый триггерпервого регистра записывается число Ь 1 (доход при назначении первогоисполксителя на 1-е место), в каждыйтриггер второго регистра записывается число Ь (доход при назначениивторого исполнителя на 1-е место),.в каждый триггер третьего регистразаписывается число 1 с (доход приназначении третьего исполнителя1-е место).В исходном состоянии все триггеры40 и триггеры 43 блока 7, а такжетриггеры 51 блока 8 имеют нулевоесостояние (обнуляются перед началомработы устройства), распределитель1 устройства находится в исходномсостоянии, при котором единичныйсигнал снимается с его выхода 13.Работа устройства начинается сподачи единичного сигнала на вход14 уссройстваЕсли все числа 1 с, с, ,М,1=114) равны нулю, то при любомназначении исполнителей на местасуммарный доход равен нулю. В этомслучае с выходов всех элементовИЛИ 21 и, следовательно, с выходаьэлемента ИЛИ 22 блока 6 снимаетсянулевой сигнал, который через выход29 блока б поступает на вход элемента И 2 устройства и запрещает1 О Единичный сигнал с выхода элемен та И 5 устройства поступает также через элемент ИЛИ 3 на вход распределителя 1 и переводит его в следующее состояние, так что к моменту прихода второго тактового импульса еди ничный сигнал уже снимается с выхода 9 распределителя 1. Если для некоторого места хотя бы один из триггеров блока 6 имеет единичное состояние, то единичный сигнал через эле 11 ент 55 ИЛИ 21 и выход 27 блока 6 поступает на вход соответствующего элемента И 36 блока 7. поступление импульсов с тактового входа 11 на остальные узлы устройства. Нулевой сигнал на выходе 29 блока 6 свидетельствует о том, что в этом случае работа устройства за кончена. При этом все триггеры блока 8 остаются в нулевом состоянии, что свидетельствует о том, что йи один исполнитель не может получить место с удовлетворительным (единичным) доходом.Если хотя бы одно число и" не равно нулю, на выходе 29 блока 6 возникает единичный сигнал. При подаче на вход 14 устройства единичного 15 сигнала тактовые импульсы с входа 11 начнут проходить через элемент И 2 устройства.Поскольку в исходном состоянии устройства единичный сигнал снима ется с выхода 13 распределителя 1, он поступает через элемент ИЛИ 4 устройства на вход элемента И 5. Поэтому первый тактовый импульс через элемент И 22 поступает на вход 25 23 блока 6, Единичный сигнал с входа 23 блока 6 поступает на входы всех элементов И 17 и 18. С выходов этих элементов сигналы поступают на блок 7. Это приводит к тому, 30 что на входах узлов 35 блока 7 (инверсный и прямой входы триггеров 31 этих узлов) появляются напряжения совпадающие с напряжениями инверсного и прямого выходов соответствующих им триггеров 15 (т.е. имеющих те же индексы , ) блока 6. Единичный сигнал с тактового входа 11 устройства поступает на тактовые входы всех узлов 35 (тактовые входы триггеров 31). Это приводит к записи содержимого триггеров 15 блока 6 в триггеры 31 соответствующих им узлов 35 блока 7. Так как единичное напряжение снимается теперь с выхода 9 распрецелителя 1, очередные тактовые импульсы с входа 11 устройства начинают проходить через элемент И 36 блока 7 на управляющий вход узла 35. В противном случае элемент И 36 закрыт и тактовые импульсы на управляющий вход узла 35 не поступают, Если в триггер 31 узла 35 записана единица, то с его нулевого выхода снимается нулевой сигнал, запрещающий прохождение тактового импульса через элемент И 33 на выход узла 35. В этом случае тактовый импульс поступаетчерез элемент ИЛИ 34 на нулевой вход триггера 31 и переводит его своим задним фронтом в нулевое состояние, что разрешает прохождение следующеготактового импульса через элемент И 33.Таким образом, если триггер 31 имеет единичное состояние, то узел 35 осуществляет функцию задержки прохождения импульса на один такт. Для фиксированного 1-го места совокупность узлов 35 осуществляет за- держку прохождения тактовых импульсов с выхода элемента И 36 на столькотактов, сколько единиц записано в триггерах 31 узлов 35.Если суммарное количество единиц, записанных в триггерах 31 узлов 3511, 351, 35 э 1, отпично от нуля и меньше или 15 авно количеству единиц, записанных в триггерах 31 узлов 351, 35, 35, а также меньше или равйо количеству единиц в триггерах 31 узлов 351, 355, 35;, то тактовый импульс, прошедший по пути:вход модуля 35 и - выход модуля 35- элемент 42 ИЛИ - выход 49 блока 7 - элемент ИЛИ 3 устройства, поступает на распределитель 1 и переводит его в следующее состояние 12. Одновременно тактовый импульс, пройдя на единичный вход триггера 40 в блоке , вызывает единичный сигнал на его выходе.Совпадение единичных сигналов на входах элемента И 41 (поскольку в рассматриваемом случае на первом входе 27 блока 7 присутствует единичный сигнал) вызывает единичный сигнал на первом выходе 26.Одновременно тактовый импульс на выходе узла 35 закрывает соответствующий элемент ЗАПРЕТ, что запрещает прохождение тактового импульсас выхода элемента ИЛИ 42 через эле менты ЗАПРЕТ 38 и элементы И 39 на единичные входы остальных триггеров 40 в случае, если в триггерах 31 узлов 351, 35, 35, либо узлов5 357 35 записано такое ко личество единиц, как в триггерах 31 узлов 35 1, 35 35.Если количество единиц в триггерах 10 31 узлов 351 , 3577, 35 7 отлично от нуля и меньше, чем количество единиц в триггерах 31 узлов 351, , 35 35 а также меньше или равно количеству единиц в триггерах 31 узлов 35 з, 15 357, 35, то тактовый импульс быстрее приходит по пути: вход узла 351 - вход узла 357, и поступает на вход элемента И 39. Поскольку на выходе , узла 35 1, тактовый импульс отсутству ет, то первый элемент ЗАПРЕТ 38 открыт. Поэтому тактовый импульс с выхода узла 35 проходит через элемент ИЛИ 42 и элемент ЗАПРЕТ и поступаетна вход элемента И 39. Совпадение 25единичных сигналов на его входах приводит к записи единицы во второй триггер 40, а на втором выходе 26 появляется единичный сигнал. Тактовый импульс с выхода узла 35 ц 7 через 30элемент ИЛИ 42, выход 49 блока 7 поступает через элемент ИЛИ 3 навход распределителя 1 и переводитего в следующее состояние 12.Если число единиц в триггерах31 узлов 35 357, 35 э равно числу единиц в триггерах 31 узлов 35,357, 35 ято тактовый импульс наединичный вход триггера 40 не прохддит, так как элемент И 39 закрыт, щб поскольку закрыт второй элемент ЗАПРЕТ 38,т. е. единичный сигнал появляется только на втором выходе 26 блока 7.Аналогично, если минимальным ноотличным от нуля) оказывается числоединиц в триггерах 31 узлов 351 35 О , 35 3, единичный сиги появляется только на третьем выходе 26блока 7.Предположим, что единичный сигнал возникает на первом выходе 26 блока 7, т.е. некоторый исполнитель назначен на первое место.Определение номера этого исполнителя происходит следующим образом.Так как единичный сигнал, снимаемый теперь с выхода 12 распределителя 1, через элемент ИЛИ 4 устройства поступает на вход элемента И 5, очередной тактовый импульс с входа 11 устройства через элементы И 2 и 5 поступает на вход блока б и через элемент .ЛЛИ 3 на вход распределителя 1, так что по окончании тактовогО импульса распределитель переходит в следующее состояние. Единичный сигнал на входе 23 блока 6 приводит к записи содержимого триггеров 15 блока 6 в триггеры 31 соответствующих узлов 35. Единичный сигнал с первого выхода 26 блока 7 поступает на входы элементов И 19 блока 6. Если в соответствующий триггер 15 записана единица (Ь 1, =), то совпадение единичных сигналов на входах соответствующего элемента И 19 вызывает единичный сигнал на входе элемента ИЛИ 20 и выходе 28 блока Ь. Это приводит к тому, что тактовые импульсы с входа 11 устройства начинают проходить через элемент И 37 блока 7, т.е. 1-й исполнитель исключается из рассмотрения при назначении исполнителей на первое место. Логика работы блока 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 и че 124 255рез элемент ИЛИ 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, что исклю - чает возможность записи единицы в З 0 триггеры 51 в дальнейшем.Если теперь все триггеры 15 находятся в нулЕвом состоянии, то нулевые сигналы на выходах элементов ИЛИ 21 блока 6 вызывают нулевой сигнал на выходе 29 блока 6, который поступает на. элемент И 2 устройства, так что очередной тактовый импульс не проходит через элемент И 2 и распределитель 1 остается в положении 13, 10 как и устройство в исходном состоянии. Нулевой сигнал на выходе 29 блока 6 свидетельствует об окончании работы устройства, так как ни оДин из оставшихся исполнителей не может быть назначен на место с единичным доходом. Если хотя бы один иэ триггеров 15 блока 6 имеет единичное состояние, то на выходе 29 блока 6 присутствует единичный сигнал и уст-, 50 ройство повторяет процедуруоназначения.Принцип распределения мест между исполнителями в устройстве заключается в последовательном выборе мес та, на которое претендует минимальное количество исполнителей и назначении на него исполнителя (из числа претендующих), имеющего минималь,ное количество мест с единичнымдоходом. Такой порядок назначенияв максимальной степени сохраняетдля оставшихся исполнителей возможность получить места с единичнымдоходам в дальнейшем. Формула изобретения. Устройство для выбора вариантов распределения мест между исполнителями, содержащее блок регистровой памяти, распределитель импульсов, элементы И и ИЛИ, а т л к ч а ю - щ е .е с я, тем, что, с целью повышения эффективности за счет обеспечения оптимального назначения для максимального числа исполнителей, в него введены блок буферной памяти и решающий блок, включающий матрицу узлов коммутации, группы элементов И, ИЛИ, ЗАПРЕТ, группы триггеров и элементы ИЛИ, причем стробкрующие входы узлов коммутации соединены с тактовым входом устройства, первый и второй информационные входы каждого узла коммутации соединены с первой и второй группами информационных выходов блока растровой памяти, первый управляющий вход каждого узла коммутации последующего столбца каждой строки матрицы соединен с первым выходом соответствующего узла коммутации предыдущего столбца соответствующей строки матрицы, а второй управляющий вход каждого последующего узла коммутации каждого столбца мат- . рицы подключен к второму выходу предыдущего узла коммутации того же столбца матрицы, первые .управляющие входы узлов коммутации первого столбца матрицы соединены соответственно с выходами элементов И первой группы, первые и вторые входы которых подключены соответственно к первому, выходу распределителя импульсов и к тактовому входу устройства, третьи входы элементов И первой группы соединены соответственно с выходами признаков номеров занятых разрядов блока регистровой памяти, вторые управляющие входы узлов коммутации первой строки соединены соответственно с выходами элементов И второй группы, первые и вторые входы которых подключены соответственно к второму выходу распределителя импульсов ик тактовому входу устройства, третьи входы элементов И второй группы соединены соответственно с выходами признаков номеров занятых ячеек бло 5 ка регистровой памяти, первые выходы узлов коммутаций последнего столбца, кроме узла коммутации последней строки, подключены соответственно к управляющим входам элементов ЗАПРЕТ первой группы, первые выходы узлов коммутации последнего столбца матрицы соединены соответственно с входами первого элемента ИЛИ решающего блока, выход которого соединен с первым входом первого элемента ИЛИ устройства и информационным входом первого элемента ЗАПРЕТ первой группы, выход каждого предыдущего элемента ЗАПРЕТ первЬй группы соединен с информационным входом каждого последующего элемента ЗАПРЕТ первой группы, выходы элементов ЗАПРЕТ первой группы соединены соответственно с первыми входами элементов И третьей 25 группы, первый выход узла коммутации первой строки последнего столбца матрицы соединен с единичным входом первого триггера первой группы, единичные входы триггеров первой группы, начиная с второго, подключены соответственно к выходам элементов И третьей группы, вторые входы которых соединены соответственно с первыми выходами узлов коммутации последнего35 столбца матрицы, начиная с второй строки, единичные выходы триггеров первой группы соединены соответственно с первыми входами элементов И четвертой группы, вторые входы которых соединены соответственно с выходами признаков номеров занятых раз. рядов блока регистровой памяти, выходы элементов И четвертой группы соединены с первым входом считывания блока регистровой памяти, вторые выходы узлов коммутации последней строки матрицы, кроме узла коммутации первого столбца последней строки, соединены соответственно с управляю 50 щими входами элементов ЗАПРЕТ второй группы, начиная с первого элемента, вторые выходы узлов коммутации последней строки матрицы соединены соответственно с входами второго элемента ИЛИ решающего блока,выходы которого подключены к второмувходу первого элемента ИЛИ устройства и к информационному входу последнего элемента ЗАПРЕТ второй группырешающего блока, информационный входкаждого предыдущего элемента ЗАПРЕТвторой группы соединен с выходом последующего элемента ЗАПРЕТ второйгруппы, выходы элементов ЗАПРЕТ,второй группы подключены соответственно к первым входам элементов Ипятой группы, единичный вход последнего триггера второй группы соединенс вторым выходом узла коммутациипоследнего столбца последней строкиматрицы, вторые выходы узлов коммутации последней строки матрицы, кромеузла коммутации последней строкипоследнего столбца, соединены соответственно с вторыми входами элементов И пятой группы, выходы которыхподключены соответственно к единичным вхоцам триггеров второй группы,единичные выходы которых соединенысоответственно с первыми входами элементов И шестой группы, вторые входыкоторых соединены соответственнос выходами признаков номеров занятыхячеек блока регистровой памяти, авыходы подключены соответственно квторому входу записи блока буфернойпамяти, выходы признаков номеровзанятых ячеек и выходы признаковномеров занятых разрядов которогоподключены соответственно к установочным входам блока регистровойпамяти, второй вход считывания которого и третий вход первого элемента ИЛИ устройства соединены; с выходом первого элемента И, выход признака окончания блока регистровойпамяти, вход пуска и тактовый входустройства соединены соответственнос входами второго элемента И устройства, выход которого и выходвторого элемента ИЛИ устройства соединены соответственно с входами первого элемента И, входы второго элемента ИЛИ устройства соединены соответственно с третьим и четвертымвыходами распределителя импульсов,вход которого соединен с выходом первого элемента ИЛИ устройства.Подписное а комитета СССи открытий Государственногелам изобретений Москва, Ж,4/ ушская на город, ул. Проектная оизводственно-полиграфическое предприятие,