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

 

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

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

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

РЕСПУБЛИК (19) (111

А1 (51) 4. G 06 G 7 122

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

К А BTOPCHOMV СВИД=ТЕЛЬСТВУ

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (21) 4428916/24-24 (22) 23.05.88 (46) 30.12.89. Бюл. М 48 (72) О.Г.Алексеев, В.В.Калист, А.Н.Мардас и Л.И.Роговой (53) 681.333 (088.8) (56) Авторское свидетельство СССР У 1078441, G 06 G 7/122, 1984.

Авторское свидетельство СССР

У 1249544, кл. С 06 G 7/122, 1988. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ МИНИМАКС.

НЬИ ЗАДАЧ ТЕОРИИ РАСПИСАНИЙ ,(57) Изобретение относится к вычис2 лительной технике и может быть использовано для решения минимаксных задач теории расписаний. Цель изобретенияповьппение быстродействия ° Устройство содержит генератор 1, триггер 4, m ключей 5-5m m трехвходовых элементов И 6-6ш, шлп разделительных диодов 7, шхп первых счетчиков 8, lm n вторых счетчиков 9, m n двухвхо довых элементов И 10, m>n элементов

НЕ 11, m n сигнальных индикаторов, п циФровых индикаторов. Повьппение быстродействия достигается sa счет исключения аналоговых элементов. 1ил., \

1532951

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

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

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

Устройство содержит генератор 1, блок индикации состоящий из сигнальых индикаторов 2>,..., 2„„„ и цифровых индикаторов 3,,...,3, тригr åð 4, ключ 5, трехвходовые элементы И, 15

6,,...,6, разделительные диоды ю о ° ,7„,, первые счетчики 8„,...,8 „, вторые счетчики 9„,...,9 „, двухвхоу овые элементы И 10,...,10,„„ элемен ы НЕ 1 1, р . ° . р 1 1 р„, 20

Перед началом работы первые счет ики 9 ;(=1,...,m, )=1,...,n) устанавливаются в исходное состояние t °, « исленно равное длительности выполнения i-й работы j-м исполнителем, вто- 25 алые счетчики 10; и цифровые индикаторы 3 обнуляются.

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

1 ! епью.

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

С выхода генератора импульс посту35 ает на замкнутой цепи ключа 5> на

1первьй вход трехвходового элементаИ, 6; (i=1,2,...m),íà втором и третьем входах которого присутствуют,сигналы логической единицы с инверторного 40 выхода триггера 4 и элементов НЕ

11„ (д=1,2,...,n) . Трехвходовый элемент И 6; открывается и импульсы от генератора через разделительные диоды 7; поступают на счетные входы

45 первых счетчиков 8; . Одновременно импульсы поступают на счетные входы вторых счетчиков 9; . Счетчики 8;; вычитают: импульсы из первоначального содержимого, а счетчики 9„" накапливают их сумму. При обнулении счетчика 8„ с минимальным содержимым, что соответствует выбору работы минимальной длительности (мин t ) в математической постановке задачи, сигнал с его выхода поступает на вход соответствующего элемента НЕ 11;

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

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

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

Составитель И.Калинкин

Редактор И.Недолуженко Техред Л.Олийнык Корректор Т.Малец

Заказ 8102/55 Тираж 668 Подписное

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

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

Производственно-издательский комбинат "Патент", r.ужгород, ул. Гагарина, 101

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

4„в ° ° ° э 4„ °

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

Устройство для решения минимаксных задач теорйи расписаний, содержащее генератор импульсов, первую и вторую группы из m n счетчиков (m-коли10 чество работ, и-количество исполнителей, m)n) отличающееся тем, что, с целью повышения быстродействия, в него введены триггер, ш-ключей,m-трехвходовых элементов И, шп разделительных диодов, пап элементов НЕ, m;n двухвходовых элементов И,причем вход пуска генератора является входом пуска устройства, выход генератора соединен с информацион-2О ными входами всех ключей, выход i-го ключа (i 1,.;., m) соединен с первьи входом i-ro трехвходового элемента

51 6

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

И, входом j i-го элемента НЕ, входом установки триггера, прямой выход триггера соединен с установочньаки входами всех счетчиков первой группы и с вторыми входами пвухвходовых элементов И, инверсный выход триггера соединен с вторыми входами трехвходовых элементов И, выходы ij-x элементов НЕ (i 1,...,ï)ñîåäèíåíû с третьим входом j-ro трехвходового ,элемента И, выход ji-го двухвходового элемента И соединен с входом установки ji-Fo счетчика второй группы, выходы счетчика второй группы являются.

;вйходами результата устройства.