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

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

Иллюстрации

Показать все

Реферат

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

1) один исполнитель выполняет только одну работу, при этом количество работ может быть больше количества исполнителей;

2) один исполнитель выполняет только одну работу и одна работа выполняется только одним исполнителем.

Наиболее близким по технической сущности является устройство [1], содержащее генератор тактовых импульсов (ГТИ) 1, первый элемент И 2, группу из m счетчиков 3₁…3_m, группу из m дешифраторов 4₁…4_m, группу из m*n первых регистров 5₁₁…5_mn, группу из m*n первых триггеров 6₁₁…6_mn, группу из m*n блоков вторых элементов И 7₁₁…7_mn, группу из m вторых регистров 8₁…8_m, группу m первых сумматоров 9₁…9_m, второй сумматор 10, группу n первых шифраторов 11₁…11_n, третий элемент И 12, схему сравнения 17, третий регистр 18, четвертый элемент И 19, элемент задержки 20, пятый элемент И 21, выход ГТИ 1 соединен с первым входом первого элемента И 2, выход которого соединен с входом счетчика 3_1, информационный выход счетчика 3_i (i=1…m) подсоединен к входу дешифратора 4_i (i=1…m), выходы которого подсоединены к входам одноименных первых триггеров 6_ij (j=1…n), выход каждого первого триггера 6_ij (i=1…m, j=1…n) подсоединен к входу второго элемента И 7_ij, к одноименному входу первого шифратора 11_j, к одноименному входу второго регистра 8_i, выход которого является первым выходом 24_i (i=1…m) устройства, выход первого регистра 5_ij (i=1…m, j=1…n) подсоединен к второму входу второго блока элементов И 7_ij (i=1…m, j=1…n), выход которого подсоединен к одноименному входу первого сумматора 9_i (i=1…m), выход которого подсоединен к одноименному входу второго сумматора 10, выход которого подсоединен к первым входам схемы сравнения 17 и четвертого элемента И 19, выход которого подсоединен к входу третьего регистра 18, выход которого является выходом 27 устройства и подсоединен к второму входу схемы сравнения 17, выход которой через элемент задержки 20 подсоединен к управляющим входам четвертого элемента И 19 и вторых регистров 8_i, выходы первых шифраторов 11_i (i=1…m) подсоединены к одноименным входам третьего элемента И 12, выход переполнения счетчика 3_i (i=1…m-1) подсоединен к входу счетчика 3_i+1, выходы переполнения счетчиков 3_i (i=1…m) подсоединены к одноименным входам пятого элемента И 21, выход которого подсоединен к второму входу первого элемента И 2 и является выходом 23 устройства

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

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

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

Новизна предлагаемого устройства заключается в том, что новое техническое устройство отличается от прототипа тем, что дополнительно в него включены группа m вторых шифраторов 13₁…13_m, шестой элемент И 14, элемент ИЛИ 15, седьмой элемент И 16, второй триггер 22, выход третьего элемента И 12 подсоединен к первому входу седьмого элемента И 16, выход которого подсоединен к управляющему входу схемы сравнения 17, входы каждого второго шифратора 13_i подсоединены к одноименным выходам первых триггеров 6_ij (i=1…m, j=1…n), а выходы подсоединены к одноименным входам шестого элемента И 14, выход которого подсоединен к первому входу элемента ИЛИ 15, выход которого подсоединен к второму входу седьмого элемента И 16, выход второго триггера 22 подсоединен к второму входу элемента ИЛИ 15.

Техническим результатом является расширение функциональных возможностей за счет решения задачи о назначениях в двух вариантах постановки задачи нахождения оптимального решения:

1) один исполнитель выполняет только одну работу и одна работа выполняется только одним исполнителем;

2) один исполнитель выполняет только одну работу, при этом количество работ может быть больше количества исполнителей.

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

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

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

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

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

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

Работа устройства начинается после подачи сигнала ПУСК на вход 26 устройства, после чего импульсы с выхода ГТИ 1 начинают поступать через открытый элемент И 2 на вход счетчика 3₁. Выход счетчика 3_i (i=1…m-1) переполнения подсоединен к входу счетчика 3_i+1. С выхода счетчика 3_i (i=1…m) код поступает на одноименный вход дешифратора 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 вырабатывают единичные сигналы.

Кроме того, с установкой триггера 6_ij его сигнал поступает также на одноименный вход шифратора 13_i, который вырабатывает единичный сигнал только в том случае, если на его входах будет только один единичный сигнал данной строки на установочном в единичное состояние выходе триггера 6_ij. Выходы шифраторов 13_i подсоединены к одноименным входам элемента И 14, на выходе которого единичный сигнал появится только в том случае, если одновременно все шифраторы 13_i вырабатывают единичные сигналы.

Для первого режима работы, при котором определяется занятость только одного сотрудника, триггер 22 по входу 25 устанавливается в единичное состояние, после чего единичный сигнал с выхода триггера 22 поступает на второй вход элемента ИЛИ 15. С выхода элемента ИЛИ 15 единичный сигнал поступает на первый вход элемента И 16. При наличии единичного сигнала на втором входе элемента И 16 (в случае единичного сигнала на всех выходах шифраторов 11) единичный сигнал поступает на разрешающий вход схемы сравнения 17 и, если текущее значение с выхода сумматора 10 меньше значения на регистре 18, на выходе схемы сравнения 17 появляется единичный сигнал, который поступает на элемент задержки 20, который задерживает сигнал на время надежного срабатывания схемы сравнения 17, после чего осуществляется перезапись содержимого сумматора 10 через открытый элемент И 19 на регистр 18.

Для второго режима работы, при котором определяется занятость только одного сотрудника при выполнении только одной должности, триггер 22 по входу 25 устанавливается в нулевое состояние, после чего нулевой сигнал с выхода триггера 22 поступает на второй вход элемента ИЛИ 15. В случае единичного сигнала на всех выходах шифраторов 13 единичный сигнал появляется на выходе элемента И 14, с выхода которого единичный сигнал поступает на другой вход элемента ИЛИ 15. С выхода элемента ИЛИ 15 единичный сигнал поступает на первый вход элемента И 16. При наличии единичного сигнала на втором входе элемента И 16 (в случае единичного сигнала на вторых выходах шифраторов 13) единичный сигнал поступает на разрешающий вход схемы сравнения 17 и, если текущее значение с выхода сумматора 10 меньше значения на регистре 18, на выходе схемы сравнения 17 появляется единичный сигнал, который поступает на элемент задержки 20. Элемент задержки 20 задерживает сигнал на время надежного срабатывания схемы сравнения 17, после чего осуществляется перезапись содержимого сумматора 10 через открытый элемент И 19 на регистр 18.

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

Частота сигналов ГТИ 1 выбирается с учетом последовательности надежного срабатывания элемента И 2, счетчиков 3₁…3_m, дешифраторов 4₁…4_m, триггеров 6₁₁…6_mn, элементов И 7₁₁…7_mn, регистров 8₁…8_m, сумматоров 9₁…9_m, сумматора 10, шифраторов 11₁…11_n, элемента И 12, элемента ИЛИ 15, элемента И 16, схемы сравнения 17, регистр 18, элемента И 19, элемента задержки 20, элемента И 21.

Результатом работы устройства являются коды на регистрах 8_i, которые могут сниматься с одноименных выходов 24_i (i=1…m).

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

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

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