Перевод названия: A CONSTRUCTIVE HEURISTIC FOR THE PROBLEM OF TWO-DIMENSIONAL GUILLOTINE PACKING
Тип публикации: статья из журнала
Год издания: 2019
Ключевые слова: двухмерная упаковка, Гильотинный раскрой, эвристика, оптимизация, two-dimensional bin packing, guilliotine cut, heuristic, optimisation
Аннотация: Задачи рационального раскроя-упаковки давно привлекают внимание исследователей и практиков в различных отраслях производства. Их относят к NP-полным задачам. Многочисленные исследования в этой области показали, что одной из основных проблем является их разнообразие и специфика. Предложены различные методы их решения. Для сравнения Показать полностьюэффективности различных методов на однотипном классе задач определяют коэффициент раскроя. Для задачи двумерной упаковки - это процентное соотношение суммарной площади всех размещенных предметов к площади затраченного материала. Однако важным вопросом при оценке того или иного метода является время решения. Это связано с тем, что в виду NP-полноты и большом количестве малых и больших предметов временные характеристики значительны. В данной работе в качестве основной рассмотрена двухмерная ортогональная гильотинная упаковка в листы одинакового размера. Существенной особенностью рассматриваемой задачи являются технологические ограничения. Необходимо разместить все прямоугольники различного размера и количества, однако шаблон размещения должен быть одинаков для всех листов. Таким образом необходимо за приемлемое время минимизировать количество листов. В работе представлен эвристический алгоритм. Проведённые вычислительные эксперименты подтверждают эффективность предложенного метода. The tasks of rational cutting-packaging have long attracted the attention of researchers and practitioners in various industries. They are classified as NP-complete problems. Numerous studies in this area have shown that one of the main problems is their diversity and specificity. Various methods for solving them are proposed. To compare the effectiveness of various methods on the same class of tasks, the cutting coefficient is determined. For the task of two-dimensional packaging, this is the percentage of the total area of all placed items to the area of the spent material. However, an important issue in evaluating a particular method is the decision time. This is due to the fact that, in view of the NP-completeness and a large number of small and large objects, the temporal characteristics are significant. In this paper, two-dimensional orthogonal guillotine packaging in sheets of the same size is considered as the main one. An essential feature of the problem under consideration is technological limitations. You must place all the rectangles of different sizes and quantities, however, the layout template should be the same for all sheets. Thus, it is necessary to minimize the number of sheets in an acceptable time. The paper presents a heuristic algorithm. The performed computational experiments confirm the effectiveness of the proposed method.
Журнал: Информатизация и связь
Выпуск журнала: № 5
Номера страниц: 110-113
ISSN журнала: 20788320
Место издания: Москва
Издатель: Автономная некоммерческая организация "Редакция журнала "Информатизация и связь"