Устройство для решения транспортных задач

 

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

СОЮЗ СОВЕТСКИХ социАлистических

РЕСПУБЛИК

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н АBTOPCHOMY СВИДЕТЕЛЬСТВУ

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

fl0 изОБРетениям и ОТКРытиям

IlPH fHHT СССР (21) 4361344/?4-24 (22) 09. 11. 87 (46) 15.02„90,Бюл, ¹ 6 (72) О, Г. Алексеев и Н, И, Ячкула (53) 681.333 (088, 8) (56} Авторское свидетельство СССР

И- 1241255, кл.С 06 F 15/20, 1984, Авторское свидетельство СССР № 1444830, кл. G 06 F 15/20, 1987. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ТРАНСПОРТНЫХ ЗАДАЧ (57) Изобретение относится к вычислительной технике и может быть использовано для оптимизации решений о назначении заданий исполнителям, Целью изобретения является повышение быстродействия устройства при решении задачи оптимального распределения заданий между исполнителями, С этой целью устройство содержит блок 1 регистровой памяти, блок 2 выбора мак симума,кнопочные выключатели 3 и 4, „„SU„„1543418 А 1 (51}5 4 06 F 15/20, С 06 G 7/122

Блок I регистровой памяти содержит матрицу из ТхР ячеек 5, где Т вЂ” количество заданий, распределяемых между P исполнителями. Блок 2 выбора максимума содержит группу из ТхР ячеек 6 выбора, Каждая ячейка 5 содержит элемент ИЛИ-НЕ 7, диод 8 светодиод 9, регистр 10 и цифроаналоговый преобразователь 11. Каждая ячейка 6 выбора содержит операционный усилитель 12, токозадающий резистор 13, резистор обратной связи

14, птунтирующий диод 15, ключевой диод 16 и триггер 17, Устройство реализует алгоритм определения варианта распределения мест между исполнителями, основанный на идее осуществления назначений по максимальным элементам матрицы эффективности выполнения заданий исполнителями, которые перед началом работы заносятся в регистры 10 ячеек 5, 2 ил, 2

1543418

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

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

Иа фиш,l представлена функциональ- 10

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

Устройство содержит блок 1 регистровой памяти, блок 2 выбора максимума и кнопочные выключатели Э и 4, Блок 1 регистровой памяти содержит матрицу.иэ ТхР ячеек 5, где — количество заданий, распределяемых между Р исполнителями, блок 2 йыбора максимума - группу из ТхР ячеек 6 выбора, Каядая ячейка 5 состоит

1иэ элемента ИЛИ-HE 7, диода 8, светодиода 9, регистра IO.и цифроаналого-, вого преобразователя (ЦАП) 11, 25

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

Устройство работает следующим об1разом, Перед началом работы значения коэффициентов эффективности использования K-ro исполнителя (K=I...,,P)

ga M-и месте (M=I...,,Т) (при ныпол—

35 ненни И"го задания) заносятся н ре гистр 10 (К,И)-й ячейки 5.

Решение начинается нажатием ныключателя 3. При этом его размыкающие" контакты рвут цель подачи напряжения от шины питания на объединенные полю-. са всех ячеек 5, Снимается сигнал высокого уровня с второго входа элемента 7 всех ячеек 5, Сигнал уровня 45

"1" с выхода элементов 7 всех ячеек

5 поступает на считывающий вход их регистров 10, Значения коэффициентов эффективности (В„„) с информационных выходов регистров 10 поступают на вход соответствующих ЦАП 11„ с выходов которых йапряжения, пропорцио-: нальные знаЧениям коэффищиентон эф-. фективности, подаются на вторые входы соответствующих элементов б выбо55 ра блока 2. Эти напряжения с вторых входов элементов выбора через токозадающие резисторы 13 поступают на вход их операционных усилителей 12, Так как узлы соединения резисторов

14 обратной связи и шунтирующих диодов 15 всех элементов выбора объединены, в блоке 2 осуществляется выбор максимального из входных напряжений и на единичном входе триггера 17, на входе операционного усилителя которого присутствует наибольший входной сигнал, появляется сигнал высокого уровня, Так, например, если В „„

= max/B 1,то на первом шаге решения сигнал высокого уровня поступает на единичный вход триггера 17 элемента ныбора 6, . Триггер переходит в единичное состояние,и сигнал высокого уровня с его единичного выхода поступает на третий полюс ячейки 5 „ блока 1, с него через диод 8 - на третий вход элемента 7 этой ячейки и ее четвертый полюс, а через светодиод

9, загорание которого сигнализирует о назначении первого исполнителя, на первое рабочее место, на первый вход элемента 7 и четвертый полюс ячейки 5 „ . Так как первые полюса объединены у всех ячеек 5, имеющих одинаковый второй индекс (по столбцам), а четвертые полюса объединены у всех ячеек, имеющих одинаковый первый индекс (то есть по строкам) то сигнал уровня "1" поступает на первые входы элементов 7 ячеек 5 „„

К = 2...,,P и на третьи входы элементов 7 ячеек 5,, M = 2,...,T

Снимается сигнал высокого уровня с . управляющих входов регистров 10 ячеек первого столбца и первой строки блока II и снимаются напряжения, На этом заканчивается первый шаг решения, На последующих шагах работа устройства аналогична его работе на первом шаге„ Решение заканчивается при P 4 Т закреплением всех исполнителей, л при Р ) Т закреплением всех рабочих мест, о чем свидетельствует свечение одного из светодиодов в каждой из строк или н каждом нз столбцов ячеек 5 блока 1 соответственно.

По окончании решения выключатель 3 отпускается, Вариант закрепления мест между исполнителями определяется по светящимся светодиодам 9 блока I и зафиксирован триггерами 17, перешедшими в единичное состояние, Для возврата схемы н исходное состояние кратковременно нажимается выключатель 4, через замыкающие контакты которого напряжение от шины пи-.

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

5 возврат в нулевое состояние тех иэ них, которые в ходе решения перешли в единичное состояние.

На фиг,2 цифровые обозначения имеют элементы 18 памяти матрицы, элементы ИЛИ 19 матрицы, блок 20 выбора максимального кода, блок 21 задания топологии, элементы ИЛИ 22 группы и вход 23 пуска устройства, Работа устройства по его обобщен-. ной схеме аналогична описанной, Однако блок 2! задания топологии . представляет собой совокупность триггеров 17 с соответствующими функциональными связями, эле- 20 менты 22 ИЛИ группы соответствуют совокупности диодов 8 всех ячеек соответствующих столбцов матрицы, а светодиоды 9 исключены из обобщенной структурной схемы, так 25 как триггеры 17 (или триггеры блока

21 задания топологии) установленные в единичное состояние, содержат полную информацию о решении задачи оптимального распределения заданий между 30 исполнителями.

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

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

18 6

ТхР элементов памяти, где Т вЂ” количество заданий распределяемых между

Р исполнителями, блок задания топологии и блок выбора максимального кода,(К,М)-й .выход позиции максимальHoFo кода KQTopoFQ (К 1 ° ° рТ1 М 1 ° вар

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

ИЛИ и группа из P элементов ИЛИ, при" чем выход признака наличия дуги из

К-й в М-ю вершину транспортной сети блока задания топологии подключен к

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

1 543418

Составитель А.Мишин

Редактор Л, Пчолинская Техред М. Дидык

Корректор В, Гирняк

Заказ 402 Тираж 565 Подписное

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101

° I

I )

1

1Ю