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

 

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

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

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

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

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

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

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

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

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

Функциональная схема устройства представлена на фиг. 1.

Устройство содержит блок 1 генерации перестановок, блок 2 регистров, блок 3 синхронизации, блок 4 формирования временных затрат (связанных с выполнением работ исполнителями), накапливающий блок 5 выбора минимального числа, счетчик 6, вход 7 запуска устройства, выход 8 оптимального назначения, выход 9 временных затрат, соответствующих оптимальному назначению, выход 10 признака окончания вычисления, а также первый 11, второй 12 и третий 13 выходы блока 3 синхронизации.

Блок 1 генерации перестановок предназначен для формирования всех возможных перестановок чисел 1, 2, n на своих n информационных выходах. При этом появление числа m на k-том информационном выходе означает, что k-тый исполнитель назначается на м-работу. В качестве такого блока может быть использовано устройство для перебора перестановок [5] изображенное на фиг. 2 и включающее блок 16 формирования множества чисел и блок 17 декодирования [5] Блок 16 предназначен для формирования определяющего множества чисел в соответствии с выбранным вариантом перестановки, выбором минимального числа из этого множества и подачи его на блок декодирования 17. Блок 16 содержит регистры дешифратор 19, схему выбора минимального числа 20, ключи элемент задержки 22, управляющий вход 23, информационный вход 24 и информационный выход 25.

Блок 17 предназначен для преобразования заданного натурального числа в соответствующую ему перестановку. Блок 17 содержит регистры 26, 27_i, 28_i<блоки деления 29_i, сумматоры 30_i, элементы задержки 31_i, 32_i, вход пуска 33, элементы ИЛИ 34, 35, ключи 36_i, второй информационный вход 37, управляющий выход 38, информационный выход 39, информационный вход 40 и группу информационных выходов устройства Вход пуска устройства для перебора перестановок 33 соединяется с выходом 12 блока 3, а информационный вход устройства 40 соединяется с выходом счетчика 6. Информационные выходы устройства соответствует n информационным выходам блока 1. Работа блока 1 подробно рассмотрена в [5] Блок 2 регистров предназначен для хранения лучшего текущего назначения и содержит n регистров, каждый из которых имеет свой информационный вход, а все входы разрешения записи объединены и образуют вход разрешения записи блока.

Блок 3 синхронизации предназначен для упорядочения и согласования во времени моментов поступления сигналов на отдельные элементы и блоки предлагаемого устройства.

Блок 4 формирования временных величин затрат предназначен для определения величин, характеризующих временные затраты, связанные с назначениями исполнителей за работами и содержит группу из n дешифраторов 14₁,14_n и n*n регистров хранения величин затрат Накапливающий блок 5 выбора минимального числа предназначен для выбора из всех кодов, поступающих на его входы, максимального значения, сравнения полученного значения кода со значением, выбранным в предыдущих тактах работы, и в том случае, если текущее значение кода не превышает ранее полученное значение, запоминая его на выходе 9 и выработки признака "не больше" данного блока [3] В качестве приема накапливающего блока выбора минимального числа может быть использован блок, изображенный на фиг. 3 [3] Блок 5 содержит информационные входы , блок выбора максимума 43, регистры 44,45, блок сравнения 46 с управляющим входом 49, выход 47 признака "не больше", элемент задержки 48, информационный выход 9.

Управляющий вход 49 сравнения 46 соединяется с выходом 13 блока 3. Выход 47, соединенный с входом разрешения записи блока 2, служит для подачи признака "не больше" на вход разрешения записи блока 2.

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

Перед началом решения записывают (-1) в счетчик 6, максимально возможное число в регистр 44 хранения минимального значения кода блока 5, в регистры блока формирования величин временных затрат заносят величины временных затрат t_ij, связанных с назначением i-того исполнителя для выполнения j-той работы, а также обнуляют регистры блока 2 регистров, в регистры 18_i, 18_n хранения переставляемых элементов блока 1 генерации перестановок записывают числа 1, 2, n.

Для решения задачи на вход блока 7 запуска устройства подают импульс уровня логической единицы. При этом блок 3 синхронизации формирует на своих выходах 11, 12, и 13 последовательность сигналов уровня логической единицы, предусмотренную временной диаграммой его работы и представленную на фиг. 4.

Сигнал уровня логической единицы с первого выхода 11 блока 3 синхронизации поступает на счетный вход счетчика 6, формируя его на выходе первое число (0), которое затем поступает на информационный вход 40 блока 1 генерации перестановок. Через время τ₁ достаточное для выполнения указанных операций, блок 3 формирует потенциал уровня логической единицы на своем втором выходе 12, поступающий затем на вход 33 пуска блока 1 генерации перестановок, в результате чего на его информационных выходах будет сформирована первая перестановка чисел 1, 2, n. Функционирование блока 1 подробно рассмотрено в [4] При этом, коды чисел поступают на входы дешифраторов блока формирования величин временных затрат, обеспечивая получение сигнала уровня логической единицы на том из своих n выходов, номер которого соответствует величине поступившего на него числа. Таким образом, для первой перестановки на j-том выходе дешифратора 14_i будет сигнал уровня логической единицы. Этот сигнал поступит на входы разрешения выдачи информации с соответствующего регистра матрицы регистров блока 4 формирования величин временных затрат. Для первой перестановки это будут регистры 15₁₁,15₂₂, 15_nn, информация с которых поступит на информационные входы накапливающего блока 5 выбора минимальной суммы.

В блоке 5 осуществляется блоком 43 выбор максимального значения кода из поступивших на его информационные выходы (тем самым определяется максимальное время, необходимое для выполнения комплекса работ). Функционирование блока 43 выбора максимума рассмотрено в [5] Значение кода времени поступает на информационный вход регистра 45 и второй вход блока сравнения 46, на первый вход которого из регистра 44 поступает значение минимального к текущему времени кода. Через время τ₂ достаточное для выполнения указанных операций, блок 3 синхронизации формирует импульс уровня логической единицы на выходе 13 продолжительностью τ₃ который через вход поступает на вход запуска блока сравнения 46, который сравнивает значение минимального к настоящему времени кода временных затрат из регистра 44 со значением временных затрат текущего варианта и если последнее меньше, то на выходе "не больше" блока 46 появляется сигнал логической единицы, который поступает на вход разрешения записи блока 2 регистров, сохраняя текущий вариант, как лучший.

Через время τ₃ достаточное для выполнения указанных процессов, блок 3 снимает потенциал высокого уровня с выходов 12 и 13. При этом сигнал уровня логической единицы, пройдя через устройство задержки 48, через время τ₄ > τ₃ поступает на вход разрешения считывания регистра 45, информация с которого будет переписана в регистр 44 и текущие временные затраты будут сохранены в качестве лучшего значения.

После выполнения указанных операций блок 3 формирует импульс уровня логической единицы на выходе 11, который поступает на вход счетчика 6, на информационном выходе которого будет сформировано новое число (1), в соответствии с которым далее в блоке 1 генерации перестановок будет образована новая перестановка.

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

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

Формула изобретения

Устройство для решения задачи о назначениях, содержащее блок синхронизации, регистр и накапливающий блок выбора минимального времени, причем вход запуска устройства подключен к входу пуска блока синхронизации, отличающееся тем, что в него введены блок генерации перестановок, блок формирования величин временных, связанных с назначениями, содержащий группу из n дешифраторов и матрицу n x n регистров хранения величин временных затрат, а также n 1 регистров и счетчик, счетный вход которого подключен к первому выходу блока синхронизации, а выход переполнения является выходом признака окончания вычислений устройства, информационный выход счетчика соединен с информационным входом блока генерации перестановок, вход формирования очередной перестановки которого подключен к второму выходу блока синхронизации, к i-му выходу блока генерации перестановок подключены информационный вход i-го регистра и вход i-го дешифратора группы блока формирования величин временных затрат, связанных с назначениями, причем информационные выходы регистров являются выходом оптимального назначения устройства, а j-й выход i-го дешифратора группы подключен к входу разрешения считывания (i, j)-го регистра хранения величин временных затрат матрицы регистров информационный выход (i, j)-го регистра матрицы регистров блока формирования величин временных затрат, связанных с назначениями, соединен с соответствующим (i, j)-м информационным входом накапливающего блока выбора минимального времени, тактовый вход которого подключен к третьему выходу блока синхронизации, выход признака "Не больше" соединен с входом разрешения записи информации регистров с первого по n-й, а выход накапливающего блока выбора минимального времени является выходом величины временных затрат оптимального назначения устройства.

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4