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

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

Реферат

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

Устройство содержит генератор тактовых импульсов (ГТИ) 1, первый элемент И 2, группу из n счетчиков 3₁…3_n, группу из n дешифраторов 4₁…4_n, группу из n*n первых регистров 5₁₁…5_nn, группу из n*n триггеров 6₁₁…6_nn, группу из n*n блоков третьих элементов И 7₁₁…7_nn, группу n вторых регистров 8₁…8_n, группу n первых сумматоров 9₁…9_n, сумматор 10, группу из n шифраторов 11₁…11_n, четвертый элемент И 12, схему сравнения 13, блок вторых элементов И 14, третий регистр 15, элемент задержки 16, пятый элемент И 17 вместе со связями.

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

Сущность рассматриваемой задачи заключается в следующем. Имеется n работ, для выполнения которых можно использовать n исполнителей, причем каждый исполнитель может выполнить только одну работу, а каждая работа может выполняться только одним исполнителем. Задана матрица длительности выполнения работ t_ij, (i=1…n, j=1…n), (i,j)-тый элемент которой равен времени, необходимому для выполнения j-той работы i-тым исполнителем. Необходимо так распределить n исполнителей по n работ, чтобы временные затраты были минимальные, а все работы выполнены.

Известны устройства для решения транспортных задач линейного программирования [1,2] которые позволяют определить лишь приближенное решение задачи.

Наиболее близким по технической сущности к заявляемому устройству является устройство для решения задач оптимизации [3], содержащее группу из n счетчиков 3₁…3_n, выход переполнения счетчика 3_i(i=1…n-1) подсоединен к входу счетчика 3_i+1, генератор тактовых импульсов (ГТИ) 1, выход которого соединен с первым входом первого элемента И 2, второй вход которого соединен с пусковым входом устройства 18, а выход подсоединен к входу счетчика 3₁, группу из n дешифраторов 4₁…4_n, группу из n*n первых регистров 5₁₁…5_nn, группу n вторых регистров 8₁…8_n, группу n первых сумматоров 9₁…9_n, сумматор 10, схему сравнения 13, блок вторых элементов И 14, третий регистр 15, элемент задержки 16, вход которого подсоединен к выходу схемы сравнения 13, а выход - к управляющим входам вторых регистров 8₁…8_n, к первому входу блока вторых элементов И 14, выход которого подсоединен к входу третьего регистра 15, выход которого является первым выходом 20 устройства и подсоединен к первому входу схемы сравнения 13.

Недостатком данного устройства является низкая его надежность из-за чрезмерных затрат аппаратных средств.

Задача изобретения - создать устройство, обеспечивающее более высокую надежность при решении задачи о назначениях.

Сущность изобретения состоит в том, что в устройство для решения задачи о назначениях, содержащее группу из n счетчиков 3₁…3_n, выход переполнения счетчика 3_i(i=1…n-1) подсоединен к выходу счетчика 3_i+1, генератор тактовых импульсов (ГТИ) 1, выход которого соединен с первым входом первого элемента И 2, второй вход которого является пусковым входом устройства 18, а выход подсоединен к входу счетчика 3₁, группу из n дешифраторов 4₁…4_n, группу из n*n первых регистров 5₁₁…5_nn, группу n вторых регистров 8₁…8_n, группу n первых сумматоров 9₁…9_n, второй сумматор 10, схему сравнения 13, блок вторых элементов И 14, третий регистр 15, элемент задержки 16, вход которого подсоединен к выходу схемы сравнения 13, а выход - к управляющим входам вторых регистров 8₁…8_n, к первому входу блока вторых элементов И 14, выход которого подсоединен к входу третьего регистра 15, выход которого является первым выходом 20 устройства и подсоединен к первому входу схемы сравнения 13, в него дополнительно включены группа из n*n триггеров 6₁₁…6_nn, группа из n*n третьих блоков элементов И 7₁₁…7_nn, первый вход каждого из которых подсоединен к выходу одноименного регистра 6_ij, (i=1…n, j=1…n), группу n шифраторов 11₁…11_n, четвертый элемент И 12, пятый элемент И 17, входы которого подсоединены к одноименным выходам переполнения одноименных счетчиков 3_i(i=1…n), а выход подсоединен к инверсному входу элемента И 2 и является вторым выходом 19 устройства, вход каждого дешифратора 4_i(i=1…n) подсоединен к выходу счетчика 3_i(i=1…n), выход дешифратора 4_i(i=1…n) подсоединен к входам триггеров 6_ij одноименной строки матрицы, выход каждого из которых подсоединен к одноименному входу регистра 8_i(i=1…n), к одноименному входу шифратора 11_i, и к второму входу третьего блока элементов И 7_ij, выход которого подсоединен к одноименному входу сумматора 9_i (i=1…n), выход которого подсоединен к одноименному входу сумматора 10, выход которого подсоединен к второму входу второго блока элементов И 14 и к второму входу схемы сравнения 13, выход шифратора 11_i(i=1…n) подсоединен к одноименному входу элемента И 12, выход которого подсоединен к третьему входу схемы сравнения 13, выход каждого регистра 8_i(i=1…n) является третьим выходом 21_i(i=1…n) устройства.

Проведенный поиск в известной научно-технической литературе не выявил наличие подобных технических решений.

Новизна предлагаемого устройства заключается в том, что новое техническое устройство отличается от прототипа тем, что дополнительно в него введены группа из n*n триггеров 6₁₁…6_nn, группа из n*n третьих блоков элементов И 7₁₁…7_nn, вход каждого из которых подсоединен к выходу одноименного регистра 6_ij, (i=1…n, j=1…n), группу n шифраторов 11₁…11_n, четвертый элемент И 12, пятый элемент И 17, входы которого подсоединены к одноименным выходам переполнения одноименных счетчиков 3_i(i=1…n), а выход подсоединен к инверсному входу элемента И 2 и является вторым выходом 19 устройства, выход дешифратора 4_i(i=1…n) подсоединен к входам триггеров 6_ij одноименной строки матрицы, выход каждого из которых подсоединен к одноименному входу регистра 8_i(i=1…n), к одноименному входу шифратора 11_i и к первому входу третьего блока элементов И 7_ij, выход которого подсоединен к одноименному входу сумматора 9_i (i=1…n), выход которого подсоединен к одноименному входу сумматора 10, выход которого подсоединен к второму входу второго блока элементов И 14 и к второму входу схемы сравнения 13, выход шифратора 11_i(i=1…n) подсоединен к одноименному входу элемента И 12, выход которого подсоединен к третьему входу схемы сравнения 13, выход каждого регистра 8_i(i=1…n) является третьим выходом 21_i(i=1…n) устройства.

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

Сущность изобретения поясняется чертежом. На чертеже представлена структурная схема предлагаемого устройства, где представлены генератор тактовых импульсов 1, первый элемент И 2, группа из n счетчиков 3₁…3_n, группа из n дешифраторов 4₁…4_n, группа из n*n первых регистров 5₁₁…5_nn, группа из n*n триггеров 6₁₁…6_nn, группа из n*n блоков третьих элементов И 7₁₁…7_nn, группа n вторых регистров 8₁…8_n, группа n первых сумматоров 9₁…9_n, сумматор 10, группа n шифраторов 11₁…11_n, четвертый элемент И 12, схема сравнения 13, блок вторых элементов И 14, третий регистр 15, элемент задержки 16, пятый элемент И 17, вход 18, выходы 19, 20, 21₁…21_n вместе со связями.

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

В исходном состоянии все счетчики 3_i (i=1…n), триггеры 6_ij (i=1…m - строки работ, j=1…n - столбцы исполнителей) устанавливаются в нулевое состояние. На регистрах 5_ij (i=1…n, j=1…n) заносятся коды времени выполнения t_ij i-ой работы j-ым исполнителем (i=1…n, j=1…n). В регистр 15 заносится максимальный код (например, во всех разрядах регистра единицы).

Работа устройства начинается после подачи сигнала ПУСК на вход 18 устройства, после чего импульсы с выхода ГТИ 1 начинают поступать через открытый элемент И 2 на вход счетчика 3₁. Выход счетчика 3_i (i=1…n-1) переполнения подсоединен к входу счетчика 3_i+1. С выхода счетчика 3_i(i=1…n) код поступает на вход одноименного дешифратора 4_j (j=1…n), на выходе которого формируется единичный сигнал только на одном из его выходов. Номер выхода дешифратора 4_j совпадает с номером кода на одноименном счетчике 3_i. Единичный сигнал с выхода дешифратора 4_j (j=1…n) поступает на установочный в единичное состояние вход триггера 6_ij, другие триггеры 6_ij в этой строке будут установлены в нулевое состояние.

Единичный сигнал с выхода триггера 6_ij поступает на управляющий вход группы элементов И 7_ij, после чего код с выхода регистра 5_ij поступает через открытые элементы И 7_ij на одноименный вход сумматора 9_i, с выхода которого код поступает на одноименный вход сумматора 10. Одновременно с установкой триггера 6_ij его сигнал поступает на одноименный вход шифратора 11_j, который вырабатывает единичный сигнал только в том случае, если на его входах будет только один единичный сигнал данного столбца на установочном в единичное состояние входе триггера 6_ij Выходы шифраторов 11_j подсоединены к одноименным входам элемента И 12, на выходе которого единичный сигнал появится только в том случае, если одновременно все шифраторы 11_j вырабатывают единичные сигналы.

Единичный сигнал на выходе элемента И 12 является разрешающим сигналом для срабатывания схемы сравнения 13, на информационные входы которой поступают текущее значение целевой функции с выхода сумматора 10 и зафиксированное ранее ее значение на регистре 15. На выходе схемы сравнения 13 появляется единичный сигнал только в том случае, если содержимое сумматора 10 меньше содержимого регистра 15. Единичный сигнал на выходе схемы сравнения 13 поступает на вход элемента задержки 16, который обеспечивает задержку сигнала на время, достаточное для надежного срабатывания схемы 13 и элемента И 14, после чего через открытую группу элементов И 14 осуществляется перезапись содержимого сумматора 10 через открытые элементы И 14 в регистр 15.

Сигналы с выходов переполнения счетчиков 3_i поступают на одноименные входы элемента И 17. При единичном значении входных сигналов с выходов переполнения счетчиков 3_i (в конце работы устройства) единичный сигнал на выходе элемента И 17 поступает на инверсный вход элемента И 2, в результате чего прекращается подача импульсов с выхода ГТИ 1 через закрытый элемент И 2. Кроме того, единичный сигнал с выхода элемента И 17 является сигналом окончания работы устройства 19.

Результатом работы устройства являются коды на регистрах 8_i, которые могут сниматься с одноименных выходов 20_i.

Источники информации

1. Авторское свидетельство СССР № 1515937, кл. G06F 15/20, 1990.

2. Авторское свидетельство СССР № 1649562, кл. G06F 15/20, 1991.

3. Авторское свидетельство СССР № 208495451, кл. G06F 15/20, 1997.

Сведения об авторах заявки на предлагаемое изобретение.

№ п/п	Авторы	% участия
1	Титов Виктор Алексеевич	50%
2	Световидов Дмитрий Михайлович	50%

Устройство для решения задачи о назначениях, содержащее группу из n счетчиков 3₁…3_n, выход переполнения счетчика 3_i(i=1…n-1) подсоединен к входу счетчика 3_i+1, генератор тактовых импульсов (ГТИ) 1, выход которого соединен с первым входом первого элемента И 2, второй вход которого соединен с пусковым входом устройства 18, а выход подсоединен к входу счетчика 3₁, группу из n дешифраторов 4₁…4_n, группу из n×n первых регистров 5₁₁…5_nn, группу n вторых регистров 8₁…8_n, группу n первых сумматоров 9₁…9_n, сумматор 10, схему сравнения 13, блок вторых элементов И 14, третий регистр 15, элемент задержки 16, вход которого подсоединен к выходу схемы сравнения 13, а выход - к управляющим входам вторых регистров 8₁…8_n, к первому входу блока вторых элементов И 14, выход которого подсоединен к входу третьего регистра 15, выход которого является первым выходом 20 устройства и подсоединен к первому входу схемы сравнения 13, отличающееся тем, что в него дополнительно включены группа из n*n триггеров 6₁₁…6_nn, группа из n*n третьих блоков элементов И 7₁₁…7_nn, первый вход каждого из которых подсоединен к выходу одноименного регистра 5_ij, (i=1…n, j=1…n), группу n шифраторов 11₁…11_n, четвертый элемент И 12, пятый элемент И 17, входы которого подсоединены к одноименным выходам переполнения одноименных счетчиков 3_i(i=1…n), а выход подсоединен к инверсному входу элемента И 2 и является вторым выходом 19 устройства, вход каждого дешифратора 4_i(i=1…n) подсоединен к выходу счетчика 3_i(i=1…n), выход дешифратора 4_i(i=1…n) подсоединен к входам триггеров 6_ij одноименной строки матрицы, выход каждого из которых подсоединен к одноименному входу регистра 8_i(i=1…n), к одноименному входу шифратора 11_i и к второму входу третьего блока элементов И 7_ij, выход которого подсоединен к одноименному входу сумматора 9_i(i=1…n), выход которого подсоединен к одноименному входу сумматора 10, выход которого подсоединен к второму входу второго блока элементов И 14 и к второму входу схемы сравнения 13, выход шифратора 11_i(i=1…n) подсоединен к одноименному входу элемента И 12, выход которого подсоединен к третьему входу схемы сравнения 13, выход каждого регистра 8_i(i=1…n) является третьим выходом 21_i(i=1…n) устройства.