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

Изобретение относится к вычислительной технике и может быть использовано для моделирования задач о назначениях при распределении 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), содержащее блок генерации перестановок, группу регистров, блок синхронизации, блок формирования величин временных затрат, связанных с назначениями, накапливающий блок выбора минимального времени и счетчик.
Недостатком данного устройства является то, что выбор проводится по минимаксному критерию на основе максимального значения временных затрат, необходимых на выполнение комплекса работ каждого варианта, а не минимальному суммарному времени выполнения всех работ.
К причинам, препятствующим достижению указанного ниже технического результата, относится отсутствие средств, обеспечивающих суммирование общих временных затрат.
1
2
n
1
2
n
11
nn
11
nn
1
2
n
1
2
n
i
i+1
i
11
nn
11
nn
1
2
n
1
2
n
Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является принятое за прототип устройство для решения задачи о назначениях (RU №2439687 С1, МПК G06F 17/50, заявлено 01.06.2010, опубликовано 10.01.2012, Бюл. №1), содержащее генератор тактовых импульсов 1, группу из n счетчиков 4, 4, …, 4, группу из n дешифраторов 5, 5, …, 5, группу из n*n первых регистров 6, …, 6, группу из n*n блоков элементов И 7, …, 7, элемент И 10, сумматор 11, схему сравнения 12, группу из n вторых регистров 13, 13, …, 13, третий регистр 14, вход пуска устройства 15, первый выход устройства 17, второй выход устройства 18, группу из n третьих выходов устройства 19, 19, …, 19, причем выход переполнения i-го счетчика 4 (i=1, 2, …, n-1) соединен с входом (i+1)-го счетчика 4, входы каждого i-го дешифратора 5 соединены с выходами соответствующего i-го счетчика 4 (i=1, 2, …, n), выходы группы из n*n первых регистров 6, …, 6 соединены с первыми входами одноименных блоков группы из n*n элементов И 7, … 7, выходы сумматора 11 соединены с первыми входами схемы сравнения 12, выходы третьего регистра 14 соединены со вторыми входами схемы сравнения 12 и являются первыми выходами устройства 17, выходы каждого регистра группы из n вторых регистров 13, 13, …, 13 являются группой из n третьих выходов устройства 19, 19, …, 19.
Недостатком данного устройства является низкая надежность, что связано с асинхронной работой блоков устройства, и невысокое быстродействие.
К причинам, препятствующим достижению указанного ниже технического результата, относятся большие аппаратные затраты, связанные с реализацией n блоков шифрации, наличие группы из n*n триггеров и группы n сумматоров, многоразрядность регистров для хранения лучшего варианта назначения исполнителей, так как распределение исполнителей хранится в унитарном коде, и большие временные затраты на вычисление значения временных затрат на выполнение комплекса работ каждого варианта.
Техническим результатом изобретения является повышение надежности устройства, уменьшение аппаратных затрат и увеличение быстродействия устройства.
1
2
n
1
2
n
11
nn
11
nn
1
2
n
1
2
n
i
i+1
i
11
nn
11
nn
1
2
n
1
2
n
1
2
n
1
2
n
1
2
n
1
2
n
1
2
n
1
2
n
1
i
i
1
2
n
i
11
nn
i
1
2
n
1
2
n
11
nn
1
2
n
n
Указанный технический результат при осуществлении изобретения достигается тем, что в устройство для решения задачи о назначениях, содержащее генератор тактовых импульсов 1, группу из n счетчиков 4, 4, …, 4, группу из n дешифраторов 5, 5, …, 5, группу из n*n первых регистров 6, …, 6, группу из n*n блоков элементов И 7, …, 7, элемент И 10, сумматор 11, схему сравнения 12, группу из n вторых регистров 13, 13, …, 13, третий регистр 14, вход пуска устройства 15, первый выход устройства 17, второй выход устройства 18, группу из n третьих выходов устройства 19, 19, …, 19, причем выход переполнения i-го счетчика 4 (i=1, 2, …, n-1) соединен с входом (i+1)-го счетчика 4, входы каждого i-го дешифратора 5 соединены с выходами соответствующего 1-го счетчика 4 (i=1, 2, …, n), выходы группы из n*n первых регистров 6, …, 6 соединены с первыми входами одноименных блоков группы из n*n элементов И 7, … 7, выходы сумматора 11 соединены с первыми входами схемы сравнения 12, выходы третьего регистра 14 соединены со вторыми входами схемы сравнения 12 и являются первыми выходами устройства 17, выходы каждого регистра группы из n вторых регистров 13, 13, …, 13 являются группой из n третьих выходов устройства 19, 19, …, 19, дополнительно введены триггер разрешения 2, триггер готовности результата 3, группа из n блоков первых элементов ИЛИ 8, 8, …, 8, группа из n блоков вторых элементов ИЛИ 9, 9, …, 9, вход сброса устройства 16, причем вход сброса устройства 16 соединен с входами синхронной установки в нулевое состояние вторым входом триггера разрешения 2, вторым входом триггера готовности результата 3, вторыми входами группы из n счетчиков 4, 4, …, 4, вторыми входами групп из n вторых регистров 13, 13, …, 13 и вторым входом синхронной установки в единичное состояние третьего регистра 14, выход ГТИ 1 соединен с входами синхронизации первым входом триггера разрешения 2, первым входом триггера готовности результата 3, первыми входами группы из n счетчиков 4, 4, …, 4, первыми входами группы из n вторых регистров 13, 13, …, 13, первым входом третьего регистра 14, вход пуска устройства 15 соединен с третьим входом разрешения работы триггера разрешения 2, выход которого соединен с третьим входом разрешения работы первого счетчика 4, выходы каждого i-го счетчика 4 соединены также с информационными входами соответствующего i-го регистра 13 (i=1, 2, …, n) группы из n вторых регистров 13, 13, …, 13, выходы каждого i-го дешифратора 5 (i=1, 2, …, n) соединены со вторыми входами соответствующей одноименной i-й строки матрицы группы из n*n блоков элементов И 7, … 7, а также одноименные j-e выходы дешифраторов 5соединены с входами соответствующего j-го блока (j=1, 2, …, n) вторых элементов ИЛИ 9, 9, …, 9, выходы которых соединены с первой группой входов элемента И 10, второй вход которой соединен с выходом схемы сравнения 12, а выход элемента И 10 соединен с третьими входами разрешения записи группы из n вторых регистров 13, 13, …, 13 и третьего регистра 14, выходы i-й строки матрицы (i=1, 2, …, n) группы из n*n блоков элементов И 7, …, 7 соединены с одноименными входами группы из n блоков первых элементов ИЛИ 8, 8, …, 8, выходы блоков которых соединены с соответствующими входами сумматора 11, выход переполнения n-го счетчика 4 соединен с четвертым входом синхронной установки в нулевое состояние триггера разрешения 2 и третьим входом синхронной установки в единичное состояние триггера готовности результата 3, выход которого является вторым выходом устройства 18.
На фиг.1 приведена схема предлагаемого устройства для решения задачи о назначениях.
1
2
n
1
2
n
11
nn
11
nn
1
2
n
1
2
n
1
2
n
1
2
n
На фиг.1 приняты следующие обозначения: генератор тактовых импульсов (ГТИ) 1, триггер разрешения 2, триггер готовности результата 3, группа из n счетчиков 4, 4, …, 4, группа из n дешифраторов 5, 5, …, 5, группа из n*n первых регистров 6, …, 6, группа из n*n блоков элементов И 7, …, 7, группа из n блоков первых элементов ИЛИ 8, 8, …, 8, группа из n блоков вторых элементов ИЛИ 9, 9, …, 9, элемент И 10, сумматор 11, схема сравнения 12, группа из n вторых регистров 13, 13, …, 13, третий регистр 14, вход пуска устройства 15, вход сброса устройства 16, первый выход устройства 17, второй выход устройства 18, группа из n третьих выходов устройства 19, 19, …, 19.
1
2
n
1
2
n
Внешний вход сброса устройства 16 соединен с входами синхронной установки в нулевое состояние вторым входом триггера разрешения 2, вторым входом триггера готовности результата 3, вторыми входами группы из n счетчиков 4, 4, …, 4, вторыми входами группы из n вторых регистров 13, 13, …, 13 и вторым входом синхронной установки в единичное состояние третьего регистра 14.
1
2
n
1
2
n
Выход ГТИ 1 соединен с входами синхронизации - первым входом триггера разрешения 2, первым входом триггера готовности результата 3, первыми входами группы из n счетчиков 4, 4, …, 4, первыми входами группы из n вторых регистров 13, 13, …, 13, первым входом третьего регистра 14.
1
Вход пуска устройства 15 соединен с третьим входом разрешения работы триггера разрешения 2, выход которого соединен с третьим входом разрешения работы первого счетчика 4.
i
i+1
Выход переполнения i-го счетчика 4 (i=1, 2, …, n-1) соединен с входом разрешения счета (i+1)-го счетчика 4.
i
i
1
2
n
i
Информационные выходы каждого i-го счетчика 4 соединены с информационными входами соответствующего i-го регистра 13 (i=1, 2, …, n) группы из n вторых регистров 13, 13, …, 13 и входами каждого i-го дешифратора 5.
11
nn
11
nn
1
2
n
1
2
n
Выходы группы из n*n первых регистров 6, …, 6 соединены с первыми входами одноименных блоков группы из n*n элементов И 7, … 7, выходы сумматора 11 соединены с первыми входами схемы сравнения 12, выходы третьего регистра 14 соединены со вторыми входами схемы сравнения 12 и являются первыми выходами устройства 17, выходы каждого регистра группы из n вторых регистров 13, 13, …, 13 являются группой из n третьих выходов устройства 19, 19, …, 19.
i
11
nn
i
1
2
n
1
2
n
Выходы каждого i-го дешифратора 5 (i=1, 2, …, n), соединены со вторыми входами соответствующей одноименной i-й строки матрицы группы из n*n блоков элементов И 7, … 7, а также одноименные j-e выходы дешифраторов 5 соединены с входами соответствующего j-го блока (j=1, 2, …, n) вторых элементов ИЛИ 9, 9, …, 9, выходы которых соединены с первой группой входов элемента И 10, второй вход которой соединен с выходом схемы сравнения 12, а выход элемента И 10 соединен с третьими входами разрешения записи группы из n вторых регистров 13, 13, …, 13 и третьего регистра 14.
11
nn
1
2
n
Выходы i-й строки матрицы группы из n*n блоков элементов И 7, …, 7 соединены с одноименными входами группы из n блоков первых элементов ИЛИ 8, 8, …, 8, выходы блоков которых соединены с соответствующими входами сумматора 11.
n
Выход переполнения n-го счетчика 4 соединен с четвертым входом синхронной установки в нулевое состояние триггера разрешения 2 и третьим входом синхронной установки в единичное состояние триггера готовности результата 3, выход которого является вторым выходом устройства 18.
1
2
n
1
2
n
i
2
i
Синхронные счетчики 4, 4, …, 4 формируют текущий вариант распределения работ за исполнителями. На группе вторых регистров 13, 13, …, 13 сохраняется наилучший вариант, который обеспечивает минимальную суммарную величину временных затрат на комплекс работ. Счетчики 4 содержат по k разрядов и имеют модуль пересчета n, соответствующий количеству исполнителей. При этом k≥log n. Вторые регистры 13 также содержат по k разрядов.
11
nn
11
nn
1
2
n
Первые регистры 6, …, 6 содержат по m разрядов, достаточных для записи максимальной длительности - выполнения отдельных работ. Каждый блок элементов И 7, …, 7 содержит m элементов И. Каждый блок первых элементов ИЛИ 8, 8, …, 8 содержит m элементов ИЛИ с n входами.
Сумматор 11 содержит n групп по m входов. Выходное количество разрядов сумматора 11 должно быть достаточно для записи максимальной суммарной длительности времени выполнения всего комплекса работ. Разрядность третьего регистра 14 соответствует разрядности сумматора 11.
1
2
n
Каждый блок группы вторых элементов ИЛИ 9, 9, …, 9 содержит элемент ИЛИ с n входами. Элемент И 10 содержит (n+1) вход.
Предлагаемое устройство для решения задачи о назначениях работает следующим образом.
Работа устройства основана на переборе всех возможных вариантов назначения и определении наилучшего варианта среди них по критерию минимума суммарных временных затрат на выполнение комплекса работ.
ij
Сущность рассматриваемой задачи заключается в следующем. Имеется n работ, для выполнения которых можно использовать n исполнителей, причем каждый исполнитель может выполнить только одну работу, а каждая работа может выполняться только одним исполнителем. Задана матрица длительности выполнения работ t (i=1, 2, …, n; j=1, 2, …, n), где (ij)-й элемент равен времени, необходимому для выполнения i-й работы j-м исполнителем. При этом необходимо так распределить n исполнителей по n работам, чтобы суммарные временные затраты были минимальны, а все работы выполнены.
ij
ij
11
nn
1
2
n
1
2
n
В исходном состоянии на регистрах 6 (i=1, 2, …, n; j=1, 2, …, n), устанавливаются коды времени t выполнения i-й работы j-м исполнителем. Группа из n*n первых регистров 6, …, 6 может быть выполнена на клавишных регистрах. Группа из n счетчиков 4, 4, …, 4 предназначена для задания текущего варианта распределения исполнителей. В процессе работы в группе из n вторых регистров 13, 13, …, 13 фиксируется текущий наилучший вариант назначения исполнителей. В сумматоре 11 вычисляются суммарные временные затраты текущего варианта, а в третьем регистре 14 фиксируется текущее минимальное значение суммарных временных затрат на выполнение комплекса работ.
i
i
Импульсы с ГТИ 1 постоянно поступают на входы синхронизации группы счетчиков 4, группы вторых регистров 13 и третьего регистра 14, режимы работы которых задаются сигналами на соответствующих входах управления.
1
2
n
1
2
n
При подаче сигнала на вход сброса устройства 16 по фронту импульса с ГТИ 1 в нулевое состояние устанавливаются триггер разрешения 2, триггер готовности результата 3, все счетчики 4, 4, …, 4, группа вторых регистров 13, 13, …, 13, а третий регистр 14 устанавливается в состояние «все единицы» - максимальный код временных затрат.
1
Работа устройства начинается после подачи сигнала ПУСК на вход устройства 15, по которому синхронно с импульсом от ГТИ 1 устанавливается в единичное состояние выход триггера разрешения 2, выход которого соединен с входом разрешения счета первого счетчика 4
1
2
n
i
i
На следующих тактах ГТИ 1 на выходах группы счетчиков 4, 4, …, 4формируется текущий вариант распределения исполнителей. С выхода счетчика 4 двоичный код поступает на вход одноименного дешифратора 5, на выходе которого формируется единичный сигнал только на одном его j-м выходе, задаваемом входным двоичным кодом.
i
11
nn
ij
ij
i
1
2
n
i
Так как все j-e выходы каждого i-го дешифратора 5 (i=1, 2, …, n, j=1, 2, …, n), соединены со вторыми входами в соответствующей одноименной i-й строке матрицы группы из n*n блоков элементов И 7, … 7, то в каждой i-й строке только через один блок элементов И 7 значение соответствующего первого регистра 6 поступает на соответствующие входы первого элемента ИЛИ 8 в i-й строке. Таким образом, на выходы группы из n блоков первых элементов ИЛИ 8, 8, …, 8 будут переданы времена выполнения каждой i-й работы. Данные значения времен с выходов первых элементов ИЛИ 8поступают на соответствующие входы сумматора 11, на выходах которого будет получено суммарное время затрат на выполнение всего комплекса из n работ.
i
1
2
n
1
2
n
i
Сигналы с одноименных j-x выходов дешифраторов 5 одновременно поступают на соответствующие входы j-го блока (j=1, 2, …, n) вторых элементов ИЛИ 9, 9, …, 9, выходы которых соединены с первой группой входов элемента И 10. На всех выходах второй группы элементов ИЛИ 9, 9, …, 9, будут установлены единичные сигналы только в том случае, когда единичные сигналы будут установлены во всех столбцах матрицы выходов дешифраторов, т.е. на различных j-x выходах дешифраторов 5. Этот вариант соответствует распределению всех n работ между n исполнителями.
i
1
2
n
В таблице 1 приведены варианты распределения n исполнителей по n работам для n=4. Только в приведенных 24 вариантах единичные значения будут установлены в различных j-x столбцах выходов дешифраторов 5 и на выходах всех вторых элементов ИЛИ 9, 9, …, 9.
ij
Код временных затрат с выхода сумматора 11 поступает на схему сравнения 12, на второй вход которой поступает код с выхода третьего регистра 14 со значением кода времени, зафиксированным на предыдущих вариантах как минимальное время. Единичный сигнал СС на выходе схемы сравнения 12 формируется только в том случае, если код временных затрат текущего варианта на выходе сумматора 11 меньше кода с выхода третьего регистра 14. В таблице 1 показаны временные затраты по i-м работам в соответствии с вариантом распределения j-x исполнителей при заданной матрице длительности выполнения работ t (i=1, 2, …, n; j=1, 2, …, n), приведенной в таблице 2. Единичный сигнал СС=1 формируется только в вариантах 1, 4, 10, когда текущий код временных затрат меньше предыдущего.
1
2
n
Единичный сигнал с выхода схемы сравнении 12 поступает на второй вход элемента И 10, и если на всех выходах второй группы элементов ИЛИ 9, 9, …, 9 также присутствует единичный сигнал, то на выходе элемента И 10 формируется единичный сигнал EN=1.
1
2
n
1
2
n
Единичный сигнал EN=1 на выходе элемента 10 разрешает запись в группу вторых регистров 13, 13, …, 13 значений с выходов счетчиков 4, 4, …, 4 варианта распределения исполнителей по работам и запись кода временных затрат в третий регистр 14 с выхода сумматора 11. Запись в данные регистры выполняется синхронно по фронту следующего тактового сигнала.
n
i
При формировании сигнала переполнения с выхода n-го счетчика 4 по тактовому сигналу триггер разрешения 2 устанавливается в нулевое состояние и останавливается счетный режим счетчика 4, а триггер готовности результата 3 устанавливается в единичное состояние, в результате чего на выходе устройства 18 формируется сигнал ГОТОВ об окончании работы устройства.
1
2
n
1
2
n
В результате работы устройства в группе вторых регистров 13, 13, …, 13 будет установлен наилучший вариант распределения исполнителей, а в третьем регистре 14 минимум суммарных временных затрат на выполнение комплекса работ. В таблице 1 наилучшее распределение получено в варианте 10 при назначении 1-й работы за первым исполнителем, 2-й работы - четвертым, 3-й работы - третьим, 4-й работы - вторым. При этом суммарные временные затраты составляют 11 единиц. Данные итоговые значения получены при выполнении сравнения в схеме 12 по условию «меньше». При этом в группе вторых регистров 13, 13, …, 13 и третьем регистре 14 фиксируется первый вариант из равных. Если сравнение проводить по условию «не больше» (или «меньше или равно»), то итоговым вариантом будет выбран последний из равных вариантов. В этом случае в таблице 1 был бы выбран вариант 12.
В предлагаемом устройстве, при единичном сигнале EN=1, запись варианта назначения исполнителей и текущего суммарного времени выполнения выполняется синхронно по фронту следующего тактового сигнала, что повышает надежность работы в сравнении с прототипом, в котором выполняется асинхронная запись по сигналам, формируемым в устройстве.
i
i
ij
i
i
В предлагаемом устройстве период синхроимпульсов СИ определяется суммой времен - времени переключения разряда синхронных счетчиков 4, времени задержки дешифратора 5, времени задержки элемента И 7, времени задержки элемента ИЛИ 8, времени задержки сумматора 11, времени задержки схемы сравнения 12, времени задержки элемента И 10 и времени предварительной установки в регистры 13 или 14.
Кроме того, в предлагаемом устройстве, в отличие от прототипа, сокращается объем аппаратных затрат за счет замены n блоков шифраторов, проверки одной единицы из n, на элементы ИЛИ, исключены группа из n*n триггеров и группа n сумматоров, а также сокращается разрядность выходных регистров, так как распределение исполнителей хранится в двоичном коде, в отличии от унитарного кода в прототипе.
Вышеизложенные сведения позволяют сделать вывод, что предлагаемое устройство для решения задачи о назначениях обладает регулярностью узлов и связей и соответствует заявляемому техническому результату - повышение надежности, сокращение аппаратных затрат, увеличение быстродействия.