УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ УПАКОВКИ Российский патент 1994 года по МПК G06F15/20 

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

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

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

Устройство содержит матрицу 1 задания совместимости объектов, группу из М блоков 2_р моделирования объектов (р=1,2,...,М), блок 3 регистрации, блок 4 подсчета общего объема объектов, генератор 5 одиночных импульсов, первый 6, второй 7 и третий 8 элементы ИЛИ, элемент И9, группу элементов И 10р, р= 1, М, группу регистров 11_р, р=1,М, вход 21 запуска устройства и вход 13 установки исходного состояния устройства.

Матрица 1 задания совместимости объектов содержит М (М-1) ячеек 14_рк, совместимости объектов, р,к=1,М, р ≠ к, каждая из которых содержит элемент И 15, триггер 16 и разделительный диод 17. Вход 18 установки в единичное состояние триггера является входом установки ячейки совместимости. Единичное состояние триггера рк-й ячейки совместимости объектов моделирует невозможность совместного размещения р-го и к-го объектов исходного множества.

Блоки 2_р, р= 1,М моделирования объектов содержат элемент 19 задержки, элемент И 20 и триггер 21. Единичное состояние триггера р-го блока моделирования объектов моделирует то, что р-й объект исходного множества уже вошел в решение.

Блок 3 регистрации предназначен для регистрации номеров объектов, входящих в упаковку на данном этапе решения, и требуемого количества упаковок для размещения всех объектов исходного множества. На чертеже цифровые обозначения имеют информационные входы 22_р, р=1,М, и вход 23 записи.

Блок 4 подсчета общего объема объектов предназначен для подсчета общего объема (массы и т.п.) объектов, уже вошедших в данную упаковку, и объекта, пробно включаемого в нее на данном шаге решения, сравнения его с ограничением на объем (массу и т.п.) упаковки. Если общий объем не превышает ограничения, то на индикаторном выходе блока появляется импульсный сигнал и объем объекта, пробно включаемого в упаковку, суммируется с объемом объектов, включенных в нее ранее. В противном случае импульсный сигнал не формируется и суммирование объемов не осуществляется. Цифровые обозначения на чертеже имеют вход 24 начальной установки, тактовый вход 25, вход 26 возврата блока в исходное состояние и информационный вход 27.

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

Перед началом работы подачей импульса на вход 13 возвращаются в исходное нулевое состояние триггеры 21 всех блоков моделирования объектов, подачей импульсов на установочные входы 18 соответствующих ячеек 14_рк задается матрица совместимости объектов исходного множества, по входу 24 начальной установки в блок 4 вводится значение ограничения на общий объем (массу и т. п. ) объектов, включаемых в одну упаковку, а в регистры 11_р вносятся значения объема (массы) р-го объекта исходного множества (р=1,М). При этом триггеры 16 соответствующих ячеек матрицы совместимости объектов переходят в единичное состояние и сигнал уровня логической "1" с их единичного выхода поступает на вход элементов И 15 этих же ячеек.

Решение осуществляется за К циклов, каждый из которых состоит из n шагов и начинается подачей импульса на вход 12 запуска устройства. С входа 12 импульс поступает на вход элемента ИЛИ 8, а с его выхода - на вход запуска генератора 5 одиночных импульсов, который формирует прямоугольный импульс, поступающий с его выхода на вход элемента 19 задержки блока 2₁, на вход элемента ИЛИ 7, на вход 26 возврата в исходное блока 4 и на считывающий вход регистра 11₁. При этом блок 4 возвращается в исходное состояние (обнуляется содержание его накапливающего сумматора), с информационного выхода регистра 11₁ значение объема (массы) первого объекта поступает на вход элемента ИЛИ 6, а с его выхода - на информационный вход 27 блока 4. Импульс с выхода элемента ИЛИ 7 поступает на тактовый вход 25 блока 4, и в нем осуществляется описанным выше порядком проверка возможности включения в решение первого объекта упаковки. Если он может быть включен в решение, то на выходе блока 4 появляется импульс, поступающий на входы элементов И 20 всех блоков моделирования объектов. К этому моменту времени появляется импульс на выходе элемента 19 задержки блока 2₁. Так как вначале решения триггеры 21 блоков моделирования объектов находятся в нулевом состоянии, то при этом присутствует сигналу ровня логической "1" на первом входе элемента И 20 блока 21 и отсутствует на его инверсном входе. Поэтому на выходе элемента И 20 блока 2₁ появляется импульс, поступающий на единичный вход триггера 21 этого блока и на информационный вход 22₁ блока 3 регистрации. В блоке 3 фиксируется включение первого объекта в первую упаковку, а триггер 21 переходит в единичное состояние и моделирует включение первого объекта в решение. При этом снимается сигнал уровня логической "1" с первого входа элемента И 20 блока 2₁, что исключает включение первого объекта в решение повторно, и появляется сигнал уровня логической "1" на единичном выходе триггера 21 блока 2₁, откуда он поступает на соответствующий вход элемента И9, на вход элемента И 10₁ и объединенные входы элементов И 15 ячеек 14_р1, р=2,М матрицы задания совместимости объектов. Так как при этом сигнал высокого уровня присутствует на обоих входах элементов И 15 ячеек соответствующих объектов, не совместимых с первым, то с выхода этих элементов И сигнал через диод 17 поступает на инверсный вход элемента И 20 соответствующих моделей объектов, чем исключается их включение в первую упаковку. На этом завершается первый шаг решения и начинается второй, который, как и последующие, аналогичен рассмотренному первому. После завершения последнего шага решения первого цикла сигнал с выхода элемента 19 задержки блока 2_М поступает на вход 23 записи блока 3 регистрации, вход элемента ИЛИ 8 и на объединенные входы элементов И 10_р, р= 1,М. При этом в блоке 3 осуществляется отключение от информационных входов первого элемента памяти и подключение второго, сигнал с выхода элемента ИЛИ 8 поступает на вход запуска генератора 5 одиночных импульсов, а с выходов элементов И10_р, соответствующих объектам, включенным в первую упаковку, сигнал поступает на объединенные нулевые входы триггеров 16 соответствующих им столбцов ячеек 14_рк матрицы задания совместимости объектов, триггеры 16 этих ячеек переходят в нулевое состояние (если не были в нем), чем исключается виляние объектов, включенных в решение, на последующую работу устройства. С появлением импульса на выходе генератора 5 начинается второй цикл решения, который, как и возможные последующие, аналогичен рассмотренному. Решение заканчивается, когда на одном из шагов решения включен в упаковку последний объект, при этом на всех входах элемента И 9 присутствуют сигналы высокого уровня и появляется сигнал на выходе элемента И 9, откуда он поступает на вход останова генератора 5 одиночных импульсов, исключая возможность его дальнейшей работы и сигнализируя об окончании решения. План упаковки объектов исходного множества и количество требуемых упаковок однозначно определяются содержимым элементов памяти блока 3.

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

Изобретение относится к вычислительной технике и может быть использовано для решения широкого класса прикладных задач, моделируемых математической постановкой задачи об упаковке с ограничением на возможность совместного размещения некоторых объектов их исходного множества. Устройство содержит матрицу задания совместимости объектов из M (M-1) ячеек (M - число объектов в исходном множестве), M блоков моделирования объектов, M регистров, M элементов И, блок подсчета общего объема объектов, блок регистрации, три элемента ИЛИ, элемент И и генератор одиночных импульсов. Каждая ячейка содержит триггер, элемент И и диод, а каждый блок моделирования объекта - элемент задержки, элемент И и триггер. Работа устройства основана на последовательном определении объектов, включаемых в данную упаковку, из числа объектов, не включенных в нее ранее, не имеющих ограничения на совместимое размещение, и с учетом ограничения на общий объем (массу и т.п.) упаковки. 1 ил.

УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ УПАКОВКИ, содержащее генератор одиночных импульсов, вычислительный блок подсчета общего объема объектов, блок регистрации, первый элемент ИЛИ и группу из M регистров, выходы которых соединены с соответствующими входами первого элемента ИЛИ, выход которого соединен с информационным входом блока подсчета общего объема объектов, отличающееся тем, что, с целью расширения функциональных возможностей за счет решения задач упаковки с ограниченной возможностью совместного размещения объектов исходного множества, в него введены группа элементов И, второй элемент ИЛИ, элемент И, группа M блоков моделирования объектов, третий элемент ИЛИ, матрица задания совместимости объектов, содержащая M · (M - 1) ячеек совместимости объектов, каждая из которых содержит триггер, элемент И и разделительный диод, анод которого является выходом ячейки совместимости объектов, катод разделительного диода соединен с выходом элемента И ячейки совместимости объектов, первый вход которого соединен с прямым выходом триггера ячейки совместимости объектов, вход установки в единичное состояние которого является входом установки ячейки совместимости объектов, а вход установки в нулевое состояние триггера ячейки совместимости объектов является входом сброса ячейки совместимости объектов, второй вход элемента И ячейки является входом опроса ячейки, блок моделирования объекта содержит элемент задержки, элемент И и триггер, инверсный выход которого соединен с первым входом элемента И модели объекта, второй вход которого является первым входом модели объекта, второй и третий входы блока моделирования объекта соединены соответственно с входом элемента задержки блока моделирования объекта и входом установки в нулевое состояние триггера блока моделирования объекта, вход установки в единичное состояние которого соединен с первым выходом блока моделирования объекта и выходом элемента И блока моделирования объекта, третий вход которого соединен с выходом элемента задержки блока моделирования объекта и вторым выходом блока моделирования объекта, третий выход которого соединен с прямым выходом триггера блока моделирования объекта, инверсный вход элемента И блока моделирования объекта является четвертым входом блока моделирования объекта, выход генератора одиночных импульсов соединен с первым входом второго элемента ИЛИ и вторым входом первого блока моделирования объекта, второй выход P-го блока моделирования объекта соединен с вторым входом (P + 1)-го блока моделирования объекта и (P + 1)-м входом второго элемента ИЛИ (где P = 1, ..., M-1), второй выход M-го блока моделирования объекта соединен с входом записи блока регистрации и первыми входами третьего элемента ИЛИ и элементов И группы, выходы которых соединены с входами сброса ячеек совместимости объектов соответствующего столбца и информационными входами соответствующего регистра группы, вход записи регистра группы соединен с соответствующим входом второго элемента ИЛИ, выход которого соединен с тактовым входом блока подсчета общего объема объектов, выход которого соединен с первыми входами блоков моделирования объектов группы, третьи входы которых соединены с входом установки исходного состояния устройства, первый выход каждого блока моделирования объекта группы соединен с соответствующим информационным входом блока регистрации, третий выход каждого блока моделирования объекта соединен с соответствующим входом элемента И, вторым входом соответствующего элемента И группы и входами опроса ячеек соответствующего столбца совместимости объектов матрицы задания совместимости, выходы ячеек каждой строки матрицы совместимости соединены через схему МОНТАЖНОЕ ИЛИ и соединены с четвертым входом соответствующего блока моделирования группы; выход элемента И соединен с входом останова работы генератора одиночных импульсов, вход запуска которого соединен с выходом третьего элемента ИЛИ, второй вход которого является входом запуска устройства, первый вход второго элемента ИЛИ соединен с входом возврата в исходное состояние блока подсчета общего объема объектов, вход начальной установки которого является входом начальной установки устройства.