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

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

Иллюстрации

Показать все

Реферат

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

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

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

Сущность изобретения поясняется чертежом, где на чертеже (фиг. 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, группа n схем сравнения 12₁…12_n, группа n регистров 13₁…13_n, элемент И 14, группа элементов И 15, группа элементов И 16, схема сравнения 17, регистр 18, группа элементов ИЛИ 19, элемент ИЛИ 20, элемент задержки 21, элемент И 22, триггер 23, выходы 24₁…24_n, 25, 26, входы 27, 28 вместе со связями.

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

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

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

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

Единичный сигнал с выхода триггера 6_ij (i=1…m, j=1…n) поступает на управляющий вход группы элементов И 7_ij, после чего код с выхода регистра 5_ij поступает через открытые группы элементов И 7_ij на одноименный вход сумматора 9_i, с выхода которого код поступает на одноименный вход сумматора 10. Одновременно с установкой триггера 6_ij его сигнал поступает на одноименный вход сумматора 11_j.

Выходы сумматоров 11_j (j=1…n) подсоединены к первым входам схем сравнения 12_j, к вторым входам схем сравнения 12_j подсоединены выходы регистров 13_j. На выходе схем сравнения 12_j единичный сигнал появится в случае равенства входных кодов. Далее этот единичный сигнал поступает на одноименный вход элемента И 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 единичный сигнал поступает на управляющие входы регистров 8_i (i=1…m) для перезаписи на них состояний триггеров 6_ij (i=1…m, j=1…n) одноименной строки, а также на управляющий вход регистра 18 для перезаписи уточненного значения целевой функции.

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

Частота сигналов ГТИ 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, элемента И 14, схемы сравнения 17, группы элементов И 16, группы элементов ИЛИ 19, регистра 18, элемента ИЛИ 20, элемента задержки 21, элемента И 22.

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

Использованные источники: 1. RU N 2439687, кл. G 6F 15/20.

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