Фрагментарные структуры в задаче двумерной упаковки в полуограниченную полосу
Рассмотрена общая задача двумерной упаковки в полуограниченную полосу. Показано, что ее можно рассматривать как задачу оптимизации на фрагментарной структуре, которая сводится к задаче комбинаторной оптимизации на множестве перестановок. Рассмотрены универсальный способ представления плоских фигур и...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2019 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2019
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/181439 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Фрагментарные структуры в задаче двумерной упаковки в полуограниченную полосу / И.В. Козин, C.Е. Батовский // Кибернетика и системный анализ. — 2019. — Т. 55, № 6. — С. 73–79. — Бібліогр.: 16 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860267544097587200 |
|---|---|
| author | Козин, И.В. Батовский, C.Е. |
| author_facet | Козин, И.В. Батовский, C.Е. |
| citation_txt | Фрагментарные структуры в задаче двумерной упаковки в полуограниченную полосу / И.В. Козин, C.Е. Батовский // Кибернетика и системный анализ. — 2019. — Т. 55, № 6. — С. 73–79. — Бібліогр.: 16 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Рассмотрена общая задача двумерной упаковки в полуограниченную полосу. Показано, что ее можно рассматривать как задачу оптимизации на фрагментарной структуре, которая сводится к задаче комбинаторной оптимизации на множестве перестановок. Рассмотрены универсальный способ представления плоских фигур и алгоритм их упаковки в полосу. Предложен способ модификации исходной задачи для достижимости оптимального решения.
Розглянуто загальну задачу двовимірного пакування в напівобмежену смугу. Показано, що її можна розглядати як задачу оптимізації на фрагментарній структурі, яка зводиться до задачі комбінаторної оптимізації на множині переставлень. Розглянуто універсальний спосіб представлення плоских фігур та алгоритм їхнього пакування в смугу. Запропоновано спосіб модифікації початкової задачі для досяжності оптимального розв’язку.
The paper considers a two-dimensional strip packing problem. It is shown that the problem can be considered as an optimization problem on a fragmented structure, which reduces to the problem of combinatorial optimization on a set of permutations. A universal approach of representing two-dimensional figures and the algorithm of their packing into the strip are considered. An approach to the modification of the original problem for the attainability of the optimal solution is proposed.
|
| first_indexed | 2025-12-07T19:03:04Z |
| format | Article |
| fulltext |
ÓÄÊ 519.87
È.Â. ÊÎÇÈÍ, C.Å. ÁÀÒÎÂÑÊÈÉ
ÔÐÀÃÌÅÍÒÀÐÍÛÅ ÑÒÐÓÊÒÓÐÛ Â ÇÀÄÀ×Å ÄÂÓÌÅÐÍÎÉ
ÓÏÀÊÎÂÊÈ Â ÏÎËÓÎÃÐÀÍÈ×ÅÍÍÓÞ ÏÎËÎÑÓ
Àííîòàöèÿ. Ðàññìîòðåíà îáùàÿ çàäà÷à äâóìåðíîé óïàêîâêè â ïîëóîãðàíè-
÷åííóþ ïîëîñó. Ïîêàçàíî, ÷òî åå ìîæíî ðàññìàòðèâàòü êàê çàäà÷ó îïòèìè-
çàöèè íà ôðàãìåíòàðíîé ñòðóêòóðå, êîòîðàÿ ñâîäèòñÿ ê çàäà÷å êîìáèíàòîð-
íîé îïòèìèçàöèè íà ìíîæåñòâå ïåðåñòàíîâîê. Ðàññìîòðåíû óíèâåðñàëüíûé
ñïîñîá ïðåäñòàâëåíèÿ ïëîñêèõ ôèãóð è àëãîðèòì èõ óïàêîâêè â ïîëîñó.
Ïðåäëîæåí ñïîñîá ìîäèôèêàöèè èñõîäíîé çàäà÷è äëÿ äîñòèæèìîñòè îïòè-
ìàëüíîãî ðåøåíèÿ.
Êëþ÷åâûå ñëîâà: äèñêðåòíàÿ îïòèìèçàöèÿ, ôðàãìåíòàðíàÿ ñòðóêòóðà, äâó-
ìåðíàÿ óïàêîâêà â ïîëîñó, ýâîëþöèîííûé àëãîðèòì.
ÂÂÅÄÅÍÈÅ
Çàäà÷à äâóìåðíîé óïàêîâêè êîíå÷íîãî íàáîðà ôèãóð â ïîëóîãðàíè÷åííóþ ïî-
ëîñó îòíîñèòñÿ ê ÷èñëó êëàññè÷åñêèõ çàäà÷ äèñêðåòíîé îïòèìèçàöèè. Äîêàçà-
íî, ÷òî â îáùåì ñëó÷àå çàäà÷à ÿâëÿåòñÿ NP-òðóäíîé [1] äàæå â òîì ñëó÷àå,
êîãäà óêëàäûâàåìûå ôèãóðû èìåþò äîñòàòî÷íî ïðîñòóþ ôîðìó, òàêóþ êàê
êðóãè èëè ïðÿìîóãîëüíèêè. Ïðè ýòîì çàäà÷à óêëàäêè â ïîëîñó âñòðå÷àåòñÿ
â ìíîãî÷èñëåííûõ ïðèëîæåíèÿõ, è ïîýòîìó ïðåäñòàâëÿþò èíòåðåñ àëãîðèòìû
ïîèñêà ïðèáëèæåííûõ ðåøåíèé ýòîé çàäà÷è ñ íåâûñîêîé âû÷èñëèòåëüíîé
ñëîæíîñòüþ.  ÷àñòíîñòè, õîðîøèå ïðèáëèæåííûå àëãîðèòìû ïîëó÷åíû íà
îñíîâå ðàçëè÷íûõ ìåòàýâðèñòèê, òàêèõ êàê ìåòîä òàáó [2], ãåíåòè÷åñêèé àëãî-
ðèòì [3–5], ìóðàâüèíûé àëãîðèòì [6, 7] è ðÿä äðóãèõ. Õîðîøèå ðåçóëüòàòû
äàåò ïîäõîä íà îñíîâå ãåîìåòðè÷åñêèõ ìåòîäîâ.
ÇÀÄÀ×À ÓÏÀÊÎÂÊÈ Â ÏÎËÓÎÃÐÀÍÈ×ÅÍÍÓÞ ÏÎËÎÑÓ
Ðàññìîòðèì èñïîëüçîâàíèå ôðàãìåíòàðíîé ìîäåëè äëÿ çàäà÷è äâóìåðíîé óïà-
êîâêè â ïîëóîãðàíè÷åííóþ ïîëîñó. Òàêîé ïîäõîä ÿâëÿåòñÿ óíèâåðñàëüíûì è
â ðÿäå ñëó÷àåâ ïîçâîëÿåò ïîëó÷èòü õîðîøèå ðåçóëüòàòû äëÿ ìíîãèõ âàæíûõ
ïðàêòè÷åñêèõ çàäà÷ óïàêîâêè.
Ïðîñòåéøèì ñëó÷àåì óïàêîâêè ÿâëÿåòñÿ óïàêîâêà ïðÿìîóãîëüíèêîâ. Ïî óñëî-
âèþ çàäàåòñÿ íåñêîëüêî âèäîâ ïðÿìîóãîëüíèêîâ è èõ êîëè÷åñòâî. Èçâåñòíà øèðèíà
ïîëóîãðàíè÷åííîé ïîëîñû, â êîòîðóþ óïàêîâûâàþòñÿ ôèãóðû. Íåîáõîäèìî îòû-
ñêàòü òàêîå ðàçìåùåíèå çàäàííûõ ïðÿìîóãîëüíèêîâ íà ïîëîñå, ïðè êîòîðîì âûñîòà
çàíÿòîé ÷àñòè ïîëîñû ÿâëÿåòñÿ ìèíèìàëüíîé. Ïðè ýòîì ïðÿìîóãîëüíèêè äîëæíû
ðàñïîëàãàòüñÿ ñòðîãî â ïðåäåëàõ ïîëîñû, íå ïåðåñåêàÿñü îäèí ñ äðóãèì. Ïî óñëîâèþ
çàäà÷è ìîæåò äîïóñêàòüñÿ âðàùåíèå ïðÿìîóãîëüíèêîâ ïîä ïðÿìûì óãëîì; ïðè
ýòîì ïîäðàçóìåâàåòñÿ, ÷òî ñòîðîíû êàæäîãî ðàçìåùàåìîãî ïðÿìîóãîëüíèêà ïàðàë-
ëåëüíû ñòîðîíàì ïîëîñû. Äëÿ ðåøåíèÿ äàííîé çàäà÷è ÷àñòî ïðåäëàãàëèñü ìåòîäû,
îñíîâàííûå íà èçâåñòíûõ ýâðèñòè÷åñêèõ àëãîðèòìàõ, òàêèõ êàê ãåíåòè÷åñêèé àë-
ãîðèòì [8, 9] èëè àëãîðèòì àäàïòèâíîãî ïîâåäåíèÿ ìóðàâüèíîé êîëîíèè [10],
à òàêæå îñíîâàííûå íà òî÷íûõ àëãîðèòìàõ, òàêèõ êàê ìåòîä âåòâåé è ãðàíèö ñ èñ-
ïîëüçîâàíèåì ìàòðè÷íîãî ïðåäñòàâëåíèÿ óïàêîâêè [11].
Áîëüøîå âíèìàíèå óäåëÿåòñÿ çàäà÷àì óïàêîâêè áîëåå ñëîæíûõ ôèãóð. Èíòåðåñ
ïðåäñòàâëÿþò çàäà÷à óïàêîâêè ïðÿìîóãîëüíèêîâ è êðóãîâ â ïîëóîãðàíè÷åííóþ ïî-
ëîñó [12], à òàêæå çàäà÷à óïàêîâêè êðóãîâ è íåâûïóêëûõ ìíîãîóãîëüíèêîâ â ïîëî-
ñó [13], â êîòîðîé ôîðìû çàäàííûõ ôèãóð ìîäåëèðóþòñÿ ñ ïîìîùüþ �-ôóíêöèé.
 íàñòîÿùåé ñòàòüå ðàññìàòðèâàåòñÿ îáùàÿ çàäà÷à äâóìåðíîé óïàêîâêè, íå
íàêëàäûâàþùàÿ íèêàêèõ îãðàíè÷åíèé íà ôîðìó çàäàâàåìûõ ôèãóð.  ýòîì
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 6 73
© È.Â. Êîçèí, C.Å. Áàòîâñêèé, 2019
ñëó÷àå íåîáõîäèìî èìåòü óíèâåðñàëüíûé ñïî-
ñîá ïðåäñòàâëåíèÿ ëþáîé äâóìåðíîé ôèãóðû,
êîòîðûé, â ñâîþ î÷åðåäü, ïîçâîëèë áû áûñòðî
îïðåäåëÿòü ïåðåñå÷åíèå îäíîé ôèãóðû ñ äðó-
ãîé ïðè èõ ðàçìåùåíèè â ïîëóîãðàíè÷åííîé
ïîëîñå. Îäèí èç òàêèõ ñïîñîáîâ îïèñàí â [9].
Èäåÿ ñîñòîèò â àïïðîêñèìàöèè ôîðìû ôèãóðû
ñ ïðåäñòàâëåíèåì åå â âèäå ìíîæåñòâà ýëåìåí-
òàðíûõ êâàäðàòîâ, ïëîòíî ïðèëåãàþùèõ îäèí
ê äðóãîìó (ðèñ. 1). Ðàçìåð ýëåìåíòàðíîãî
êâàäðàòà — ýòî ïàðàìåòð äåòàëèçàöèè, ïîçâî-
ëÿþùåé ñäåëàòü âûáîð ìåæäó ïðîñòîòîé ïðåä-
ñòàâëåíèÿ ôèãóðû è òî÷íîñòüþ åå ïðèáëèæå-
íèÿ. Íà ïðàêòèêå ðàçìåð ýëåìåíòàðíîãî êâàä-
ðàòà îáû÷íî âûáèðàåòñÿ òàêèì, ÷òîáû øèðèíà
ïîëîñû, â êîòîðóþ óïàêîâûâàþòñÿ ôèãóðû, ñîñòîÿëà èç öåëîãî ÷èñëà êâàäðàòîâ.
Çàäà÷ó ñ òàêèì ïðåäñòàâëåíèåì ôèãóð áóäåì íàçûâàòü êëåòî÷íîé àïïðîêñèìàöèåé.
Ïðè óïàêîâêå ôèãóð äîïóñêàþòñÿ ïîâîðîòû íà óãîë, êðàòíûé ïðÿìîìó, à òàêæå
îòðàæåíèÿ îòíîñèòåëüíî âåðòèêàëüíîé è ãîðèçîíòàëüíîé îñåé.
ÔÐÀÃÌÅÍÒÀÐÍÛÅ ÑÒÐÓÊÒÓÐÛ È ÈÕ ÑÂÎÉÑÒÂÀ
Îïðåäåëåíèå 1. Ôðàãìåíòàðíîé ñòðóêòóðîé ( , )X E íà êîíå÷íîì ìíîæåñòâå X
íàçûâàåòñÿ ñåìåéñòâî åãî ïîäìíîæåñòâ E E E En� { }1 2, , ,� , ãäå E Xi � , òàêîå,
÷òî � �E Ei , Ei � �, �e Ei , E e Ei \ { }� .
Ýëåìåíòû èç ìíîæåñòâà E íàçîâåì äîïóñòèìûìè ôðàãìåíòàìè. Îäíîýëå-
ìåíòíûå äîïóñòèìûå ôðàãìåíòû íàçûâàþòñÿ ýëåìåíòàðíûìè ôðàãìåíòàìè. Äî-
ïóñòèìûé ôðàãìåíò íàçîâåì ìàêñèìàëüíûì, åñëè îí íå ÿâëÿåòñÿ ïîäìíîæåñòâîì
íèêàêîãî äðóãîãî äîïóñòèìîãî ôðàãìåíòà. Î÷åâèäíî, ÷òî ïóñòîå ìíîæåñòâî ÿâ-
ëÿåòñÿ äîïóñòèìûì ôðàãìåíòîì. Áîëåå ïîäðîáíî ñâîéñòâà ôðàãìåíòàðíûõ
ñòðóêòóð ïðåäñòàâëåíû â [14, 15].
Ëþáîé ìàêñèìàëüíûé ôðàãìåíò ìîæíî ïîñòðîèòü èç ïóñòîãî ìíîæåñòâà, ïî-
ñëåäîâàòåëüíî äîáàâëÿÿ ê íåìó ýëåìåíòû òàê, ÷òîáû íà êàæäîì øàãå òàêîé ïðî-
öåäóðû ïîëó÷åííîå ïîäìíîæåñòâî áûëî äîïóñòèìûì ôðàãìåíòîì. Ýòî óñëîâèå
íàçîâåì óñëîâèåì ïðèñîåäèíåíèÿ.
Àëãîðèòì ïîñòðîåíèÿ ìàêñèìàëüíîãî ôðàãìåíòà:
1) íà íà÷àëüíîì øàãå âûáèðàåòñÿ ïóñòîå ìíîæåñòâî X 0 � �;
2) íà øàãå ñ íîìåðîì k
1âûáèðàåòñÿ ëþáîé ýëåìåíò x X X k� \ , óäîâëåòâî-
ðÿþùèé óñëîâèþ ïðèñîåäèíåíèÿ X x Ek � { }� ;
3) àëãîðèòì çàêàí÷èâàåò ðàáîòó, åñëè íà î÷åðåäíîì øàãå íå óäàëîñü íàéòè
ýëåìåíò x X X k� \ ñ òðåáóåìûì ñâîéñòâîì.
Î÷åâèäíà ñëåäóþùàÿ òåîðåìà.
Òåîðåìà 1. Åñëè � �A E è � �x X ñóùåñòâóåò àëãîðèòì ïîëèíîìèàëüíîé
òðóäîåìêîñòè ïî ÷èñëó ýëåìåíòîâ ìíîæåñòâà X äëÿ ïðîâåðêè óñëîâèÿ ïðèñîåäè-
íåíèÿ A x E� { }� , òî çàäà÷à ïîñòðîåíèÿ ìàêñèìàëüíîãî ôðàãìåíòà ÿâëÿåòñÿ ïî-
ëèíîìèàëüíî ðàçðåøèìîé.
Èçâåñòíî, ÷òî ðåçóëüòàò ðàáîòû àëãîðèòìà çàâèñèò îò ýëåìåíòîâ, êîòîðûå áóäóò
âûáèðàòüñÿ íà êàæäîì øàãå. ×òîáû ðåçóëüòàò áûë îäíîçíà÷íûì, äîñòàòî÷íî îïðåäå-
ëèòü íåêîòîðûé ëèíåéíûé ïîðÿäîê íà ìíîæåñòâå X è âûáèðàòü íà øàãå 2 àëãîðèòìà
ïåðâûé â ýòîì ïîðÿäêå ýëåìåíò, êîòîðûé óäîâëåòâîðÿåò óñëîâèþ ïðèñîåäèíåíèÿ.
Àëãîðèòì îòûñêàíèÿ ìàêñèìàëüíîãî ôðàãìåíòà â ôðàãìåíòàðíîé ñòðóêòóðå ïðè
çàäàííîì óïîðÿäî÷åíèè ýëåìåíòîâ â äàëüíåéøåì íàçîâåì ôðàãìåíòàðíûì àëãîðèòìîì.
Îïðåäåëåíèå 2. Óïîðÿäî÷åííîé ôðàãìåíòàðíîé ñòðóêòóðîé íà ìíîæåñòâå
X x x xn� { }1 2, , ,� íàçîâåì ñåìåéñòâî E ïîñëåäîâàòåëüíîñòåé { }( , , , )x x xi i ik1 2
�
ýëåìåíòîâ ìíîæåñòâà X òàêèõ, ÷òî åñëè ( , , , ) ,x x x Ei i ik1 2
� � òî è ëþáàÿ åå íà-
74 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 6
Ðèñ. 1. Ïðèìåð àïïðîêñèìàöèè ôèãóð
÷àëüíàÿ ïîäïîñëåäîâàòåëüíîñòü ( , , , )x x xi i im1 2
� , m k� , òàêæå ïðèíàäëåæèò E.
Ñîîòâåòñòâåííî ýëåìåíòû óïîðÿäî÷åííîé ôðàãìåíòàðíîé ñòðóêòóðû íàçîâåì
óïîðÿäî÷åííûìè ôðàãìåíòàìè.
Êàæäîé ôðàãìåíòàðíîé ñòðóêòóðå ìîæíî ñîïîñòàâèòü ìíîæåñòâî ðàçëè÷íûõ
óïîðÿäî÷åííûõ ôðàãìåíòàðíûõ ñòðóêòóð. Äëÿ óïîðÿäî÷åííîé ôðàãìåíòàðíîé
ñòðóêòóðû ðåçóëüòàò ðàáîòû ôðàãìåíòàðíîãî àëãîðèòìà îïðåäåëåí îäíîçíà÷íî.
Òàêèì îáðàçîì, çàäàåòñÿ îòîáðàæåíèå ìíîæåñòâà ïåðåñòàíîâîê S n èç n ýëåìåíòîâ
âî ìíîæåñòâî ìàêñèìàëüíûõ ôðàãìåíòîâ çàäàííîé ôðàãìåíòàðíîé ñòðóêòóðû. Ýòî
îòîáðàæåíèå, êîòîðîå íàçîâåì íàêðûâàþùèì îòîáðàæåíèåì, ñþðúåêòèâíî, ò.å.
êàæäûé ìàêñèìàëüíûé ôðàãìåíò ÿâëÿåòñÿ îáðàçîì íåêîòîðîé ïåðåñòàíîâêè.
ÇÀÄÀ×À ÎÏÒÈÌÈÇÀÖÈÈ ÍÀ ÔÐÀÃÌÅÍÒÀÐÍÎÉ ÑÒÐÓÊÒÓÐÅ
Ïóñòü çàäàíà ôðàãìåíòàðíàÿ ñòðóêòóðà E E E En� { }1 2, , ,� íà êîíå÷íîì ìíî-
æåñòâå X . Ïóñòü òàêæå îïðåäåëåíà ìîíîòîííàÿ ïî âêëþ÷åíèþ ôóíêöèÿ-êðèòå-
ðèé f E R: �
1, êîòîðàÿ êàæäîìó äîïóñòèìîìó ôðàãìåíòó ñòàâèò â ñîîòâåò-
ñòâèå íåêîòîðîå âåùåñòâåííîå ÷èñëî, ò.å. � �E E Ei j, èç óñëîâèÿ E Ei j� ñëå-
äóåò, ÷òî f E f Ei j( ) ( )� (èëè f E f Ei j( ) ( )
). Çàäà÷à îïòèìèçàöèè íà
ôðàãìåíòàðíîé ñòðóêòóðå çàêëþ÷àåòñÿ â îòûñêàíèè äîïóñòèìîãî ôðàãìåíòà
ñ ìàêñèìàëüíûì (èëè ìèíèìàëüíûì) çíà÷åíèåì êðèòåðèÿ. Î÷åâèäíî, îïòè-
ìàëüíûì ðåøåíèåì ýòîé çàäà÷è áóäåò îäèí èç ìàêñèìàëüíûõ ôðàãìåíòîâ. Ïî
êðàéíåé ìåðå, òàêîé ôðàãìåíò âñåãäà ïðèñóòñòâóåò ñðåäè îïòèìàëüíûõ ðåøå-
íèé. Òàêèì îáðàçîì, ëþáàÿ çàäà÷à îïòèìèçàöèè íà ôðàãìåíòàðíîé ñòðóêòóðå
ñ ìîíîòîííîé öåëåâîé ôóíêöèåé ìîæåò áûòü ñâåäåíà ê êîìáèíàòîðíîé çàäà÷å
îïòèìèçàöèè íà ìíîæåñòâå ïåðåñòàíîâîê.
ÔÐÀÃÌÅÍÒÀÐÍÀß ÑÒÐÓÊÒÓÐÀ ÇÀÄÀ×È ÄÂÓÌÅÐÍÎÉ ÓÏÀÊÎÂÊÈ.
ÄÎÑÒÈÆÈÌÎÑÒÜ ÎÏÒÈÌÀËÜÍÎÃÎ ÐÅØÅÍÈß
Ðàññìîòðèì îáùóþ çàäà÷ó äâóìåðíîé óïàêîâêè â ïîëóîãðàíè÷åííóþ ïîëîñó.
Ïóñòü çàäàíî ìíîæåñòâî ôèãóð { }f i , i n�1 2, , ,� , äèàìåòð êàæäîé èç êîòîðûõ
ìåíüøå øèðèíû ïîëîñû. Ïðåäïîëàãàåòñÿ, ÷òî â ïðîöåññå óêëàäêè â ïîëîñó
äîïóñêàþòñÿ âðàùåíèÿ ôèãóð íà óãîë, êðàòíûé ïðÿìîìó, è çåðêàëüíûå îòðà-
æåíèÿ. Âûïîëíèì ñëåäóþùèå ïðåîáðàçîâàíèÿ.
1. Ïðîâåäåì êëåòî÷íóþ àïïðîêñèìàöèþ çàäà÷è, ò.å. êàæäóþ çàäàííóþ ôèãóðó
çàìåíèì ôèãóðîé, ñîñòàâëåííîé èç ýëåìåíòàðíûõ êâàäðàòîâ ñî ñòîðîíîé �, ãäå �
— ïîëîæèòåëüíîå çàäàííîå ÷èñëî. Ôèãóðó ïîäáåðåì òàêèì îáðàçîì, ÷òîáû îíà
öåëèêîì ïîêðûâàëà çàìåíÿåìóþ ôèãóðó è ïðè ýòîì ÷òîáû åå ïëîùàäü áûëà ìèíè-
ìàëüíî âîçìîæíîé. Òàêîå ïðåîáðàçîâàíèå íàçîâåì êâàäðèðîâàíèåì. Íà êâàäðàòû
òàêîãî æå ðàçìåðà ðàçîáüåì ïîëóáåñêîíå÷íóþ ïîëîñó L, ïðåäïîëàãàÿ, ÷òî øèðèíà
ïîëîñû êðàòíà �; ïðè ýòîì ïîëîñà áåñêîíå÷íà ïî íàïðàâëåíèþ âíèç. Âåëè÷èíó �
â äàëüíåéøåì áóäåì ðàññìàòðèâàòü êàê åäèíèöó ìàñøòàáà, à ôèãóðû èç çàäàííîãî
ìíîæåñòâà ñ÷èòàòü ñîâïàäàþùèìè ñ èõ êëåòî÷íîé àïïðîêñèìàöèåé.
2. Êàæäîé êâàäðèðîâàííîé ôèãóðå { }f i , i n�1 2, , ,� , ñîïîñòàâèì íàáîð ôè-
ãóð { }f ij , êîòîðûå îòëè÷àþòñÿ îò íåå óãëîì ïîâîðîòà, êðàòíûì 90 �, è (èëè) çåð-
êàëüí³ì îòðàæåíèåì. Ýòîò íàáîð íàçîâåì ñâÿçàííûì íàáîðîì ôèãóðû { }f i .
Îáúåäèíåíèå âñåõ ñâÿçàííûõ íàáîðîâ áóäåì ðàññìàòðèâàòü êàê áàçîâîå ìíîæåñ-
òâî ôðàãìåíòàðíîé ñòðóêòóðû.
Êàæäûé ýëåìåíò áàçîâîãî ìíîæåñòâà õàðàêòåðèçóåòñÿ äâóìÿ èíäåêñàìè:
ïåðâûé îáîçíà÷àåò íîìåð ôèãóðû, à âòîðîé — íîìåð åå ýêçåìïëÿðà â ñâÿçàííîì
íàáîðå, ïîëó÷åííîì ïî ï. 2.
Îïèøåì òåïåðü TL-àëãîðèòì (top-left àëãîðèòì) ïîñòðîåíèÿ äâóìåðíîé óïà-
êîâêè. Â êàæäîé ôèãóðå îòìåòèì âåðõíþþ ëåâóþ êëåòêó. Âûáåðåì ïðîèçâîëü-
íóþ óïîðÿäî÷åííóþ ïîñëåäîâàòåëüíîñòü ôèãóð áàçîâîãî ìíîæåñòâà. Ôèãóðû ïî-
ñëåäîâàòåëüíîñòè ðàññìàòðèâàþòñÿ â çàäàííîì ïîðÿäêå. Íà î÷åðåäíîì øàãå âû-
áèðàåòñÿ ïåðâàÿ ïî ïîðÿäêó ôèãóðà fij
òàêàÿ, ÷òîáû â óïàêîâêå îòñóòñòâîâàëà
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 6 75
ôèãóðà èç áàçîâîãî íàáîðà ôèãóðû f i . Ðàçìåñòèì ôèãóðó f ij â óïàêîâêå
ñ ñîáëþäåíèåì ñëåäóþùèõ ïðàâèë:
— ôèãóðà öåëèêîì ðàñïîëîæåíà â ïîëîñå L, ïðè÷åì êëåòêè ôèãóðû ñîâïà-
äàþò ñ êëåòêàìè ïîëîñû;
— âíóòðåííîñòü ôèãóðû íå ïåðåñåêàåòñÿ ñ âíóòðåííîñòÿìè óæå óïàêîâàí-
íûõ ôèãóð;
— îòìå÷åííàÿ êëåòêà ôèãóðû çàíèìàåò ìåñòî, ñîîòâåòñòâóþùåå íàèáîëåå
âûñîêîé è êðàéíåé ñëåâà ñâîáîäíîé êëåòêå ïîëîñû.
Ïðîöåññ óïàêîâêè çàêàí÷èâàåòñÿ, êîãäà âñå ôèãóðû ïîñëåäîâàòåëüíîñòè áó-
äóò ïðîñìîòðåíû. Çíà÷åíèå öåëåâîé ôóíêöèè äëÿ çàäàííîé ïîñëåäîâàòåëüíîñòè
ôèãóð — ýòî âûñîòà ïîñòðîåííîé óïàêîâêè.
Çàìåòèì, ÷òî õîòÿ àëãîðèòì óïàêîâêè ñõîäèòñÿ äëÿ êàæäîé çàäàííîé ïîñëå-
äîâàòåëüíîñòè ôèãóð, íå âñåãäà ñ ïîìîùüþ ýòîãî àëãîðèòìà ìîæíî ïîëó÷èòü
îïòèìàëüíîå ðåøåíèå çàäà÷è.
Òàê, ðàññìîòðèì òðè ôèãóðû (ðèñ. 2) è ïîëîñó ñ øèðèíîé, ðàâíîé ñåìè. Áàçî-
âîå ìíîæåñòâî â ýòîì ñëó÷àå ñîñòîèò èç øåñòè ýëåìåíòîâ. Îïòèìàëüíûì ðåøå-
íèåì çàäà÷è ÿâëÿåòñÿ ëþáàÿ èç óïàêîâîê, ïîêàçàííûõ íà ðèñ. 3. Óïàêîâêè íå ìî-
ãóò áûòü ïîëó÷åíû ïóòåì ïðèìåíåíèÿ âûøåîïèñàííîãî àëãîðèòìà íè ïðè êàêîé
ïåðåñòàíîâêå ôèãóð èç áàçîâîãî ìíîæåñòâà.
Áóäåì ñ÷èòàòü, ÷òî ôðàãìåíòàðíàÿ ñòðóêòóðà çàäà÷è óïàêîâêè îáëàäàåò ñâîé-
ñòâîì äîñòèæèìîñòè, åñëè õîòÿ áû îäíà îïòèìàëüíàÿ óïàêîâêà ìîæåò áûòü ïîëó-
÷åíà ïóòåì ïðèìåíåíèÿ TL-àëãîðèòìà ê íåêîòîðîé ïîñëåäîâàòåëüíîñòè ýëå-
ìåíòîâ áàçîâîãî ìíîæåñòâà. Ïîêàæåì òåïåðü, ÷òî ñóùåñòâóåò êëàññ çàäà÷ äâóìåð-
íîé óïàêîâêè è äëÿ êàæäîé çàäà÷è èìååò ìåñòî ñâîéñòâî äîñòèæèìîñòè. Ïóñòü
øèðèíà ïîëîñû ðàâíà W, à âûñîòà óïàêîâêè ôèãóð ìíîæåñòâà { }f i , i n�1 2, , ,� ,
ðàâíà H . Óïàêîâêó íàçîâåì ïëîòíîé, åñëè ñóììàðíàÿ ïëîùàäü âñåõ ôèãóð óïà-
êîâêè ðàâíà â òî÷íîñòè W H� . Î÷åâèäíî, ïëîòíàÿ óïàêîâêà ÿâëÿåòñÿ îïòèìàëü-
íîé ïî êðèòåðèþ âûñîòû.
Òåîðåìà 2. Åñëè äëÿ çàäà÷è óïàêîâêè â ïîëóîãðàíè÷åííóþ ïîëîñó ñóùåñò-
âóåò îïòèìàëüíîå ðåøåíèå â âèäå ïëîòíîé óïàêîâêè, òî ôðàãìåíòàðíàÿ ñòðóêòó-
ðà ýòîé çàäà÷è îáëàäàåò ñâîéñòâîì äîñòèæèìîñòè.
Äîêàçàòåëüñòâî. Ïóñòü äëÿ çàäà÷è óïàêîâêè â ïîëóîãðàíè÷åííóþ ïîëîñó
ñóùåñòâóåò îïòèìàëüíîå ðåøåíèå â âèäå ïëîòíîé óïàêîâêè. Ðàññìîòðèì ýòó óïà-
êîâêó è ïîñòðîèì ïîñëåäîâàòåëüíîñòü ôèãóð ïî ñëåäóþùåìó àëãîðèòìó. Â ïîëî-
ñå âûáèðàåòñÿ âåðõíÿÿ ëåâàÿ êëåòêà. Ââèäó ïëîòíîñòè óïàêîâêè ýòà êëåòêà òàêæå
ÿâëÿåòñÿ âåðõíåé ëåâîé êëåòêîé îäíîé èç ôèãóð áàçîâîãî ìíîæåñòâà. Ýòó ôèãóðó
äîáàâëÿåì â ïîñëåäîâàòåëüíîñòü è «âûðåçàåì» èç óïàêîâêè âìåñòå ñ ñîîòâåòñòâó-
þùåé ÷àñòüþ ïîëîñû. Ïðîäîëæàåì òàêèì îáðàçîì âîçäåéñòâîâàòü íà îñòàâøóþ-
ñÿ ÷àñòü ïîëîñû äî òåõ ïîð, ïîêà âñå ôèãóðû óïàêîâêè íè áóäóò óäàëåíû. Ðåçóëü-
òàòîì ðàáîòû àëãîðèòìà è áóäåò òðåáóåìàÿ ïîñëåäîâàòåëüíîñòü áàçîâûõ ôèãóð.
Ðàññìîòðèì òåïåðü ïðîèçâîëüíóþ çàäà÷ó óïàêîâêè â ïîëóîãðàíè÷åííóþ ïî-
ëîñó. Ìíîæåñòâî ôèãóð { }f i , i n�1 2, , ,� , ýòîé çàäà÷è âñåãäà ìîæíî äîïîëíèòü
êîíå÷íûì íàáîðîì îäíîêëåòî÷íûõ ôèãóð
òàêèì îáðàçîì, ÷òîáû èçìåíåííàÿ çàäà÷à
äîïóñêàëà ïëîòíóþ óïàêîâêó. Äåéñòâèòåëüíî,
çàäàäèì ïðîèçâîëüíóþ óïàêîâêó âûñîòû H , êî-
òîðàÿ ÿâëÿåòñÿ äîïóñòèìûì ðåøåíèåì çàäà÷è.
Âñå ñâîáîäíûå êëåòêè â ó÷àñòêå ïîëîñû âûñî-
òû H çàïîëíèì îäíîêëåòî÷íûìè ôèãóðàìè.
Ýòà óïàêîâêà ïî îïðåäåëåíèþ ÿâëÿåòñÿ ïëîò-
íîé. Ñîïîñòàâèì êàæäîé óïàêîâêå U âûñîòû H
÷èñëî k U WH S f i
i
n
( ) ( )� �
�
�
1
, ãäå S f i( ) — ïëî-
ùàäü ñîîòâåòñòâóþùåé ôèãóðû. Òîãäà ìèíè-
76 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 6
Ðèñ. 2. Áàçîâîå ìíîæåñòâî ôèãóð
Ðèñ. 3. Îïòèìàëüíûå óïàêîâêè
ìóì kmin âåëè÷èíû k U( ) äîñòèãàåòñÿ íà îïòèìàëüíîé óïàêîâêå. Òàêèì îáðàçîì,
âîçìîæåí ñëåäóþùèé àëãîðèòì ïîèñêà îïòèìàëüíîé óïàêîâêè. Ê èñõîäíîìó
ìíîæåñòâó ôèãóð äîáàâëÿþòñÿ kmin îäíîêëåòî÷íûõ ôèãóð. Îòûñêèâàåòñÿ ïåðå-
ñòàíîâêà ôèãóð, äëÿ êîòîðîé ñ ïîìîùüþ TL-àëãîðèòìà ìîæíî ïîñòðîèòü ïëîò-
íóþ óïàêîâêó. Èç ïîñòðîåííîé ïëîòíîé óïàêîâêè óäàëÿþòñÿ kmin îäíîêëåòî÷-
íûõ ôèãóð. Ïîëó÷åííàÿ óïàêîâêà ôèãóð â ïîëóîãðàíè÷åííóþ ïîëîñó è áóäåò
îïòèìàëüíîé ïî âûñîòå óïàêîâêîé.
Ê ñîæàëåíèþ, ÷èñëî kmin çàðàíåå íåèçâåñòíî, è, òàêèì îáðàçîì, çàäà÷ó ìîæ-
íî ðåøàòü òîëüêî ïîäáîðîì, èñïîëüçóÿ âìåñòî ÷èñëà kmin åãî âåðõíþþ îöåíêó.
ÌÅÒÀÝÂÐÈÑÒÈÊÈ ÍÀ ÔÐÀÃÌÅÍÒÀÐÍÎÉ ÑÒÐÓÊÒÓÐÅ
 [14] ïîêàçàíî, ÷òî íàëè÷èå ôðàãìåíòàðíîé ñòðóêòóðû çàäà÷è ïîçâîëÿåò ïðè-
ìåíèòü ðÿä èçâåñòíûõ ìåòàýâðèñòèê äëÿ îòûñêàíèÿ ïðèáëèæåííîãî ðåøåíèÿ
çàäà÷è. Ê òàêèì ìåòàýâðèñòèêàì îòíîñÿòñÿ ýâîëþöèîííûé àëãîðèòì íà ôðàã-
ìåíòàðíîé ñòðóêòóðå è àëãîðèòì ìóðàâüèíîé êîëîíèè.
Äëÿ ïðîâåðêè ýôôåêòèâíîñòè óêàçàííûõ ìåòàýâðèñòèê ïðèìåíèòåëüíî ê çà-
äà÷å îá óïàêîâêå äâóìåðíûõ ôèãóð â ïîëóîãðàíè÷åííóþ ïîëîñó áûë ðàññìîòðåí
ðÿä èçâåñòíûõ â ëèòåðàòóðå ïðèìåðîâ. Ïåðâûé ïðèìåð ðàññìîòðåí â ðàáîòå [9].
Ïî óñëîâèþ çàäà÷è áûëè îïðåäåëåíû äåâÿòü âèäîâ ôèãóð è èõ êîëè÷åñòâî
(ðèñ. 4). Ïîñëå àïïðîêñèìàöèè ôèãóð ñ òàêîé æå òî÷íîñòüþ áûëà çàäàíà øèðèíà W
ïîëóáåñêîíå÷íîé ïîëîñû, ðàâíàÿ 46 ýëåìåíòàðíûì êâàäðàòàì, ÷òîáû ñîîòâåò-
ñòâîâàòü ðåøåíèþ, ïîëó÷åííîìó â [9]. Ðåøåíèå ýòîé çàäà÷è äàåò çíà÷åíèå âûñî-
òû óïàêîâêè H � 51. Ðåøåíèå, êîòîðîå áûëî ïîëó÷åíî ïîñëå 350 èòåðàöèé àëãî-
ðèòìà ìóðàâüèíîé êîëîíèè, óëó÷øàåò ðåøåíèå èç ðàáîòû [9] çíà÷åíèåì H � 43
(ðèñ. 5). Ëó÷øåå ðåøåíèå ýòîé çàäà÷è, ïîëó÷åííîå ñ ïîìîùüþ ýâîëþöèîííîãî
àëãîðèòìà íà ôðàãìåíòàðíîé ñòðóêòóðå, òàêæå äàåò çíà÷åíèå H � 43.
 êà÷åñòâå âòîðîãî ïðèìåðà âçÿòà çàäà÷à, ðàññìîòðåííàÿ â ðàáîòå [16], ðåøå-
íèå, ïîëó÷åííîå â íåé, èçîáðàæåíî â ìàñøòàáå íà ðèñ. 6 íàñòîÿùåé ñòàòüè.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 6 77
10 ýêç.
10 ýêç.
10 ýêç.
10 ýêç.
10 ýêç.
10 ýêç.
10 ýêç.
10 ýêç.
20 ýêç.
Ðèñ. 4. Ôîðìà çàäàííûõ ôèãóð è èõ êîëè÷åñòâî
Ðèñ. 5. Ðåøåíèå çàäà÷è ñ ïîìîùüþ
ýâîëþöèîííîãî àëãîðèòìà
Ðèñ. 6. Èñõîäíîå ðåøåíèå çàäà÷è
0
43 l�
� – 27.7
Áûëà ðàññìîòðåíà êëåòî÷íàÿ àïïðîêñèìàöèÿ çàäà÷è, ãäå ýëåìåíòàðíûì
êâàäðàòîì ÿâëÿåòñÿ îäèí ïèêñåëü. Ðåøåíèÿ, ïîëó÷åííûå ñ ïîìîùüþ ýâîëþöèîí-
íîãî àëãîðèòìà íà ôðàãìåíòàðíîé ñòðóêòóðå, îòðàæåíû íà ðèñ. 7 â ìàñøòàáå.
ÇÀÊËÞ×ÅÍÈÅ
Ðàññìîòðåííûé â íàñòîÿùåé ñòàòüå ïîäõîä ïîçâîëÿåò ñâåñòè îáùóþ çàäà÷ó
äâóìåðíîé óïàêîâêè â ïîëóîãðàíè÷åííóþ ïîëîñó, â êîòîðîé îòñóòñòâóþò êà-
êèå-ëèáî îãðàíè÷åíèÿ íà ôîðìó ôèãóð, ê çàäà÷å êîìáèíàòîðíîé îïòèìèçàöèè,
÷òî, â ñâîþ î÷åðåäü, ïîçâîëÿåò ïðèìåíèòü èçâåñòíûå ìåòàýâðèñòèêè äëÿ ïîèñ-
êà ïðèáëèæåííûõ ðåøåíèé çà ïðèåìëåìîå âðåìÿ. Ïðåäñòàâëåííûå ïðàêòè÷åñ-
êèå ðåçóëüòàòû ïîêàçûâàþò ýôôåêòèâíîñòü ðàáîòû ìåòàýâðèñòèê (â ÷àñòíîñòè,
ãåíåòè÷åñêîãî àëãîðèòìà è àëãîðèòìà ìóðàâüèíîé êîëîíèè), êîòîðûå îñíîâà-
íû íà ôðàãìåíòàðíîé ñòðóêòóðå çàäà÷è.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ãýðè Ì., Äæîíñîí Ä. Âû÷èñëèòåëüíûå ìàøèíû è òðóäíîðåøàåìûå çàäà÷è. Ìîñêâà: Ìèð,
1982. 416 ñ.
2. Glover F., Taillard E., de Werra D. A user’s guide to tabu search. Annals of Operation Research.
1993. Vol. 41, Iss. 1. P. 1–28.
3. Holland J.H. Adaptation in natural and artificial systems. Boston, MA: MIT Press, 1992. 288 p.
4. Êóðåé÷èê Â.Ì. Ãåíåòè÷åñêèå àëãîðèòìû. Ñîñòîÿíèå. Ïðîáëåìû. Ïåðñïåêòèâû. Èçâåñòèÿ
ÐÀÍ. Òåîðèÿ è ñèñòåìû óïðàâëåíèÿ. 1999. ¹ 1. Ñ. 144–160.
5. Gonñalves J.F. A hybrid genetic algorithm-heuristic for a two-dimensional orthogonal packing
problem. European Journal of Operational Research. 2007. Vol. 183, N 3. P. 1212–1229.
6. Øòîâáà Ñ.Ä. Ìóðàâüèíûå àëãîðèòìû: òåîðèÿ è ïðèìåíåíèå. Ïðîãðàììèðîâàíèå. 2005. ¹ 4.
Ñ. 1–16.
78 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 6
Ðèñ. 7. Íîâûå ðåøåíèÿ çàäà÷è ñ ïîìîùüþ ýâîëþöèîííîãî àëãîðèòìà
Y
X
X
7. Dorigo Ì. Optimization, learning, and natural algorithms. PhD Thesis, Dipartimento di Elettronica,
Politechnico di Milano, Italy, 1992. 140 p.
8. Lodi A., Martello S., Monaci M. Two-dimensional packing problems: A survey. European Journal
of Operation Research. 2002. Vol. 141, N 2. P. 241–252.
9. Jain S., Gea H.C. Two dimensional packing problems using genetic algorithms. Engineering with
Computers. 1998. Vol. 14, N 3. P. 206–213.
10. Âàíèäîâñêèé Â.À., Ëåáåäåâ Î.Á. Äâóìåðíàÿ óïàêîâêà â ïîëóîãðàíè÷åííóþ ïîëîñó íà îñíîâå
ìîäåëèðîâàíèÿ àäàïòèâíîãî ïîâåäåíèÿ ìóðàâüèíîé êîëîíèè. Èçâåñòèÿ ÞÔÓ. Òåõíè÷åñêèå
íàóêè. 2014. ¹ 7 (156). Ñ. 34–42.
11. Êàðòàê Â.Ì. Çàäà÷à óïàêîâêè ïðÿìîóãîëüíèêîâ. Òî÷íûé àëãîðèòì íà áàçå ìàòðè÷íîãî ïðåä-
ñòàâëåíèÿ. Âåñòíèê ÓÃÀÒÓ. 2007. Ò. 9, ¹ 4 (22). Ñ. 104–110.
12. Ðóäíåâ À.Ñ. Âåðîÿòíîñòíûé ïîèñê ñ çàïðåòàìè äëÿ çàäà÷è óïàêîâêè êðóãîâ è ïðÿìîóãîëüíè-
êîâ â ïîëîñó. Äèñêðåòíûé àíàëèç è èññëåäîâàíèå îïåðàöèé. 2009. Ò. 16, ¹ 4. C. 61–86.
13. Ñòîÿí Þ.Ã., Çëîòíèê Ì.Â. Ðàçìåùåíèå êðóãîâ è íåâûïóêëûõ ìíîãîóãîëüíèêîâ ñ ïîâîðîòàìè
â ïðÿìîóãîëüíèêå ìèíèìàëüíîé äëèíû. Äîïîâ³ä³ Íàö³îíàëüíî¿ àêàäå쳿 íàóê Óêðà¿íè. 2007.
¹ 2. Ñ. 37–42.
14. Êîçèí È.Â., Ìàêñèøêî Í.Ê., Ïåðåïåëèöà Â.À. Ôðàãìåíòàðíûå ñòðóêòóðû â çàäà÷àõ äèñêðåò-
íîé îïòèìèçàöèè. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. 2017. Ò. 53, ¹ 6. C. 125–131.
15. Êîçèí È.Â. Ýâîëþöèîííî-ôðàãìåíòàðíàÿ ìîäåëü çàäà÷è óïàêîâêè ïåíòàìèíî. Äèñêðåòíûé
àíàëèç è èññëåäîâàíèå îïåðàöèé. 2014. Ò. 21, ¹ 6. C. 35–50.
16. Ðîìàíîâà Ò.Å., Ñòóïàê Å.À., Çëîòíèê Ì.Â. Ìàòåìàòè÷åñêàÿ ìîäåëü è ìåòîä ðåøåíèÿ çàäà÷è
îïòèìèçàöèè óïàêîâêè ïðîèçâîëüíûõ äâóìåðíûõ îáúåêòîâ â ïðÿìîóãîëüíûõ îáëàñòÿõ. Äîïîâ³ä³
Íàö³îíàëüíî¿ àêàäå쳿 íàóê Óêðà¿íè. 2009. ¹ 1. Ñ. 48–53.
Íàä³éøëà äî ðåäàêö³¿ 16.11.2018
².Â. Êîç³í, Ñ.ª. Áàòîâñüêèé
ÔÐÀÃÌÅÍÒÀÐͲ ÑÒÐÓÊÒÓÐÈ Â ÇÀÄÀײ ÄÂÎÂÈ̲ÐÍÎÃÎ ÏÀÊÓÂÀÍÍß
Ó ÍÀϲÂÎÁÌÅÆÅÍÓ ÑÌÓÃÓ
Àíîòàö³ÿ. Ðîçãëÿíóòî çàãàëüíó çàäà÷ó äâîâèì³ðíîãî ïàêóâàííÿ â íàï³âîáìå-
æåíó ñìóãó. Ïîêàçàíî, ùî ¿¿ ìîæíà ðîçãëÿäàòè ÿê çàäà÷ó îïòèì³çàö³¿ íà
ôðàãìåíòàðí³é ñòðóêòóð³, ÿêà çâîäèòüñÿ äî çàäà÷³ êîìá³íàòîðíî¿ îïòèì³çàö³¿
íà ìíîæèí³ ïåðåñòàâëåíü. Ðîçãëÿíóòî óí³âåðñàëüíèé ñïîñ³á ïðåäñòàâëåííÿ
ïëîñêèõ ô³ãóð òà àëãîðèòì ¿õíüîãî ïàêóâàííÿ â ñìóãó. Çàïðîïîíîâàíî ñïîñ³á
ìîäèô³êàö³¿ ïî÷àòêîâî¿ çàäà÷³ äëÿ äîñÿæíîñò³ îïòèìàëüíîãî ðîçâ’ÿçêó.
Êëþ÷îâ³ ñëîâà: äèñêðåòíà îïòèì³çàö³ÿ, ôðàãìåíòàðíà ñòðóêòóðà, äâîâèì³ðíå
ïàêóâàííÿ ó ñìóãó, åâîëþö³éíèé àëãîðèòì.
I.V. Kozin, S.E. Batovskiy
FRAGMENTARY STRUCTURES IN TWO-DIMENSIONAL STRIP PACKING PROBLEM
Abstract. The paper considers a two-dimensional strip packing problem. It is
shown that the problem can be considered as an optimization problem on
a fragmented structure, which reduces to the problem of combinatorial
optimization on a set of permutations. A universal approach of representing
two-dimensional figures and the algorithm of their packing into the strip are
considered. An approach to the modification of the original problem for the
attainability of the optimal solution is proposed.
Keywords: discrete optimization, fragmentary structure, two-dimensional strip
packing, evolutionary algorithm.
Êîçèí Èãîðü Âèêòîðîâè÷,
äîêòîð ôèç.-ìàò. íàóê, ïðîôåññîð, ïðîôåññîð êàôåäðû Çàïîðîæñêîãî íàöèîíàëüíîãî óíèâåðñèòåòà,
e-mail: ainc00@gmail.com.
Áàòîâñêèé Ñåðãåé Åâãåíüåâè÷,
àñïèðàíò Çàïîðîæñêîãî íàöèîíàëüíîãî óíèâåðñèòåòà, e-mail: maxishko@ukr.net.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 6 79
|
| id | nasplib_isofts_kiev_ua-123456789-181439 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1019-5262 |
| language | Russian |
| last_indexed | 2025-12-07T19:03:04Z |
| publishDate | 2019 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Козин, И.В. Батовский, C.Е. 2021-11-17T14:01:11Z 2021-11-17T14:01:11Z 2019 Фрагментарные структуры в задаче двумерной упаковки в полуограниченную полосу / И.В. Козин, C.Е. Батовский // Кибернетика и системный анализ. — 2019. — Т. 55, № 6. — С. 73–79. — Бібліогр.: 16 назв. — рос. 1019-5262 https://nasplib.isofts.kiev.ua/handle/123456789/181439 519.87 Рассмотрена общая задача двумерной упаковки в полуограниченную полосу. Показано, что ее можно рассматривать как задачу оптимизации на фрагментарной структуре, которая сводится к задаче комбинаторной оптимизации на множестве перестановок. Рассмотрены универсальный способ представления плоских фигур и алгоритм их упаковки в полосу. Предложен способ модификации исходной задачи для достижимости оптимального решения. Розглянуто загальну задачу двовимірного пакування в напівобмежену смугу. Показано, що її можна розглядати як задачу оптимізації на фрагментарній структурі, яка зводиться до задачі комбінаторної оптимізації на множині переставлень. Розглянуто універсальний спосіб представлення плоских фігур та алгоритм їхнього пакування в смугу. Запропоновано спосіб модифікації початкової задачі для досяжності оптимального розв’язку. The paper considers a two-dimensional strip packing problem. It is shown that the problem can be considered as an optimization problem on a fragmented structure, which reduces to the problem of combinatorial optimization on a set of permutations. A universal approach of representing two-dimensional figures and the algorithm of their packing into the strip are considered. An approach to the modification of the original problem for the attainability of the optimal solution is proposed. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системний аналіз Фрагментарные структуры в задаче двумерной упаковки в полуограниченную полосу Фрагментарні структури в задачі двовимірного пакування у напівобмежену смугу Fragmentary structures in two-dimensional strip packing problem Article published earlier |
| spellingShingle | Фрагментарные структуры в задаче двумерной упаковки в полуограниченную полосу Козин, И.В. Батовский, C.Е. Системний аналіз |
| title | Фрагментарные структуры в задаче двумерной упаковки в полуограниченную полосу |
| title_alt | Фрагментарні структури в задачі двовимірного пакування у напівобмежену смугу Fragmentary structures in two-dimensional strip packing problem |
| title_full | Фрагментарные структуры в задаче двумерной упаковки в полуограниченную полосу |
| title_fullStr | Фрагментарные структуры в задаче двумерной упаковки в полуограниченную полосу |
| title_full_unstemmed | Фрагментарные структуры в задаче двумерной упаковки в полуограниченную полосу |
| title_short | Фрагментарные структуры в задаче двумерной упаковки в полуограниченную полосу |
| title_sort | фрагментарные структуры в задаче двумерной упаковки в полуограниченную полосу |
| topic | Системний аналіз |
| topic_facet | Системний аналіз |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/181439 |
| work_keys_str_mv | AT koziniv fragmentarnyestrukturyvzadačedvumernoiupakovkivpoluograničennuûpolosu AT batovskiice fragmentarnyestrukturyvzadačedvumernoiupakovkivpoluograničennuûpolosu AT koziniv fragmentarnístrukturivzadačídvovimírnogopakuvannâunapívobmeženusmugu AT batovskiice fragmentarnístrukturivzadačídvovimírnogopakuvannâunapívobmeženusmugu AT koziniv fragmentarystructuresintwodimensionalstrippackingproblem AT batovskiice fragmentarystructuresintwodimensionalstrippackingproblem |