Способ и устройство для оптимизации плана гильотинной резки кусков стекла
Изобретение относится к области способов резки стекла, а точнее представляет собой способ и устройство, позволяющее оптимизировать такую резку. Технический результат – создание оптимизированного плана гильотинной резки, учитывающего ограничение по размещению кусков, с минимизацией потери стекла. Способ включает: определение ограничений резки и размещения кусков, критерия оптимизации; создание алгоритма в виде дерева, содержащего «корневую систему», «листья», каждый из которых представляет полный план резки, где каждый другой узел алгоритма представляет частичный план резки, представляющего полный план резки; выбор полного плана резки в зависимости от упомянутого критерия оптимизации. 4 н. и 13 з.п. ф-лы, 10 ил.
Предпосылки создания изобретения
Настоящее изобретение относится к области способов резки стекла, а точнее, представляет собой способ и устройство, позволяющее оптимизировать такую резку.
Способ и процесс согласно изобретению позволяют, в частности, снизить потери стекла при получении партии разрезанных деталей на заводе.
Следует напомнить, что план гильотинной резки комплекта прямоугольных стеклянных кусков должен учитывать, что куски должны быть штабелированы на одном или нескольких каркасах в соответствии с предварительно заданной последовательностью, соответствующей каждому каркасу.
В существующем уровне техники нет программного обеспечения, позволяющего оптимизировать конструкционное решение, связанное с планом резки, позволяющее учитывать эти ограничения размещения, с минимизацией потерь стекла.
На самом деле, программные обеспечения, используемые в настоящее время для этой цели, позволяют спроектировать лишь ограниченное количество планов резки, с учетом ограничений по размещению, что на практике заставляет оператора использовать одновременно несколько программ и выбирать из этих планов резки, создаваемых различными программами, тот, который минимизирует потери стекла.
В документе «An exact algorithm for gêneral, orthogonal, two-dimensional knapsack problems, European journal of operational research, vol. 83, no. 1, 18 mai 1995, Hadjisconstantinou и al.)» («Точный алгоритм для решения проблем, связанных с общим ортогональным двумерным ранцевым аппаратом», Европейский журнал операционных исследований, т. 83, №1, 18 мая 1995 г.) описан способ резки кусков от одного листа. Этот способ неприменим для способа гильотинной резки, в котором куски могут обладать очень разными размерами, причем эти куски в случае необходимости складывают штабелями на нескольких каркасах, с последовательностью, заданной для каждого par каркаса.
Задача и сущность изобретения
Целью изобретения является способ и устройство для определения плана резки, который не обладает вышеописанными недостатками.
Точнее говоря, и согласно первому аспекту изобретение относится к способу, воплощаемому компьютером для определения плана, оптимального для гильотинной резки партии прямоугольных стеклянных кусков, по меньшей мере, от одного листа стекла, причем куски после резки необходимо штабелировать на одном или нескольких каркасах, причем куски на каркасе должны быть размещены на листе для разрезания согласно последовательности, предварительно заданной для этого каркаса, причем упомянутый способ включает в себя:
- этап определения ограничений резки и ограничений размещения упомянутых кусков, а также критерия оптимизации;
- создание алгоритма в виде дерева, содержащего «корневую систему», «листья», каждый из которых представляет полный план резки, позволяющий разрезать любые куски из партии, причем каждый другой узел алгоритма представляет частичный план резки, причем план резки связан с узлом дерева, полученным путем его добавления к частичному плану резки, связанному с исходным узлом данного узла, и с учетом заданных ограничений, причем следующий кусок, принадлежащий упомянутому каркасу, определяют согласно заданной последовательности для этого каркаса; и
- этап выбора полного плана резки, связанного с листом дерева, в зависимости от упомянутого критерия оптимизации.
Изобретение находит преимущественное применение, когда куски необходимо штабелировать, по меньшей мере, на два каркаса, в последовательности, предварительно заданной для каждого каркаса.
Изобретение также находит преимущественно применение при использовании, по меньшей мере, двух листов стекла.
Таким образом, и в целом, целью изобретения является создание способа, позволяющего разработать большое количество полных планов резки, в том числе для комплексных партий. Способ примечателен тем, что он позволяет постепенно спроектировать алгоритм для частичных планов резки, с размещением кусков друг за другом, с учетом ограничений.
Согласно изобретению куски для частичных и полных планов резки обладают размерами кусков, предназначенных для эффективного штабелирования на каркасах; каждый полный план резки содержит точное количество кусков, предназначенных для комплекта каркасов. Это составляет фундаментальное отличие от способа, описанного в документе Hadjisconstantinou и др., в котором допускается резка множества кусков, которые изменяются согласно предварительно заданному лимиту.
Специалистам в данной области техники известны алгоритмы в виде дерева, с использованием термина «уровень». Корневая система составляет 1ый уровень алгоритма, «дочерние узлы» корневой системы образуют 2ой уровень дерева алгоритма, «дочерние узлы этих дочерних узлов» образуют 3ий уровень алгоритма, и т.д.
Этот способ демонстрирует дополнительное преимущество, сотоящее в том, что его легко выполнять параллельно.
Способ сильно облегчает оператору задачу, состоящую в основном в установлении ограничений и критерия оптимизации.
Этот критерий оптимизации может быть предназначен для минимизации общей поверхности потерь, порождаемых резкой. В качестве варианта, оператор может определить другой критерий оптимизации, например, для минимизации количества используемых листо стекла.
В конкретном варианте воплощения, ограничения резки могут быть выбраны из:
- максимального количества уровней резки;
- минимальной ширины обрезков, например, двукратно превышающих толщину листа;
- направления первого разламывания, например, в направлении ширины листа, или максимальной протяженности уровня резки, например, три метра, из-за ограничений в манипулировании.
Следует отметить, что не следует смешивать понятия «уровень в дереве алгоритма» и «уровень резки», которые полностью независимы друг от друга.
В конкретном варианте воплощения, ограничения размещения могут быть выбраны из ориентации кусков на листе, положения относительно кусков на одном и том же листе, в зависимости от их уровня, максимального количества листов упомянутых, по меньшей мере, одного листа стекла.
В конкретном варианте воплощения, узел алгоритма содержит максимум 9⋅m «дочерних узлов», где m - количество каркасов. На самом деле, для каждого каркаса, новый кусок, выбранный с учетом ограничений размещения, можно добавлять к частичному плану резки, причем девятью различными способами, а именно:
- справа от предыдущего куска (на уровне 3 резки), по горизонтали и по вертикали;
- выше предыдущего куска, если эти два последних куска обладают одной и той же протяженностью (на новом уровне 4 резки), причем среди горизонтальной или вертикальной позиции достаточно только одной, протяженность которой равна протяженности предыдущего куска;
- выше предыдущего куска, на левом конце текущего поперечника (на новом уровне 2 резки), по горизонтали и по вертикали;
- на новом поперечнике (на новом уровне 1 резки), по горизонтали и по вертикали;
- на новом листе, по горизонтали и по вертикали.
В оптимизированном варианте воплощения, создание алгоритма в виде дерева включает в себя:
- этап, состоящий в создании, под корневой системой и для каждого из каркасов узел, связанный с частичным планом резки для каждой из допустимых позиций первого куска для каркаса, с учетом ограничений; и
- по меньшей мере, одну итерацию, причем каждая итерация включает в себя:
- этап выбора текущего узла алгоритма, в зависимости от характеристик частичного плана резки, представленного этим узлом; и
- этап создания, по меньшей мере, одного «дочернего» узла упомянутого текущего узла, причем план резки, связанный с упомянутыми «дочерними» узлами, получают путем добавления к частичному плану резки, связанному с упомянутым текущим узлом, и с учетом ограничений, следующего куска для каркаса, взятого согласно заданной последовательности для этого каркаса.
Этот вариант примечателен тем, что он включает в себя, при каждой итерации, этап выбора текущего узла, у которого «дочерние узлы» создают, в зависимости от характеристики частичного плана резки, представленного этим узлом.
Эта характеристика позволяет выбирать текущий узел, более способствующий достижению оптимального решения, таким образом, чтобы способ, как правило, быстрее достигал оптимального решения.
Поэтому, является предпочтительным, чтобы в конкретном варианте воплощения способ включал в себя этап прекращения итераций, если продолжительность исполнения способа превосходит предварительно заданную продолжительность, чтобы позволить оператору изучить оптимальное решение или подходящее решение в разумные сроки.
В конкретном варианте воплощения, способ позволяет пользователю найти наилучшее решение в любой момент, продолжая исполнение способа, для нахождения, в конце концов, наилучших решений.
В конкретном варианте воплощения, текущий узел выбран:
- согласно первому критерию, называемому «критерием минимальных отходов», состоящему в выборе узла, связанного с планом резки, для которого соотношение поверхность потерь/полезная поверхность минимальное; или
- согласно второму критерию, называемому «критерием максимальной поверхности», состоящему в выборе узла, связанного с планом резки, для которого больше важна полезная поверхность.
Эта стратегия исследования дерева алгоритма, иными словами выбор текущего узла состоит в чередовании между собой двух критериев, - «минимальные отходы» и «максимальная поверхность».
Например, «критерий минимальных отходов» можно использовать в течение определенных периодов времени или в течение определенного количества заданных итераций, или до достижения определенной степени заполнения ОЗУ компьютера (примерно 2 миллиона открытых узлов).
Применение критерия «минимальных отходов» позволяет исследовать перспективные области алгоритма, где созданные частичные планы имеют минимальные отходы и могут привести к полным планам резки, близким к оптимальномуу решению. Однако, применение этого критерия приводит к созданию нескольких новых узлов, и если предел не установлен, это может привести к насыщению памяти компьютера.
Таким образом, преимущественно, в данном варианте воплощения изобретения, когда вышеуказанный предел (по времени, по количеству итераций, по степени заполнения ОЗУ) достигнут, стратегию исследования меняют на применение критерия «максимальная поверхность».
Этот последний критерий способствует преимущественно выбору узлов, частичный план которых близок к полному плану резки, при выборе частичных планов с большей поверхностью уже уложенных кусков. Это позволяет быстрее достигать полных планов резки и пробовать усовершенствовать наилучшие полные планы резки, достигнутые к настоящему времени.
Для экономии места в памяти, в конкретном варианте воплощения, один «лист», связанный с полным планом резки, максимизирующим критерий оптимизации вводят в память, при этом другие листья удаляют. Иными словами, первый полученный «лист» вводят в память, и при получении нового «листа», в памяти сохраняют только «лист», связанный с наилучшим полным планом резки.
В конкретном варианте воплощения, способ включает в себя этап удаления узлов алгоритма, связанных с частичными планами резки, для которых поверхность получаемых обрезков превосходит поверхность потерь полного плана резки, связанного с упомянутым листом.
Этот вариант воплощения можно успешно комбинировать с вариантом воплощения, описанным ранее, в котором чередуют «критерий минимальных отходов» и «критерий максимальной поверхности»
На самом деле, если получен наилучший полный план резки, операцию сокращения осуществляют на всех текущих узлах, чтобы попытаться удалить неперспективные узлы, которые не позволяют получить наилучший полный план резки. Это осуществляют посредством сравнения геометрических потерь еще не исследованного узла с потерями для наилучшего решения, полученного до сих пор; иными словами, если потери узла превышают потери для наилучшего решения, этот узел удаляют). Это позволяет снижать количество узлов, остающихся для исследования, а также высвобождать память. Этот критерий также применяют в течение определенного времени или в течение заданного количества итераций, затем критерий «минимальных отходов» применяют для создания новых перспективных узлов.
Технология состоит в чередовании этих двух критериев, т.е., в чередовании создания новых перспективных узлов и получения новых улучшенных решений, которые позволяют удалять менее перспективные узлы.
Этот термин «получаемые обрезки» связан с другими терминами, применительно к Фигуре 7, представляющей частичный план резки PDP.
На этом частичном плане предлагается определить три типа поверхности, а именно:
- полезную поверхность, содержащую куски, с указанием на этой Фигуре номера каркаса, которому они принадлежат,
- получаемые обрезки (заштрихованы), т.е., неиспользуемую поверхность, на которую невозможно добавить ни одного куска; и
- поверхность (крапчатую), которую можно использовать для последующего размещения дополнительных кусков (светло-серую).
Таким образом, в конкретном варианте воплощения, при определении того, что узел алгоритма связан с частичным планом резки, поверхность получаемых обрезков которого уже превышает поверхность потерь полного плана резки, известно, что этот узел можно удалить, поскольку он ни в каком случае не может породить полный план резки, дающий наилучшее решение.
Этот конкретный вариант воплощения позволяет сократить алгоритм и значительно уменьшить продолжительность выполнения способа.
В конкретном варианте воплощения, способ оптимизации согласно изобретению позволяет избежать или минимизировать создание в алгоритме узлов, соответствующих изоморфным частичным планам резки, а именно, планы резки, включающие в себя одни и те же куски и обладающие одной и той же поверхностью получаемых обрезков. В качестве примера, частичные планы резки PDPA и PDBP согласно Фигуре 9 являются изоморфными.
Таким образом, в конкретном варианте воплощения, упомянутые ограничения размещения включают в себя, по меньшей мере, одно лексикографическое ограничение, налагаемое на количество упомянутых каркасов, для предотвращения или минимизации создания узлов, соответствующих изоморфным частичным планам резки.
Например, ограничения размещения могут включать в себя два лексикографических правила, согласно которым:
- если последний кусок размещают выше предыдущего, номер каркаса этого последнего куска должен быть ниже номера каркаса предыдущего куска;
- если последний кусок размещают справа от предыдущего, номер каркаса этого последнего куска должен быть больше или равен номеру каркаса предыдущего куска.
В конкретном варианте воплощения, при каждом создании узла, классифицируют узел в зависимости, по меньшей мере, от одной характеристики плана резки, представленного этим узлом, причем этой или характеристики этих характеристик достаточно для выбора оптимизированного полного плана резки.
Эта характеристика является предпочтительной характеристикой условно, используемой в ходе упомянутого этапа выбора текущего узла алгоритма в оптимизированном варианте воплощения.
Этот вариант воплощения позволяе избежать повторного прохождения всего алгоритма для выбора оптимизированного полного плана резки и для выбора текущего узла в оптимизированном варианте воплощения.
В конкретном варианте воплощения, другие узлы алгоритма в виде дерева, в том числе «листья», представлены в памяти номером каркаса для последнего уложенного куска, и направлением, в котором он был уложен.
Этот вариант воплощения позволяет в минимальной степени загружать память.
Целью изобретения также является устройство для определения оптимизированного плана гильотинной резки партии прямоугольных стеклянных кусков, по меньшей мере, от одного листа стекла, причем куски должны быть после резки штабелированы, по меньшей мере, на одном каркасе, причем куски на каркасе должны быть размещены на листе для резки согласно заданной последовательности для данного каркаса, причем упомянутое устройство включает в себя:
- модуль для определения ограничений резки и ограничений размещения кусков и критерия оптимизации;
- модуль для создания алгоритма в виде дерева, содержащего «корневую систему», «листья», каждый из которых представляет полный план резки, позволяющий разрезать любые куски партии, причем каждый другой узел алгоритма представляет частичный план резки, причем план резки, связанный с узлом алгоритма, получен путем его добавления к частичному плану резки, связанному с исходным узлом данного узла, с учетом ограничений, а следующий кусок, принадлежащий каркасу, определяют согласно заданной последовательности для этого каркаса; и
- модуль для выбора полного плана резки, связанного с листом дерева, в зависимости от упомянутого критерия оптимизации.
Планы резки, полученные способом согласно изобретению, можно, в частности, использовать:
- для создания оптимизированных партий резки выше относительно линии резки;
- в ходе резки, причем резка состоит в основном в распространении трещин по стеклу, согласно соответствующему плану резки;
- для содействия оператору в ходе разламывания листа стекла, для получения кусков для их размещения на различных каркасах.
Следовательно, целью изобретения также является способ гильотинной резки партии прямоугольных стеклянных кусков, по меньшей мере, от одного листа стекла, характеризующийся тем, что он включает в себя:
- воплощение способа определения оптимизированного плана резки, такого как вышеупомянутый;
- упомянутый оптимизированный план используют в ходе стадии резки на упомянутом листе и в ходе стадии разламывания на упомянутом листе. В конкретном варианте воплощения этого способа, саму по себе партию определяют, осуществляя способ определения оптимизированного плана резки, такого как описанный ранее.
В конкретном варианте воплощения, различные этапы способа определения оптимизированного плана резки согласно изобретению определяют с помощью команд компьютерных программ.
Следовательно, целью изобретения также является компьютерная программа на носителе информации, причем эта программа включает в себя команды, адаптированные для воплощения этапов способа определения оптимизированного плана резки согласно изобретению.
Эта программа может использовать любой язык программирования и иметь форму исходного кода, объектного кода или промежуточного кода между исходным кодом и объектным кодом, например, в частично компилированной форме, или в любой другой желаемой форме.
Целью изобретения также является носитель информации, считываемый компьютером и включающий в себя команды компьютерной программы, такой, как была упомянута выше.
Носитель информации может представлять собой любой объект или устройство, пригодное для хранения программы. Например, носитель может включать в себя средство хранения, такое как ПЗУ, например, CD-ROM или ПЗУ микроэлектронной цепи, или еще средство магнитной записи, например, жесткий диск.
С другой стороны, носитель информации может представлять собой передаваемый носитель, такой как электрический или оптический сигнал, который может передаваться по электрическому или оптическому кабелю, по радио или с помощью других средств. Программа согласно изобретению может, в частности, передаваться по сети типа Интернет.
В качестве альтернативы, носитель информации может представлять собой интегральную схему, в которую встроена программа, причем интегральная схема адаптирована для исполнения или для использования при исполнении рассматриваемого способа.
Краткое описание чертежей
Другие характеристики и преимущества настоящего изобретения следуют из описания, приведенного ниже, со ссылкой на прилагаемые чертежи, которые иллюстрируют пример воплощения, лишенный какого-либо ограничительного характера. На Фигурах:
- Фигура 1 демонстрирует каркасы, на которых размещены стеклянные куски;
- Фигуры 2A и 2B демонстрируют полные планы резки, позволяющие разрезать комплект кусков, принадлежащих каркасам согласно Фигуре 1;
- Фигура 3 демонстрирует в форме блок-схемы основные этапы способа определения, соответствующего первому конкретному варианту воплощения изобретения; и
- Фигура 4 демонстрирует частичные планы резки, которые могут быть получены с помощью изобретения;
- Фигура 5 демонстрирует в форме блок-схемы основные этапы способа определения, соответствующего второму конкретному варианту воплощения изобретения;
- Фигура 6 демонстрирует в форме блок-схемы основные этапы функции оптимизация, осуществляемой способом определения по Фигуре 5;
- Фигура 7, уже описанная, демонстрирует частичный план резки;
- Фигура 8 демонстрирует буферную память для запоминания узлов, связанных с частичными планами резки в конкретном варианте воплощения изобретения;
- Фигура 9, уже описанная, демонстрирует изоморфные частичные планы резки; и
- Фигура 10 схематически демонстрирует аппаратную архитектуру устройства для определения, соответствующего конкретному варианту воплощения изобретения.
Подробное описание первого варианта воплощения изобретения
Применительно к Фигуре 1, мы будем описывать пример воплощения изобретения в первом конкретном варианте воплощения изобретения для определения оптимизированного плана гильотинной резки партии из пяти прямоугольных стеклянных кусков P11, P12, P13, P21 и P22, которые должны быть штабелированы на двух каркасах Cl и C2, с учетом определенного количества ограничений, с минимизацией потерь резки.
Этот способ может быть осуществлен на устройстве 100 определения, соответствующем изобретению, представленном на Фигуре 10. Это устройство обладает аппаратной архитектурой компьютера. Оно включает в себя, в частности, процессор 101, постоянное запоминающее устройство типа ROM 102, оперативное запоминающее устройство типа RAM 103, клавиатуру 104, монитор 105 и жесткий диск 106.
Память типа ROM 102 представляет собой носитель согласно замыслу изобретения. Она включает в себя компьютерную программу PG, содержащую команды для исполнения этапов способа определения оптимизированного плана резки согласно изобретению.
В данном примере, программа PG содержит команды, позволяющие исполнять этапы, представленные на Фигуре 3.
Эта программа позволяет определять оптимизированный план гильотинной резки кусков P11-P22, по меньшей мере, на одном листе стекла.
Эта программа включает в себя модуль, позволяющий оператору использовать клавиатуру или любой другое средством чтобы вводить в устройство 100 ограничения резки и ограничения размещения кусков, а также критерий оптимизации. Эти данные могут быть занесены в память на жесткий диск 106.
Эта программа включает в себя также модуль для создания алгоритма в виде дерева, содержащего «корневую систему», «листья», каждый из которых представляет полный план резки, позволяющий разрезать любые куски партии, тогда как каждый другой узел алгоритма представляет частичный план резки, причем план резки, связанный с узлом алгоритма, получают путем его добавления к частичному плану резки, связанному с исходным узлом данного узла, с учетом упомянутых ограничений, причем следующий кусок, принадлежащий упомянутому каркасу, определяют согласно заданной последовательности для этого каркаса.
В варианте воплощения, описанном здесь, узлы алгоритма занесены в оперативную память 103.
Программа PG включает в себя также модуль для выбора полного плана резки, связанного с «листом дерева», в зависимости от критерия оптимизации, занесенного в память на жесткий диск 106.
В описанном здесь варианте воплощения открытые узлы, то есть узлы, представляющие частичные планы резки, для которых продолжение посредством куска не было изучено, сохраняют в буфере в оперативной памяти.
В описанном здесь варианте воплощения, и как представлено на Фигуре 8, буферная память организована в форме диаграммы T с двумя входами в которой:
- строки позволяют классифицировать узлы согласно процентной доле поверхности потерь соответствующего плана резки;
- столбцы позволяют классифицировать узлы согласно процентной доле полезной поверхности соответствующего плана резки.
В примере на Фигуре 8, диаграмма включает в себя 20 строк и 20 столбцов, иными словами, шаг 5%. Величина этого шага имеет изменяемую конфигурацию и может быть различной для строк и столбцов.
Таким образом, в качестве примера, узел, связанный с частичным планом резки, имеющим 91% полезной поверхности и 6% поверхности потерь, будет сохранен в памяти в ячейке Tl.
Эта диаграмма обновляется при каждом создании узла.
В описанном здесь варианте воплощения, каждый открытый узел характеризуется:
- диаграммой, указывающей на то, какой следующий кусок доступен на каждом каркасе;
- размерами слева и справа для уровня гильотины 1, правее, соответственно, меток xll и xlr на Фигуре 7;
- размерами снизу и сверху для уровня гильотины 2, расположенного выше, соответственно, y2f и y2c;
- размером справа от последнего размещенного куска, x3
- размером выше последнего размещенного куска, y4.
Закрытый узел представлен в памяти номером каркаса последнего уложенного куска, а также направлением, в котором он был уложен.
В описанном здесь примере воплощения, ограничения размещения предполагают, в частности:
- что куски P11, P12 и P13 будут размещены в этом порядке на каркасе Cl; и
- что куски P21 и P22 будут размещены в этом порядке на каркасе C2.
А ограничения резки предполагают:
- максимум 4 уровней резки;
- минимальную протяженность обрезков;
- максимальную протяженность поперечных параметров (или уровней).
Фигуры 2A и 2B представляют два комплекта планов резки PDl, PD2, а именно (ФИГ. 2A) первый план резки PDl, в котором любые куски размещены на одном и том же листе PLF1, и второй план резки PD2, в котором куски размещены на двух листах PLF2, PLF3.
В качестве примера, на плане резки PDl Фигуры 2A выявлены:
- две резки для уровня 1, помеченные как dl, d2;
- две резки для уровня 2, помеченные как d3, d4
- резка для уровня 3, помеченная как d5.
В этом примере план резки PD1 для Фигуры 2A является предпочтительным перед планом резки PD2 Фигуры 2B, поскольку он минимизирует поверхность образующихся обрезков, представленную штриховыми линиями.
Фигура 3 представляет основные этапы способа оптимизации резки стекла, соответствующего первому варианту воплощения изобретения.
Применительно к этой Фигуре, способ включает в себя этап E5 определения ограничений резки и ограничений размещения упомянутых кусков, а также критерия оптимизации. Этот этап позволяет инициализировать способ с:
- количеством каркасов, в данном случае, двумя;
- порядком кусков P11-P13 и P21-P22 на этих каркасах;
- размером каждого куска;
- размером листов;
- максимальным количеством уровней резки, в частности, 4;
- минимальной протяженностью обрезков;
- максимальной протяженностью поперечных параметров; и
- критерием оптимизации.
За этапом инициализации E10 следует этап E10 создания первой Ll стадии алгоритма T планов резки.
Следует напомнить, что согласно изобретению полные планы резки представлены «листьями» алгоритма в виде дерева, причем родительские узлы листа представляют полный план резки, представляющие частичные планы резки PDP, позволяющие получать этот полный план резки.
Таким образом, согласно изобретению, начиная с корневой системы алгоритма в виде дерева T, каждый узел («дочерний») получают, начиная с предыдущего узла («родительского»), путем добавления к частичному плану резки, представленному этим родительским узлом, дополнительного куска, с учетом ограничений размещения и резки.
Комплект частичных планов, подходящих для первой Ll стадии алгоритма T, состоит из комплекта частичных планов, которые могут быть получены путем размещения первого куска, принадлежащего каждому из каркасов Cl или C2, а именно, куска P11 или куска P21, в углу листа стекла.
Как представлено на Фигуре 4, таким образом, получают четыре частичных плана резки PDPl-PDP4, в соответствии с которыми размещают кусок P11 или кусок P21, и в соответствии с которыми этот кусок размещают горизонтально или вертикально. На первой Ll стадии, каждый из этих частичных планов резки (представленный пунктирными линиями) включает в себя только лист стекла PLF1 (представленный сплошными линиями).
На этапе E35 создают «дочерние узлы» каждого из узлов согласно стадии Ll, и эти узлы составляют стадию L2 алгоритма T.
На Фигуре 4 подробно описаны «дочерние узлы» PDP1/1-PDP1/12 узла PDPl, но «дочерние узлы» PDP2/1-PDP4/12 узлов PDP2-PDP4 лишь представлены.
Частичные планы резки PDPl/1 получены из частичного плана резки PDPl:
- с учетом того, что куски, размещенные согласно частичному плану PDPl, были удалены с каркасов;
- с учетом того, что все планы резки, которые могут быть получены путем добавления к плану резки PDPl каждого из кусков, находящихся на каркасах Cl, C2 с учетом, таким образом, ограничений размещения и резки.
В примере по Фигуре 4, куски для каркасов Cl и C2, на выходе частичного плана резки PDPl, представляют собой кусок 12 для каркаса Cl и кусок 21 для каркаса C2. В этом примере допустимые планы резки, которые могут быть получены, исходя из частичного плана PDPl, путем размещения куска 12 или куска 21, являются следующими:
- план резки PDP1/1, полученный при размещении куска 12 справа от куска 11 в вертикальной позиции, причем этот план включает в себя только один лист PLF1;
- план резки PDP1/2, полученный при размещении куска 12 справа от куска 11 в горизонтальной позиции, причем этот план включает в себя только один лист PLF1;
- план резки PDP1/3, полученный при размещении куска 12 на куске 11 в горизонтальной позиции, причем этот план включает в себя только один лист PLF1;
- план резки PDP1/4, полученный при размещении куска 12 на куске 11 в вертикальной позиции, причем этот план включает в себя только один лист PLF1;
- план резки PDP1/5, полученный при размещении куска 21 справа от куска 11 в горизонтальной позиции, причем этот план включает в себя только один лист PLF1;
- план резки PDP1/6, полученный при размещении куска 21 справа от куска 11 в вертикальной позиции, причем этот план включает в себя только один лист PLF1;
- план резки PDP1/7, полученный при размещении куска 21 на куске 11 в горизонтальной позиции, причем этот план включает в себя только один лист PLF1;
- план резки PDP1/8, полученный при размещении куска 12 на куске 11 в вертикальной позиции, причем этот план включает в себя только один лист PLF1;
- план резки PDP1/9, полученный путем создания нового листа PLF2, включающего в себя кусок 12 в вертикальной позиции PLF;
- план резки PDP1/10, полученный путем создания нового листа PLF2, включающего в себя кусок 12 в горизонтальной позиции;
- план резки PDP1/11, полученный путем создания нового листа PLF2, включающего в себя кусок 21 в горизонтальной позиции;
- план резки PDP1/12, полученный путем создания нового листа PLF2, включающего в себя кусок 21 в вертикальной позиции.
В этом примере стадия L2 включает в себя также:
- все допустимые частичные планы резки PDP2/1-PDP2/12, которые могут быть получены путем добавления куска 12 или 21 к частичному плану резки PDP2;
- все допустимые частичные планы резки PDP3/1-PDP3/12, которые могут быть получены путем добавления куска 11 или 22 к частичному плану резки PDP3;
- все допустимые частичные планы резки PDP4/1-PDP4/12, которые могут быть получены путем добавления куска 11 или 22 к частичному плану резки PDP4.
Неоднократное итеративное повторение этого процесса до полного высвобождения каркасов Cl и C2 от их кусков (испытание E90) приводит к алгоритму T, состоящему из пяти стадий, при этом каждый из «листьев» соответствует полному плану резки, удовлетворяющему ограничениям резки и размещения. Полные планы резки PD1 и PD2 по Фигурам 2A и 2B составляют часть этих «листьев».
Способ согласно этому первому варианту воплощения включает в себя этап E100, в ходе которого среди всех листьев алгоритма T выбирают полный план резки, который минимизирует поверхность обрезков.
Этот план резки позволяет оптимизировать резку для листов стекла для составления каркасов Cl и C2.
Подробное описание второго варианта воплощения
Когда партии сложные, время расчета, необходимое для создания полного алгоритма T в соответствии с первым вариантом воплощения изобретения, может быть избыточно длительным.
Во втором конкретном варианте воплощения изобретения, который далее будет описан применительно к Фигуре 5, ограничивают общую продолжительность исполнения способа и отказываются от создания комплекта узлов алгоритма, с выбором при каждой итерации среди уже созданных узлов алгоритма, текущего узла, представляющего перспективный частичный план резки, «сыновние элементы» были созданы.
Этот способ может быть осуществлен с помощью устройства 100 определения, соответствующего изобретению, представленного на Фигуре 10, но в этом примере, программа PG содержит команды, позволяющие исполнять этапы, представленные на Фигуре 5.
В описанном здесь варианте воплощения, каждый открытый узел дополнительно характеризуется:
- номером каркаса, направлением размещения и положением последнего размещенного куска;
- «родительским» узлом, который соответствует частичному плану резки, без последнего размещенного куска; и
- серией вторичных признаков, корректируемых для управления прохождением алгоритма, а именно, получаемыми обрезками, площадью, занимаемой листом, соответствующей сумме площадей кусков согласно частичному плану, с учетом геометрических потерь, количеством используемых листов, его позицией по отношению к предыдущему куску (справа или сверху).
В конкретном описанном здесь варианте воплощения, способ включает в себя два критерия выбора, для выбора этого перспективного частичного плана резки, а именно:
- критерий, называемый «критерием минимальных отходов», состоящий в выборе среди всех уже созданных частичных планов резки того, для которого соотношение поверхность потерь/полезная поверхность минимальное;
- критерий, называемый «критерием максимальной поверхности», состоящий в выборе среди всех уже созданных частичных планов резки того, для которого больше важна полезная поверхность.
В описанном здесь варианте воплощения, после создания первой Ll стадии (см. этап E10 согласно первому варианту воплощения), критерий выбора, на этапе E20, инициализируется как «критерий минимальных отходов». В ходе того же самого этапа E20, счетчик времени устанавливается равным 0.
В описанном здесь варианте воплощения каждая итерация включает в себя общий этап E25, в ходе которого подтверждают, что он подходит для смены критерия выбора.
В конкретном варианте воплощения изобретения этот этап описан применительно к Фигуре 6.
На этапе E251 инициализируется величина TMAX, в зависимости от текущего критерия выбора. В этом примере, если текущий критерий выбора представляет собой «критерий минимальных отходов», TMAX равен 10 с, а если текущий критерий выбора представляет собой «критерий максимальной поверхности», TMAX равен 20 с.
На этапе E252 проверяется, превышает ли отсчет времени t, инициализированный на этапе E20, эту продолжительность TMAX. Если это не так, то общий этап E25 завершается без изменения критерия выбора или перезапуска отсчета времени t.
Если отсчет времени превышает продолжительность TMAX, то на этапе E253 определяется, какой критерий выбора должен быть использован для выбора следующего узла, у которого будут созданы «дочерние узлы». В описанном здесь варианте воплощения:
- критерий типа «критерия максимальной поверхности» сохраняется (этап E254), если текущим критерием является критерий типа «критерия минимальных отходов», или если количество узлов алгоритма T превышает предварительно заданную величину NMAX.
Для этой цели, в данном варианте воплощения используют общую переменную nb_noeuds, которая сохраняет в оперативной памяти 103 количество узлов алгоритма T, причем эта переменная в данном примере, в конце этапа E10 создания первой Ll стадии имеет величину 4;
- в других случаях сохраняется (этап E255) критерий типа «критерия минимальных отходов».
На этапе E256 отсчет времени t сбрасывается до 0, и общий этап E25 изменения критерия завершается.
Возвращаясь к Фигуре 5, на этапе E30 среди уже созданных узлов алгоритма выбирают текущий узел, в зависимости от критерия выбора, сохраненного на этапе E25:
- если критерий выбора представляет собой «критерий минимальных отходов», выбирают узел алгоритма, представляющий план резки, для которого соотношение поверхность потерь/полезная поверхность минимальное.
В конкретном варианте воплощения по Фигуре 8, это сводится к выбору узла, сохраненного в памяти в самой верхней ячейки диаграммы. Если несколько имеются несколько возможностей, то выбирают узел, находящийся в более правой ячейке (процент от максимальной полезной поверхности);
- если критерий выбора представляет собой «критерий максимальной поверхности», то выбирают узел алгоритма, представляющий план резки, для которого больше важна полезная поверхность. В конкретном варианте воплощения по Фигуре 8, это сводится к выбору узла, сохраненного в память в ячейке в правой части диаграммы. Если имеются несколько возможностей, то выбирают узел в верхней ячейке диаграммы (процент от минимальной поверхности потерь). На этапе E35, создают «дочерние узлы» текущего узла. Этот этап идентичен этапу E35, описанному применительно к Фигуре 3. На этом же этапе, рассчитывают и сохраняют в память атрибуты каждого из созданных узлов и обновляют переменную nb_noeuds, отвечающую за количество узлов алгоритма.
В данном варианте воплощения, на этапе E40 текущий узел удаляется.
На этапе E45 проверяют, являются ли один или несколько узлов, созданных на этапе E35, «листьями» алгоритма в виде дерева, иными словами содержат ли они комплект кусков, принадлежащих каркасам.
Если это так, то на этапе E50 сохраняют в памяти «лист», связанный с полным планом резки, соответствующим наилучшему решению, полученному до сих пор, т.е., в этом примере минимизируется поверхность обрезков. Другие «листья» могут быть отменены. При получении первого листа, этот «лист» сохраняется в памяти.
На этапе E55 проверяют, соответствует ли «лист», полученный на этапе E35, усовершенствованному решению, и если это так, то на этапе E60 алгоритма T отменяются все узлы, у которых поверхность получаемых обрезков превосходит поверхность потерь для этого «листа».
В описанном здесь варианте воплощения, способ оптимизации включает в себя этап E65, в ходе которого проверяют, не превосходит ли общая продолжительность исполнения способа предварительно заданную продолжительность DMAX, например, на час. Для этой цели можно использовать общий отсчет времени tps_calc, инициализированный на этапе E5.
Если на этапе E65 было выявлено, что продолжительность DMAX не была достигнута, то на этапе E25 определения критерия выбора следующего узла способ продолжается в виде цикла.
Когда определяют, что продолжительность DMAX была достигнута, способ возвращается к этапу E70 полного плана резки, соответствующего наилучшему решению, сохраненному в памяти на этапе E50.
Подробное описание третьего варианта воплощения
В конкретном варианте воплощения, способ оптимизации согласно изобретению избегает или минимизирует создание в алгоритме T узлов, соответствующих изоморфным частичным планам резки, а именно планов резки, включающих в себя одни и те же куски, имеющих одну и ту же поверхность получаемых обрезков и одни и те же значения для xll, x3, xlr, y2f, y4 и y2c.
В этом представленном здесь третьем варианте воплощения, на каждом этапе E35 создания узла, перед созданием узла удостоверяются, что он не представляет частичный или полный план резки, сходный по форме с планом резки, связанным с уже созданным узлом в алгоритме.
Для этого, в описанном здесь варианте воплощения, лексикографические правила добавляют к ограничениям размещения. Например, можно добавить два правила, согласно которым:
- если последний кусок размещен выше предыдущего, то номер каркаса этого последнего куска должен быть ниже номера каркаса предыдущего куска;
- если последний кусок размещен справа от предыдущего, номер каркаса этого последнего куска должен быть больше или равен номеру каркаса предыдущего куска.
Для снижения риска сохранения сходных по форме планов резки, также можно, например, принять решение открывать новый уровень 1, только если выполнено, по меньшей мере, одно из двух следующих условий:
- Условие 1: K предыдущих уровней 1 включают в себя, по меньшей мере, один кусок, который должен быть расположен на одном и том же каркасе. В качестве примера, применительно к Фигуре 2A, при K=2, куски из двух предыдущих уровней 1, представляют собой, соответственно, {Pli, P21, P22} и {P12, P13}; следовательно, каждый из этих уровней 1 включает в себя, по меньшей мере, один кусок, принадлежащий каркасу Cl, так, что выполняется условие 1;
- Условие 2: порядок каркасов для последнего куска, уложенного на Q последних уровней 1, повышается. В качестве примера, применительно к Фигуре 2A, при Q=2, последние куски, уложенные на два последних уровня 1, представляют собой, соответственно, P22 и P13; порядок каркасов (C2, Cl) понижается так, что условие 2 не выполняется.
1. Способ, выполняемый компьютером, для определения оптимизированного плана гильотинной резки партии прямоугольных стеклянных кусков, по меньшей мере, на одном листе стекла, причем куски должны быть после резки штабелированы, по меньшей мере, на одном каркасе (Ci), причем куски на каркасе необходимо размещать на упомянутом, по меньшей мере, одном листе для разрезания согласно заданной последовательности для данного каркаса, причем упомянутый способ включает в себя:
- этап (E5) определения ограничений резки и ограничений размещения упомянутых кусков, а также критерия оптимизации;
- создание (E10, E35) алгоритма в виде дерева (T), содержащего «корневую систему», «листья», каждый из которых представляет полный план резки, позволяющий разрезать любые куски из упомянутой партии, причем каждый другой узел алгоритма представляет частичный план резки, причем план резки связывают с получаемым (E35) узлом путем его добавления к частичному плану резки, связанному с исходным узлом данного узла, с учетом упомянутых ограничений, причем следующий кусок, принадлежащий упомянутому каркасу, определяют согласно заданной последовательности для этого каркаса; и
- этап (E100) выбора полного плана резки, связанного с листом дерева, в зависимости от упомянутого критерия оптимизации.
2. Способ по п. 1, в котором критерий оптимизации выбирают из:
- критерия, предназначенного для минимизации количества используемых листов для стекла;
- критерия, предназначенного для минимизации общей поверхности потерь, порождаемых резкой.
3. Способ по п. 1 или 2, в котором упомянутые ограничения резки могут быть выбраны из:
- максимального количества уровней резки;
- минимальной протяженности обрезков;
- максимальной протяженности уровня резки;
- направления первого разламывания.
4. Способ по любому из пп. 1-3, в котором упомянутые ограничения размещения могут быть выбраны из ориентации кусков на листе, положения относительно кусков на одном и том же листе, в зависимости от их уровня, и максимального количества упомянутых, по меньшей мере, одного листа стекла.
5. Способ по любому из пп. 1-4, характеризующийся тем, что узел алгоритма содержит максимум 9⋅m «дочерних узлов», причем m представляет собой количество каркасов, причем новый кусок можно выбирать для каждого каркаса с учетом ограничений размещения этого каркаса и добавлять к частичному плану резки девятью различными способами, а именно:
- справа от предыдущего куска (на уровне 3 резки), по горизонтали и по вертикали;
- выше предыдущего куска, если эти два последних куска обладают одной и той же протяженностью (на новом уровне 4 резки), причем среди горизонтальной или вертикальной позиции достаточно только одной, протяженность которой равна протяженности предыдущего куска;
- выше предыдущего куска, на левом конце текущего поперечника (на новом уровне 2 резки), по горизонтали и по вертикали;
- на новом поперечнике (на новом уровне 1 резки), по горизонтали и по вертикали;
- на новом листе, по горизонтали и по вертикали.
6. Способ по любому из пп. 1-5, в котором упомянутое создание алгоритма в виде дерева включает в себя:
- этап (E10), состоящий в создании под упомянутой корневой системой и для каждого из упомянутых каркасов (Cl, C2) узла, связанного с частичным планом резки для каждой из допустимых позиций первого куска, принадлежащего упомянутому каркасу, с учетом упомянутых ограничений; и
- по меньшей мере, одну итерацию, причем каждая итерация включает в себя:
- этап (E30) выбора текущего узла алгоритма, в зависимости от характеристик частичного плана резки, представленного этим узлом; и
- этап (E35) создания, по меньшей мере, одного «дочернего» узла упомянутого текущего узла, причем план резки, связанный с упомянутыми «дочерними» узлами, получают (E35) путем добавления к частичному плану резки, связанному с упомянутым текущим узлом, и с учетом упомянутых ограничений следующего куска, принадлежащего упомянутому каркасу, взятого согласно заданной последовательности для этого каркаса.
7. Способ по п. 6, характеризующийся тем, что он включает в себя этап (E60) прекращения упомянутых итераций, если продолжительность исполнения способа превышает заданную продолжительность (DMAX).
8. Способ по п. 6 или 7, характеризующийся тем, что упомянутый текущий узел выбирают (E30):
- согласно первому критерию, называемому «критерием минимальных отходов», состоящему в выборе узла, связанного с планом резки, для которого соотношение поверхность потерь и общей поверхности, занятой кусками, соответствующими упомянутому плану, минимальное; или
- согласно второму критерию, называемому «критерием максимальной поверхности», состоящему в выборе узла, связанного с планом резки, для которого больше важна полезная поверхность.
9. Способ по любому из пп. 1-8, в котором один «лист», связанный с полным планом резки, максимизирующим упомянутый критерий оптимизации, вводят в память (E50), при этом другие «листья» удаляют.
10. Способ по любому из пп. 1-9, характеризующийся тем, что он включает в себя этап (E60) удаления узлов алгоритма, связанных с частичными планами резки, для которых поверхность получаемых обрезков превосходит поверхность потерь полного плана резки, связанного с упомянутым «листом».
11. Способ по любому из пп. 1-10, характеризующийся тем, что упомянутые ограничения размещения включают в себя, по меньшей мере, одно лексикографическое ограничение, налагаемое на количество упомянутых каркасов, для предотвращения или минимизации создания узлов, соответствующих изоморфным частичным планам резки.
12. Способ по любому из пп. 1-11, в котором при каждом создании узла упомянутый узел классифицируют в зависимости, по меньшей мере, от одной характеристики плана резки, представленного этим узлом, причем упомянутой, по меньшей мере, одной характеристики достаточно для выбора упомянутого полного плана резки.
13. Способ по п. 6 или 12, в котором упомянутая, по меньшей мере, одна характеристика, используемая для упомянутого классифицирования, представляет собой упомянутую, по меньшей мере, одну характеристику, используемую в ходе упомянутого этапа выбора текущего узла алгоритма.
14. Устройство для определения оптимизированного плана гильотинной резки партии прямоугольных стеклянных кусков, по меньшей мере, на одном листе стекла (PLF), причем куски должны быть после резки штабелированы, по меньшей мере, на одном каркасе (Ci), причем куски на каркасе необходимо размещать на упомянутом, по меньшей мере, одном листе для разрезания согласно заданной последовательности для данного каркаса, причем упомянутое устройство включает в себя:
- модуль для определения ограничений резки и ограничений размещения упомянутых кусков, а также критерия оптимизации;
- модуль для создания алгоритма в виде дерева (T), содержащего «корневую систему», «листья», каждый из которых представляет полный план резки, позволяющий разрезать любые куски из упомянутой партии, причем каждый другой узел алгоритма представляет частичный план резки, причем план резки связывают с получаемым (E35) узлом путем его добавления к частичному плану резки, связанному с исходным узлом данного узла, с учетом упомянутых ограничений, причем следующий кусок, принадлежащий упомянутому каркасу, определяют согласно заданной последовательности для этого каркаса; и
- модуль для выбора полного плана резки, связанного с листом дерева алгоритма, в зависимости от упомянутого критерия оптимизации.
15. Считываемый компьютером (100) носитель записи (103), на котором записана компьютерная программа (PG), включающая в себя команды для исполнения этапов способа определения оптимизированного плана резки по любому из пп. 1-13, когда упомянутая программа исполняется компьютером.
16. Способ гильотинной резки партии прямоугольных стеклянных кусков, по меньшей мере, на одном листе стекла, характеризующийся тем, что он включает в себя:
- выполнение способа определения оптимизированного плана резки по любому из пп. 1-13;
причем упомянутый оптимизированный план используют в ходе стадии резки упомянутого листа и в ходе стадии разламывания упомянутого листа.
17. Способ резки по п. 16, в котором упомянутую партию определяют путем реализации способа определения оптимизированного плана резки по любому из пп. 1-13.
