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

СОГОЗ СОВЕТСКИХСО ИЛЛИСТИЧЕСКИХРЕСПУБЛИК 1817105 9) (1 15/20(51) 5 САНИЕ ИЗОБРЕТЕ ВИДЕТЕЛЬСТ АВТОРСКОе4 ОСУДАРСТВЕННОЕ ПАТЕНТНВЕДОМСТВО СССРГОСПАТЕНТ СССР)(56) Авторское свидетельство СССРМ 1443007, кл. 6 06 6.7/122, 1987,Авторское свидетельство СССРМ 1569844, кл, 6 06 Г 15/20, 1989,(54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧКАЛ Е НДАР НОГО ПЛАНИ РОВАН И Я(57) Изобретение относится к вычислительной технике и может быть использовано дляаппаратного определения по исходномумножеству частично ресурсно-независимыхработ последовательности подмножеств ресурсно-независимых работ при ограничении на максимальную мощность этих подмножеств. Цель изобретения - расширение функциональных возможностей за счет оп-, ределения последовательности подмножеств ресурсно-независимых работ при ограничениях на максимальную мощность этих подмножеств, Поставленная цель достигается тем, что устройство для решения задач календарного планирования содержит распределитель импульсов 4, матрицу размером Н х Н блоков формирования признака зависимости работ 11, где Н - число работ в исходном множестве, Н блоков моделирования работ 16, счетчик 5, блок регистрации 3, первый и второй элементы ИЛИ 9 и 10, элемент И 8, группу из Н элементов И 7 и генератор тактовых импульсов 6, 1 ил.5 10 15 20 25 30 35 40 45 50 55 Изобретение относится к вычислительной технике и предназначено для аппаратного решения задач календарного планирования, заключающихся в определении по исходному множеству частично ресурсно-зависимых работ (проектов, заданий) последовательности подмножеств ресурсно-независимых работ, при ограничениина максимальную мощность этих подмножеств,Данная задача имеет приложения, например, при планировании обслуживания заявок многопроцессорной вычислительной системой (мощность искомых подмножеств ограничена числом процессоров) или при составлении расписаний занятий (мощность подмножеств ограничена максимально допустимым число занятий в учебный день, а роль общих ресурсов играют технические средства обучения, аудитории (классы), преподаватели),Цель изобретения - расширение функциональных возможностей устройства за счет решения задачи определения последовательности подмножеств ресурсно-независимых работ при ограничении на максимальную мощность этих подмножеств.Схема устройства приведена на чертеже.Устройство содержит матрицу 1 блоков формирования признаков зависимости работ, блоки 2 а моделирования работ, блок 3 регистрации, распределитель импульсов 4, счетчик 5, генератор тактовых импульсов 6, группу элементов И 7 а, элемент И 8, первый и второй элементы ИЛИ 8 и 9, соответственно (а = 1, 2, , Н, где Н - количество работ в исходном множестве), Цифровые обозначения имеют также вход запуска устройства 10 и вход 11 начальной установки устройства.Матрица 1 содержит блоки формирования признаков зависимости работ 12 аК а, М = 1, 2, Н, аК каждый из которых состоит из триггера 13 и элемента И 14. Цифровое обозначение на схеме имеет также установочный вход 15 блока формирования признака зависимости работ. Единичное состояние триггера 13 блока 12 аК моделирует необходимость для выполнения а-й и 1-й работ общего неделимого ресурса.Блоки 2 а, а = 1, 2, , Н моделирования работ одинаковы и каждый содержит триггер 16 и элемент И 17, Переход триггера блока 2 а в единичное состояние моделирует включение а-й работы в одно из множеств ресурсно-независимых работ.Блок 3 регистрации предназначен для фиксирования состава и количества определяемых подмножеств работ, На схеме обозначены тактовый вход блока 18 и информационные входы 19 а, а1, 2,Н, При поступлении импульсов на информационные входы блока они регистрируются в соответствующих ячейках элементов памяти блока, а при поступлении импульса на тактовый вход текущий элемент памяти отключается от информационных входов блока и осуществляется подключение к ним очередного элемента памяти,Распределитель импульсов 4 предназначен для распределения импульсов, поступающих на его тактовый вход 20 последовательно между информационными выходами 21 а, а = 1, 2, , Н, Н + 1, При поступлении импульса на вход 22 обеспечивается возврат распределителя в исходное состояние, Распределитель импульсов может быть реализован на основе известных многоустойчивых регистровых схем или кольцевых сдвигающих схем Счетчик 5 обеспечивает подсчет импульсов, поступающих на вход 23 и сравнение их числа с числом М, введенным по установочному входу 24, При равенстве этих значений счетчик формирует на выходе импульс уровня логической единицы и обнуляет свое текущее значение (М - максимально допустимая мощность искомых подмножеств).Работает устройство следующим образом, Перед началом работы подачей импульсов на входы 15 соответствующих блоков 12 аМ задается ресурсная зависимость исходное множества работ, а по входу 24 в счетчик 5 вводится число М, Решение начинается подачей импульса на вход 10 запуска устройства, откуда он поступает на генератор тактовых импульсов 6 и генератор начинает вырабатывать импульсы, первый из которых с выхода генератора поступает на тактовый вход 20 распределителя импульсов 4 С выхода 211 распределителя 4 импульс поступает на вход элемента И 17 блока 21, Так как, в начале решения триггер 16 всех блоков 2 а, а =1,2 Н находятся в нулевом состоянии, то при этом будет присутствовать сигнал высокого уровня на другом входе элемента И 17 блока 21 и сигнал низкого уровня - на инверсном входе элемента И 17 этого блока моделирования работ, Поэтому импульс с первого входа элемента И 17 блока 21 поступает на выход элемента И и далее - на единичный вход триггера 16 этого же блока и соответствующих вход элемента ИЛИ 10 и вход 191 блока 3 регистрации, Триггер 16 блока 21 переходит в единичное состояние и сигнал с его единичного выхода поступает на соответствующий вход элемента И 8, входы элементов И 14 блоков 12 а, а = 1, 2, , Н и вход элементов И 71, В блоке 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 будетприсутствовать сигнал высокого уровня сединичных выходов триггера блоков моде 10 лирования работ и с выхода этого элементаИ он поступит на вход останова генератора.Генератор прекращает работу, что сигнализирует об окончании решения. Последовательность ресурсно-независимых15 подмножеств работ исходного множествабудет однозначно зафиксирована элементами памяти блока 3, а число задействованныхэлементов памяти будет соответствоватьчислу интервалов времени, необходимых20 для выполнения всего исходного множестваработ,Таким образом, предлагаемое устройство обеспечивает за конечное число шаговрешения определение последовательности25 подмножеств ресурсно-независимых работ,которые могут быть выполнены за один интервал времени, при ограничении на максимальную мощность этих подмножеств,Кроме того, устройство позволяет опреде 30 лить требуемое число интервалов временидля выполнения всех рабо исходного множества. а его функциональная схема не зависит от топологии графа, моделирующегоресурную зависимость работ,35 Формула изобретенияУстройство для решения задач календарного планирования, содержащее распределитель импульсов и матрицуразмером НхН блоков формирования при 40 знака зависимости работ, где Н - количество работ в исходном множестве, причемкаждый блок формирования признака зависимости работ сОдержит триггер и элементИ, при этом в каждом блоке формирования45 признака зависимости работ матрицы установочный вход подключен к входу установкив "1" триггера, выход которого подключен кпервому входу элемента И, выход которогоподключен к выходу блока формирования50 признака зависимости работ матрицы, первый вход которого подключен к входу установки в "0" триггера, о т л и ч а ю щ е е с ятем, что, с целью расширения функциональных возможностей за счет определения по 55 следовательности подмножествресурсно-независимых работ при ограничениях на максимальную мощность этих подмножеств, оно содержит Н блоковмоделирования работ, счетчик, блок регистрации червь й и второй элементы ИЛИ, эле1817105 Составитель Н,ЯчкулаТехред М,Моргентал Корректор Н,Король Редактор Г.Бельская Заказ 1724 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб 4/5 Производственно-издательский комбинат "Патент", г, Ужгород, ул,Гагарина, 101 мент И, группу из Н элементов И и генератор тактовых импульсов, при этом вход запуска устройства подключен к входу запуска генератора тактовых импульсов, выход которого подключен к входу синхронизации 5 распределителя импульсов, выходы с первого по Н-й группы которого подключены соответственно к первым входам блоков моделирования работ с первого по Н-й, первый выход а-го блока моделирования работ, 10 где а: 1 Н, подключен к а-му входу элемента И, к первому входу а-го элемента И группы и к вторым входам блоков форми-. рования признака зависимости работ а-го столбца матрицы, второй выход а-го блока 15 моделирования работ подключен к а-му информационному входу блока регистрации и к а-му входу первого элемента ИЛИ, выход которого подключен к входу декремента счетчика, выход признака нулевого резуль тата которого подключен к первому входу второго элемента ИЛИ, выход которого объединен с (Н + 1-м выходом распределителя импульсов с помощью элемента МОНТАЖНОЕ ИЛИ и подключен к вторым входам 25 всех элементов И группы и к входу синхронизации блока регистрации, выход а-го элемента И группы подключен к первым входам блоков формирования признака зависимости работ а-го столбца матрицы, выходы 30 блоков формирования признака зависимости работ астроки матрицы обьединены с помощью элементов МОНТАЖНОЕ ИЛИ и подключены к второму входу а-го блока моделирования работ, выход элемента И подключен к входу останова генератора тактовых импульсов, (Н + 2-й выход распределителя импульсов подключен к второму входу второго элемента ИЛИ, первый вход начальной установки устройства - к установочным входам всех блоков формирования признака зависимости работ матрицы, второй вход начальной установки устройства - к установочным входам всех блоков моделирования работ, вход значения максимально допустимой мощности искомых подмножеств устройства - к информационному входу счетчика, причем каждый блок моделирования работ содержит элемент И и триггер, причем в каждом блоке моделирования работ первый и второй входы блока моделирования работ подключены соответственно к первому и второму (инверсному) входам элемента И, выход которого подключен к информационному входу триггера и к второму выходу блока моделирования работ, установочный вход которого подключен к входу установки в "0" триггера, прямой и обратный выходы которого подключены соответственно к первому выходу блока моделирования работ и к третьему входу элемента И.