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

 

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

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

СОЦЙАЛИСТИ4ЕСНИХ

РЕСПУБЛИК (19) (11) 3(51) G 06 G 7 122

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3504154/18-24 (22) 25.10.82 (46) 07.03.84. Бюл.Р 9 (72) В.И. Большаков, Г.Г, Гершелис и А.И. Субботин (53) 681,333(088,8) (56) 1.Авторское свидетельство СССР

Р 690505, кл. 0 06 с 7/122, 1978, 2. Авторское свидетельство СССР

М 920752, кл, 0 06 0 7/122, 1980 (прототип).

3. Бэ.lut $.J. Scheduling to minimize t,he number of late gobs set-up апй processing times are uncertain.—

")4anagement sciense". v. 19, 1973

July-, Р 11, р.р. 1283-1288. (54)(57) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ

ТЕОРИИ РАСПИСАНИЙ, содержащее генератор импульсон и распределитель импульсов, первый вход которого подключен к выходу генератора импульсов, о т л и ч а ю щ е е с я тем, что, с целью расширения класса решаемыХ задач, оно содержит дополнительное реле, блок определения длительности обслуживания, блок выбора максимума, включающий две группы реле, элементы

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

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

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

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

1аксимума, входы которых являются входами устройства, блок запоминания, коммутатор и блок сравнения„ входы которого соединены с выходами блоков выбора максимума„ выход блока сравнения через коммутатор подключен к блоку запоминания. выход которого яв>ляется выходом устройства $1/, 1

Наиболее близким к предлагаемому по технической сущности является

i.;1ûëoãoâoå устройство для минимиза:ии длительности обрабо ки изделий в конвейерной системе, содержащее генератор импульсов„., выхсдь> которого соединены соответственно с в>.одом распределителя импульсов и

1ерез эа.:ыкзющий контакт реле с у и р а в .. 110 pc é о 6 M 0 T h . о Й

«еля, механически связанного с под;-иж1-.=>ми контактами двух делителей к.-;ïpë>êåíè>i, два инвертора,два сумма тора, поляризованное реле, блок памяти и блок вь1бора минимальнОго сигнала, входь1 которого подключены к выходам делителей напряжения соответственно, а выход соединен с первым вхоцом первого сумматора, второй вход которого является управляющим входом устройства, первый вход второго сумматора подключен к выходу первого делителя напряжения, выход второго делителя напряжевия через инвертор соед>1нсн с втОрым входом второго сумматора... выход которого подключен к управляющей с>бмо>: ке поляр1лзОБан1ло1 О реле, вь>ход 1:ер-" выход которого подключен к соответствующему переключающему контакту дополнительного реле, выход второго сумматора подключен к второму входу схемы сравнения, выход которой подключен к другому выводу обмотки дополнительного реле и к входу распределителя импульсов, входы индикаторов подключены к соответствующим переключающим контактам реле второй группы блока выбора максимума,. вого сумматора через переключающий контакт поляризованного реле соединен с выходом и входом второго инвертора, выход которого соединен с информационным входом блока памяти, управляющие входы которого подключены к выходам распределителя импульсов, соответственно, выходы блока памяти являются выходами устройства (2J .

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

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

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

1078441 запуска устройства и ныходу узла дифференцирования, один вывод нагрузочного резистора соединен с шиной нулевого потенциала, другой вывод — с входом узла дифференцирования, блок определения длительности обслуживания включает дне группы реле, потенциометр, узел умножения, узел извлечения квадрат ного корня, два сумматора и схему сравнения, причем одни выводы об- 10 моток реле первой и второй групп блока определения длительности обслуживания через переключающие контакты дополнительного реле соединены с выходом распределителя им- 15 пульсов, другие выводы обмоток реле первой группы блока определения длительности обслуживания подключены к выходу узла дифференцирования и к входу запуска устройства, входы 2О задания директивного времени устройства через соответствующие переключающие контакты реле второй группы блока ныбора максимума и переключающие контакты реле второй группы 25

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

На чертеже представлена структурная схема устройстна для решения задач теории расписаний.

Устройство содержит генератор 1 импульсов, распределитель 2 импульсов, дополнительное реле 3 с контактами 3 -3", блок 4 выбора мак1 симума, блок 5 определения длительности обслуживания. Блок 4 вьфора максимума содержит разделительные диоды 61 в би, первую группу реле

71 -7 с контактами 7, -7, 7,-7„, I lt p

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и r контактами 171 -17, 17 -17„", потенциометр 18, первый сумматор 19, блок 20 умножения и блок 21 извлечения квадратного корня.

Входами устройства являются входы 22,-22„ задания директивного времени, .входы 231 -23„ задания дисперсии времени обслуж11вания, входы 241-241, задания времени обслуживания и вход

25 запуска устройства.

В основу работы устройства положен алгоритм $3), Первый шаг.

Упорядочить требование в порядке неубывания директивных сроков выполнения 6, т.е. и 1 < и . i ...t1 „.. ° .ti где J< — номер требовайия, обслужи.ваемого k-м по порядку.

Вычислить h = ((e(- 1(цД где(р -<1(1;) — функция обратная функ ни Лапласа, т.е. . 2

<(tl= Je dt. 27

Принять i = 0 и I = Р, где I< — множество индексов требова ний, включенных в расписание до п включительно.

Второй шаг.

Проверка i = n если нет, то к шагу 3, а если да, то закончено формирование оптимальной последовательности, Третий шаг.

Сформировать I = I (11Я где U(i3 — множество индексов т1 ебований.

Четвертый шаг.

Проверка условия (Т).

1078441

Если

В противЯ((» . )2-(E <> t I

jå(, » ф 1. -, и"1 (It K <,2

3EТ, „, 1 то возвращаемся к г»агу 2.„ с

= »л, 1 1 . 6 ) I - (a () - = ", д,< 1 e (к исключить К :: †; Т и перейти к ша< гу 2.

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

Генератор 1 импульсов предназначен дпя получения последовательности тактовых импульсов : подключен к первому входу распределителя 2 импульсов, выходы которого через контакты 3 -3 реле 3 подключаются либо к нходам блоков :<, либо к входам блока 5. Переключающий контакт 3р < реле 3 подключает выход блока ?1 извлечения квадратного корня к второму сумматору 15.

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

Генератор 1 импульсов вь-.рабатынае тактовые импульсы, которые †:.ерез гервый вход подаются на распре-делитель 2 кмпульсов, с выходов .

3 -3п реле 3 поступают либо н . вход блока «!, либо на вход блока, Положение контактов реле 3 определяет-,ÿ управляющими сигналами блоков 4 и 5 и сигналом с входа 25, Блок 5 пред- 40 назначен для проверки условия (T)., В блоке 5 * потенциометра 18 снимает.;я напряжение„. пропорциональное подается на второй вход бз:.= .=- 20 множения„ Импульсы опрос-::":,ç.=.»спре делителя 2 последовательно постуают па первую к вторую группы реле

Ш! . . Г 1 < TI>I I< DTOPbIÕ 3 а»»" -1К аЮТС и ,".,-;к:: <чают напряжение: U;„; с вхо»

Д

"„2 "., -: ер<-,. 3 Е<0Н TBEEт » E>, „к с л"»затору»

» (второ;.1у 15 обеспечива»т образоваU ние суммы;,,,-- " > напряжение t!<,": с нхо,(= <„ j да 23 к первому сумматору 19,, напряжение П<(с вход«. 22 на г,:ервый вход схемы 16 oäàq:« -u. <, На выходе пер зого сумматора 1" образуе:.:ся сумма 0 „

1 котo.. а< в узле 2С,:. .ень . ается на 1<, а»2 зел 21 извле<<а- т <» аq 6О ратный кор.=:нь :-:з произведения. Напряженке с узла 21 через контакт Зп"" поступает на:з>.os : :—2.: «зрс го с- мматора

l5, где осуществля-.:oEE:..ëoæåíuå с су .д; к<с ." "; - к,.;,, Г. о I, .:.-.. "ое напряжение 65 нсм .лучае шагy 5 E2Ie m — мате1 матин<.ское ожидание выполнения требования; б; — дисперсия времени выполнения требования.

Пятый шаг.

Выбрать индекс К таким, что с выхода су..гматора 15 подается на схему 16 сравнения и сравнивается со значением Пз . После окончания действия очередного j-ro импульса опроса контакты реле 17 остаются в замкнутом положении (напряжения

:/<», «1; поданы на второй сумматор с»

15 . контакты 17 размыкаются импульсом с узла 11 дифференцирования блока 4 и сигналом запуск устрой ства с входа 25 н начале решения

q дачи.

После первого импульса опроса на вторую и первую схемы 16 сравненкH поступят соответственно Ug u !,;„" (", П jjCTh . (1; Пб„)" . Это означает, что гервое требование не будет обслужено в заданный директивный срок„ тсгда схема 16 сравнения выдает управляющий импульс на реле 3, ксн-акты которого подключат распределитель 2 импульсов к блоку 4 выбсра макскмума и подсоединят выход узла умножения к входу дифференцирующей схемы 11 блока 5, »<роме того, управляющкй кмгульс поступает на второк вход распределителя 2 импуль. соь для возврата его в ксходное положение, Если 4 g, П + (h- .П

2. (1-. (Пб,+П j . Сумма этих напряжений будет сравниваться уже с П

2 ,,oëu указанная сумма больше ".,1, то г схема 16 выдаст сигнал, н про-.квном случае сигнал не формируется и т .д .

Блок 4 вь1бора максимума предназначен для нахождения ":<-цепочки для которой выполняется условие (2).

В исходном положении контакты реле 7, и 9 подключают приложен,» ные к разделительным диодам б входные напряжения U с входа 24

В напряжения Ur с входа 23 к соответствующим входам блока 5. Через контакты реле 9 напряжения UJ с входа

22 поступают на входы блока 5. С расJ 1 предслuтеля 2 импульсов поочередно поступают импульсы опроса на реле

7, и на вторые входы элементов И 8.

Под действием импульсон опроса кон1078441

10 такты 7, + 7„ и 7",, + 7 „ поочередно размыкаются и отключают входные напряжения tJ и tJ() от входов 23 и 24 блока 5, а следовательно и от входа

3 узла 11 дифференцирования. Если импульс опроса подан на группу, для которой выполняется условие (2),то вследствие размыкания контактов реле

7 (7 и 7 „) напряжение 0К будет отключено от дифференцирующей схемы

11, на ее входе возникает скачок напряжения, равный разности между и самым большим из неотключенных напряжений. Схема 11 сформирует импульс, который поступает на первые входы элементов И 8 — 8>, иэ которых 15 сработает 8 . Импульс с элемента .И 8 переключит реле. 9у,, контакты которого отключат напряжения

06„и U „от соответствующих входов блока 5, В исходное положение контакты реле 9 возвратятся лишь при подаче сигнала "Запуск устройства" с входа 25. Одновременно контакты реле 9 подключат напряжение к индикатору 10, который будет сиг- 25 нализировать об этом до конца решения задачи. Кроме того, импульс с дифференцирующей схемы 11 через линию 12 задержки возвращает контакты реле 7 -7 в исходное положение и через реле 3 подключает выходы распределителя 2 к блоку 5, выход блока 21 умножения подключают к второму сумматору 15, контакты реле

171 -17„ возвращает в исходное поло- 35 жение.

Если условие (2) выполняется для двух цепочек (k,ï), то при отключении контактов реле 7 (7 и 7„" ) первой группы скачка на выходе узла 11 не будет, т.е. к узлу 11 дифферен- 4О цирования приложено напряжение

Очередным импульсом отключится Ut„, на входе узла 11 возникнет скачок напряжения и выходной импульс с узла 11 поступит одновременно с импульсом опроса на вход элемента И 8щ, сработает реле 9 и напряжения tT, tg u 0,1 будут окончательно отключены от входов блока 5.

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

"Запуск устройства" с входа 25 приводит схему в исходное состояние и начинается поступление импульсов опроса. Пусть очередной импульс поступит на реле 17 и 14 . К первому входу схемы 16 сравнения приложено напряжение БЗ, а к второму входу U> . Если U< ) U < т.е. требование с номером s не будет обслужено в директивный срок d схема

16 выдает импульс, который приведет к осуществлению ранее описанных действий, т.е. блок 4 выбора максимума отключит от входов блока 6 напряжения Uù, U и с), а импульс

ЗИАД с узла 11 дифференцирования возвратит схему в исходное состояние, кроме реле 9 -9д .

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

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

1078441

Ф

ВНИИПИ 3акаэ 96S/43 Тираж 699 Подписное

Филиал ППП "Патент", r. Ужгород, ул. Проектная,4