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

 

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

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

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

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

Устройство содержит матрицу 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 блоков моделирования объектов, третий элемент ИЛИ, матрица задания совместимости объектов, содержащая M · (M - 1) ячеек совместимости объектов, каждая из которых содержит триггер, элемент И и разделительный диод, анод которого является выходом ячейки совместимости объектов, катод разделительного диода соединен с выходом элемента И ячейки совместимости объектов, первый вход которого соединен с прямым выходом триггера ячейки совместимости объектов, вход установки в единичное состояние которого является входом установки ячейки совместимости объектов, а вход установки в нулевое состояние триггера ячейки совместимости объектов является входом сброса ячейки совместимости объектов, второй вход элемента И ячейки является входом опроса ячейки, блок моделирования объекта содержит элемент задержки, элемент И и триггер, инверсный выход которого соединен с первым входом элемента И модели объекта, второй вход которого является первым входом модели объекта, второй и третий входы блока моделирования объекта соединены соответственно с входом элемента задержки блока моделирования объекта и входом установки в нулевое состояние триггера блока моделирования объекта, вход установки в единичное состояние которого соединен с первым выходом блока моделирования объекта и выходом элемента И блока моделирования объекта, третий вход которого соединен с выходом элемента задержки блока моделирования объекта и вторым выходом блока моделирования объекта, третий выход которого соединен с прямым выходом триггера блока моделирования объекта, инверсный вход элемента И блока моделирования объекта является четвертым входом блока моделирования объекта, выход генератора одиночных импульсов соединен с первым входом второго элемента ИЛИ и вторым входом первого блока моделирования объекта, второй выход P-го блока моделирования объекта соединен с вторым входом (P + 1)-го блока моделирования объекта и (P + 1)-м входом второго элемента ИЛИ (где P = 1, ..., M-1), второй выход M-го блока моделирования объекта соединен с входом записи блока регистрации и первыми входами третьего элемента ИЛИ и элементов И группы, выходы которых соединены с входами сброса ячеек совместимости объектов соответствующего столбца и информационными входами соответствующего регистра группы, вход записи регистра группы соединен с соответствующим входом второго элемента ИЛИ, выход которого соединен с тактовым входом блока подсчета общего объема объектов, выход которого соединен с первыми входами блоков моделирования объектов группы, третьи входы которых соединены с входом установки исходного состояния устройства, первый выход каждого блока моделирования объекта группы соединен с соответствующим информационным входом блока регистрации, третий выход каждого блока моделирования объекта соединен с соответствующим входом элемента И, вторым входом соответствующего элемента И группы и входами опроса ячеек соответствующего столбца совместимости объектов матрицы задания совместимости, выходы ячеек каждой строки матрицы совместимости соединены через схему МОНТАЖНОЕ ИЛИ и соединены с четвертым входом соответствующего блока моделирования группы; выход элемента И соединен с входом останова работы генератора одиночных импульсов, вход запуска которого соединен с выходом третьего элемента ИЛИ, второй вход которого является входом запуска устройства, первый вход второго элемента ИЛИ соединен с входом возврата в исходное состояние блока подсчета общего объема объектов, вход начальной установки которого является входом начальной установки устройства.

РИСУНКИ

Рисунок 1