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

I-о-- нЬоо -- --Оо-I

23, 2, 232 2 223rj 2Чп

43

3 9

ЧВ, 7, 6z 2 Чбп

I

О-оо о o

О1

О1

бп

О-

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

Фиг.1

Блок 3 вычисления предназначен для управления работой устройства и индикации результатов решения и содержит первую 23|,...23„... 23л и вторую 24,,... 24„ ... 24„ группы информационных входов, первую 25|,..., 25,, ..., 25л и вторую 26i,..., 26,,..., 26п групппы элементов И, группу 27,..., 27,,... 27л элементов ИЛИ, группу 28|,..., 28,, ..., 28„, вычитающих счетчиков, первую 29i,..., 29,..., 29rt и вторую 30|,..., 30,,..., 30л группы реИзобретение относится к вычислительной технике и может быть использовано для решения задач календарного планирования производства, технологических процессов и т.п.

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

На фиг. 1 приведен пример реализации устройства; на фиг. 2 - то же, блока за- 10 гистров, первую 311,..., 3h ,..., 31n и вторую

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

d, (i 1, 2,..., п; п - количество этапов в 20 47 47,,..., 47л группы информационных

календарном плане) решаемой задачи и со- выходов, информационный выход 48, выход

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

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

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

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

держит; вход разрешения задания коэффициентов затрат 4, треугольную матрицу ячеек 5ij, регистр 6 сдвига, вход 7 установки начального состояния и информационный вход 8, первую 9|..., 9,..., 9„ и вторую 10|..., 10,..., 10п группы информационных входов,

первую 111,..., 11, 11л и вторую 12

12,,...12л группы выходов, причем каждая ячейка матрицы содержит первый I3ij и второй 14ij элементы И, первый 15ij и второй 16ij ключи, первый 17,/ и второй 18,, задат- чики коэффициентов затрат. Количество ячеек 5,, определяется исходя из числа п - количества этапов в календарном плане, причем индексация ячеек и элементов в них

25

И НЕ 51.

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

30

Если ввести следующие обозначения для i-ro этапа планирования: С, - производственные затраты на единицу продукции при обычном режиме работы; d, - производственные затраты на единицу совпадает с индексацией соответствую-продукции при работе в экстренном режиме;

щих переменных в математической поста-h, - затраты на хранение единицы продукции

новке задачи календарного планирования.переходящей из этапа i в этап i + l;

Блок 2 выбора максимума предназначенas, - производственная мощность (в единицах продукции) при обычном режиме работы;

на задатчиках 17,, и 18,, и коммутации ее 40 аг, - производственная мощность (в едини- с блоком 3 вычисления. Схемная реали-цах продукции) при работе в экстренном

для определения ячейки 5,, из матрицы ячеек, имеющей максимальное напряжение

зация блока 2 аналогична схемной реализации соответствующего блока известного устройства. На фиг. 1 входы и выходы блока 2 отражены группами полюсов 19,, 20, и 21,, 22т (i 1, 2,...,п) соответственно.

45

режиме;

Ь, - спрос (в единицах продукции),

то задачу календарного планирования можно

представить в виде транспортной задачи,

условия которой приведены в таблице.

Блок 3 вычисления предназначен для управления работой устройства и индикации результатов решения и содержит первую 23|,...23„... 23л и вторую 24,,... 24„ ... 24„ группы информационных входов, первую 25|,..., 25,, ..., 25л и вторую 26i,..., 26,,..., 26п групппы элементов И, группу 27,..., 27,,... 27л элементов ИЛИ, группу 28|,..., 28,, ..., 28„, вычитающих счетчиков, первую 29i,..., 29,..., 29rt и вторую 30|,..., 30,,..., 30л группы регистров, первую 311,..., 3h ,..., 31n и вторую

25

И НЕ 51.

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

45

режиме;

Ь, - спрос (в единицах продукции),

то задачу календарного планирования можно

представить в виде транспортной задачи,

условия которой приведены в таблице.

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

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

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

заполнению до уровней ал, и ат,, соответственно равных мощностям на i-м этапе, для вычитающего счетчика 41 - заполнению до уровня п, равного общему количеству этапов планирования, для регистров 29/ и 30, (i I, 2,..., п) - состоянию обнуления. Одновременно на R-вход триггера 37 поступает сигнал, переводящий его в нулевое состояние. Затем замыкают выключатель 4 блока I и с помощью задатчиков 17,j и 18,у ячеек 5,/ (i 1, 2,..., п, j i) задают соответствующие коэффициентам затрат С,/ и cLy напряжения U,/ С-U,, и и,7 V-V,/, где U,v со С, /, V,y со d,-,, а U

,,, V,, у , причем С,, C,-f- 2. h и

- d,7 d,-j- S, ht.

Рещенйё начинается замыканием выключателя 50 блока 3 и подачей питания по замкнутой цепи SWB-ключа 42 на генератор 40 одиночных импульсов. Вырабатываемые генератором 40 импульсы поступают на вторые входы элементов 25, и 26, (, 2,.... п) первой и второй групп элементов И. В блоке 1 сигнал логической единицы с первого выхода регистра 6 сдвига поступает на первые входы элементов И 13ii и 14:i ячейки 5||, т.е. на элементы И ячеек первого столбца матрицы ячеек. На вторые входы элементов И 13ii и Ии через входные полюсы 9| и 10| блока 1 и выходные полюсы 46| и 47| блока 3 поступает сигнал логической единицы с выходов элементов НЕ 33| и 34i соответственно. С выхода элементов И 13ii и 4 блока I сигнал поступает на S-входы SWM-ключей 15ii и 16(1 соответственно и замыкает их исполнительные цепи, подключая ячейки первого столбца матрицы ячеек к соответствующим

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

одиночных импульсов через элемент ИЛИ 27| начинают поступать на счетный вход вычитающего счетчика 28|. Одновременно импульсы поступают на вход регистра 29i и вычитающего счетчика 311. Для определен5 ности будем полагать, что а., bi, тогда первым обнулится счетчик 3I|. Это будет означать, что производственные мощности обычного режима работы на первом этапе полностью используются для удовлетворения спроса. Потребленная мощность в еди0 ницах продукции оказывается записанной в регистре 29. С выхода обнуленного счетчика 311 сигнал поступает на вход элемента НЕ 33|, на выходе которого сигнал логической единицы исчезает и, соответственно,

5 закрывается элемент И 13ii ячейки 5ii блока 1. Исполнительная цепь SWM-ключа 6 размыкается и отключает задатчик l/n от входа блока 2 выбора максимума. Теперь максимальным среди напряжений задатчиков первого столбца матрицы ячеек блока I

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

5 И 26(, который открывается и через элемент ИЛИ 27 импульсы от генератора 40 одиночных импульсов продолжают поступать на счетный вход вычитающего счетчика 28|. Одновременно импульсы поступают на вход регистра 30i и вычитающего счетчика 32|.

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

задачи предполагает для К 1, 2,..., п)

сигнал с его выхода, пройдя через элемент п ИЛИ 35, поступает на S-вход триггера 37 и вход элемента 36 задержки. Триггер 37 переходит в единичное состояние и сигнал с его выхода поступает на счетный вход вычитающего счетчика 41, вычитание единицы в котором означает завершение первого этапа планирования. Одновременно сигналы с выходов регистров 29i и 30i поступают на входы 39 устройства отображения (например, буквенно-цифровой газоразрядный индикатор), в соответствующих позициях которого отображаются потребляемыс на первом aiaiit мощности, а на индикаторах вычитающих счетчиков 31 и 32| вые печи ваются ве.ничииы неиспользованных на данном и переи1едших на следующие таны ирои.шодственных мощностей. Через промежуток BfieMeiHi TI, достаточный для срабатывания устройства отображения, сигнал с выхода элемента 36 задержки поступает на R-вход триггера 37 и возвра- HtaeT его в ну.1евое состояние. Наличие раз- де.лительноп) диода 38 и эле.мента И НН 51 нредотнраи1ает возврат вычитающих счетчиков и регистров устройства в исход- нос состояние. Одновременно сигнал с выхода :)леменга 36 заде)жки через выходной ||(),1юс 48 блока 3 и входной полюс 8 блока 1 ностуиаег на нгорой вход ьлемеьгга И - HF и далес на инфор.маниониый вход регистра 6 сд1И1га нереводя его во второе положение, означающее наличие сигнала логической единицы на его втором выходе. Первый ет(;лбец матрицы ячеек отключится от ре1 истра 6 сдвига и входов блока 2 вы- бо)а максимума. Усгройство переходит к рас11)еделению мощностей производства }ia втором этапе, состоящему в последовательном с)нреде;1ении ячеек 5,, с максимальными уровнями напряжений на задатчиках 17,, и 18,, (i 1, 2; i), вычитании соответствующего количества единиц в вычитающих счетчиках 28L, ЗЬ, 322, записи его в ре- 1истрах и ЗО, отображении его во второй ег)оке устройства 39 отображения и выч1ггании очередной единицы из вычитаю- ще1ч) счетчика 4 1.

дальнейн1ем )йство работает ана- ;|О1 ично. По завершении этапа п счетчик 41 блока 3 обнуляегся, сигнал с его выхода поступает па S-вход SWB-ключа 42 и на S-ход SWB-ключа 44. Исполнительная цепь SWB-ключа 44 соединяет транспарант 45 с источнико.м опорного напряжения. Загорание транспаранта 45 свилете;|ьствует об окончании рен1ения п-эгапной задачи календарного планирования На экране устройства 39 отображения отражается план использования пр(жзводс1 венных мощностей по этапам, а на ин;1икаторах групп 31;,...,

31, 31„ и 32|,..., 32,, ..., 32л вычитающих

счетчиков - ве;1нчины неиспользованных по этана.м мощпостей. (,игнал, поступивщий на S-вход SWB-ключа 42, разрывает его исполнительную цепь и ос1анавливает генератор 40 одиночных импульсов.

Для возврата схемы в исходное состояние необходимо снягь напряжение питания с входа, раз(хмкнуть выключатели 4 блока 1 и 50 блока .3 и снягь напряжение с тин питания )йсгва.

Po/,«y,u и:1о6рстения

Устройство для р1Ч11ения задач календарного планирования, содержащее блок вычисления, блок выбора максимума, блок задания коэф|{1ипиентов затрат, содержащий

- количество этапов в календарном плане), каждая ячейка матрицы содержит задат- 5 чик коэффициента затрат, ключ и элемент И, причем блок вычисления содержит генератор одиночных импульсов, транспарант, ключ, группу из п элемептов ИЛИ, первую и вторую группы элементов НЕ по п эле0 ментов в каждой, отличающееся тем, что, с целью расширения области применения устройства путем решения многоэтапной задачи калепдарного планирования, в блок задания коэффициентов затрат введены элемент И - НЕ и регистр сдви1 а, в блок вычисле5 ния введены первая и вторая группы из п элементов И, первая и вторая группы из п регистров, п-входовый элементв ИЛИ, первая, вторая и 1ретья группы из и вычитающих счетчиков, элемент задержки, тригQ гер, диод, вычитающий счетчик и второй ключ, информационный вход которого является входом пуска устройства и соединен с информационным входом первого ключа блока вычисления, выход второго ключа которого соединен с первым выводом

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

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

0 группы и с первым входом i-ro элемента ИЛИ группы, второй вход которого соединен с выходо.м i-ro элемента И второй группы, со счетным входо.м i-ro вычитающего счетчика третьей группы и с информационным входом i-ro регистра второй группы,

5 вход установки в «О которого соединен с входами установки в «О всех регистров второй группы, с информационными входами всех вычитающих счетчиков первой, второй и третьей групп, с информационным входом вычитающего счетчика, с входами

0

5

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

в «1 триггера и с выходом п-входового элемента ИЛИ, i-й вход которого соединен с выходом i-ro вычитающего счетчика первой группы, счетный вход которого соединен с выходом i-ro элемента ИЛИ группы, выходы регистров первой и второй групп являются выходом признака максимального уровня затрат, выход i-ro вычитающего счетчика второй группы соединен с входом 1-го элемента НЕ первой группы, выход коматрицы соединены с j-м выходом регистра сдвига, вход разрешения записи которого соединен с входом установки начального состояния блока задания коэффициентов и с первым входом элемента И - НЕ, выход которого соединен с информационным входом регистра сдвига, второй вход элемента И-НЕ является информационным входом блока задания коэффициентов, первые информационные входы ячеек i-й строки матI ГУ ,-ч ж J.vjj v ij- Lft „ и /V v/J,IJl i-lWI in V,lIJWI rl (VlOJторого является i-м информационным выхо-10 рицы соединены с i-м информационным

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

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

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

второй вход первого элемента И явля-JQ, ячеек i-й строки матрицы объединены и

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

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

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

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

группы, i-e информационные выходы первой и второй групп которого соединены с i-ми информационными входами соответственно первой и второй групп блока вычисления, j-e информационные выходы первой и второй

...T, и.1,, jaAai4ni a и ивли-J-e информационные ВЫХОДЫ первои И второи

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

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

матрицы соединены с j-м выходом регистра сдвига, вход разрешения записи которого соединен с входом установки начального состояния блока задания коэффициентов и с первым входом элемента И - НЕ, выход которого соединен с информационным входом регистра сдвига, второй вход элемента И-НЕ является информационным входом блока задания коэффициентов, первые информационные входы ячеек i-й строки матvjj v ij- Lft „ и /V v/J,IJl i-lWI in V,lIJWI rl (VlOJрицы соединены с i-м информационным

входом блока выбора максимума первой

группы, i-e информационные выходы первой и второй групп которого соединены с i-ми информационными входами соответственно первой и второй групп блока вычисления, j-e информационные выходы первой и второй

J-e информационные ВЫХОДЫ первои И второи

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

:;3-н8ьto

со