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

 

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

СОГОЗ СОВЕТСКИХ

«Ol (ИЛЛИСТИЧЕСКИХ

РГ«ПУБЛИК (я)з G 06 F I5/20

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4827669/24 (22) 21,05.90 (46) 23,05.93. Бюл. N 19 (72) В.В.Барабанов, А.M,Áoðèñoâ, В.Т.Данцев и H.È.ß÷êóëà (56) Авторское свидетельство СССР

¹ 1443007, кл. G 06 G.7/122, 1987, Авторское свидетельство СССР

N 1569844, кл, G 06 F 15/20, 1989. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ

КАЛ Е НДАР НОГО ПЛАНИ РОВАН И Я (57) Изобретение относится к вычислительной технике и может быть использовано для аппаратного определения по исходному множеству частично ресурсно-независимых работ последовательности подмножеств ресурсно-независимых работ при ограниче„„Я3 „„1817105 А1 нии на максимальную мощность этих подмножеств. Цель изобретения — расширение функциональных возможностей за счет определения последовательности подмножеств ресурсно-независимых работ при ограничениях на максимальную мощность этих подмножеств, Поставленная цель достигается тем, что устройство для решения задач календарного планирования содержит распределитель импульсов 4, матрицу размером Н х Н блоков формирования при знака зависимости работ 11, где Н вЂ” число работ в исходном множестве, Н блоков моделирования работ 16, счетчик 5, блок регистрации 3, первый и второй элементы ИЛИ

9 и 10, элемент И 8, группу из Н элементов

И 7 и генератор тактовых импульсов 6. 1 ил.

1817105

10

20

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

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

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

Матрица 1 содержит блоки формирования признаков зависимости работ 12 ak, à, k

= 1, 2, „Н, à + К каждый из которых состоит из триггера 13 и элемента И 14. Цифровое обозначение на схеме имеет также установочный вход 15 блока формирования признака зависимости работ. Единичное состояние триггера 13 блока 12 ak моделирует необходимость для выполнения а-й и

k-й работ общего неделимого ресурса.

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

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

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

Счетчик 5 обеспечивает подсчет импульсов, поступающих на вход 23 и сравнение их числа с числом М, введенным по установочному входу 24. При равенстве этих значений счетчик формирует на выходе импульс уровня логической единицы и обнуляет свое текущее значение (М вЂ” максимально допустимая мощность искомых подмножеств).

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

ak задается ресурсная зависимость исходное множества работ, а по входу 24 в счетчик

5 вводится число М. Решение начинается подачей импульса на вход 10 запуска устройства, откуда он поступает на генератор тактовых импульсов 6 и генератор начинает вырабатывать импульсы, первый из которых с выхода генератора поступает на тактовый вход 20 распределителя импульсов 4. С выхода 211 распределителя 4 импульс поступает на вход элемента И 17 блока 2>, Так как, в начале решения триггер 16 всех блоков 2а, а = 1, 2... „Н находятся в нулевом состоянии, то при этом будет присутствовать сигнал высокого уровня на другом входе элемента

И 17 блока 21 и сигнал низкого уровня — на инверсном входе элемента И 17 этого блока моделирования работ, Поэтому импульс с первого входа элемента И 17 блока 21 поступает на выход элемента И и далее — на единичный вход триггера 16 этого же блока и соответствующих вход элемента ИЛИ 10 и вход 19> блока 3 регистрации. Триггер 16 блока 21 переходит в единичное состояние и сигнал с его единичного выхода поступает на соответствующий вход элемента И 8, входы элементов И 14 блоков 12а. а = 1. 2, ..., Н и вход элементов И 7 . В блоке 3 в первом

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

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

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

По завершению этих операций на тактовый вход 20 распределителя импульсов поступает второй импульс, он распределяется на выход 21 и начинается второй шаг решения, который как и последующие аналогичен вышерассмотренному первому, Если на очередном р-том шаге (р < Н) осуществится включение в искомое подмножество М-й по счету работы, то появится импульс на выходе счетчика 5, который поступит на вход элемента ИЛИ 9. С выхода элемента ИЛИ 9 импульс поступает на вход 22 распределителя, тактовый вход 18 блока 3 и обьединенные входы элементов И

7а, а = 1, 2, ..., Н. При этом распределитель

4 переходит в исходное состояние, в блоке регистрации к информационным входам

19а, а = 1, 2, „„Н подключается очередной элемент памяти, а с выходов элементов И

7а, соответствующих работам, включенным в первое подмножество ресурсно-независимых работ, импульс поступает на обьединенные нулевые входы триггеров 13 блоков соответствующих столбцов матрицы 1. Те из триггеров этих блоков, которые находились в единичном состоянии, переходят в нулевое, чем моделируется исключение из дальнейшего рассмотрения работ, уже вошедших в решение. На этом заканчивается первый этап решения, Он может закончится и при условии, что за Н шагов решения мощность искомого множества не достигает значения M. В этом случае. очередной импульс генератора 6 с входа 20 распределится на выход 21 Н + 1, а с него — на вход элемента ИЛИ 9 и работа схемы по завершению этапа решения будет аналогична рассмотренной.

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

Решение заканчивается, когда на одном

5 из шагов очередного этапа решения не будет включена в решение погледняя работа.

При этом на всех входах элемента И 8 будет присутствовать сигнал высокого уровня с единичных выходов триггера блоков моде10 лирования работ и с выхода этого элемента

И он поступит на вход останова генератора.

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

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

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

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

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

И, при этом в каждом блоке формирования

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

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

Составитель Н.Ячкула

Техред М,Моргентал Корректор Н.Король

Редактор Г. Бельская

Заказ 1724 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб.. 4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101 мент И, группу из Н элементов И и генератор тактовых импульсов, при этом вход запуска устройства подключен к входу запуска генератора тактовых импульсов, выход которого подключен к входу синхронизации 5 распределителя импульсов, выходы с первого по Н-й группы которого подключены соответственно к первым входам блоков моделирования работ с первого по Н-й, первый выход а-го блока моделирования работ, 10 где а = 1, .;., Н, подключен к а-му входу элемента И, к первому входу а-го элемента

И группы и к вторым входам блоков форми-. рования признака зависимости работ а-го столбца матрицы, второй выход а-ro блока 15 моделирования работ подключен к а-му информационному входу блока регистрации и к а-му входу первого элемента ИЛИ, выход которого подключен к входу декремента счетчика, выход признака нулевого резуль- 20 тата которого подключен к первому входу второго элемента ИЛИ, выход которого объединен с (Н + 1 -м выходом распределителя импульсов с помощью элемента МОНТАЖН0Е ИЛИ и подключен к вторым входам 25 всех элементов И группы и к входу синхронизации блока регистрации, выход а-го элемента И группы подключен к первым входам блоков формирования признака зависимости работ а-го столбца матрицы, выходы 30 блоков формирования признака зависимости работ а-й строки матрицы обьединены с помощью элементов МОНТАЖНОЕ ИЛИ и подключены к второму входу а-ro блока моделирования работ, выход элемента И подключен к входу останова генератора тактовых импульсов, (Н + 2 -й выход распределителя импульсов подключен к второму входу второго элемента ИЛИ, первый вход начальной установки устройства — к установочным входам всех блоков формирования признака зависимости работ матрицы, второй вход начальной установки устройства— к установочным входам всех блоков моделирования работ, вход значения максимально допустимой мощности искомых подмножеств устройства — к информационному входу счетчика, причем каждый блок моделирования работ содержит элемент И и триггер, причем в каждом блоке моделирования работ первый и второй входы блока моделирования работ подключены соответственно к первому и второму (инверсному) входам элемента И, выход которого подключен к информационному входу триггера и к второму выходу блока моделирования работ, установочный вход которого подключен к входу установки в "0" триггера, прямой и обратный выходы которого подключены соответственно к первому выходу блока моделирования работ и к третьему входу элемента И.