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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к вычислительной технике и может быть использовано для решения задач календарного планирования производства, технологических процессов . Цель изобретения - расширение области применения устройства путем решения многоэтапной задачи календарного планирования . Устройство содержит блок 1 задания коэффициентов затрат, блок 2 выбора максимума и блок 3 вычисления. 3 ил.

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

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

РЕСПУБЛИН

ÄÄSUÄÄ 1392575

А1 (Sg 4 G 06 F 15/20

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

К АBTOPCHOMY СВИДЕТЕЛЬСТВУ (21) 4168350/24-24 (22) 31.10.86 (46) 30.04.88. Бюл. № 16 (72) О. Г. Алексеев, С. А. Васильковский, М. В. Крикун и А. Н. Мардас (53) 681.333 (088.8) (56) Авторское свидетельство СССР № 690505, кл. G 06 G 7/76, 1979.

Авторское свидетельство СССР № 1263094, кл. G 06 G 7/76 29.07.85. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ 3АДАЧ КАЛЕНДАРНОГО ПЛАНИРОВАНИЯ (57) Изобретение относится к вычислительной технике и может быть использовано для решения задач календарного планирования производства, технологических процессов. Цель изобретения — расширение области применения устройства путем решения многоэтапной задачи календарного планирования. Устройство содержит блок 1 задания коэффициентов затрат, блок 2 выбора максимума и блок 3 вычисления. 3 ил.!

392575

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

Цель изобретения — расширение области применения устройства путем решения многоэтапной задачи календарного планирования.

На фиг. 1 приведен пример реализации устройства; на фиг. 2 — то же, блока за- 1р дания коэффициентов затрат; на фиг. 3— то же, блока выбора максимума и блока вычисления.

Устройство содержит блок задания коэффициентов затрат (фиг. 2), блок 2 выбора максимума и блок 3 управления вы- 15 числения и индикации (фиг. 3).

Блок 1 задания коэффициентов затрат предназначен для задания напряжений, определяемых по коэффициентам затрат С, и

d, (i= 1, 2,..., и; и — количество этапов в календарном плане) решаемой задачи и содержит: вход разрешения задания коэффициентов затрат 4, треугольную матрицу ячеек 5ij, регистр 6 сдвига, вход 7 установки начального состояния и информационный вход 8, первую 9ь.., 9,..., 9„и вторую 10 ..., 10,..., !О„группы информационных входов, первую 11,..., 11 11„и вторую 12i, 12„...12„группы выходов, причем каждая ячейка матрицы содержит первый 13ij и второй 14ij элементы И, первый 15ij и второй

l6ij ключи, первый 17„и второй !8„задатчики коэффициентов затрат. Количество ячеек 5„определяется исходя из числа и количества этапов в календарном плане, причем индексация ячеек и элементов в них совпадает с индексацией соответствующих переменных в математической постановке задачи календарного планирования.

Блок 2 выбора максимума предназначен для определения ячейки 5;, из матрицы ячеек, имеющей максимальное напряжение на задатчиках 17„и 18„и коммутации ее 40 с блоком 3 вычисления. Схемная реализация блока 2 аналогична схемной реализации соответствующего блока известного устройства. На фиг. 1 входы и выходы блока

2 отражены группами полюсов 19„20, и 21,, 22 (i= 1, 2,...,n) соответственно.

Блок 3 вычисления предназначен для управления работой устройства и индикации результатов решения и содержит первую

23,...23„... 23„и вторую 24ь... 24„... 24„группы информационных входов, первую 25,..., 25„..., 25„и вторую 26,..., 26„..., 26. групппы элементов И, группу 27,..., 27;,... 27, элементов ИЛИ, группу 28ь..., 28;, ..., 28„, вычитающих счетчиков, первую 29ь..., 29,..., 29п и вторую 30ь..., 30Ä..., 30„группы регистров, первую 31 i,..., 31c,..., 31п и вторую

32,..., 32;,..., 32„группы вычитающих индикаторных счетчиков, первую 33ь..., 33;, ..., 33„ и вторую 34,..., 34„..., 34„группы элементов НЕ, п-входовый элемент ИЛИ 35, элемент 36 задержки, триггер 37, диод 38, устройство 39 отображения, генератор 40 одиночных импульсов, вычитающий счетчик 41, первый ключ 42, вход 43 начальной установки устройства, второй ключ 44, транспарант 45, первую 46ь..., 46„..., 46„и вторую

47ь..., 47„..., 47„группы информационных выходов, информационный выход 48, выход

49 установки начального состояния и вход

50 пуска устройства.

Блок 2 устройства содержит элемент

И НЕ 51.

Принцип действия устройства основан на возможности точного решения и-этапной задачи клендарного планирования путем решения соответствующей транспортной задачи линейного программирования.

Если ввести следующие обозначения для

i-го этапа планирования:

С, — производственные затраты на единицу продукции при обычном режиме работы;

Д, — производственные затраты на единицу продукции при работе в экстренном режиме;

h, — затраты на хранение единицы продукции переходящей из этапа i в этап i+ !; ая, — производственная мощность (в единицах продукции) при обычном режиме работы;

ai, — производственная мощность (в единицах продукции) при работе в экстренном режиме;

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

1392575

Решение осуществляется путем последовательного назначения максимального возможных поставок по наиболее дешевым элемента первого столбца (этап 1) . Затем корректируются значения а„которые после этого определяют оставшиеся мощности для различных этапов.

Далее рассматривается этап 2 и его спрос удовлетворяется наиболее дешевыми поставками в пределах новых ограничений на производственные мощности. Процесс продолжа- !0 ется до тех пор, пока не будет удовлетворен спрос этапа п.

Перед началом решения задачи замыкают кнопочный выключатель 43 блока 3 и устанавливают все счетчики и регистры устройства в начальное положение, которое для регистра 6 сдвига блока 1 означает наличие сигнала логической единицы на первом выходе и логического нуля на остальных выходах, для вычитающих счетчиков 28, (i= 1, 2,..., п) блока 3 соответствует за- 20 полнению до уровня Ь„равного потребностям на i-м этапе, для вычитающих индикаторных счетчиков 31, и 32; (i= 1, 2,..., и)— заполнению до уровней а, и ат„соответственно равных мощностям на i-м этапе, для вычитающего счетчика 41 — заполнению до уровня и, равного общему количеству этапов планирования, для регистров

29, и 30; (i = 1, 2,..., п) — состоянию обнуления. Одновременно на R-вход триггера

37 поступает сигнал, переводящий его в ну- 30 левое состояние. Затем замыкают выключатель 4 блока 1 и с помощью задатчиков

17;, и 18;; ячеек 5„ (i= 1, 2,..., n, j) i) задают соответствующие коэффициентам зат рат C и ц напряжения U, С вЂ” U, и U;,=Ч вЂ” V„, где U С;;, V d;,,,,à U = 35

j-1

max(U;;, Ч;,f, причем C;;= С,+ Z. h> и

3С= g

А/ — — 1,+ Z, hk.

Решенйе начинается замыканием выключателя 50 блока 3 и подачей питания по замкнутой цепи SWB-ключа 42 на генератор 40 одиночных импульсов. Вырабатываемые генератором 40 импульсы поступают на вторые входы элементов 25; и 26; (i= 1, 2,.... и) первой и второй групп элементов И. В 4 блоке 1 сигнал логической единицы с первого выхода регистра 6 сдвига поступает на цервые входы элементов И 13и и 14и ячейки 5и, т.е. на элементы И ячеек первого столбца матрицы ячеек. На вторые входы элементов И 1Зи и 14i через входные полюсы 9i и 10i блока 1 и выходные полюсы 46 и 47 блока 3 поступает сигнал логической единицы с выходов элементов

НЕ 33 и 34, соответственно. С выхода элементов И 13„14и блока 1 сигнал поступает на S-входы SWM-ключей 151 и

16ii соответственно и замыкает их исполнительные цепи, подключая ячейки первого столбца матрицы ячеек к соответствующим выходам 191 и 201 блока 2 выбора максимума. С выхода блока 2, соответствующего максимальному входному напряжению (а следовательно, минимальному коэффициенту затрат), сигнал посту пает на соответствующий вход блока 3. Для определенности считаем, что это входной полюс 23и С входного полюса 23 сигнал поступает на первый вход элемента И 25и Элемент И 25 открывается и импульсы от генератора 40 одиночных импульсов через элемент ИЛИ

27 начинают поступать на счетный вход вычитающего счетчика 28и Одновременно импульсы поступают на вход регистра 29 и вычитающего счетчика 31i. Для определенности будем полагать, что а, (Ь|, тогда первым обнулится счетчик 31и Это будет означать, что производственные мощности обычного режима работы на первом этапе полностью используются для удовлетворения спроса. Потребленная мощность в единицах продукции оказывается записанной в регистре 29и С выхода обнуленного счетчика

31i сигнал поступает на вход элемента

НЕ 33и на выходе которого сигнал логической единицы исчезает и, соответственно, закрывается элемент И 13и ячейки 5i блока

1. Исполнительная цепь SWM-ключа 16 1 размыкается и отключает задатчик 17 от входа блока 2 выбора максимума. Теперь максимальным среди напряжений задатчиков первого столбца матрицы ячеек блока будет напряжение на задатчике 18 и который через исполнительную цепь замкнутого SWM-ключа 16 i соединен с входом 20 блока 2 выбора максимума. С выхода 22 блока 2 через входной полюс 24 блока 3 сигнал поступает на первый вход элемента

И 26и который открывается и через элемент ИЛИ 27 импульсы от генератора 40 одиночных импульсов продолжают поступать на счетный вход вычитающего счетчика 28и

Одновременно импульсы поступают на вход регистра 30 и вычитающего счетчика 32и

Вычитание импульсов в счетчике 32 означает использование на первом этапе производственной мощности а., в экстренном режиме для удовлетворения потребностей.

При обнулении счетчика 28 (математическая постановка задачи предполагает

Х (а,+ а.,))$ b, для К= 1, 2,..., и)

1 }=1 сигнал с его выхода, пройдя через элемент п ИЛИ 35, поступает íà S-вход триггера 37 и вход элемента 36 задержки. Триггер 37 переходит в единичное состояние и сигнал с его выхода поступает на счетный вход вычитающего счетчика 41, вычитание единицы в котором означает завершение первого этапа планирования. Одновременно сигналы с выходов регистров 29 и 30 поступают на входы 39 устройства отображения (например, буквенно-цифровой газоразрядный индикатор), в соответствующих позициях которого отображаются потребляе1392575 и > <.>!>.11 !). 1и Н З(> < > 1) (1 «Н П Я мы«н;1 H(рвом э)а;<с мощности, à Hd ин(икаторах k)IIHHI dl<>kk(H< счетчиков 311 и 321 высвсчивак>lся в«личины неиспользованных

H;I;kiIfIkfok(1 и переш«дших на следующие этапы прои.<водстненных мо)цностей. Через иром«жу гок врс мени т, достаточный для срабатывания устройства отображения, сигнал «выхода элем«нта 36 задержки flor«ay«d«I на К-вход триггера 37 и возвра)цаст «п> H нулевое со«ToHHH«. Наличие раз,(«л)г) «льHo

51 предотнраща«т возврат вычитающих сч(гчиков и регистров устройства в исходн<ц «ос тоянис. ()i,Hok)!>(менно сигнал с выхода v,l(мс и гkl 36 Hd.l«ржки через выходной

<н>люс 48 6 10Kd 3 и входной полюс 8 блока ! по« г па«т. па вгорой вход элемента И вЂ” HF н д;1.1 с 1113 ипф >рмационный вход регистра 6 с,синга п«рея<)дя «го но второе положеНИЕ, ОзпаЧаЮ<ц«Е НаЛИЧИЕ СИГНаЛа ЛОГИЧЕ«кой единицы на pl o втором выходе. !

1«рвый ст<>лб«ц матрицы ячеек отключится от регистра 6 с,kflkH и входов блока 2 выоора максимума. У "I ройство переходит к рас пред«лс пию мощностей производства на

Hòîðoм этап«, с >стоян(«му в последовательи >и определении ячеек 5, с максимальными уровнями напряжеHHH на задатчиках !7Н и 18„(I= — 1, 2; J ) I), вычитании соответствун)<пегo колич«стна «диниц в вычитающих сч«тчиках 28,,31, 32, записи его в реI истр;)х 29 и 30, отображении его во второй (грокс у «тройст13(1 39 отображения и вычитании <> вредной сдиницы из вычитаюп(сго « I(. тчика 41. !

3 дальн«йшем «I роиство работает аналогично. (!о 3аверп<«ппи этапа 13 счетчик

41 блока 3 обнуляс гс51, сигнал с его выхода полупел«T па S-вход NV, !3-ключа 42 и на

S-ход 39, Â-клк)ча 44. Исполнительная цепь

89 !3-клк)ча 44 соединяет транспарант 45 с источником опорного напряжения. Загорание транспаранта 45 свидетельствует об

ОКОНЧаНИИ рЕШспня 11-эсаПНОй ЗадаЧИ КаЛЕНдd!)Holo п.<анирования На экране устройства 39 отображения отражается план исНо.IüçîHHHèÿ произв<),гственных мощностей по этапам,;I на индикаторах групп 311,..., 31„.... 31„и 321,..., >2,, 32„вычитающих счегчиков — в«личины неиспользованных по этапам мошност«й (,игнал, поступивший на >-вход Ъ !3-ключа 42, разрывает его ис<юлнительнук> цепь и останавливает генератор 40 одино lklhlx импульсов.

Для возвр frd сх«мы в исходное состоянис нсобходим<> снись напряжение питания с k)xo,kà, разомкнуть выключатели 4 блока и 50 блока . 3 H сня гь напряжение с шин питания усгр<)нсгва

Ус) ройств ) I.I>I р(ш«ния )адан кал«ндарного планирования, сод«ржащее блок вычисл«ния, блок выбора м;>ксимума, блок задания к )эффици«Hтов затрат. содержащий

6 и +1 треугольную матрицу ячеек (и — ко2 личество этапов в календарном плане), каждая ячейка матрицы содержит задатчик коэффициента затрат, ключ и элемент

И, причем блок вычисления содержит генератор одиночных импульсов, транспарант, ключ, группу из п элементов ИЛИ, первук) и вторую группы элементов НГ по и элементов в каждой, от.)ик<(кги3«««н т«м. чTo, с целью расширения области примен«ния устройства путем решения многоэтапной задачи календарного планирования, в блок задания коэффициентов затрат введены элемент

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

i-го элемента И первой группы (i=1, и) соединен с информационным входом i-го регистра первой группы, с информационным входом i-го вычитающего счетчика второй группы и с первым входом i-го элемента

ИЛИ группы, второй вход которого соединен с выходом I-lo элемента И второй группы, со счетным входом 1-го вычитан)щего счетчика третьей группы и с информационным входом i-го регистра второй группы, вход установки в «О» ко)орого соединен с входами установки в «О» всех регистров второй группы, с информационными входами всех вычитающих счетчиков первой, второй и гретьей групп, с информационным входом вычитающего счетчика, с входами установки в «О» всех регистров первой группы, с выходом установки начального состояния блока вычисления, с анодом диода и с входом начальной установки устройства, счетный вход вычитающего счетчика соединен с выходом триггера, вход установки в «О» которого соединен с ка)одом диода, с информационным входом блока вычисления и с выходом элемента задержки, вход которого соединен с входом установки

1392575 в «1» триггера и с выходом и-входового элемента ИЛИ, i-й вход которого соединен с выходом i-го вычитающего счетчика первой группы, счетный вход которого соединен с выходом i-го элемента ИЛИ группы, выходы регистров первой и второй групп являются выходом признака максимального уровня затрат, выход i-ro вычитающего счетчика второй группы соединен с входом

i-го элемента НЕ первой группы, выход которого является i-м информационным выходом первой группы блока вычисления, выход i-го вычитающего счетчика третьей группы соединен с входом i-ro элемента НЕ второй группы, выход которого является

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

И вЂ” НЕ является информационным входом блока задания коэффициентов, первые информационные входы ячеек i-й строки мат10 рицы соединены с i-м информационным входом блока задания коэффициентов первой группы, вторые информационные входы ячеек i é строки матрицы соединены с i-м информационным входом блока задания коэффициентов второй группы, первый входы ячеек матрицы соединены с входом разрешения задания коэффициентов затрат, первые выходы ячеек i-й строки матрицы соединены с i-м выходом блока задания коэффициентов первой группы, вторые выходы о, ячеек i-й строки матрицы объединены и являются i-м выходом блока задания коэффициентов второй группы, который соединен с i-м входом блока выбора максимума второй группы, i-й выход блока задания коэффициентов первой группы соединен с i-м входом блока выбора максимума первой группы, i-e информационные выходы первой и второй групп которого соединены с i-ми информационными входами соответственно первой и второй групп блока вычисления, j å информационные выходы первой и второй групп которого соединены с i-ми информационными входами соответственно первой и второй групп блока задания коэффициентов затрат, выход установки начального состояния блока вычисления соединен с входом установки начального состояния блока задания коэффициентов, информационный вход которого соединен с информационным выходом блока вычисления.

1392575

Составитель С. Кошелев

Редактор А. Маковская Техред И. Верес Корректор В. Бутяга

Заказ 1809/54 Тираж 704 Подписное

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

1!3035, Москва, Ж 35, Раушская наб., д. 4!5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4