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

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

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

УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ ТЕОРИИ РАСПИСАНИЙ, содержащее генератор импульсов и распределитель импульсов , первый вход которого подключен к выходу генератора импульсов, отличающееся тем, что, с целью расширения класса решаемых задач, оно содержит дополнительное реле, блок определения длительности обслуживания, блок выбора максимума, включающий две группы реле, элементы И узел дифференцирования, линию задержки, индикаторы, нагрузочный резистор и разделительные диоды,причем одни выводы обмоток реле первой группы и первые входы элементов И через переключающие контакты дополнительного реле соединены с выходами распределителя импульсов,выход узла дифференцирования блока выбора максимума соединен с одним выводом обмотки дополнительного реле, с вторым входом распределителя импульсов, с входом линии задержки и с вторыгли входами элементов И, выходы которых подключены к одним выводам обмоток реле второй группы, другие выводы обмоток реле первой и второй групп подключены ,к входу запуска устройства и выходу узла дифференцирования, один вывод нагрузочного резистора соединен с шиной нулевого потенциала, другой вывод - с входом узла дифференцирования, блок определения длительности обслуживания включает две группы реле, потенциометр,узел умножения, узел извлечения квадратного корня, два сумматора и схему сравнения, причем одни выводы обмоток реле первой и второй групп блока определения длительности обслуживания через переключающие контакты дополнительного реле соединены с выходом распределителя импульсов, другие выводы обмоток реле первой группы блока определения длительности обслуживания подключены к (Л выходу узла дифференцирования и к входу запуска устройства, входы задания директивного времени устройства через соответствующие переключающие контакты реле второй группы блока выбора максимума и переключающие контакты реле второй группы блока определения длительности обслуживания соединены с пер .вым входом cxeNK сравнения блока определения длительности обслужи00 4 4 вания, входы задания ,, дисперсии времени обслуживания устройства через соответствующие переключающие контакты реле первой и второй групп блока выбора максимума и через соответствующие пересекающие контакты реле первой группы подключены к входу первого сумматора, выход которого подключен к первому входу узла умножения блока определения длительности обслуживания, входы задания времени обслуживания устройства через разделитель ные диоды, соответствующие переключающие контакты реле первой и второй групп блока выбора максиму.ма, через соответствующие переклю(чающие контакты реле первой группы

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

Известно аналоговое устройство для решения задач теории расписа-. ВИЙ, содержащее два блока выбора чаксимума, входы которых являются входами устройства, блок запоминания, коммутатор и блок сравнения,входы которого соединены с выходами блоков выбора максимумаf выход блока сравнения через коммутатор подключен к блоку запоминания выход которого является выходом устройства i „

Наиболее близким к предлагаемому по технической сущности является аналоговое устройство для минимизаГИи длительности обработки изделий в конвейерной системер содержащее генератор импульсов, выходы которого соединены соответственно с входом распределителя импульсов и через йаг-Та чающкй контакт реле с упраау;нющей обмоткой шагового искателк. механически связанного с подBvnKi-ib «5 контактами двух делителей напряжения, два инвертора,два сумма тора г поляризованноереле, блок памяти и блок выбора, минимального сигнала, входы которого подключены к зьжодам делителей напряжения соответственно, а выход соединен с первым входом первого сумг атора, второй вход гссгорого является управляющим входом устройства, первый вход второго CiiviMaTopa подключен к выходу первого делит-зля напряжения, выход второго делителя напряжения через инвертор соедийен с вторым входом второго cyi-a-iaTopaj. виход которого подключен к управляющей обмо ке поляркзованкогс реле, выход первого сумматора через переключающий контакт поляризованного реле соединен с выходом и входом второго инвертора, выход которого соединен с информационным входом блока памяти управляющие входы которого подключены к выходам распределителя импульсов ,соответственно, выходы блока памяти являются выходами устройства 2 .

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

Цель изобретения - расширение класса решаемых задач.

Поставленная цель достигается тем, что в устройство для решения задач теор1-1И расписаний, содержащее генератор иг.шульсов и распределитель импульсов, первый вход которого подключен к выходу генератора импульсов, введены дополнительное реле р блок определения длительности обслуживания, блок выбора максимума, включающий две группы реле, элементы И, узел дифференцирования, линию задержки, индикаторы, нагрузочный резистор и разделительные диоды, причем одни выводы обмоток реле первой группы реле и первые входы элементов И через переключающие контакты дополнительного реле соединены с выходами разделителя импульсов, выходы узла дифференцирования блока выбора максимума соединен с OAHHN выводом обмотки- дополнительного реле, с вторым входом распределителя импульсов, с входом линии задержки и с вторыми входами элементов И, выходы которых подключены к одним выводам обмоток реле второй группы, другие выводы обмоток реле первой и второй групп подключены к входу запуска устройства, и выходу узла дифференцирования, один вывод нагрузочного резистора соединен с шиной нулевого потенциала, другой вывод - с входом узла дифференцирования, блок определения длительности обслуживания включает две группы реле, потенциометр, узел умножения, узел извлечения квадрат ного корня, два сумматора и схему сравнения, причем одни выводы обмоток реле первой и второй групп блока определения длительности обслуживания через переключающие контакты дополнительного реле соединены с выходом распределителя им пульсов, другие выводы обмоток реле первой группы блока определения длительности обслуживания подключены к выходу узла дифференцирован и к входу запуска устройства, вход задания директивного времени устро ства через соответствующие переклю чающие контакты реле второй группы блока выбора максимума и переключа щие контакты реле второй группы блока определения длительности обслуживания соединены с первым вхо дом схемы сравнения блока определения длительности обслуживания, вход задания дисперсии времени обслуживания устройства через соответствую щие переключающие контакты реле пер вой и второй групп блока выбора мак симума и через соответствующие переключающие контакты реле первой группы подключены к входу первого cyNwaTopa, выход которого подключен к первому входу узла умножения блока определения длительности обслуживания, входы задания времени обслуживания устройства через разделительные диоды, соответствующие переключающие контакты реле первой и второй групп блока выбора максимума и соответствующие переключающие контакты реле первой группы блока определения длительности обслуживания, и соответствующий контакт дополнительного реле подключены к входу второго сумматора блока определения длительности обслужива ,ния и к входу узла дифференцирования блока выбора максимума, подвижный контакт потенциометра подключен к второму входу узла умножения, выход которого соединен с входом узла извлечения квадратного корня, выход которого подключен к соответствующему переключающему контакту дополнительного реле, выход второго сумматора подключен к второму входу схемы сравнения, выход которой подключен к другому выводу обмотки дополнительного реле и к входу распределителя импульсов, входы индикаторов подключены к соответствующим переключающим контактам реле второй группы блока выбора максимума. На чертеже представлена структурная схема устройства для решения задач теории расписаний. Устройство содержит генератор 1 импульсов, распределитель 2 импульсов, дополнительное реле 3 с контактами з -З , блок 4 выбора мак- симума, блок 5 определения длительности обслуживания. Блок 4 цырора максимума содержит разделительные диоды 6f,, первую группу реле 7| 7м с контактами 7,-7п , 7 ,-7 , , элементы И8,-8, вторую группу реле 9)-9 и с контактами 91-9и, 9,- 9Ц- 9; -9;;, индикаторы 10,-10,, узел 11 дифференцирования, -линию 12 задержки, нагрузочный резистор 13. Блок 5 определения длительности обслуживания содержит вторую группу реле 14|-14,. с контактами , второй сумматор 15, схему 16 срав- нения, первую группу реле 17, -17р с контактами 17, -17, , ,, потенциометр 18, первый сумматор 19, блок 20 умножения и блок 21 извлеения квадратного корня. Входами устройства являются вхоы 22,-22„ задания дире стивного вреени, .входы 23,-23„ задания дисперсии времени обслуясивания, входы 24(-24п задания времени обслуживания и вход 25 запуска устройства. В основу работы устройства полоен алгоритм З . Первый шаг. Упорядочить требование в порядке неубывания директивных сроков вьтолнения d , т.е. dj, : i .. .,.. . . д де J|, - номер требования, обслужиаемогр k-м по порядку. Вычислить Ь ф -Пtn ) - функция обратная функдии Лапласа, т.е. п t 45 it) -%-Je dt. Принять i о и I Ф, де I - множество индексов требова НИИ, включенных в расписа- ние до п включительно. Второй шаг. Проверка i п, если нет, то к агу 3, а если да, то закончено форирование оптимальной последовательости. Третий шаг. Сформировать 1 1;{и{;5 де Ufi - множество индексов требований. Четвертый шаг. Проверка условия (1).

Если

., ,,1.5j,,,

Г

jei.

,то возвращаемся к тагу 2 В противU,m,4h((,s:6f)-i, )

)Ы; jfcJ.,L и перейти к шаисключить k :-i3 ГУ 2. После окончан гя работы алгоритма множество 1 у, будет представлять собой гчаксимальное число требований обслуженных одним прибором в заданные директивные сроки. Генератор 1 импульсов предназначен для получения последовательност тактовых импульсов и подключен к первому входу распределителя 2 импульсов , выходы которого через контакты З-З реле 3 подключаются либо к входам блоков 4,, либо к входам блока 5, Переключающий контакт реле 3 подключает выход блока 21 из влечения квадратного корыя к второму сумматору 15, Устройство работает следуюцим об разом. Генератор 1 импульсов вырабатывает тактовые импульсы, которые через первый вход подаются на распределитель 2 импульсов, с выходов кот о р о г о ч с р е 3 пере к л ю i ающ и е 3, 3.,, jji реле 3 поступают либо на вход блока. 4, либо не вход блока 5 Л1ол-О жение контактозз реле 3 определяется управляющими -сигн.алами блоков 4 и 5 и сигналом-с входа 25, Блок 5- предназначен для проверки условия (l) 3 блоке 5 U потенциометра 18 снимае ся напряжение; пропорциональное h Ч подается на второй вход блока 20 умнонениЯг, Импульсы опроса с -распре делителя 2 последовательно поступа.-от на первую .;-i з-торую группы реле ..; У. ( j 1 f 2 , „ , п ) J соотЕвтстзу о ssi-c « пакты которых заг.алкаются п подключают напря.«ение1 чаоез контакт 3 к сумг-латору (второму 15 ,.обеспечивая образова- I ние сутлмн лг-с напряжение Ud-. с вгсо - j-t,J да 23 к первому сумматору 19,, напря жение Ujj с зходс 22 на первый вход схемы 16 сраикеннй.: На выходе первого суммагора 19 образуется с;/1.ма 1. Jкоторая в узле 20 уменьгаается па h, а узел 21 извлека ратный корень .из произведения „ Напр жение с узУ,.- 21 Через контакт поступает ьа вкс, eTOj.-oro сумматора 15, где осуществляйiCK сложение с сумь)МОй . Jv;-rj с, Пo.lly- :eниoe напряжен

ном случае в luaiy 5,

где т. - матеJматнчоское охсидание выполнения j требования; дисперсия времени вь:полк€;ния требования.

Пятый шаг,

Выбрать индекс k таким, что

1(,

iet,

с выхода сумглатора 15 подается на схему 16 сравнения и сравнивается со значением Uj; . После окончания действия очередного j-ro импульса опроса контакты реле 17 остаются в замкнутом положении (напряжения Уг)11 -йл поданы на второй сумматор 15;. Контакты 17J размыкаются импульсом с узла 11 дифференцирования блока 4 и сигналом запуск устройства с входа 25 в начале решения задачи. После первого импульса опроса на вторую и первую схемы 16 сравнения поступят соответственно Uj и Ui,- (h . i;c, Гг . Пусть Uj,. (h U(j ) . Это означает, что первое требование не будет обслужено в заданный директивный срок, тогда схема 16 сравнения выдает управляющий иг-тульс на зеле 3, контакты которого .подключат: распределитель 2 импульсов к блоку 4 выбора максимума и подсоединят выход узла 21умножений к входу дифференцирующей схеь1ы 11 блока 5, Кроме того, управляющий импульс поступает на jjTopofi: вход распределителя 2 импульсоБ для возврата его в исходное положение. Если V. (h- ijf} } , то схема 16 сравнения сигнал не выдачст и после второго импульса опроса к входу второго сумматора 15 через контакты 17j ,17 и 1 , 17 будут подключены напряжения J,, + -i- (h (U((j ). Сумма этих напряжеНИИ будет сравниваться уже с . Пели указанная сумма больше IN, то схема 16 выдаст сигнал, в прот ивном сл,1ае сигнал не формируется и . Блок 4 выбора максимума предназначен для нахождения k-цепочки, для которой выполняется условие (2), В исходном положении контакты реле 7,| и 9 подключают приложен- ные к разделительным диодам б входные напряжения U с входа 24 и напряжения с входа 23 к соответствующим входам блока 5. Через коктакты реле 9; напряжения Uj с входа 22поступают на входы блока 5. С распределителя 2 импульсов поочередно поступают импульсы опроса на реле 7| и на вторые входы элементов И 8. Под действием импульсов опроса контакты 7, + 7|, и 71. + 7( поочередно размыкаются и откл 1чают входные напряжения Urti и от входов 23 и 24 блока 5, а Ьледовательно и от входа узла 11 дифференцирования. Если импульс опроса подан на группу, для которой вьшолняется условие (2),то вследствие размыкания контактов рел 7 (; (l и 1) напряжение и будет отключено от дифференцирующей схемы 11, на ее входе возникает скачок напряжения, равный разности между и и самым большим из неотключенных напряжений.Схема 11 сформирует импульс, который поступает на первые входы элементов И 8,, из которы сработает 8ц , Нмпульс с элемента И 8 переключит реле-9к, контакты которого отключат напряжения U«ii; U(5 и ид от соответствующих входов блока 5. В исходное положение контакты реле 9i(, возвратятся лишь при подаче сигнала Запуск устройства |С входа 25, Одновременно контакты реле 9 подключат напряжение к индикатору 10 , который будет сиг нализировать об этом до конца решения задачи. Кроме того, импульс с дифференцирующей схемы 11 через линию 12 задержки возвращает контакты реле 1(1п в исходное положение и через реле 3 подключает выход распределителя 2 к блоку 5, выход блока 21 умножения подключают к второму сумматору 15, контакты реле 17 17ц возвращает в исходное положение.

Если условие (2) выполняется для двух цепочек (k,m), то при отключении контактов реле 7 (7 и ) первой группы скачка на выходе узла 11 не будет, т.е. к узлу 11 дифференцирования приложено напряжение Um UK. Очередным импульсом отключится , на входе узла 11 возникнет скачок напряжения и выходной

импульс с узла 11 поступит одновременно с импульсом опроса на вход элемента И 8f,,, сработает реле 9 и напряжения Um,v fn iw будут окончательно отключены от входов блока 5.

При отключении немаксимального напряжения скачка напряжения на входе узла 11 дифференцирования не происходит .

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

Перед началом решения сигнал Запуск устройства с входа 25 приводит схему в исходное состояние и начинается поступление импульсов опроса. Пусть очередной импульс поступит на реле 17 и 14(5. первому входу схемы 16 сравнения приложено напряжение U, а к второму входу Ug. Если Ug Uj Т.е. требование с номером S не будет обслужено в директивный срок dg, схема 16 вьщает импульс, который приведет к осуществлению ранее описанных действий, т.е. блок 4 выбора максимума отключи от входов блока 6 напряжения и , U(i и Jj , а импульс с узла 11 дифференцирования возвратит схему в исходное состояние, кроме реле 9i -9п.

Процесс решения задачи заканчивается тогда, когда отсутствует сигнал на выходе cx. 16 сравнения, при подаче импульса опроса на реле 17jp и 14((, вследствие чего прекращается подача импульсов с распределителя 2. Требования, номера которых не зафиксированы индикаторами 10ц, входят в оптимальную последовательность.

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