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

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

Цель изобретения - повышение быстродействия.

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

| Устройство содержит генератор 1, блок индикации состоящий из сигнальных индикаторов 2h ,..., 2тл и цифровых индикаторов 3,,...,3П, триг- rjep 4,-ключ 5, трехвходовые элементы Hk Р4,...,бт, разделительные диоды 74 .. ,7т , первые счетчики 8„,...,8т„ вторые счетчики 9„,...,9mn, двухвхо- 4овые элементы И 10ц ,...,10mn элемен ы НЕ 11М ,..., 11mn.

Перед началом работы первые счет- ики 9jj(,...,m, ,...,n) уста- н|авливаются в исходное состояние tjj , г|исленно равное длительности выполне- Ция i-й работы j-м исполнителем, вто- рые счетчики 10j- и цифровые индикаторы 3j обнуляются.

Для триггера 4 исходным является Достояние логического нуля, а для флектронных ключей 5, ,... 5W - сое- |ояние с замкнутой исполнительной йепью,

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

С выхода генератора импульс посту- jiaer на замкнутой цепи ключа 5j на йервый вход трехвходового элементам , 6; (,2,..,т),на втором и третьем входах которого присутствуют.сигналы логической единицы с инверторного выхода триггера 4 и элементов НЕ 1 lij (j 1 ,2, ... ,п) . Трехвходовый элемент И 6 открывается и импульсы от генератора через разделительные диоды поступают на счетные входы первых счетчиков 8,-: . Одновременно импульсы поступают на счетные входы вторых счетчиков 9,-j . Счетчики 8;; вычитают .- импульсы из первоначапь

ного содержимого, а счетчики накапливают их сумму. При обнулении счетчика с минимальным содержимым, что соответствует выбору работы минимальной длительности (мин t) в математической постановке задачи, сигнал с его выхода поступает на вход соответствующего элемента НЕ . Для определенности в дальнейшем считаем, что это элемент НЕ 11И. На

5 0

5

о

0

5

0

5

выходе элемента НЕ 11() сигнал логической единицы исчезает и вследствие этого элемент И 61(закрывается. В это же время сигнал обнуления с выхода счетчика 8 поступает на вход триггера 4 и переводит его в единичное состояние. Сигнал с прямого выхода триггера поступает на управляющие входы счетчиков 8; и на первый вход элемента И 10 , на втором входе которого присутствовал сигнал с выхода счетчика 8,.Счетчики 8;j возвращаются в состояние, соответствующее значению времени выполнения i-й работы j-м исполнителем. С выхода открытого элемента И 10,,, сигнал поступает на управляющий вход второго счетчика 9,{. Содержимое счетчика 9 по цепи выдачи добавляется к содержимому счетчиков 8К (,...,m). Одновременно передний фронт сигнала с выхода счетчика 9 зажигает инди- котор 2 , свидетельствуя таким образом о принятии к исполнению первой работы первым исполнителем. Содержимое счетчика 9 поступает также на первый вход цифрового индикатора 3. Первый же импульс с выхода счетчика 9 поступает на управляющий вход ключа 5i , исполнительная цепь которого разрывается.

Таким образом, в результате перво-1 го шага решения определяются работа, принимаемая к исполнению, и ее исполнитель (отражаются индикатором 2-:), а также общее время задействования каждого исполнителя (отражается на цифровых индикаторах 3 j). При этом ввиду задействования исполнителя на одну работу, продолжительность остальных его работ увеличивается на величину ее длительности (выполнет ние любой последующей работы может быть начато лишь по завершению предыдущей) .

На последующих шагах устройство функционирует аналогично - определяется счетчик 8 с минимальным содержимым и i-я работа включается в расписание для выполнения j-м исполнителем, что отражается на индикаторе 2.-и цифровом индикаторе 3:.По завершении решения результаты отражаются порядком выполнения работ (расписанием) на индикаторах 2,,,..., 2т, общим временем занятости исполнителя на цифровых индикаторах 3. ,..., Зп и временем завершения комплекса работ (максимальное

показание на цифровых индикаторах

Ч

V

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

Устройство для решения минимаксных задач теорий расписаний, содержащее генератор импульсов, первую и вторую группы из m«n счетчиков (т-коли- чество работ, n-количество исполнителей, ), отличающееся тем, что, с целью повышения быстродействия, в него введены триггер, т-ключей,т-трехвходовых элементов И, m«n разделительных диодов, nwn эле- ментов НЕ, m-.n двухвходовых элемен-. тов И,причем вход пуска генератора является входом пуска устройства, выИ, выход которого соединен через соот ветствующий разделительный диод со счетными входами j i-x счетчиков (.«.n) первой и второй групп, выход признака обнуления j1-го счетчика первой группы соединен с первым входом j1-го двухвходового элемента И, входом ji-ro элемента НЕ, входом установки триггера, прямой выход триггера соединен с установочными входами всех счетчиков первой группы и с вторыми входами двухвходовых элементов И, инверсный выход триггера соединен с вторыми входами трех- входовых элементов И, выходы ij-x элементов НЕ (,...,п)соединены с третьим входом j-ro трехвходового .элемента И, выход ji-ro двухвходового

10

15

ход генератора соединен с информацион-20 элемента И соединен с входом установ- ными входами всех ключей, выход 1-го ки ji-ro счетчика второй группы, вы- ключа (,..., m) соединен с первым входом i-ro трехвходового элемента

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

х 532951

И, выход которого соединен через соответствующий разделительный диод со счетными входами j i-x счетчиков (.«.n) первой и второй групп, выход признака обнуления j1-го счетчика первой группы соединен с первым входом j1-го двухвходового элемента И, входом ji-ro элемента НЕ, входом установки триггера, прямой выход триггера соединен с установочными входами всех счетчиков первой группы и с вторыми входами двухвходовых элементов И, инверсный выход триггера соединен с вторыми входами трех- входовых элементов И, выходы ij-x элементов НЕ (,...,п)соединены с третьим входом j-ro трехвходового .элемента И, выход ji-ro двухвходового

10

15

элемента И соединен с входом установ- ки ji-ro счетчика второй группы, вы-

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

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