УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧИ О НАЗНАЧЕНИЯХ

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

Известно устройство для решения задачи о рюкзаке (RU №2461060 С1, МПК G06F 17/00, G06F 7/00, заявлено 25.05.2011, опубликовано 10.09.2012, Бюл. №25), содержащее генератор тактовых импульсов (ГТИ), триггер разрешения, триггер готовности результата, группу из m счетчиков, группы из m первых, вторых и третьих регистров, четвертый и пятый регистры, группы из m шестых, седьмых и восьмых регистров, девятый регистр, первый и второй сумматоры, группы из m третьих и четвертых сумматоров, первую и вторую схемы сравнения, группы из m третьих схем сравнения, элемент И, вход пуска устройства, вход сброса устройства, первый выход устройства, группу из m вторых выходов устройства, третьи выходы устройства, четвертые выходы устройства.

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

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

Известно устройство для решения задачи о назначениях (RU №2084954 С1, МПК G06F 17/00, заявлено 24.05.1994, опубликовано 20.07.1997), содержащее блок генерации перестановок, группу регистров, блок синхронизации, блок формирования величин временных затрат, связанных с назначениями, накапливающий блок выбора минимального времени и счетчик.

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

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

Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является принятое за прототип устройство для решения задачи о назначениях (RU №2439687 С1, МПК G06F 17/50, заявлено 01.06.2010, опубликовано 10.01.2012, Бюл. №1), содержащее генератор тактовых импульсов 1, группу из n счетчиков 4₁, 4₂, …, 4_n, группу из n дешифраторов 5₁, 5₂, …, 5_n, группу из n*n первых регистров 6₁₁, …, 6_nn, группу из n*n блоков элементов И 7₁₁, …, 7_nn, элемент И 10, сумматор 11, схему сравнения 12, группу из n вторых регистров 13₁, 13₂, …, 13_n, третий регистр 14, вход пуска устройства 15, первый выход устройства 17, второй выход устройства 18, группу из n третьих выходов устройства 19₁, 19₂, …, 19_n, причем выход переполнения i-го счетчика 4_i (i=1, 2, …, n-1) соединен с входом (i+1)-го счетчика 4_i+1, входы каждого i-го дешифратора 5 соединены с выходами соответствующего i-го счетчика 4_i (i=1, 2, …, n), выходы группы из n*n первых регистров 6₁₁, …, 6_nn соединены с первыми входами одноименных блоков группы из n*n элементов И 7₁₁, … 7_nn, выходы сумматора 11 соединены с первыми входами схемы сравнения 12, выходы третьего регистра 14 соединены со вторыми входами схемы сравнения 12 и являются первыми выходами устройства 17, выходы каждого регистра группы из n вторых регистров 13₁, 13₂, …, 13_n являются группой из n третьих выходов устройства 19₁, 19₂, …, 19_n.

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

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

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

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

На фиг.1 приведена схема предлагаемого устройства для решения задачи о назначениях.

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

Внешний вход сброса устройства 16 соединен с входами синхронной установки в нулевое состояние вторым входом триггера разрешения 2, вторым входом триггера готовности результата 3, вторыми входами группы из n счетчиков 4₁, 4₂, …, 4_n, вторыми входами группы из n вторых регистров 13₁, 13₂, …, 13_n и вторым входом синхронной установки в единичное состояние третьего регистра 14.

Выход ГТИ 1 соединен с входами синхронизации - первым входом триггера разрешения 2, первым входом триггера готовности результата 3, первыми входами группы из n счетчиков 4₁, 4₂, …, 4_n, первыми входами группы из n вторых регистров 13₁, 13₂, …, 13_n, первым входом третьего регистра 14.

Вход пуска устройства 15 соединен с третьим входом разрешения работы триггера разрешения 2, выход которого соединен с третьим входом разрешения работы первого счетчика 4₁.

Выход переполнения i-го счетчика 4_i (i=1, 2, …, n-1) соединен с входом разрешения счета (i+1)-го счетчика 4_i+1.

Информационные выходы каждого i-го счетчика 4_i соединены с информационными входами соответствующего i-го регистра 13_i (i=1, 2, …, n) группы из n вторых регистров 13₁, 13₂, …, 13_n и входами каждого i-го дешифратора 5_i.

Выходы группы из n*n первых регистров 6₁₁, …, 6_nn соединены с первыми входами одноименных блоков группы из n*n элементов И 7₁₁, … 7_nn, выходы сумматора 11 соединены с первыми входами схемы сравнения 12, выходы третьего регистра 14 соединены со вторыми входами схемы сравнения 12 и являются первыми выходами устройства 17, выходы каждого регистра группы из n вторых регистров 13₁, 13₂, …, 13_n являются группой из n третьих выходов устройства 19₁, 19₂, …, 19_n.

Выходы каждого i-го дешифратора 5_i (i=1, 2, …, n), соединены со вторыми входами соответствующей одноименной i-й строки матрицы группы из n*n блоков элементов И 7₁₁, … 7_nn, а также одноименные j-e выходы дешифраторов 5_i соединены с входами соответствующего j-го блока (j=1, 2, …, n) вторых элементов ИЛИ 9₁, 9₂, …, 9_n, выходы которых соединены с первой группой входов элемента И 10, второй вход которой соединен с выходом схемы сравнения 12, а выход элемента И 10 соединен с третьими входами разрешения записи группы из n вторых регистров 13₁, 13₂, …, 13_n и третьего регистра 14.

Выходы i-й строки матрицы группы из n*n блоков элементов И 7₁₁, …, 7_nn соединены с одноименными входами группы из n блоков первых элементов ИЛИ 8₁, 8₂, …, 8_n, выходы блоков которых соединены с соответствующими входами сумматора 11.

Выход переполнения n-го счетчика 4_n соединен с четвертым входом синхронной установки в нулевое состояние триггера разрешения 2 и третьим входом синхронной установки в единичное состояние триггера готовности результата 3, выход которого является вторым выходом устройства 18.

Синхронные счетчики 4₁, 4₂, …, 4_n формируют текущий вариант распределения работ за исполнителями. На группе вторых регистров 13₁, 13₂, …, 13_n сохраняется наилучший вариант, который обеспечивает минимальную суммарную величину временных затрат на комплекс работ. Счетчики 4_i содержат по k разрядов и имеют модуль пересчета n, соответствующий количеству исполнителей. При этом k≥log₂ n. Вторые регистры 13_i также содержат по k разрядов.

Первые регистры 6₁₁, …, 6_nn содержат по m разрядов, достаточных для записи максимальной длительности - выполнения отдельных работ. Каждый блок элементов И 7₁₁, …, 7_nn содержит m элементов И. Каждый блок первых элементов ИЛИ 8₁, 8₂, …, 8_n содержит m элементов ИЛИ с n входами.

Сумматор 11 содержит n групп по m входов. Выходное количество разрядов сумматора 11 должно быть достаточно для записи максимальной суммарной длительности времени выполнения всего комплекса работ. Разрядность третьего регистра 14 соответствует разрядности сумматора 11.

Каждый блок группы вторых элементов ИЛИ 9₁, 9₂, …, 9_n содержит элемент ИЛИ с n входами. Элемент И 10 содержит (n+1) вход.

Предлагаемое устройство для решения задачи о назначениях работает следующим образом.

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

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

В исходном состоянии на регистрах 6_ij (i=1, 2, …, n; j=1, 2, …, n), устанавливаются коды времени t_ij выполнения i-й работы j-м исполнителем. Группа из n*n первых регистров 6₁₁, …, 6_nn может быть выполнена на клавишных регистрах. Группа из n счетчиков 4₁, 4₂, …, 4_n предназначена для задания текущего варианта распределения исполнителей. В процессе работы в группе из n вторых регистров 13₁, 13₂, …, 13_n фиксируется текущий наилучший вариант назначения исполнителей. В сумматоре 11 вычисляются суммарные временные затраты текущего варианта, а в третьем регистре 14 фиксируется текущее минимальное значение суммарных временных затрат на выполнение комплекса работ.

Импульсы с ГТИ 1 постоянно поступают на входы синхронизации группы счетчиков 4_i, группы вторых регистров 13_i и третьего регистра 14, режимы работы которых задаются сигналами на соответствующих входах управления.

При подаче сигнала на вход сброса устройства 16 по фронту импульса с ГТИ 1 в нулевое состояние устанавливаются триггер разрешения 2, триггер готовности результата 3, все счетчики 4₁, 4₂, …, 4_n, группа вторых регистров 13₁, 13₂, …, 13_n, а третий регистр 14 устанавливается в состояние «все единицы» - максимальный код временных затрат.

Работа устройства начинается после подачи сигнала ПУСК на вход устройства 15, по которому синхронно с импульсом от ГТИ 1 устанавливается в единичное состояние выход триггера разрешения 2, выход которого соединен с входом разрешения счета первого счетчика 4₁

На следующих тактах ГТИ 1 на выходах группы счетчиков 4₁, 4₂, …, 4_n формируется текущий вариант распределения исполнителей. С выхода счетчика 4_i двоичный код поступает на вход одноименного дешифратора 5_i, на выходе которого формируется единичный сигнал только на одном его j-м выходе, задаваемом входным двоичным кодом.

Так как все j-e выходы каждого i-го дешифратора 5_i (i=1, 2, …, n, j=1, 2, …, n), соединены со вторыми входами в соответствующей одноименной i-й строке матрицы группы из n*n блоков элементов И 7₁₁, … 7_nn, то в каждой i-й строке только через один блок элементов И 7_ij значение соответствующего первого регистра 6_ij поступает на соответствующие входы первого элемента ИЛИ 8_i в i-й строке. Таким образом, на выходы группы из n блоков первых элементов ИЛИ 8₁, 8₂, …, 8_n будут переданы времена выполнения каждой i-й работы. Данные значения времен с выходов первых элементов ИЛИ 8_i поступают на соответствующие входы сумматора 11, на выходах которого будет получено суммарное время затрат на выполнение всего комплекса из n работ.

Сигналы с одноименных j-x выходов дешифраторов 5_i одновременно поступают на соответствующие входы j-го блока (j=1, 2, …, n) вторых элементов ИЛИ 9₁, 9₂, …, 9_n, выходы которых соединены с первой группой входов элемента И 10. На всех выходах второй группы элементов ИЛИ 9₁, 9₂, …, 9_n, будут установлены единичные сигналы только в том случае, когда единичные сигналы будут установлены во всех столбцах матрицы выходов дешифраторов, т.е. на различных j-x выходах дешифраторов 5_i. Этот вариант соответствует распределению всех n работ между n исполнителями.

В таблице 1 приведены варианты распределения n исполнителей по n работам для n=4. Только в приведенных 24 вариантах единичные значения будут установлены в различных j-x столбцах выходов дешифраторов 5_i и на выходах всех вторых элементов ИЛИ 9₁, 9₂, …, 9_n.

Код временных затрат с выхода сумматора 11 поступает на схему сравнения 12, на второй вход которой поступает код с выхода третьего регистра 14 со значением кода времени, зафиксированным на предыдущих вариантах как минимальное время. Единичный сигнал СС на выходе схемы сравнения 12 формируется только в том случае, если код временных затрат текущего варианта на выходе сумматора 11 меньше кода с выхода третьего регистра 14. В таблице 1 показаны временные затраты по i-м работам в соответствии с вариантом распределения j-x исполнителей при заданной матрице длительности выполнения работ t_ij (i=1, 2, …, n; j=1, 2, …, n), приведенной в таблице 2. Единичный сигнал СС=1 формируется только в вариантах 1, 4, 10, когда текущий код временных затрат меньше предыдущего.

Единичный сигнал с выхода схемы сравнении 12 поступает на второй вход элемента И 10, и если на всех выходах второй группы элементов ИЛИ 9₁, 9₂, …, 9_n также присутствует единичный сигнал, то на выходе элемента И 10 формируется единичный сигнал EN=1.

Единичный сигнал EN=1 на выходе элемента 10 разрешает запись в группу вторых регистров 13₁, 13₂, …, 13_n значений с выходов счетчиков 4₁, 4₂, …, 4_n варианта распределения исполнителей по работам и запись кода временных затрат в третий регистр 14 с выхода сумматора 11. Запись в данные регистры выполняется синхронно по фронту следующего тактового сигнала.

При формировании сигнала переполнения с выхода n-го счетчика 4_n по тактовому сигналу триггер разрешения 2 устанавливается в нулевое состояние и останавливается счетный режим счетчика 4_i, а триггер готовности результата 3 устанавливается в единичное состояние, в результате чего на выходе устройства 18 формируется сигнал ГОТОВ об окончании работы устройства.

В результате работы устройства в группе вторых регистров 13₁, 13₂, …, 13_n будет установлен наилучший вариант распределения исполнителей, а в третьем регистре 14 минимум суммарных временных затрат на выполнение комплекса работ. В таблице 1 наилучшее распределение получено в варианте 10 при назначении 1-й работы за первым исполнителем, 2-й работы - четвертым, 3-й работы - третьим, 4-й работы - вторым. При этом суммарные временные затраты составляют 11 единиц. Данные итоговые значения получены при выполнении сравнения в схеме 12 по условию «меньше». При этом в группе вторых регистров 13₁, 13₂, …, 13_n и третьем регистре 14 фиксируется первый вариант из равных. Если сравнение проводить по условию «не больше» (или «меньше или равно»), то итоговым вариантом будет выбран последний из равных вариантов. В этом случае в таблице 1 был бы выбран вариант 12.

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

В предлагаемом устройстве период синхроимпульсов СИ определяется суммой времен - времени переключения разряда синхронных счетчиков 4_i, времени задержки дешифратора 5_i, времени задержки элемента И 7_ij, времени задержки элемента ИЛИ 8_i, времени задержки сумматора 11, времени задержки схемы сравнения 12, времени задержки элемента И 10 и времени предварительной установки в регистры 13_i или 14.

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

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