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

,ЯО 06 С ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР ПИ Е ИЗОБРЕТЕНИЯ К АВТОРСКОМ Д:ТЕЛЬСТ Бюл. 9 4ев, В.В.И.Роговой88.8)свидетелС 7/122идетельсС 06 С 7 ст,ство СССР 1984. во СССР 122, 1988(54) УСТРОЙСТВО ДЛЯНЫХ ЗАДАЧ ТЕОРИИ РА,(57) Изобретение от 2лительной технике и может быть исполь зовано для решения минимаксных задач теории расписаний. Цель изобретенияповьппение быстродействияУстройство содержит генератор 1, триггер 4, ш ключей 5-5 ш, ш трехвходовых элементов И 6-6 ш, шлп разделительных диодов 7, шп первых счетчиков 8, шип вторых счетчиков 9, шип двухвхо. довых элементов И 10, шп элементов НЕ 11, шп сигнальных индикаторов, п циФровых индикаторов. Повьппение быстродействия достигается за счет исключения аналоговых элементов. 1 илИзобретение относится к вычв литльной технике и может быть использовано для решения задач теории расписаний и других практических задач.Цель изобретения - повышение быстродействия.На чертеже показана функциональная схема устройства. 10Устройство содержит генератор 1, блок индикации состоящий из сигнальых индикаторов 21,., 2111 и цифровых индикаторов 3,3 триг, огер 4, ключ 5, трехвходовые элементы И, 15,7 первые счетчики 881,1 вторые счетчики 99 1, двухвхоуовые элементы И 10110, элемень НЕ 11, реер 111120Перед началом работы первые счетсики 9(.=1 ш 1=1п) устаавливаются в исходное состояние с; численно равное длительности выполнеНия х-й работы 1-м исполнителем, вто ые счетчики 10; и цифровые индикато 1 ы 3 обнуляются.Для триггера 4 исходным является 4 остояние логического нуля, а для электронных ключей 5 51 - сосояние с замкнутой исполнительнойепью.Устройство работает следующим образом.С выхода генератора импульс постуает на замкнутой цепи к юча 51 на , М ервьй вход трехвходового элементаИ, 6; (=1,2,т),на втором и третьемвходах которого присутствуют,сигналы логической единицы с инверторного 40выхода триггера 4 и элементов НЕ11Ц=1,2. . .и) . Трехвходовый элеф Юфмент И 6; открывается и импульсы отгенератора через разделительные диоды 7; поступают на счетные входы45первых счетчиков 8; . Одновременноимпульсы поступают на счетные входывторых счетчиков 9; . Счетчики 8,;вычитают; импульсы из первоначального содержимого, а счетчики 9" накапливают их сумму. При обнулениисчетчика 8 с минимальным содержимым,1что соответствует выбору работы минимальной длительности (мин С,) в математической постановке задачи, сигнал с его выхода поступает на входсоответствующего элемента НЕ 11; Для определенности в дальнеишем считаем, что это элемент НЕ 11,. На выходе элемента НЕ 11 нсигнал логической единицы исчезает и вследствие этого элемент И 6 закрывается. В эта же время сигнал обнуления с выхода счетчика 811 поступает на вход триггера 4 и переводит его в единичное состояние. Сигнал с прямого выхода триггера поступает на управляющие входы счетчиков 8, и на первый вход элемента И 10, на втором входе которого присутствовал сигнал с выхода счетчика 8 и.Счетчики 8;возвращаются в состояние, соответствующее значению 11 времени выполнения 1-й работы -м исполнителем. С выхода открытого элемента И 10 м сигнал поступает на управляющий вход второго счетчика 9 м. Содержимое счетчика 9, по цепи выдачи добавляется к содержимому счетчиков 8 к (К=2 ш), Одновременно передний Фронт сигнала с выхода счетчика 9 зажигает индикотор 2 Н , свидетельствуя таким образом о принятии к исполнению первой работы первым исполнителем. Содержимое счетчика 9 поступает также на первый вход цифрового индикатора 3 . Первый же импульс с выхода счетчика 9 поступает на управляющий вход ключа 5 , исполнительная цепь которого разрывается.Таким образом, в результате перво го шага решения определяются работа, принимаемая к исполнению, и ее исполнитель (отражаются индикатором 2, ), а также общее время задействования каждого исполнителя (отражается на цифровых индикаторах 3). При этом ввиду задействования исполнителя на одну работу, продолжительность остальных его работ увеличивается на величину ее длительности (выполне; ние любой последующей работы может быть начато лишь по завершению преды" дущей).На последующих шагах устройство Функционирует аналогично - определяется счетчик 8 с минимальным содержиЯмым и -я работа включается в расписание для выполнения 1-м исполнителем, что отражается на индикаторе 2 ицифровом индикаторе 3.По завершенйи решения результаты отражаются порядкомвыполнения работ (расписанием) на индикаторах 2, 2 1, общим временем заМ 11 фнятости исполнителя на цифровых индикаторах 3 3 и временем завершения комплекса работ (максимальноеСоставитель И.КалинкинРедактор И,Недолуженко Техред Л.Олийнык Корректор Т.Малец Заказ 8102/55 Тираж бб 8 ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР113035, Москва, Ж Раушская наб., д. 4/5 Производственно-издательский комбинат "Патент", г.ужгород, ул. Гагарина, 101 515329показание на цифровых индикаторах1 фф ь Формула изобретения5 Устройство для решения минимаксных задач теорйи расписаний, содержащее генератор импульсов, первую и вторую группы из ш и счетчиков (ш-коли 10 чество работ, и-количество исполнителей, шп), о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены триггер, ш-ключей,ш-трехвходовых элементов И, шп разделительных диодов, шип элементов НЕ, ш;и двухвходовых элементов И,причем вход пуска генератора является входом пуска устройства, выход генератора соединен с информационными входами всех ключей, выход д-го ключа ( 1,.;., ш) соединен с первьи входом а-го трехвходового элемента 51 6И,. выход которого соединен через соответствующий разделительный диод со счетными входами 3 -х счетчиков (3=1,.,и) первой и второй групп, выход признака обнуления 3 1-го счетчика первой группы соединен с первьм входом 1-го двухвходового элемента И, входом Зд-го элемента НЕ, входом установки триггера, прямой выход триггера соединен с установочньки входами всех счетчиков первой группы и с вторыми входами двухвходовых элементов И, инверсный выход триггера соединен с вторыми входами трехвходовых элементов И, выходы Ц-х элементов НЕ (ь. 1п)соединены с третьим входом 3-го трехвходового ,элемента И, выход 1-го двухвходового элемента И соединен с входом установки 1-го счетчика второй группы, выходы счетчика второй группы являются. ,вйходами результата устройства.