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

) 4 С 06 С ИОАН ЗОБРЕТЕНИ Н АВТОРСНОМ 1и 2 ил. Ю Ю ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(54) УСТРОЙСТВО ДЛЯ РБЦЕНИЯ ЗАДАЧ ТЕОРИИ РАСПИСАНИЙ(57) Изобретение относится к вычислительной технике, может быть исполь зовано для решения задач теории рас" писаний и позволяет минимизировать суммарное время исполнения технологически зависимых заданий, Устройство содержит блок 1 синхронизации счетчик 2, блок 3 памяти, группу з Р накапливающих сумматоров 4, где Р - .количество однотипных исполнителей, между которыми распределяются задания, ключ 5, блок 6 выбора максимального кода, блок 7 выбора минимального к блок 8 приоритетов, группу из Р элементов И 9, коммутатор 10, элемент ИЛИ 11, Кроме того, на фиг, 1 цифровые обозначения имеют вход 12 начальной установки устройства, вход 13 задания режима работы устройства, выход 14 номера задания устройства, выход 15 назначения времени исполнения задания устройства, выходы 16 признаков назначения заданий исполнителям, выход 17 признака окончания работы устройства, с первого по пятый выходы .18 - 22, блок 1 синхронизации, вход 23 пуска устройства, Перед началом работы длительность исполнения заданий заносится в блок 3 памяти. ф Далее, по сигналам с выходом 18 - 22 блока 1 синхронизации время исполнения заданий последовательно считыва" ется из блока 3 памяти и соответствующие задания назначаются исполнителям с учетом заданий, назначенных им в предшествующих тактах рабо 1443007Изобретение относится к вычислительной технике и может быть использовано для оптимизации расписаний выполнения технологически эависи 5 мых заданий однотипными исполнителями.Цель изобретения - расширениефункциональных возможностей устройства за счет решения задачи минимизации суммарного времени исполнениятехнологически зависимых заданий,На фиг. 1 представлена Функцио"нальная схема устройства; на Фиг. 2 -временная диаграмма работы блокасинхронизации,Устройство содержит блок 1 синхронизации, счетчик 2, блок 3 памяти, группу из Р накапливающих сумматоров 4, где Р - количество однотипных исполнителей, между которыми распределяются задания, ключ 5,блок 6 выбора максимального кода,блок 7 выбора минимального кода,блок 8 приоритетов, группу из Р элементов И 9, коммутатор 1 О, элементИЛИ 11,Кроме того, обозначены вход 12начальной установки устройства,вход 13 задания режима работы устройства, вход 14 номера задания устройства, выход 15 назначения времени исполнения задания устройства,выходы 16 признаков назначения заданий исполнителям, выход 17 признакаокончания работы устройства, с первого по пятый выходы 18 - 22 блока 1синхронизации, вход 23 пуска устройства,Устройство работает следующимобразом.Пусть в рамках каждого из трехразличных технологических процессовнеобходимо выполнить по три заданияс временем выполнения заданий 5,3,7(единиц времени) для первого прсцес"са, 8,1,3 - для второго и 4,6,2для третьего силами двух (Р=2) однотипных исполнителей (например, Э 6 И),При этом задания различных технологических процессов нельзя выполнятьодновременно. Перед началом работвремени исполнения заданий в рамкахкаждого технологического процессаупорядочиваются по невозрастаниювремени их исполнения и заносятсяв блок 3 памяти таким образом, чтопо адресам соответственно 0,1, , 8располагаются числа 7,5,3; 8,3,1 и О 5 2 О 25 30 35 4 О 45 50 6,4,2. Тем самым одновременно каждому заданию присваивается номер, равный адресу, по которому в блок 3 памяти записано время исполнения задания, Причем количество заданий в каждом из технологических процессов должно быть одинаковым. В противном случае технологические процессы с меньшим количеством заданий дополняются фиктивными заданиями с нулевым временем исполнения до их кол:. - чества в технологическом процессе с максимальным количеством заданий,На вход 12 начальной установки устройства подают импульсный сигнал единичного уровня, при этом устанавливается в ноль счетчик 2, замыкается информационная цепь ключа 5, обнуляются все сумматоры 4, На вход 23 пуска устройства подают импульсный сигнал единичного уровня, при этом блок 1 синхронизации начинает вырабатывать последовательность импульсов, предусмотренную временной диаграммой его работыИмпульсный сигнал единичного уро.-: ня появляется на выходе 18 блока 1, При этом из блока 3 памяти считьвается код числа 7 (максимальное по длительности задание первого технологического процесса). Через время Т 1, достаточное для выбора числа 7 из блока 3 памяти, блоксинхронизации Формирует импульс на выходе 19. При. этом на первом выходе 16 формируется признак назначения задания первому исполнителю и код числа 7 суммируется с содержимым первого накапливающего сумматора 4 (поскольку последний хранит наименьший код и обладает наибольшим приоритетом). Через время Т 2, достаточное для записи информации в сумматор 4 и обре ботки исполнителем признака назн,- чения задания блок 1 синхронизации сбрасывает сигналы на выходах 18 и 9 и формирует импульсный сигнал единичного уровня на выходе 20, гри этом на выходе счетчика прибавляет к текущему значению единицу, Через время ТЗ, достаточное для прибавления единицы; блок 1 сбрасывает сигнал на выходе 20 и формирует сигнал единичного уровня на выходе 18, Далее устройство работает аналогично, и второе и третье по величине задания назначаются второму исполнителю, Однако после того, каг сбраУстройство для решения задач теории расписаний, содержащее блок па 314430074сываетсЯ сигнал на выходе 20 (после мЯти, блок выбора максимального коназначения третьей работы второму ис- да, группу из Р накапливающих суммаполнителю), блок 1 синхронизации торов, где Р - количество однотипформируф ет импульсный сигнал единич 5ных исполнителен, между ко.горыми расного уровня на выходе . Ри этом21П и этом пределяются задания, и блок синхрониустройство выпает исполнителям приз- за 11 ии, вход пуска которого являетсянак выдачи максимального времени ис- входом пуска устройства, о т л иполнения назначенных заданий и ве- ю е е с я тем что с цельюличину времени исполнения заданий на 10 расн Рни ФУ.пи ения Ь нкциональных возможносвыход 15 устройства, тей устройства за счет решения задачи минимизации суммарного времениобработки исполнителями признака вы- исполнения технологически зависимыхмножеств абот в него введены эледачи времени исполнения, блок 1 син- мно ес Рхронизации сбрасывает сигнал на вы мент И 311,нт И 11 И счетчик ключ, блок выбораФминимального кода, блок приоритетов,ходе 21 и формирует импульсный сигнал единичного уровня на выходе 22. группа иг ппа из Р элементов И и коммутатор,При этом обнуляются все накапливающие причем входвхо начальной установки устсумматоры 4 группы.(в том случае, ес- ройства дойства по ключен к входу отключенияли нет запрета на одновременность ис ключа, к и Рч к пе вом входу элемента ИЛИполнения заданий различных техноло- и к входу усстановки в 0 счетчикагических процессов, то перед началом информационный выход которого являетработы подают импульсный сигнал еди- ся выходом ном р доме а за ания устройстничного уровня на вход 13 задания ре- ва и подключе др ук а есном входу бложима работы устройства, при этом раз ка памяти, в д : рыхо кото ого подключенмыкается информационная цепь ключа 5 к входам слагаемо вгаемого всех накапливаюи по сигналу с выхода 22 блока 1 обну- щих сумматоров группы, выход К-голение накапливающих сумматоров 4 не накапливающего сумматора группыпроисходит), Через. время Т 5, доста- (Х = 1 Р) подключен к К-м инточное для установки в ноль суммато- З 0 формационным входам коммутатора, блоров 4, блок 1 синхронизации снимает ка выбора максимального кода и блокасигнал с выхода 22 и Формирует им- выбора минимального кода, К-й выпульсный сигнал единичного уровня ход позиции минимального кода которого подключен к К-му входу блокана выходе 18,Далее работа устройства повторя- приоритетов, К-й выход позиции сигется После того, как распределены нала с наибольшим приоритетом котоза ания происходит переполнение рого подключен к первому входу К-гоо кото огосчетчика 2, Сигнал переполнения ос- элемента И группы, выход к ртанавливает блок 1 синхронизации является выходом признака наэначеи поступает на выхоьход 17 устройства О ния задания К-му исполнителю устрой 40в качестве признака окончания работы ства и подключен к входу признакаустройства, записи К-го накапливающего сумматораВ представленном примере перво- группы, К-й выход позиции максимальму исполнителю назначаются задания ного кода блока выбора максимальногос длительностью 7,8,6 единиц времени 45 кода подключен к К-му управляющемуа.второму - задания с длительностью входу коммутатора, выход котоРого5 3,3,1,4,2 (в том случае, если зада- является выходом назначения времени1 Ф 1 Ф 9ст пе -ния различных технологических про- исполнения задания устройства, перцессов могут выполняться одновремен- вый выход блока синхронизации подно; они распределяются между двумя ключен к входу признака чтения лохаисполнителями следующим образом: 7,8 в памяти, второй выход блока синхрони 4 первому исполнителю и 5,3,3,1,6,2 зации подключен к вторым входам всехвторому исполнителю), элементов И РупРг пы т етий выходБлок 3 памяти может быть выполнен блока синхронизации подключен к выв виде матрицы регистров. читающему вх дуо счетчика выход призФнака переполнения которого являетсяФормула и з Роб ет ениявыходом признака окончания работыустройства и подключен к.входу останова блока синхронизации, четвертыйСоставитель А, ПакТехред М.Ходанич Корректор Л, Пилипенк Редактор В,Подписн 6 ака омитета ССоткрытий д, ул. Проектная, 4 Производственно-полиграфическое предприятие, г, Ужго 544 выход которого является признаком выдачи времени исполнения задания устройства, пятый выход блока синхронизации подключен к информационному входу ключа, выход которого подключен к,второму входу элемента ИЛИ,Тираж 70 А ВНИИПИ Государственног по делам йзобретений 3035, Москва, Ж, Равыход которого подключен к входам установки в 0 всех накапливающих сумматоров группы, вход задания режима работы устройства. подключен к входу включения ключа.