Устройство для решения задач календарного планирования Советский патент 1993 года по МПК G06F15/20 

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

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

Схема устройства приведена на чертеже.

Устройство содержит матрицу 1 блоков формирования признаков зависимости работ, блоки 2а моделирования работ, блок 3 регистрации, распределитель импульсов А, счетчик 5, генератор тактовых импульсов 6, группу элементов И 7а, элемент И 8, первый и второй элементы ИЛИ 8 и 9, соответственно (а 1, 2,..., Н, где Н - количество работе исходном множестве). Цифровые обозначения имеют также вход запуска устройства 10 и вход 11 начальной установки устройства.

Матрица 1 содержит блоки формирования признаков зависимости работ 12 ak, a, k 1,2,...,H,, каждый из которых состоит из триггера 13 и элемента И 14. Цифровое обозначение на схеме имеет также установочный вход 15 блока формирования признака зависимости работ. Единичное состояние триггера 13 блока 12 ak моделирует необходимость для выполнения а-й и k-й работ общего неделимого ресурса.

Блоки 2а, а 1, 2, ..., Н моделирования работ одинаковы и каждый содержит триггер 16 и элемент И 17. Переход триггера блока 2а в единичное состояние моделирует включение а-й работы в одно из множеств ресурсно-независимых работ.

Блок 3 регистрации предназначен для фиксирования состава и количества определяемых подмножеств работ. На схеме обоз- начены тактовый вход блока 18 и

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

0 Распределитель импульсов 4 предназначен для распределения импульсов, поступающих на его тактовый вход 20 последовательно между информационными выходами 21а, а 1, 2, ..., Н, Н + 1. При

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

0 кольцевых сдвигающих схем.

Счетчик 5 обеспечивает подсчет импульсов, поступающих на вход 23 и сравнение их числа с числом М, введенным по установочному входу 24. При равенстве этих

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

0 Работает устройство следующим образом. Перед началом работы подачей импульсов на входы 15 соответствующих блоков 12 ak задается ресурсная зависимость исходное множества работ, а по входу 24 в счетчиК

5 5 вводится число М. Решение начинается подачей импульса на вход 10 запуска устройства, откуда он поступает на генератор тактовых импульсов 6 и генератор начинает вырабатывать импульсы, первый из которых

0 с выхода генератора поступает на тактовый вход 20 распределителя импульсов 4 С выхода 211 распределителя 4 импульс поступает на вход элемента И 17 блока 2i. Так как, в начале решения триггер 16 всех блоков 2а,

5 а 1,2,.... Н находятся в нулевом состоянии, то при этом будет присутствовать сигнал высокого уровня на другом входе элемента И 17 блока 2i и сигнал низкого уровня - на инверсном входе элемента И 17 этого блока

0 моделирования работ, Поэтому импульс с первого входа элемента И 17 блока 21 поступает на выход элемента И и далее - на единичный вход триггера 16 этого же блока и соответствующих вход элемента ИЛИ 10 и

5 вход 19i блока 3 регистрации. Триггер 16 блока 2i переходит а единичное состояние и сигнал с его единичного выхода поступает на соответствующий вход элемента И 8, входы элементов И 14 блоков 12а, а 1. 2,..., Н

„-.Лвход элементов И 7i. В блоке 3 в первом

элементе памяти фиксируется включение первой работы в первое искомое подмножество.

С выхода элемента ИЛИ 10 импульс поступает на вход 23 счетчика, текущее содержимое счетчика сравнивается с числом М и так как предполагается, что 1 М Н, то в результате первого шага первого этапа работы импульс на выходе счетчика не формируется.

С выхода элементов И 14 блоков 12а1, триггер 13 которых находится в единичном состоянии, сигнал уровня логической единицы поступает на инверсный вход элемента И 17 соответствующего блока моделирования работы. Этим исключается возможность включения в первое подмножество работ, претендующих на общий с первой работой ресурс.

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

Если на очередном р-том шаге (р Н) осуществится включение в искомое подмножество М-й по счету работы, то появится импульс на выходе счетчика 5, который поступит на вход элемента ИЛИ 9. С выхода элемента ИЛИ 9 импульс поступает на вход 22 распределителя, тактовый вход 18 блока 3 и объединенные входы элементов И 7а, а 1. 2, .... Н. При этом распределитель 4 переходит в исходное состояние, в блоке регистрации к информационным входам 19а, а 1, 2, .,,, Н подключается очередной элемент памяти, а с выходов элементов И 7а, соответствующих работам, включенным в первое подмножество ресурсно-независимых работ, импульс поступает на объединенные нулевые входы триггеров 13 блоков соответствующих столбцов матрицы 1. Те из триггеров этих блоков, которые находились в единичном состоянии, переходят в нулевое, чем моделируется исключение из дальнейшего рассмотрения работ, уже вошедших в решение. На этом заканчивается первый этап решения. Он может закончится и при условии, что за Н шагов решения мощность искомого множества не достигает значения М. В этом случае. очередной импульс генератора 6 с входа 20 распределится на выход 21 Н + 1, а с него - на вход элемента ИЛИ 9 и работа схемы по завершению этапа решения будет аналогична рассмотренной.

Очередной импульс с выхода генератора 6 поступает на вход 20 распределителя 4, снова распределяется на выход 211 и начинается второй этап решения, который, как и последующие, будет аналогичен рассмотренному.

Решение заканчивается, когда на одном 5 из шагов очередного этапа решения не будет включена в решение последняя работа. При этом на всех входах элемента И 8 будет присутствовать сигнал высокого уровня с единичных выходов триггера блоков моде0 лирования работ и с выхода этого элемента И он поступит на вход останова генератора. Генератор прекращает работу, что сигнализирует об окончании решения. Последовательность ресурсно-независимых

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

0 для выполнения всего исходного множества работ.

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

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

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

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

5 признака зависимости работ матрицы установочный вход подключен к входу установки в 1 триггера, выход которого подключен к первому входу элемента И, выход которого подключен к выходу блока формирования

0 признака зависимости работ матрицы, первый вход которого подключен к входу установки в О триггера, отличающееся тем, что, с целью расширения функциональных возможностей за счет определения по5 следовательностиподмножеств ресурсно-независимых работ при ограничениях на максимальную мощность этих подмножеств, оно содержит Н блоков моделирования работ, счетчик, блок регистрации пор,ВЫй и второй элементы ИЛИ, элемент И, группу из Н элементов И и генератор тактовых импульсов, при этом вход запуска устройства подключен к входу запуска генератора тактовых импульсов, выход ко- toporo подключен к входу синхронизации распределителя импульсов, выходы с первого по Н-й группы которого подключены соответственно к первым входам блоков моделирования работ с первого по Н-й, первый выход а-го блока моделирования работ, где а : 1, .... Н, подключен к а-му входу элемента И, к первому входу а-го элемента И группы и к вторым входам блоков формирования признака зависимости работ а-го столбца матрицы, второй выход а-го блока моделирования работ подключен к а-му информационному входу блока регистрации и к а-му входу первого элемента ИЛИ, выход которого подключен к входу декремента счетчика, выход признака нулевого резуль- тэта которого подключен к первому входу второго элемента ИЛИ, выход которого объединен с (Н + 1)-м выходом распределителя импульсов с помощью элемента МОНТАЖНОЕ ИЛИ и подключен к вторым входам всех элементов И группы и к входу синхро- низации блока регистрации, выход а-гО элемента И группы подключен к первым входам блоков формирования признака зависимости работ а-го столбца матрицы, выходы блоков формирования признака зависимости работ а-й строки матрицы объединены с помощью элементов МОНТАЖНОЕ ИЛИ и подключены к второму входу а-го блока моделирования работ, выход элемента И под- ключен к входу останова генератора тактовых импульсов, (Н + 2)-й выход распределителя импульсов подключен к второму входу второго элемента ИЛИ, первый вход начальной установки устройства - к установочным входам всех блоков формирования признака зависимости работ матрицы, второй вход начальной установки устройства - к установочным входам всех блоков моделирования работ, вход значения максимально допустимой мощности искомых подмножеств устройства - к информационному входу счетчика, причем каждый блок моделирования работ содержит элемент И и триггер, причем в каждом блоке моделирования работ первый и второй входы блока моделирования работ подключены соответственно к первому и второму (инверсному) входам элемента И, выход которого подключен к информационному входу триггера и к второму выходу блока моделирования работ, установочный вход которого подключен к входу установки в О триггера, прямой и обратный, выходы которого подключены соответственно к первому выходу блока моделирования работ и к третьему аходу элемента И.

Изобретение относится к вычислительной технике и может быть использовано для аппаратного определения по исходному множеству частично ресурсно-независимых работ последовательности подмножеств ресурсно-независимых работ при ограничении на максимальную мощность этих подмножеств. Цель изобретения - расширение функциональных возможностей за счет определения последовательности подмножеств ресурсно-независимых работ при ограничениях на максимальную мощность этих подмножеств. Поставленная цель достигается тем, что устройство для решения задач календарного планирования содержит распределитель импульсов 4, матрицу размером Н х Н блоков формирования при- знака зависимости работ 11, где Н - число работ в исходном множестве, Н блоков моделирования работ 16, счетчик 5, блок регистрации 3, первый и второй элементы ИЛИ 9 и 10, элемент И 8, группу из Н элементов И 7 и генератор тактовых импульсов 6. 1 ил.