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

Изобретение относится к области вычислительной техники и может быть использовано для получения точного решения задачи о назначениях. Технический результат заключается в повышении точности работы устройства за счет оптимизации решения задачи о назначениях в двух вариантах постановки задачи нахождения оптимального решения. Устройство содержит группу из m счетчиков 31…3m, группу дешифраторов 41…4m, группы регистров, группы триггеров, группы сумматоров, группу шифраторов. Введение группы вторых шифраторов, элементов И, ИЛИ и схемы сравнения обеспечивает возможность работы в двух вариантах постановки задачи нахождения оптимального решения. 1 ил.

 

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

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

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

Наиболее близким по технической сущности является устройство [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, третий элемент И 12, схему сравнения 17, третий регистр 18, четвертый элемент И 19, элемент задержки 20, пятый элемент И 21, выход ГТИ 1 соединен с первым входом первого элемента И 2, выход которого соединен с входом счетчика 31, информационный выход счетчика 3i (i=1…m) подсоединен к входу дешифратора 4i (i=1…m), выходы которого подсоединены к входам одноименных первых триггеров 6ij (j=1…n), выход каждого первого триггера 6ij (i=1…m, j=1…n) подсоединен к входу второго элемента И 7ij, к одноименному входу первого шифратора 11j, к одноименному входу второго регистра 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 и четвертого элемента И 19, выход которого подсоединен к входу третьего регистра 18, выход которого является выходом 27 устройства и подсоединен к второму входу схемы сравнения 17, выход которой через элемент задержки 20 подсоединен к управляющим входам четвертого элемента И 19 и вторых регистров 8i, выходы первых шифраторов 11i (i=1…m) подсоединены к одноименным входам третьего элемента И 12, выход переполнения счетчика 3i (i=1…m-1) подсоединен к входу счетчика 3i+1, выходы переполнения счетчиков 3i (i=1…m) подсоединены к одноименным входам пятого элемента И 21, выход которого подсоединен к второму входу первого элемента И 2 и является выходом 23 устройства

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Для первого режима работы, при котором определяется занятость только одного сотрудника, триггер 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.

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

Частота сигналов ГТИ 1 выбирается с учетом последовательности надежного срабатывания элемента И 2, счетчиков 31…3m, дешифраторов 41…4m, триггеров 611…6mn, элементов И 711…7mn, регистров 81…8m, сумматоров 91…9m, сумматора 10, шифраторов 111…11n, элемента И 12, элемента ИЛИ 15, элемента И 16, схемы сравнения 17, регистр 18, элемента И 19, элемента задержки 20, элемента И 21.

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

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

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

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



 

Похожие патенты:

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

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

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

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

Изобретение относится к области автоматизированных рабочих мест операторов мобильных и стационарных пунктов управления автоматизированных систем управления различными объектами.

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

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

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

Изобретение относится к системам обмена информацией. Технический результат - высокая автономность работы устройства.

Изобретение относится к многофункциональным защищенным микровычислителям. Технический результат заключается в обеспечении устройства комплексной защитой от внешних воздействующих факторов при сохранении функциональных возможностей устройства. Устройство содержит сверхбольшую интегральную схему «система на кристалле», проводные и беспроводные порты ввода-вывода информации, размещенные в общем защитном экране, выполненном из многослойного защитного материала, а также пульт дистанционного управления, при этом корпуса проводных портов ввода-вывода информации, расположенных в отверстиях корпуса, выполнены из многослойного защитного материала либо выполнены из стандартного материала и снабжены заглушками, выполненными из многослойного защитного материала. 3 з.п. ф-лы, 1 ил.
Наверх