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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИК И) 006 07 ОПИСАНИЕ ИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ фА т С,";4 Г. Г, Гершели бло- служи- бслу- литель ОСУДАРСТВЕННЫЙ НОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЦТИ(56) 1.Авторское свидетельство СССРР 690505, кл. 0 06 О 7/122, 1978,2, Авторское свидетельство СССРМ 920752, кл, О 06 0 7/122, 1980(прототип),3. Ба 1 цС Я. 1. БсЬейц 11 па Со и 1 п 1 п 1 ге СЬе пцщЬег оГ 1 аСе )оЬя яеС-црапй ргосеяя 1 пЕ. С 1 иея аге цпсегСахп. -(54)(57) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧТЕОРИИ РАСПИСАНИЙ, содержащее генератор импульсон и распределитель импульсов, первый вход которого подключен к выходу генератора импульсов,о т л и ч а ю щ е е с я тем, что,с целью расширения класса решаемыХзадач, оно содержит дополнительноереле, блок определения длительностиобслуживания, блок выбора максимума,включающий две группы реле, элементыИ узел дифференцирования, линию задержки, индикаторы, нагруэочный резистор и разделительные диоды,причем одни выводы обмоток реле первой группы и первые входы элементовИ через переключающие контакты дополнительного реле соединены с выходами распределителя импульсов, выходузла дифференцирования блока выборамаксимума соединен с одним выводомобмотки дополнительного реле, свторым входом распределителя импульсов, с входом линии задержки и свторыми входами элементон И, выходы которых подключены к одним выводам обмоток реле второй группы,другие выводы обмоток реле первойи второй групп подключены к входузапуска устройства и выходу узла дифференцирования, один вывод нагруэочного резистора соединен с шиной нулевого потенциала, другой вывод - с входом узла дифференцирования, блок определения длительности обслуживания включает две группы реле, потенциометр,узел умножения, узел извлечения квадратного корня, два сумматора и схему сравнения, причем одни выводы обмоток реле первой и второй групп блока определения длительности обслуживания через переключающие контакты дополнительного реле соединены с ныхсдом распределителя импульсов, другие выводы обмоток реле первой группы блока определения длительности обслуживания подключены к выходу узла дифференцирования и к входу запуска устройства, входы задания директивного времени устрой . ства через соответствующие переключающие контакты реле второй группы блока выбора максимума и переключающие контакты реле второй группы блока определения длительйости обслужинания соединены с пер.вым входом схемы сравнения блока определения длительности обслуживания, входы заданиядисперсии времени обслуживания устройства через соответствующие переключающие контакты реле перной и второй групп блока выбора максимума и через соответстнующие пересекающие контакты реле первой группы подключены к входу первого сумматора, выход которого подключен к первому входу узла умножения ка определения длительности об вания, входы задания времени о живания устройства через разде ные диоды, соответствующие переключающие контакты реле первой и второй групп блока выбора максимума, через соответствующие переключающие контакты реле первой группы1078441 блока определения длительностиобслуживания и соответствующий контакт дополнительного реле подключены к входу второго сумматора блока определения длительности обслуживания и к вхоцу узла дифференцирования блока выбора максимума,подвижный контакт потенциометра подключен к второму входу узла умножения,выход которого соединен с входомузла извлечения квацратного корня,Изобретение относится к зычислительной технике и может быть использовано для Определения максимального числа требований, обслуженных одним приборам в заданныедирективные сроки при условии, чтодлительность обслуживания требований носит вероятностный характер.Известно аналоговое устройстводля решения задач теории расписа-,ний, содержащее два блока выборааксимума, входы которых являютсявходами устройства, блок запоминания, коммутатор и блок сравнения.Входы которого соединены с выходами блоков выбора максимума выходблока сравнения через коммутаторподключен к блоку запоминания. выход которого является выходом устройства 1,Наиболее близким к предлагаемомупо технической сущности являетсяаналоговое устройство для минимиза".ии длительности обработки изделийв конвейерной системе, содержащеегенератор импульсов., выходы которого соединены соответственно свходом распределителя импульсов ичерез эа.ык ающий контакт реле суправ.51 ю 1 цей ОбмОткОЙ ша 1 ОВОгО искаеля, механически связанного с подгижь.;ми контактами двух делителейнапряжения, два инвертора,два сумматора, поляризованное реле, блок памяти и блок Выбора минимального сигнала, входь 1 которого подключены квыходам делителей напряжения сботВетственно, а выход соединен спервым вхоцом первого сумматора,второй вход которого является управляю 1 цим входом устройства, первыйвход второго сумматора подключен квыходу первого делителя напряжения,выход второго делителя напряжевиячерез инвертор сОединен с вторымвходом второго сумматора, выход которо 1 о подключен к Управляющеи обмоке поляризованно 1 с реле выход 51 ер-" выход которого подключен к соответствующему переключающему контактудополнительного реле, выход второгосумматора подключен к второму входу схемы сравнения, выход которойподключен к другому выводу обмотки дополнительного реле и к входураспределителя импульсов, входыиндикаторов подключены к соответствующим переключающим контактам релевторой группы блока выбора максимума,. вого сумматора через переключающийконтакт поляризованного реле соединен с выходом и входом второго инвертора, выход которого соединен синформационным входом блока памяти,управляющие входы которого подключены к выходам распределителя импульсов, соответственно, выходы блока памяти являются выходами устройства 21 .Однако устройства не позволяютрешать задачи определения максималького числа требований обслуженныходним прибором, в заданные (директивные сроки, если длительностьобслуживания требований носит вероятностный характер,Цель изобретения - расширениекласса решаемых задач. Поставленная цель достигается тем, что в устройство для решения задач теории расписаний, содержащее генератор импульсов и распределитель импульсов, первый вход которого подключен к выходу генератора импульсов, введены дополнительное реле, блок определения длительности обслуживания, блок выбора максимума, включающий две группы реле,элементы И, узел дифференцирования, линию задержки, индикаторы,нагрузочный резистор и разделительные диоды, причем одни выводы обмоток реле первой группы реле и первые входы элементов И через переключающие контакты дополнительногореле соединены с выходами разделителя импульсов, выходы узла дифференцирования блока выбора максимума соединен с ОдниФ выводом обмотки дополнительного реле, с вторым входом распределителя импульсов, с входом линии задержки и свторыми входами элементов И, выходы которых подключены к одним выводам обмоток реле второй группы,другие выводы обмоток реле первойи второй групп подключены к входузапуска устройства и ныходу узла дифференцирования, один вывод нагрузочного резистора соединен с шиной нулевого потенциала, другой вывод - с входом узла дифференцирования, блок определения длительности обслуживания включает дне группы реле, потенциометр, узел умножения, узел извлечения квадрат ного корня, два сумматора и схему сравнения, причем одни выводы об моток реле первой и второй групп блока определения длительности обслуживания через переключающие контакты дополнительного реле соединены с выходом распределителя им пульсов, другие выводы обмоток реле первой группы блока определения длительности обслуживания подключены к выходу узла дифференцирования и к входу запуска устройства, входы 20 задания директивного времени устройства через соответствующие переключающие контакты реле второй группы блока ныбора максимума и переключающие контакты реле второй группы 25 блока определения длительности обслуживания соединены с первым входом схемы сравнения блока определения длительности обслуживания, входы задания дисперсии времени обслуживания устройства через соответствующие переключающие контакты реле первой и второй групп блока выбора максимума и через соответствующие переключающие контакты реле первой группы подключены к входу первого сумматора, выход которого подключен к первому входу узла умножения блока определения длительности обслуживания, входы задания времени обслуживания устройства через разделительные диоды, соответствующие переключающие контакты реле первой и второй групп блока выбора максимума и соответствующие переключающие контакты реле первой группы блока определения длительности обслуживания, и соответствующий контакт дополнительного реле подключены к входу второго сумматора блока определения длительности обслуживания и к входу узла дифференцирования блока выбора максимума, подвижный контакт потенциометра подключен к второму входу узла умножения, выход которого соединен с 55 входом узла извлечения квадратного корня, выход которого подключен к соответствующему переключающему контакту дополнительного реле, выход второго сумматора подключен к 60 второму входу схемы сравнения, ныход которой подключен к другому выводу обмотки дополнительного реле и к входу распределителя импульсов, входы индикаторов подключены к 65 соответствующим переключающим контактам реле второй группы блока выбора максимума.На чертеже представлена структурная схема устройстна для решениязадач теории расписаний,Устройство содержит генератор 1импульсов, распределитель 2 импульсов, дополнительное реле 3 с контактами 3 -3", блок 4 выбора мак-1симумае блок 5 определения длительности обслуживания. Блок 4 вы 15 орамаксимума содержит разделительныедиоды 61 в би, пеРвУю гРееппУ Реле71 -7 с контактами 7, -7 ее, 7,-7,7,"-7", элементы И 81-8 е вторую группу реле 9 -9 с контактами 9,-9,9" , - 9 - 9 -9", индикаторы 10 е -1011,узел 11 дифФеренцированиялинию 12задержки, нагрузочный резистор 13.Блок 5 определения длительностиобслуживания содержит вторую группуреле 141 -14 е с контактами 14, -14,второй сумматор 15, схему 16 сравнения, первую группу реле 171 -17 сконтактами 171 -17 е 17-17 е потенциометр 18, первый сумматор 19,блок 20 умножения и блок 21 извлечения квадратного корня,Входами устройства являются входы 22,-22 задания директивного времени, .входы 231 -23 задания дисперсиивремени обслуж 11 вания, входы 241-24задания времени обслуживания и вход25 запуска устройства.В основу работы устройства положен алгоритм 3),Первый шаг.Упорядочить требование в порядкенеубывания директивных сроков выполнениягде ) - номер требовайия, обслужи,ваемого К-м по порядку.Вычислить , (р)11где(Р 11) - функция обратная функ%ни Лапласа, т,е.lПринять 1 = 0 и Тгде 1; - множество индексов требований, включенных в расписание до п включительно,Второй шаг,Проверка т = и, если нет, то кшагу 3, а если да, то закончено формирование оптимальной последователь.ности,Третий шаг,Сформировать ; = 1, 11 Ягде И 3 - множество индексов требований,Четвертый шаг,Проверка условия (Т).)(к исключить К . в ; Т и перейти к цагу 2.После окончания работы алгоритмамножество Т.л будет представлять собой максимальное число требований,обслуженных одним прибором в заданные директивные сроки,енератор 1 импульсов предназначен дпя получения последовательноститактовых импульсов : подключен кпервому входу распределителя 2 импульсов, выходь которого через контакть 1 3-3 реле 3 подключаются либо к входам блоков :, либо к входамблока 5, Переключающий контакт 3реле 3 подключает выход блока 1 извлечения квадратного корня к второму сумматору 15,Устройство работает следуютим образом.Генератор 1 импульсов вьрабаты.вае . тактовые импульсы, которые ерез первый вход подаются на распределитель 2 кмпульсов с выходов ко.торого через гереключаюцие контакть3 -Зп реле 3 поступают либо на. входблока 4, либо на вход блока 5,Положение контактов реле 3 определяетсяуправляющими сигналами блоков 4 и 5и сигналом с входа 25, Блок 5 предназначен для проверки условия (У.).,В блоке 5потенциометра 18 снимает.;я напряжение, пропорциональноеподается на второй вход блэка 20умножения Импульсы опрос-: с распределителя 2 последовательно поступавт ка первую к вторую группы релел -,; лкть которых замыкаютс;яздк: .тчают напряжение: В ; с вхо- Я)( вторсл.у 15 обеспечивая образование суммв;: -- "днапряжение Пб: с входа 23 к первому сумматору 19, напря"жение П с, входа 22 на первый вход зсхемы 16 саавнь."-кя На выходе перзого сумма.ора 19 образуется суммарО1 котоая в узле 20,леньааетс я на (:, а узел 21 извлекает квад Оратный корень кз произведения. Напряженке с узла 21 через контакт 3"поступает ьа:з:,с,г вссорсго с мматора15, г-;е ссущес;твля.ся сложение ссуиккс.к; Го. .е.-вое напряжение 65 нсм лучае . цагу 5 где ."и - математкчс.ское ожидание выполнения требования; с; - дисперсия времени вылполнения требования.Пятый шаг.Выбрать индекс К таким, что с выхода сумматора 15 подается на схему 16 сравнения и сравнивается со значением С,) . После окончания действия очередного ,)-.го импульса опроса контакты реле 17 остаются в замкнутом положении (напряжения Сп"Г; поданы на второй сумматор 15, контакты 17 размыкаются импульсом с узла 11 дифференцирования блока 4 и сигналом запуск устрой ства с входа 25 в начале рецения задачи.После первого импульса опроса на вторую и первую схемы 16 сравненкя поступят соответственно Сз и (р" (ьпс )Пусть( (; П б) ", Это означает, что псрвое требование не будет обслужено в заданный директивный срок тсгда схема 16 сравнения выдает управляющий импульс на реле 3, кон-акты которого подключат распределитель 2 импульсов к блоку 4 выбсра макскмума и подсоединят выход узла 21 умножения к входу дифференцирующей схемы 11 блока 5, роме того, управляющкй кмгульс поступает на второк вход распределителя 2 импуль соь для возврата его в ксходное положение, Если В, 1 и,+ (Ь Пс )то схема 16 сравнения сигнал не выдаст и после второго импульса опроса к входу второго сумматора 15 через контакты 1717 и 17 17" будут подключены напряжения ц+ ( +2.(1 (Я+И ). Сумма этих напряжений будет сравниваться уже с П2 Если указанная сумма больце то1 а схема 16 выдаст сигнал, в противном случае сигнал не формируется и т .д .Блок 4 вь 1 бора максимума предназнатен для нахождения к-цзгочки для которой выполняется условие (2). В исходном положении контакты реле 7, и 9 подключают приложен-ные к разделительным диодам бвходные напряжения Пс входа 24Внапряжения 5 с входа 23 к соответствующим входам блока 5. Через контакты реле 9 напряжения ц с входа 22 поступают на входы блока 5. С рас. предслителя 2 импульсов поочередно поступают импульсы опроса на реле 7, и на вторые входы элементов И 8. Под действием импульсов опроса кон10 такты 7, + 7 и 7" + 7 поочередно размыкаются и отключают входные напряжения 0 и И от входов 23 и 24 блока 5, а следовательно и от входа узла 11 дифференцирования, Если импульс опроса подан на группу, для которой выполняется условие (2),то вследствие размыкания контактов реле 7 (7 и 7) напряжение 0 К будет отключено от дифференцирующей схемы 11, на ее входе возникает скачок напряжения, равный разности междуи самым большим из неотключенных напряжений, Схема 11 сформирует импульс, который поступает на первые входы элементов И 84 в 8, иэ которых 15 сработает 8 , Импульс с элемента .И 8 переключит реле 9 к, контакты которого отключат напряжения 06 и Щ от соответствующих входов блока 5, В исходное положение контакты реле 9 возвратятся лишь при подаче сигнала "Запуск устройства" с входа 25. Одновременно контакты реле 9 подключат напряжение к индикатору 10 , который будет сиг. 25 нализировать об этом до конца решения задачи. Кроме того, импульс с дифференцирующей схемы 11 через линию 12 задержки возвращает контакты реле 71-7 в исходное положение и через реле 3 подключает выходы распределителя 2 к блоку 5, выход блока 21 умножения подключают к второму сумматору 15, контакты реле 171 -17 я возвращает в исходное положение,Если условие (2) выполняется для двух цепочек (Е,щ), то при отключении контактов реле 7 (7 и 7" ) первой группы скачка на выходе узла 11 не будет, т.е. к узлу 11 дифферен О цирования приложено напряжениеОчередным импульсом отключится ц, на входе узла 11 возникнет скачок напряжения и выходной импульс с узла 11 поступит одновременно с импульсом опроса на входэлемента И 8 щ, сработает реле 9 инапряжения Пщ, 1 и 01 будут окон.чательно отключены от входов блока 5,При отключении немаксимальногонапряжения скачка напряжения на вхо,де узла 11 дифференцирования не происходит,Устройство в целом работаетследующим образом,Перед началом решения сигнал"Запуск устройства" с входа 25 приводит схему в исходное состояние иначинается поступление импульсовопроса, Пусть очередной импульс поступит на реле 17 и 14. К первомувходу схемы 16 сравнения приложено напряжение БЗ , а к второмувходу Уэ . Если У ) У, т,е, требование с номером я не будет обслужено в директивный срок й, схема16 выдает импульс, который приведетк осуществлению ранее описанныхдействий, т.е. блок 4 выбора максимума отключит от входов блока 6 напряжения Пщ , иц и .1 С) , а импульсИд фс узла 11 дифференцирования возвратит схему в исходное состояние,кроме реле 91 -9 ь. Процесс решения задачи заканчивается тогда, когда отсутствует сигнал на выходе схемы 16 сравнения, при подаче импульса опроса на реле 17, и 14, вследствие чего прекращается подача импульсов с распределителя 2, Требования, номера которых не зафиксированы индикаторами 10 - 10, входят в оптимальную последовательность.Таким образом, благодаря введению дополнительных элементов предла гаемое устройство позволяет расширить класс решаемых задач