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

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

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

На фиг, I представлена функциональная схема устройства; на фиг. 2- временная диаграмма работы блока синхронизации.

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

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

Устройство работает следуюпцда образом.

Пусть в рамках каждого из трех различных технологических процессов необходимо выполнить по три задания с временем выполнения заданий 5,3,7 (единиц времени) для первого процесса, 8,1,3 - для второго и 4,6,2 - для третьего силами двух () однотипных исполнителей (например, ЭёМ) При этом задания различных технологических процессов нельзя вып.олнять одновременн9. Перед началом работы времени исполнения заданий в рамках каждого технологического процесса упорядочиваются по невозрастанию времени их исполнения и заносятся в блок 3 памяти таким образом, что по адресам соответственно 0,l,.,,j,8 располагаются числа 7,5,3; 8,3,1 и

6,4,2. Тем самым одновременно каждому заданию присваивается номер, равный адресу, по которому в блок 3

памяти записано время исполнения задания. Причем количество заданий в каждом из технологических процес- сой должно быть одинаковым. В противном случае технологические процессы

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

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

предусмотренную временной диаграммой его работы.

Импульсный сигнал единичного уро - ня появляется на выходе 18 блока I. При этом из блока 3 памяти считьюается код числа 7 (максимальное по длительности задание первого технологического процесса), Через время Т1, достаточное для выбора числа 7 из блока 3 памяти, блок I синхронизации формирует импульс на выходе 19, При этом на первом выходе 16 формируется признак назначения задания первому исполнителю и код числа 7 суммируется с содерж1 мым первого накапливающего сумматора 4 (поскольку последний хранит наименьший код и обладает наибольшим приоритетом). Через время Т2 достаточное для записи информации в сумматор 4 и обра-ботки исполнителем признака назн - чения задания, блок 1 синхронизации сбрасьшает сигналы на выходах 8 и 19 и формирует импульсный сигнал единичного уровня на выходе 20, при

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

сьтается сигнал на выходе 20 (после назначения третьей работы второму исполнителю) , блок 1 синхронизации формирует импульсный сигнал единичного уровня на выходе 21. При этом устройство выдаст исполнителям признак выдачи максимального времени исполнения назначенных заданий и величину времени исполнения заданий на выход 15 устройства.

Через вр емя ТА, достаточное для обработки исполнителями признака выдачи времени исполнения, блок 1 синхронизации сбрасьшает сигнал на выходе 21 и формирует импульсный сигнал единичного уровня на выходе 22. При этом обнуляются все накапливающи сумматоры А группы-(в том случае, если нет запрета на одновременность исполнения заданий различных технологических процессов, то перед началом работы подают импульсный сигнал единичного уровня на вход 13 задания режима работы устройства, при этом размыкается информационная цепь ключа 5 jи по сигналу с выхода 22 блока 1 обнуление накапливающих сумматоров 4 не происходит). Через.время Т5, достаточное для установки в ноль сумматоров А, блок 1 синхрониза1у1И снимает сигнал с выхода 22 и формирует импульсный сигнал единичного уровня на выходе 18,

Далее работа устройства повторяется. После того, как распределены все задания, происходит переполнение счетчика 2, Сигнал переполнения останавливает блок 1 синхронизации и поступает на выход 17 устройства в качестве признака окончания работы устройства,

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

Блок 3 памяти может быть вьшолнен в виде матрицы регистров.

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

Устройство для решения задач теории расписаний, содержащее блок па

ЛЛП07

мяти, блок выбора максимального кода, группу из Р накапливающих сумматоров, где Р - количество однотипных исполнителей, между которыми рас- .пределяются задания, и блок синхронизации, вход пуска которого является входом пуска устройства, отличающееся тем, что, с целью Q раскгпрения функциональных возможностей устройства за счет решения задачи минимизации суммарного времени исполнения технологически зависимых множеств работ, в него введены эле- 15 мент ИЛИ, счетчик, ключ, блок выбора минимального кода, блок приоритетов, группа из Р элементов И и коммутатор, причем вход начальной установки устройства подключен к входу отключения 20 ключа, к первому входу элемента ИЛИ и к входу установки в О счетчика, информационный выход которого является выходом номера задания устройства и подключен к адресному входу бло- 25 ка памяти, выход которого подключен к входам слагаемого всех накапливающих сумматоров группы, выход К-го накапливаюв1его сумматора группы (К 1 , ,,,, Р) подключен к К-м ин- 30 формационным входам коммутатора, блока выбора максимального кода и блока выбора минимального кода, К-й выход позиции минимального кода которого подключен к К-му входу блока 25 приоритетов, К-й выход позиции сигнала с наибольшим приоритетом которого подключен к первому входу К-го элемента И группы, выход которого является выходом признака назначе- 4Q ния задания К-му исполнителю устройства и подключен к входу признака записи К-го накапливающего сумматора группы, К-й выход позиции максимального кода блока выбора максимального 45 кода подключен к К-му управляющему входу коммутатора, выход которого является выходом назначения времени исполнения задания устройства, первый выход блока синхронизации подключен к входу признака чтения блока памяти, второй выход блока синхронизации подключен к вторым входам всех элементов И группы, третий вйход блока синхронизации подключен к вы- сс читающему входу счетчика, выход признака переполнения которого является выходом признака окончания работы устройства и подключен к входу останова блока синхронизации, четвертый

50

14430076

выход которого является призйаком вы- выход которого подключе к входям дачи времени исполнения задания уст- установки в О всех накапливающих ройства, пятый выход блока синхронизации подключен к информационному

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

выход которого подключе к входям установки в О всех накапливающих

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

Изобретение относится к вычислительной технике, может быть использовано для решения задач теории расписаний и позволяет минимизировать суммарное время исполнения технологически зависимых заданий. Устройство содержит блок 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 САР

входу ключа, выход которого подключен к .второму входу элемента ИЖ,

ду включения ключа.