Устройство для решения задачи о назначениях исполнителей по работам
Изобретение относится к области вычислительной техники. Технический результат заключается в обеспечении нахождения минимума и нахождения максимума целевой функции. Технический результат достигается за счет устройства для решения задачи о назначениях, содержащего генератор тактовых импульсов (ГТИ), первый элемент И, группу из m счетчиков 31…3m, группу из m дешифраторов 41…4m, группу из m*n первых регистров 511…5mn, группу из m*n первых триггеров 611…6mn, группу из m*n блоков вторых элементов И 711…7mn, группу из m вторых регистров 81…8m, группу m первых сумматоров 91…9m, второй сумматор, первую схему сравнения, третий регистр, элемент задержки, и третий элемент И. 1 ил.
Изобретение относится к области вычислительной техники и может быть использовано для получения точного решения задачи о назначениях при нахождении минимума или максимума целевой функции.
Известно устройство для решения задачи о назначениях [1], которое позволяет получить точное решение задачи о назначениях при нахождении только максимума целевой функции,
Недостатком данного устройства является невозможность определения минимума или максимума целевой функции.
Задача изобретения - создать устройство, обеспечивающее расширение функциональных возможностей за счет решения задачи о назначениях в двух вариантах постановки задачи нахождения оптимального решения: нахождения минимума и нахождения максимума целевой функции. Кроме того, предлагаемое устройство может работать в режиме, при котором один исполнитель выполняет только одну работу и одна работа может выполняться несколькими исполнителями, например, при назначении двух водителей на автомобиль дальнего следования.
Это решение достигается тем, что в устройство, содержащее генератор тактовых импульсов (ГТИ) 1, первый элемент И 2, группу из m счетчиков 31…3m, группу из m дешифраторов 41…4m, группу из m*n первых регистров 511…5mn, группу из m*n первых триггеров 611…6mn, группу из m*n блоков вторых элементов И 711…7mn, группу из m вторых регистров 81…8m, группу т первых сумматоров 91…9m, второй сумматор 10, первую схему сравнения 17, третий регистр 18, элемент задержки 21, третий элемент И 22, выход ГТИ 1 соединен с первым входом первого элемента И 2, выход которого соединен с входом счетчика 31, выход переполнения счетчика 3i (i=1…m-1) подсоединен к входу счетчика 3i+1, информационный выход счетчика 3i (i=1…m) подсоединен к входу дешифратора 4i (i=1…m), выходы которого подсоединены к входам одноименных первых триггеров 6ij (j=1…n), выход каждого первого триггера 6ij (i=1…m, j=1…n) подсоединен к первому входу второго блока элементов И 7ij, к одноименному входу второго регистра 8i, выход которого является первым выходом 24i (i=1…m) устройства, выход первого регистра 5ij (i=1…m, j=1…n) подсоединен к второму входу второго блока элементов И 7ij (i=1…m, j=1…n), выход которого подсоединен к одноименному входу первого сумматора 9i (i=1…m), выход которого подсоединен к одноименному входу второго сумматора 10, выход которого подсоединен к первому входу первой схемы сравнения 17, второй вход которой подсоединен к выходу третьего регистра 18, выходы переполнения счетчиков 3i (i=1…m) подсоединены к одноименным входам третьего элемента И 22, выход которого подсоединен к второму входу первого элемента И 2 и является выходом 25 устройства, выход элемента задержки 21 подсоединен к управляющим входам третьего регистра 18 и вторых регистров 8i (i=1…m), дополнительно включены группа n третьих сумматоров 111…11n, группа n вторых схем сравнения 121…12n, группа n четвертых регистров 131…13n, четвертый элемент И 14, группа пятых элементов И 15, группа шестых элементов И 16, группа первых элементов ИЛИ 19, второй элемент ИЛИ 20, второй триггер 23, входы каждого третьего сумматора 11i подсоединены к одноименным выходам первых триггеров 6ij (i=1…m, j=1…n), а выходы подсоединены к одноименным первым входам вторых схем сравнения 12j (j=1…n), вторые входы которых подсоединены к выходам четвертых регистров 13j (j=1…n), а выходы подсоединены к одноименным входам четвертого элемента И 14, выход которого подсоединен к управляющему входу схемы сравнения 17, первый выход которой подсоединен к первому входу группы пятых элементов И 15, второй вход которого подсоединен к выходу второго сумматора 10, а выход подсоединен к первому входу первой группы элементов ИЛИ 19, второй выход схемы сравнения 17 подсоединен к первому входу группы шестых элементов И 16, второй вход которого подсоединен к выходу второго сумматора 10, а выход подсоединен к второму входу первой группы элементов ИЛИ 19, выход которой подсоединен к информационному входу третьего регистра 18 и к входам второго элемента ИЛИ 20, выход которого подсоединен к входу элемента задержки 21, первый выход второго триггера 23 подсоединен к управляющему входу группы пятых элементов И 15, второй выход второго триггера 23 подсоединен к управляющему входу шестой группы элементов И 16.
Проведенный поиск в известной научно-технической литературе не выявил наличие подобных технических решений.
Сущность изобретения поясняется чертежом, где на чертеже (фиг. 1) представлена структурная схема предлагаемого устройства, где представлены генератор тактовых импульсов (ГТИ) 1, элемент И 2, группа из m счетчиков 31…3m, группа из m дешифраторов 41…4m, группа из m*n регистров 511…5mn, группа из m*n триггеров 611…6mn, группа из m*n блоков элементов И 711…7mn, группа m регистров 81…8m, группа m сумматоров 91…9m, сумматор 10, группа n сумматоров 111…11n, группа n схем сравнения 121…12n, группа n регистров 131…13n, элемент И 14, группа элементов И 15, группа элементов И 16, схема сравнения 17, регистр 18, группа элементов ИЛИ 19, элемент ИЛИ 20, элемент задержки 21, элемент И 22, триггер 23, выходы 241…24n, 25, 26, входы 27, 28 вместе со связями.
Устройство работает следующим образом.
В исходном состоянии все счетчики 3i (i=1…m), триггеры 6ij (i=1…m - строки исполнителей, j=1…n - столбцы работ) устанавливаются в нулевое состояние. На триггере 23 хранится код нуля или единицы в зависимости от режима работы устройства.
На регистры 5ij (i=1…m, j=1…n) заносятся коды времени выполнения tij i-ым исполнителем j-ой работы (i=1…m, j=1…n). В регистр 18 заносится максимальный код (например, во всех разрядах регистра единицы) или код нуля в зависимости от режима работы устройства. На регистры 13j (j=1…n) заносятся коды количества исполнителей для j-ой работы.
Работа устройства начинается после подачи сигнала ПУСК на вход 27 устройства, после чего импульсы с выхода ГТИ 1 начинают поступать через открытый элемент И 2 на вход счетчика 31. Выход счетчика 3i (i=1…m-1) переполнения подсоединен к входу счетчика 3i+1. С выхода счетчика 3i (i=1…m) код поступает на вход одноименного дешифратора 4i (i=1…m), на выходе которого формируется единичный сигнал только на одном из его выходов. Номер выхода дешифратора 4i (i=1…m) совпадает с номером кода на одноименном счетчике 3i. Единичный сигнал с выхода дешифратора 4i (i=1…m) поступает на установочный в единичное состояние вход триггера 6ij, другие триггеры 6ij в этой строке будут установлены в нулевое состояние.
Единичный сигнал с выхода триггера 6ij (i=1…m, j=1…n) поступает на управляющий вход группы элементов И 7ij, после чего код с выхода регистра 5ij поступает через открытые группы элементов И 7ij на одноименный вход сумматора 9i, с выхода которого код поступает на одноименный вход сумматора 10. Одновременно с установкой триггера 6ij его сигнал поступает на одноименный вход сумматора 11j.
Выходы сумматоров 11j (j=1…n) подсоединены к первым входам схем сравнения 12j, к вторым входам схем сравнения 12j подсоединены выходы регистров 13j. На выходе схем сравнения 12j единичный сигнал появится в случае равенства входных кодов. Далее этот единичный сигнал поступает на одноименный вход элемента И 14, с выхода которого сигнал поступает на управляющий вход схемы сравнения 17. С первого выхода схемы сравнения 17 сигнал поступает на первый вход группы элементов И 15, со второго выхода схемы сравнения 17 сигнал поступает на первый вход группы элементов И 16. На вторые входы групп элементов И 15 и И 16 поступает код с выхода сумматора 10.
Для первого режима работы, при котором определяется минимум целевой функции на регистре 18, триггер 23 в исходном состоянии по входу 28 устанавливается в нулевое состояние, после чего единичный сигнал с инверсного выхода триггера 23 поступает на третий вход группы элементов И 16. С выхода группы элементов И 16 код поступает на первый вход группы элементов ИЛИ 19.
Для второго режима работы, при котором определяется максимум целевой функции на регистре 18, триггер 23 в исходном состоянии по входу 28 устанавливается в единичное состояние, после чего единичный сигнал с прямого выхода триггера 23 поступает на третий вход группы элементов И 15. С выхода группы элементов И 15 код поступает на второй вход группы элементов ИЛИ 19.
Код с выхода группы элементов ИЛИ 19 поступает на первый вход регистра 18 для перезаписи уточненного значения целевой функции и на вход элемента ИЛИ 20, на выходе которого появляется единичный сигнал, запускающий элемент задержки 21.
Элемент задержки 21 задерживает сигнал на время надежного срабатывания схемы сравнения 17, элемента И 15, группы элементов ИЛИ 19, элемента ИЛИ 20, после чего осуществляется перезапись содержимого сумматора 10 через открытую группу элементов И 15 или элементов И 16, группу элементов ИЛИ 19 на регистр 18.
С выхода элемента задержки 21 единичный сигнал поступает на управляющие входы регистров 8i (i=1…m) для перезаписи на них состояний триггеров 6ij (i=1…m, j=1…n) одноименной строки, а также на управляющий вход регистра 18 для перезаписи уточненного значения целевой функции.
Сигналы с выходов переполнения счетчиков 3i поступают также на одноименные входы элемента И 22. При единичном значении выходных сигналов с выходов переполнения счетчиков 3i (в конце работы устройства) единичный сигнал на выходе элемента И 22 поступает на инверсный вход элемента И 2, в результате чего прекращается подача импульсов с выхода ГТИ 1 через закрытый элемент И 2. Кроме того, единичный сигнал с выхода элемента И 22 является сигналом окончания 25 работы устройства.
Частота сигналов ГТИ 1 выбирается с учетом последовательности надежного срабатывания элемента И 2, счетчиков 31…3m, дешифраторов 41…4m, триггеров 611…6mn, группы элементов И 711…7mn, регистров 81…8m, сумматоров 91…9m, сумматора 10, сумматоров 111…11n, схемы сравнения 12, элемента И 14, схемы сравнения 17, группы элементов И 16, группы элементов ИЛИ 19, регистра 18, элемента ИЛИ 20, элемента задержки 21, элемента И 22.
Результатом работы устройства являются коды на регистрах 8i, которые могут сниматься с одноименных выходов 24i (i=1…m) и код с выхода 26 устройства со значением целевой функции.
Использованные источники: 1. RU N 2439687, кл. G 6F 15/20.
Устройство для решения задачи о назначениях исполнителей по работам, содержащее генератор тактовых импульсов (ГТИ) 1, первый элемент И 2, группу из m счетчиков 31…3m, группу из m дешифраторов 41…4m, группу из m*n первых регистров 511…5mn, группу из m*n первых триггеров 611…6mn, группу из m*n блоков вторых элементов И 711…7mn, группу из m вторых регистров 81…8m, группу m первых сумматоров 91…9m, второй сумматор 10, первую схему сравнения 17, третий регистр 18, элемент задержки 21, третий элемент И 22, выход ГТИ 1 соединен с первым входом первого элемента И 2, выход которого соединен с входом счетчика 31, выход переполнения счетчика 3i (i=1…m-1) подсоединен к входу счетчика 3i+1, информационный выход счетчика 3i (i=1…m) подсоединен к входу дешифратора 4i (i=1…m), выходы которого подсоединены к входам одноименных первых триггеров 6ij (j=1…n), выход каждого первого триггера 6ij (i=1…m, j=1…n) подсоединен к первому входу второго блока элементов И 7ij, к одноименному входу второго регистра 8i, выход которого является первым выходом 24i (i=1…m) устройства, выход первого регистра 5ij (i=1…m, j=1…n) подсоединен к второму входу второго блока элементов И 7ij (i=1…m, j=1…n), выход которого подсоединен к одноименному входу первого сумматора 9i (i=1…m), выход которого подсоединен к одноименному входу второго сумматора 10, выход которого подсоединен к первому входу первой схемы сравнения 17, второй вход которой подсоединен к выходу третьего регистра 18, выходы переполнения счетчиков 3i (i=1…m) подсоединены к одноименным входам третьего элемента И 22, выход которого подсоединен к второму входу первого элемента И 2 и является выходом 25 устройства, выход элемента задержки 21 подсоединен к управляющим входам третьего регистра 18 и вторых регистров 8i (i=1…m), отличающееся тем, что в него дополнительно включены группа n третьих сумматоров 111…11n, группа n вторых схем сравнения 121…12n, группа n четвертых регистров 131…13n, четвертый элемент И 14, группа пятых элементов И 15, группа шестых элементов И 16, группа первых элементов ИЛИ 19, второй элемент ИЛИ 20, второй триггер 23, входы каждого третьего сумматора 11 j подсоединены к одноименным выходам первых триггеров 6ij (i=1…m, j=1…n), а выходы подсоединены к одноименным первым входам вторых схем сравнения 12j (j=1…n), вторые входы которых подсоединены к выходам четвертых регистров 13j (j=1…n), а выходы подсоединены к одноименным входам четвертого элемента И 14, выход которого подсоединен к управляющему входу схемы сравнения 17, первый выход которой подсоединен к первому входу группы пятых элементов И 15, второй вход которого подсоединен к выходу второго сумматора 10, а выход подсоединен к первому входу первой группы элементов ИЛИ 19, второй выход схемы сравнения 17 подсоединен к первому входу группы шестых элементов И 16, второй вход которого подсоединен к выходу второго сумматора 10, а выход подсоединен к второму входу первой группы элементов ИЛИ 19, выход которой подсоединен к информационному входу третьего регистра 18 и к входам второго элемента ИЛИ 20, выход которого подсоединен к входу элемента задержки 21, первый выход второго триггера 23 подсоединен к управляющему входу группы пятых элементов И 15, второй выход второго триггера 23 подсоединен к управляющему входу шестой группы элементов И 16.
