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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧ ЕСНИХРЕСПУБЛИН А 1(50 4 6 06 Г 15/2 ПИСАНИЕ ИЗОБРЕТЕНИЯ ГВЩд К АВТОРСКОМУ ЕТЕПЬСТВ ОСУДАРСТВЕННЫИ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИИ(54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ КАЛЕНДАРНОГО ПЛАНИРОВАНИЯ(57) Изобретение относится к вычислительной технике и может быть использовано для решения задач календарного планирования производства, технологических процессов, Цель изобретения - расширение области применения устройства путем решения многоэтапной задачи календарного планирования. Устройство содержит блок 1 задания коэффициентов затрат, блок 2 выбора максимума и блок 3 вычисления. 3 ил.Изобретение относится к вычислительной технике и может быть использовано для решения задач календарного планирования производства, технологических процессов и т.п.Цель изобретения - расширение области применения устройства путем решения многоэтапной задачи календарного планирования.На фиг. 1 приведен пример реализации устройства; на фиг. 2 - то же, блока за дания коэффициентов затрат; на фиг. 3 - то же, блока выбора максимума и блока вычисления.Устройство содержит блок 1 задания коэффициентов затрат (фиг. 2), блок 2 выбора максимума и блок 3 управления вы числения и индикации (фиг. 3).Блок 1 задания коэффициентов затрат предназначен для задания напряжений, определяемых по коэффициентам затрат С, и(1= 1, 2 и; и - количество этапов в календарном плане) решаемой задачи и содержит: вход разрешения задания коэффициентов затрат 4, треугольную матрицу ячеек 511, регистр 6 сдвига, вход 7 установки начального состояния и информационный вход 8, первую 9 ь, 9 9 и вторую 1 О, 10 10 группы информационных входов, первую 11 11, 11 и вторую 12 ь, 1212 группы выходов, причем каждая ячейка матрицы содержит первый 1311 и второй 141) элементы И, первый 151 и второй 1611 ключи, первый 17 и второй 18 задатчики коэффициентов затрат. Количество ячеек 5 определяется исходя из числа и количества этапов в календарном плане, причем индексация ячеек и элементов в них совпадает с индексацией соответствующих переменных в математической постановке задачи календарного планирования.Блок 2 выбора максимума предназначен для определения ячейки 5;, из матрицы ячеек, имеющей максимальное напряжение на задатчиках 17 и 18 и коммутации ее 40 с блоком 3 вычисления. Схемная реализация блока 2 аналогична схемной реализации соответствующего блока известного устройства. На фиг. 1 входы и выходы блока 2 отражены группами полюсов 1920, и 21 22 (1= 1, 2п) соответственно. Блок 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 31 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.Принцип действия устройства основан на возможности точного решения и-этапной задачи клендарного планирования путем решения соответствующей транспортной задачи линейного программирования. Если ввести следующие обозначения для 1-го этапа планирования:С, - производственные затраты на единицу продукции при обычном режиме работы; Д, - производственные затраты на единицу продукции при работе в экстренном режиме; Ь, - затраты на хранение единицы продукции переходящей из этапав этап +1;ая, - производственная мощность (в единицах продукции) при обычном режиме работы;а, - производственная мощность (в единицах продукции) при работе в экстренном режиме;Ь, - спрос (в единицах продукции), то задачу календарного планирования можно представить в виде транспортной задачи, условия которой приведены в таблице.Решение осуществляется путем последовательного назначения максимального возможных поставок по наиболее дешевым элемента первого столбца (этап 1). Затем корректируются значения акоторые после этого определяют оставшиеся мощности для различных этапов.Далее рассматривается этап 2 и его спрос удовлетворяется наиболее дешевыми поставками в пределах новых ограничений на производственные мощности. Процесс продолжа ется до тех пор, пока не будет удовлетворен спрос этапа п.Перед началом решения задачи замыкают кнопочный выключатель 43 блока 3 и устанавливают все счетчики и регистры устройства в начальное положение, которое для регистра 6 сдвига блока 1 означает наличие сигнала логической единицы на первом выходе и логического нуля на остальных выходах, для вычитающих счетчиков 28, (1= 1, 2 п) блока 3 соответствует за полнению до уровня Ь равного потребностям на 1-м этапе, для вычитающих индикаторных счетчиков 31, и 32; (1= 1, 2 и) - заполнению до уровней а , и атсоответственно равных мощностям на 1-м этапе, для вычитающего счетчика 41 - заполнению до уровня и, равного общему количеству этапов планирования, для регистров 29, и 30; (1 = 1, 2 п) - состоянию обнуления. Одновременно на К-вход триггера 37 поступает сигнал, переводящий его в ну левое состояние. Затем замыкают выключатель 4 блока 1 и с помощью задатчиков 17 и 18 ячеек 5 (1= 1, 2 и, 1) 1) задают соответствующие коэффициентам зат рат С и бнапряжения Ц,= С - Ц, и Ц,= Ч - Ч, где Ц,С, Чся д; а 1 = 354-1вах(Ц;, Ч; причем С= С,+ Х, Ь и)ьи= 1,+Х Ь,.Решенйе начинается замыканием выключателя 50 блока 3 и подачей питания по замкнутой цепи 5%В-ключа 42 на генератор 40 одиночных импульсов. Вырабатываемые генератором 40 импульсы поступают на вторые входы элементов 25; и 26, (1=1, 2,и) первой и второй групп элементов И. В 45 блоке 1 сигнал логической единицы с первого выхода регистра 6 сдвига поступает на цервые входы элементов И 13 и и 14 и ячейки 5 и, т.е. на элементы И ячеек первого столбца матрицы ячеек. На вторые входы элементов И 13 и 141 через вход ные полюсы 9 и 10 блока 1 и выходные полюсы 461 и 47 блока 3 поступает сигнал логической единицы с выходов элементов НЕ 33 и 341 соответственно. С выхода элементов И 131 и 14 и блока 1 сигнал поступает на 8-входы 5%М-ключей 151 и 16 ц соответственно и замыкает их исполнительные цепи, подключая ячейки первого столбца матрицы ячеек к соответствующим выходам 19 и 201 блока 2 выбора максимума. С выхода блока 2, соответствующего максимальному входному напряжению (а следовательно, минимальному коэффициенту затрат), сигнал поступает на соответствующий вход блока 3. Для определенности считаем, что это входной полюс 23 и С входного полюса 23 сигнал поступает на иер.вый вход элемента И 25 и Элемент И 25 открывается и импульсы от генератора 40 одиночных импульсов через элемент ИЛИ 27 начинают поступать на счетный вход вычитающего счетчика 28 и Одновременно импульсы поступают на вход регистра 29 и вычитающего счетчика 31 и Для определенности будем полагать, что а, ( Ьи тогда первым обнулится счетчик 31 и Это будет означать, что производственные мощности обычного режима работы на первом этапе полностью используются для удовлетворения спроса. Потребленная мощность в единицах продукции оказывается записанной в регистре 29 и С выхода обнуленного счетчика 31 сигнал поступает на вход элемента НЕ 33 и на выходе которого сигнал логической единицы исчезает и, соответственно, закрывается элемент И 13,ячейки 5блока 1. Исполнительная цепь ЬЮМ-ключа 161 размыкается и отключает задатчик 17от входа блока 2 выбора максимума. Теперь максимальным среди напряжений задатчиков первого столбца матрицы ячеек блокабудет напряжение на задатчике 18 и, который через исполнительную цепь замкнутого 8%М-ключа6соединен с входом 20 блока 2 выбора максимума. С выхода 22 блока 2 через входной полюс 24 блока 3 сигнал поступает на первый вход элемента И 26 и который открывается и через элемент ИЛИ 27 импульсы от генератора 40 одиночных импульсов продолжают поступать на счетный вход вычитающего счетчика 28 и Одновременно импульсы поступают на вход регистра 30 и вычитающего счетчика 32 и Вычитание импульсов в счетчике 32 озна. чает использование на первом этапе производственной мощности а., в экстренном режиме для удовлетворения потребностей. При обнулении счетчика 281 (математическая постановка задачи предполагает Х (а,+ ат,)Ь, для К= 1, 2 и) (Усигнал с его выхода, пройдя через элемент п ИЛИ 35, поступает на 5-вход триггера 37 и вход элемента 36 задержки. Триггер 37 переходит в единичное состояние и сигнал с его выхода поступает на счетный вход вычитающего счетчика 41, вычитание единицы в котором означает завершение первого этапа планирования. Одновременно сигналы с выходов регистров 29 и 30 поступают на входы 39 устройства отображения (например, буквенно-цифровой газоразрядный индикатор), в соответствующих позициях которого отображаются потребляе 392575Фо 11,и пзо 61)тенин мыс и) первом э) дп. мощности, а на индикаторах вычитдкцих счетчиков 31) и 32 вьсвсчивдкся величины неиспользованных пд л;пом и перешедших на след) ющие этапы производственных моцностей. Через промежу гок времени т, достдточный для срабатывания устройства отображения, сигнал с выхода элемента 36 задержки поступаег на К.вход триггера 37 и возврапдет со в нулевое состояние. Наличие разделительно лиолд 38 и элемента И НЕ 51 прелотнрдшат возврат вычитаюших сч гчиков и регистров устройства в исходиц сотояни. .Элновременно сигнал с выхода э,)менгд 36 задержки через выходной нлюс 48 блока 3 и вхолной полюс 8 блока 1 по"гх пас г нд вгорой вход элемента И - НГ н л;лн;) ипфрмацинный вход регистра 6 сдвига ереволя его но второе положе. ние, озндчдюгцее наличие сигнала логической единицы на его втором выходе 11 ервый отлбец матрицы ячеек отключится от регистра 6 сдвига и вхолов блока 2 выбора максимума, Уа ройство переходит к р)спрелеленик) мощностей производства на втором этапе, с)стоянему в последовательном определении ячеек 5, с максимальными уровнями напряжений нд задатчиках 17 и 18(1= - 1, 2; ) 1, вычитании соответствун)него количества единиц в вычитаю. ши. счетчиках 28 31, 32, записи его в ре истр;)х 2 Э и 30, отображении его во второйсрок устр)йствд 39 отображения и вьчнтднии чредной единицы из вычитаюпего с тчикд 41Б дальнейшем устроиство работает аналогично. 11 )двериенин этапа и счетчик 41 блокд 3 обнуляется, сигнал с его выхола полупуст на -вхо. ЪВ-ключа 42 и на -хол 8%В-клк)ча 44. 1 сполнительная цепь 8%В-клоч) 44 соединяет транспарант 45 с источником опорного )апряжения. Загорание транспаранта 45 свидетельствует об окончании решения п.ганной задачи календарного п.днир)вдпия На экране устройства 39 отображения отражается план испо.ьзовдния произв)лственных мощностей по эта)ам, д нд индикаторах групп 3 31 31 и 32 ь, 32 32 вычитдющих счегчиков - величины неиспользованных по этапам моши)отей игндл, поступивший нд -вход ЯЪВ-ключа 42, разрывает его исполнительную цепь и останавливает генератор 40 одиночных импульсов.,Чля возврата схемы в исходное состояни. нсобхолимо снять напряжение питания с выла, разомкнуть выключатели 4 блокаи 50 блока 3 и сня гь напряжение с шин питания усгр)исгва Ул ройство,)ля р кения задач календарного лднров)ния, содержащее блок вычислния, блок ивбора м,ксимума, блок задания к )эффивнетон затрат, содержащий 5 10 15 20 25 30 35 40 45 50 55 6и+-1треугольную матрицу ячеек 1 п - ко 2 личество этапов в календарном плане), каждая ячейка матрицы содержит залатчик коэффициента затрат, ключ и элемент И, причем блок вычисления содержит генератор одиночных импульсов, транспарант, ключ, группу из п элементов ИЛИ, первук) и вторую группы элементов НГ по и элемент)в в каждой, отличоиееся тем. что, с целью расширения области применения устройства путем решения многоэтапной задачи календарного планирования, в блок задания коэффициентов затрат введены элемент И - НЕ и регистр сдвига, в блок вычисления введены первая и вторая группы из и элементов И, первая и втораяруппы из п регистров, и-входовый элементв ИЛИ, первая, вторая и зретья группы из и вычитающих счетчиков, элемент задержки, триггер, диод, вычитающий счетчик и второй ключ, информационный вход которого является входом пуска устройства и соединен с информационным входом первого ключа блока вычисления, выход второго ключа которого соединен с первым выводом транспаранта, второй вывод которого соединен с входом нулевого потенциала устройства, управляющий вход второго ключа соединен с выходом признака окончания счета вычитающего счетчика и с управляющим входом первого ключа, выход которого соединен с входом генератора одиночных импульсов, выход которого соединен с первыми входами первой и второй групп элементов И, вторые входы элементов И первой и второй групп являются соответственно первой и второй группами информационных входов блока вычисления, выход )-го элемента И первой группы (1=1, и) соединен с информационным входом 1-го регистра первой группы, с информационным входом .го вычитающего счетчика второй группы и с первым входом 1-го элемента ИЛИ группы, второй вход которого соединен с выходом 1-го элемента И второй группы, со счетным входом 1-го вычитан)пего счетчика третьей группы и с информационным входом -го регистра второй группы, вход установки в О ко)орого соединен с входами установки в О всех регистров второй группы, с информационными входами всех вычитающих счетчиков первой, второй и гретьей групп, с информационным входом вычитающего счетчика, с входами установки в О всех регистров первой группы, с выходом установки начального состояния блока вычисления, с ан)дом диода и с входом начальной установки устройства, счетный вход вычитающего счетчика соединен с выходом триггера, вход установки в О которого соединен с кд) одом диода, с информационным входом блока вычисления и с выходом элемента задержки, вход которого соединен с входом установки392575 Ы,10,111 172 10 п 11 п У втриггера и с выходом и-входового элемента ИЛИ, -й вход которого соединен с выходом -го вычитающего счетчика первой группы, счетный вход которого соединен с выходом -го элемента ИЛИ группы, выходы регистров первой и второй групп являются выходом признака максимального уровня затрат, выход -го вычитающего счетчика второй группы соединен с входом 1-го элемента НЕ первой группы, выход которого является -м информационным выходом первой группы блока вычисления, выход -го вычитающего счетчика третьей группы соединен с входом -го элемента НЕ второй группы, выход которого является -м информационным выходом второй группы блока вычисления, первый вход второго элемента И каждой ячейки матрицы блока задания коэффициентов соединен с первым входом первого элемента И и является входом начальной установки ячейки матрицы, второй вход первого элемента И является первым информационным входом ячейки матрицы, второй вход второго элемента И является вторым информационным входом ячейки матрицы, выход первого элемента И соединен с управляющим входом первого ключа, выход которого является первым выходом ячейки матрицы, информационный вход первого ключа соединен с выходом первого задатчика коэффициента затрат, первый вход которого соединен с первым входом второго задатчика и является первым входом ячейки матрицы, вторые входы задатчиков соединены с входом нулевого потенциала устройства, выход второго задатчика соединен с информационным входом второго ключа, управляющий вход которого соединен с выходом второго элемента И, выход второго ключа является вторым выходом ячейки матрицы, входы начальной установки ячеек -го столбца матрицы соединены с -м выходом регистра сдвига, вход разрешения записи которого соединен с входом установки начального состояния блока задания коэффициентов и с первым входом элемента И НЕ, выход которого соединен с информационным входом регистра сдвига, второй вход элемента И - НЕ является информационным входом блока задания коэффициентов, первые информационные входы ячеек -й строки мат- О рицы соединены с -м информационнымвходом блока задания коэффициентов первой группы, вторые информационные входы ячеек -й строки матрицы соединены с -м информационным входом блока задания коэффициентов второй группы, первый входы ячеек матрицы соединены с входом разрешения задания коэффициентов затрат, первые выходы ячеек -й строки матрицы соединены с -м выходом блока задания коэффициентов первой группы, вторые выходы о, ячеек -й строки матрицы объединены иявляются -м выходом блока задания коэффициентов второй группы, который соединен с -м входом блока выбора максимума второй группы, -й выход блока задания коэффициентов первой группы соединен с -м входом блока выбора максимума первой группы, -е информационные выходы первой и второй групп которого соединены с -ми информационными входами соответственно первой и второй групп блока вычисления, -е информационные выходы первой и второй групп которого соединены с -ми информационными входами соответственно первой и второй групп блока задания коэффициентов затрат, выход установки начального состояния блока вычисления соединен с входом установки начального состояния блока задания коэффициентов, информационный вход которого соединен с информационным выходом блока вычисления.тяга Составитель С. Кошелев я Техред И. Верес Корректор В. Бу Тираж 704 Подписное нного комитета СССР по делам изобретений и открытий Москва, Ж 35, Раушская наб., д. 45 играфицеское предприятие, г. Ужгород, ул. Проектная, 4