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

 

Изобретение относится к вычислительной технике, может быть использовано для решения задач теории расписаний и позволяет минимизировать суммарное время исполнения технологически зависимых заданий. Устройство содержит блок 1 синхронизации, счетчик 2, блок 3 памяти, группу из Р накапливаютях сумматоров 4, где Р - .количество однотипных исполнителей , между которыми распределяются задания, ключ 5, блок 6 выбора максимального кода, блок 7 выбора минимального кода, блок 8 приоритетов , группу из Р элементов И 9, коммутатор 10, элемент ИЛИ 11. Кроме того, на фиг. 1 цифровые обозначения имеют вход 12 начальной установки устройства, вход 13 задания режима работы устройства, выход 14 номера задания устройства, выход 15 назначения времени исполнения задания устройства, выходы 16 признаков назначения заданий исполнителям, выход 17 признака окончания работы устройства, с первого по пятый выходы .18 - 22, блок синхронизации, вход 23 пуска устройства. Перед началом работы длительность исполнения заданий заносится в блок 3 памяти. Далее, по сигналам с выходом 18-22 блока 1 синхронизации время исполнения заданий последовательно считьгаается из блока 3 памяти и со ответствующие задания назначаются исполнителям с учетом заданий, назначенных им в предшествующих тактах работы . 2 ил . (Л 4 4ib САР

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН (51)4 G 06 G 7/122

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

1Гр

ffg

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4242950/24-24 (22) 12.05.87 (46) 07,12.88. Бюл. №- 45 (72) О.Г.Алексеев, С.А.Васильковский, В.Т,Данцев и Н.И.Ячкула (53) 681.333(088.8) (56) Авторское свидетельство СССР № 1233161, кл. G 06 F 15/20, 1984.

Авторское свидетельство СССР № 1336042; 31.10.86. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ

ТЕОРИИ РАСПИСАНИЙ (57) Изобретение относится к вычислительной технике, может быть использовано для решения задач теории рас" писаний и позволяет минимизировать суммарное время исполнения технологически зависимых заданий. Устройство содержит блок 1 синхронизации, счетчик 2, блок 3 памяти, группу из

Р накапливающих сумматоров 4, где

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

SU 1443007 А 1 минимального кода, блок 8 приоритетов, группу из P элементов И 9, коммутатор 10, элемент ИЛИ ll. Кроме того, на фиг. 1 цифровые обозначения имеют вход 12 начальной установки устройства, вход 13 задания режима работы устройства, выход 14 номера задания устройства, выход 15 назначения времени исполнения задания устройства, выходы 16 признаков назначения заданий исполнителям, выход 17 признака окончания работы устройства, с первого по пятый выходы 18 — 22, блок I синхронизации, вход 23 пуска устройства, Перед началом работы длительность исполнения заданий заносится в блок 3 памяти.

Далее, по сигналам с выходом 18 — 22 блока 1 синхронизации время исполнения заданий последовательно считывается из блока 3 памяти и соответствующие задания назначаются исполнителям с учетом заданий, назначенных им в предшествующих тактах рабо- . ты. 2 ил.

1443007

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

Цель изобретения — расширение функциональных возможностей устройства за счет решения задачи минимизации суммарного времени исполнения технологически зависимых заданий, На фиг. 1 представлена функцио" нальная схема устройства; на фиг. 2—

1 временная диаграмма работы блока синхронизации, Устройство содержит блок 1 синхронизации, счетчик 2, блок 3 памяти, группу из P накапливающих сумматоров 4, где P — количество однотипных исполнителей, между которыми распределяются задания, ключ 5, блок 6 выбора максимального кода, блок 7 выбора минимального. кода, блок 8 приоритетов, группу из Р элементон И 9, коммутатор 10, элемент

ИЛИ 11.

Кроме того, обозначены вход 12 начальной установки устройства, вход 13 задания режима работы устройства, вход 14 номера задания устройства, ньгход 1S назначения времени исполнения задания устройства, выходы 16 признаков назначения заданий исполнителям, выход 17 признака окончания работы устройства, с первого по пятый выходы 18 — 22 блока 1 синхронизации, вход 23 пуска устройства, Устройство работает следующим образом.

Пусть в рамках каждого из трех различных технологических процессов необходимо выполнить по три задания с временем выполнения заданий S,3,7 (единиц времени) для первого прсцес-са, 8,1,3 — для второго и 4,6,2 для третьего силами двух (Р=2) одНо THIIHblx исполнителей (например, 3AM), При этом задания различных технологических процессов нельзя выполнять одновременно. Перед началом работы времени исполнения заданий в рамках каждого технологического процесса упорядочиваются по невозрастанию времени их исполнения и заносятся в блок 3 памяти таким образом, что по адресам соответственно 0,1. . .8 располагаются числа 7,5,3; 8,3,1 и

16

26

36

46

56 пользонано для оптимизации расписаний выполнения технологически эаниси5 мых заданий однотипными исполнителя6,4,2. Тем самым одновременно каждому заданию присняинается номер, равный адресу, по которому н блок 3 памяти записано время исполнения задания, Причем количество заданий в каждом из технологических процессов должно быть одинаковым. В противном случае технологические процессы с меньшим количеством заданий дополняются фиктивными заданиями с нулевым временем исполнения до их кол:;— честна в технологическом процессе с максимальным количеством заданий.

На вход 12 начальной установки устройстна подают импульсный сигнал единичного уровня, при этом устанавливается в ноль счетчик 2, замыкается информационная цепь ключа 5, обнуляются все сумматоры 4, На вход 23 пуска устройства подают импульсный

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

Импульсный сигнал единичного уро. -: ня появляется на выходе 18 блока

При этом из блока 3 памяти считывается код числа 7 (максимальное по длительности задание первого технологического процесса). Через время

Tl достаточное для выбора числа 7 из блока 3 памяти, блок 1 синхрони— зации формирует импульс на выходе 19.

При. этом на первом выходе 16 формируется признак назначения задания первому исполнителю и код числа 7 суммируется с содержимым первого накапливающего сумматора 4 (поскольку последний хранит наименьший код и обладает наибольшим приоритетом).

Через время Т2, достаточное для записи информации в сумматор 4 и обра.ботки исполнителем признака назн.-. чения задания„ блок l синхронизации сбрасывает сигналы на выходах 18 и !

9 и формирует импульсный сигнал единичного уровня на выходе 20, ри этом на выходе счетчика прибавляет к текущему значению единицу. Чере- время ТЗ, достаточное для прибавления единицы; блок 1 сбрасывает сигнал на выходе 20 и формирует сигнал единичного уровня на выходе 18, Далее устройство работает аналогично, и второе и третье по величине задания назначаются второму исполнителю, Однако после того, ка" сбраУстройство для решения задач теории расписаний, содержащее блок па3

1443007

4 сывается сигнал на нг»ходе 20 (после мяти, блок выбора максимального коназначения третьей работы второму ис- да, группу иэ P накапливающих суммаполнителю), блок 1 синхронизации торов, где Р— количество однотипформиру ф ет импульсный сигнал единич5 ных исполнителен, между ко-горыми расного уровня на выходе . Ри этом

21 П и этом пределяются задания, и блок синхрониустройство выдает исполнителям приз- за11ии, вход пуска которого является нак выдачи максимального времени ис- входом пуска устройства, о т л и полнения назначенных заданий и ве- ю е е с я тем что с целью личину времени исполнения заданий íà 10 рас.:н р ни фу ц пи ения ь нкциональных возможносвыход 15 устройства. тей уст;:îécòíà за счет решения задачи минимизации суммарного времени обработки исполнителями признака вы- исполнения технологически зависимых множеств абот в него введены эледачи времени исполнения, блок 1 син- мно ес Р хронизации сбрасывает сигнал íà IIbt 15 мент И!11, ит И!1И счет (ик ключ, блок выбора

S минимального кода, блок приоритетов, ходе 21 и формирует импульсный сигнал единичного уровня на выходе 22. группа и г ппа из P элементов И и коммутатор, При этом обнуляются все накапливающие причем вход вхо начальной установки устсумматоры 4 группы.(в том случае, ес- ройства д ойства по ключен к входу отключения ли нет запрета на одновременность ис- 20 ключа s и р ч к пе вом входу элемента ИЛИ полнения заданий различных техноло- и к входу ус становки в "0 счетчика гических процессов, то перед началом информационный выход которого являетработы подают импульсный сигнал еди- ся выходом ном р д оме а sa ания устройстничного уровня на вход 13 задания ре- ва и подключе др у к а есном входу бложима работы устройства, при этом раз- 25 ка памяти, в д : p

ыхо кото ого подключен мыкается информационная цепь ключа 5 к входам слагаемо в гаемого всех накапливаю и по сигналу с выхода 22 блока 1 обну- щих сумматоров группы, выход К-го ление накапливающих сумматоров 4 не накапливающего сумматора группы происходит). Через. время Т5, доста- (Х = 1,..., Р) подключен к К-м инточное для установки в ноль суммато- 0 формационным входам коммутатора, блоров 4, блок 1 синхронизации снимает ка выбора максимального кода и блока сигнал с выхода 22 и формирует им- выбора минимального кода, К-й выпульсный сигнал единичного уровня ход позиции минимального кода которого подключен к К-му входу блока на выходе 18.

Палее работа устройства повторя 35 приоритетов, К-й выход позиции сигется После того, как распределены нала с наибольшим приоритетом котоза ания происходит переполнение рого подключен к первому входу К-го о кото ого счетчика 2. Сигнал переполнения ос- элемента И группы, выход к р танавливает блок 1 синхронизации является выходом признака наэначеи поступает на выхо ьход 17 устройства О ния задания К-му исполнителю устрой40 в качестве признака окончания работы ства и подключен к входу признака устройства. записи К-го накапливающего сумматора

В представленном примере перво- группы, К-й выход позиции максимальму исполнителю назначаются задания ного кода блока выбора максимального с длительностью 7,8,6 единиц времени, 45 кода подключен к К-му управляющему а.второмУ вЂ” зацаниЯ с Длительностью входу коммутатора, выход которого

5 3,3,1,4,2 (в том случае, если зада- является выходом назначения времени в в э э е ст пе— ния различных технологических про- исполнения задания устройства, пер цессов могут выполняться одновремен- вый выход блока синхронизации подно; они распределяются между двумя ключен к входу признака чтения ло.<а исполнителями следующим образом: 7 8э памяти, второй выход блока синхрони4 первому исполнителю и 5,3,3,1,6i2 зации подключен к вторым входам всех второму исполнителю). элементов И руп, р г пы т етий вЫход

Блок 3 памяти может быть выполнен блока синхронизации подключен к выв виде матрицы регистров. читающему Вх ду о счетчика выход призФ нака переполнения которого является Формула и з Р об ет ения выходом признака окончания работы" устройства и подключен к.входу останова блока синхронизации, четвертый

Составитель А. Пак

Техред М. Ходанич Корректор JI Пилипенко

Редактор В. Петраш

Заказ 6386/46 Тираж 704 Подписное

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

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

Производственно-полиграфическое г:,редприятие, r. Ужгород, ул. Проектная, 4

144 выход которого является признаком выдачи времени исполнения задания устройства, пятый выход блока синхронизации подключен к информационному входу ключа, выход которого подключен к .второму входу элемента ИЛИ,. выход которого подключен к входам установки в "0" всех накапливаюших сумматоров группы, вход задания режи5 ма работы устройства. подключен к входу включения ключа.