Устройство для решения транспортных задач Советский патент 1990 года по МПК G06G7/122 

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

Цель изобретения - повышение быс-г одейст вия устройства при решении Задачи оптимального распределения Заданий между исполнителями.

На фига01 представлена функциональная схема примера реализации устройства; на фиг.2 - обобщенная структурная схема устройства.

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

Блок регистровой памяти содер- Жит матрицу из ТхР ячеек 5, где t - количество заданий, распределяемых между Р исполнителями, блок 2 выбора максимума - группу из ТхР ячеек 6 выбора. Каждая ячейка 5 состоит Из элемента ИЛИ-НЕ 7, диода 8, свето- диода 9, регистра 10 и цифроаналого- вого преобразователя (ЦАП 11.

Каждый элемент 6 выбора содержит операционный усилитель 12, токозадаю- щий резисиор 13, резистор 14 обратной связи, шунтирующий диод 15, ключевой диод 16 и триггер 17.

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

Перед началом работы значения Коэффициентов эффективности использо- ания К-го исполнителя (,.,,,Р) tia М-м месте ( ,с «,Т) (при выпол - ении М-го зздания), заносятся в регистр 10 (К9М)-й ячейки 5.

Решение начинается нажатием выключателя 3. При этом его размыкающие контакты рвут цель подачи напряжения от шины питания на объединенные полюса всех ячеек 5, Снимается сигнал высокого уровня с второго входа элемента 7 всех ячеек 5. Сигнал уровня I с выхода элементов 7 всех ячеек 5 поступает на считывакщий вход их регистров 10, Значения коэффициентов эффективности (BklVl) с информационных выходов регистров 10 поступают f на вход соответствующих ЦДЛ II,, с выходов которых напряжения, пропорцио-. нальные значениям коэффициентов эф фективности, подаются на вторые входы соответствующих элементов 6 выбора блока 2. Эти напряжения с вторых входов элементов выбора через токо- задающие резисторы 13 поступают на вход их операционных усилителей 12.

5

0

5

0

5

0

5

0

5

Так как узлы соединения резисторов 14 обратной связи и шунтирующих диодов 15 всех элементов выбора объединены, в блоке 2 осуществляется выбор максимального из входных напряжений и на единичном входе триггера 17, на входе операционного усилителя которого присутствует наибольший входной сигнал, появляется сигнал высокого уровня. Так, например, если В11 ,то на первом шаге решения сигнал высокого уровня поступает на единичный вход триггера I7 элемента выбора 61f . Триггер переходит в единичное состояние,и сигнал высокого уровня с его единичного выхода поступает на третий полюс ячейки 51ч блока 1, с него через диод 8 - на третий вход элемента 7 этой ячейки и ее четвертый полюс, а через светодиод 9, загорание которого сигнализирует о назначении первого исполнителя, - на первое рабочее место, на первый вход элемента 7 и четвертый полюс ячейки 5 и « Так как первые полюса объединены у всех ячеек 5, имеющих одинаковый второй индекс (по столбцам) , а четвертые полюса объединены у всех ячеек, имеющих одинаковый первый индекс (то есть по строкам) то сигнал уровня 1 поступает на первые входы элементов 7 ячеек 5К1, К 2,с,, и на третьи входы элементов 7 ячеек 51м, М 2,000,Т, Снимается сигнал высокого уровня с управляющих входов регистров 10 ячеек первого столбца и первой строки блока 1 и снимаются напряжения. На этом заканчивается первый шаг решения, На последующих шагах работа устройства аналогична его работе на первом таге,, Решение заканчивается при Р Т закреплением всех исполнителей, л при Р Т закреплением всех Рабочих мест, о чем свидетельствует свечение одного из светодиодов в каждой из строк или в каждом из столбцов ячеек 5 блока } соответственно. По окончании решения выключатель 3 отпускается Вариант закрепления мест между исполнителями определяется по светящимся светодиодам 9 блока и зафиксирован триггерами 57, перешедшими в единичное состояние„

Для возврата схемы в исходное состояние кратковременно нажимается выключатель 4, через замыкающие контакты которого напряжение.от шины пи-.

тания поступает при этом на объединенные первые входы всех элементов 6 выбора блока 2, а с них на нулевые входы триггеров 17, обеспечивая возврат в нулевое состояние тех из них, которые в ходе решения перешли в единичное состояние„

На фиг.2 цифровые обозначения имеют элементы 18 памяти матрицы, элементы ИЛИ 19 матрицы, блок 20 выбора максимального кода, блок 2 задания топологии, элементы ИЛИ 22 группы и вход 23 пуска устройства.

Работа устройства по его обобщенной схеме аналогична описанной. Однако блок 21 задания топологии представляет собой совокупность триггеров 17 с соответствующими функциональными связями, элементы 22 ИЛИ группы соответствуют совокупности диодов 8 всех ячеек соответствующих столбцов матрицы, а светодиоды 9 исключены из обобщенной структурной схемы, так как триггеры 17 (или триггеры блока 21 задания топологии) установленные в единичное состояние, содержат полную информацию о решении задачи оптимального распределения Заданий между исполнителями. Формула изобрете н-и я

Устройство для решения транспортных задач, содержащее матрицу из

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

Q транспортной сети блока задания топологии, отличающееся тем, что, с целью повышения быстродействия устройства при решении задачи оптимального распределения за5 даний между исполнителями, в него введена матрица из ТхР элементов ИЛИ и группа из Р элементов ИЛИ, причем выход признака наличия дуги из К-й в М-ю вершину транспортной сети

0 блока задания топологии подключен к М-му входу К-го элемента ИЛИ группы, выход которого подключен к первым входам всех элементов ИЛИ К-го столбца матрицы и к вторым входам всех

5 элементов ИЛИ К-й строки матрицы, г выход К-го элемента ИЛИ М-й строки матрицы подключен к входу блокировки чтения К-го элемента памяти М-й строки матрицы, выход которого под0 ключей к (К,М)-му информационному входу блока выбора максимального кода, вход опроса которого является входом пуска устройства.

Изобретение относится к вычислительной технике и может быть использовано для оптимизации решений о назначении заданий исполнителям. Целью изобретения является повышение быстродействия устройства при решении задачи оптимального распределения заданий между исполнителями. С этой целью устройство содержит блок 1 регистровой памяти, блок 2 выбора максимума, кнопочные выключатели 3 и 4. Блок 1 регистровой памяти содержит матрицу из T^.P ячеек 5, где T - количество заданий, распределяемых между P исполнителями. Блок 2 выбора максимума содержит группу из T^.P ячеек 6 выбора. Каждая ячейка 5 содержит элемент ИЛИ-НЕ 7, диод 8, светодиод 9, регистр 10 и цифроаналоговый преобразователь 11. Каждая ячейка 6 выбора содержит операционный усилитель 12, токозадающий резистор 13, резистор обратной связи 14, шунтирующий диод 15, ключевой диод 16 и триггер 17. Устройство реализует алгоритм определения варианта распределения мест между исполнителями, основанный на идее осуществления назначений по максимальным элементам матрицы эффективности выполнения заданий исполнителями, которые перед началом работы заносятся в регистры 10 ячеек 5. 2 ил.