Теоретическое и прикладное значение задач раскроя/упаковки

[Rasool]

Когда-то давно я имел дело с задачами раскроя/упаковки. Сейчас есть возможность использовать новые методы машинного обучения для решения этих задач. Меня интересует теоретическое и прикладное значение задач дискретной оптимизации, в частности задач одномерного, двумерного, многомерного раскроя/упаковки. (Например, задача коммивояжера имеет такой теоретический смысл: если задачу коммивояжера полиномиально свести к задаче "X", то можно сделать вывод, что задача "X" NP-полная). Спрашиваю для того, чтобы иметь мотивацию для изучения литературы в этой области (на это уйдет приблизительно около года, не менее того). Хочу выяснить, стоит ли овчинка выделки.
Спрашивал в Гугле, но конкретного ответа не нашел.

[_Swetlana]

Чисто для дальнейшей информации.
В Уфе в УГАТУ Мухачева Элита Александровна создала большую научную школу, все занимаются именно этим: раскроем и упаковкой. Например, А.Ф. Валеева (когда-то на кафедру пришёл автореферат её кандидатской диссертации, писала отзыв), сейчас погуглила - она уже доктор:
http://novtex.ru/IT/it2006/number11_pril.htm
Смотрите оглавление журнала Информационные технологии, там много статей на эту тему. В начале любой статьи (и автореферата) будет и теоретическое, и прикладное значение, стандартный зачин.

Мне лично эти задачи никогда не нравились, поэтому замотивировать не могу
С чем имела дело в качестве учебной задачи - одномерная упаковка. Задача об упаковке в минимальное число контейнеров (см., например, Гэри, Джонсон) прекрасно решается приближённым FFD-алгоритмом, оценка погрешности известна, на реальных данных FFD работает практически как точный. Применяется при изготовлении пластиковых окон - минимизация используемых заготовок.

P.S. Только сейчас заметила, что вы из Уфы. Зачем у гугла-то спрашивать. У них, видимо, есть какие-то спецсеминары, там и спросить можно у специалистов.

[Rasool]

_Swetlana в сообщении #1529441 писал(а):

Чисто для дальнейшей информации.
P.S. Только сейчас заметила, что вы из Уфы. Зачем у гугла-то спрашивать. У них, видимо, есть какие-то спецсеминары, там и спросить можно у специалистов.

У Э.А.Мухачевой защитилось больше десятка кандидатов и докторов наук, ее ученики работают в Германии, Австралии. Но сама Элита Александровна скончалась где-то в 2011-м году. Сейчас знаю следующих раскройщиков: д.т.н. М.А.Верхотуров - сейчас зав. кафедрой в УГАТУ, д.ф.-м.н. В.М.Картак - тоже зав. кафедрой УГАТУ, внучка Элиты Александровны - А.С.Филиппова - зав. кафедрой в БГПУ. В УГАТУ на кафедре ВМиК сейчас работает д.т.н. А.Ф.Валеева.
У меня сейчас лежит на компе монография Э.А.Мухачевой по раскрою/упаковке нулевых годов.

Цитата:

http://novtex.ru/IT/it2006/number11_pril.htm

Спасибо за ссылку.

[_Swetlana]

Ссылка, наверно, не самая удачная, что первое нагуглилось.
По поводу раскроя ещё одно замечание, вернее, случай из жизни.

(Оффтоп)

Мой школьный товарищ и одновременно коллега преподаёт линейное программирование.
Тут подвернулся хоздоговор, связанный с двумерным раскроем, он стал его делать, естественно, линейным программированием. Сделали, деньги получили, докладывает мой товарищ на местной конференции, тут я, чтобы немножко его подначить, спрашиваю:
- Вот скажи, какая у вас вычислительная сложность алгоритма? Как долго программа-то считает?
И получаю гениальный ответ:
- Заказчика устраивает.

[Mihaylo]

Rasool в сообщении #1529439 писал(а):

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

Да, действительно, таких решений нет (именно с использованием методов МО). Есть только генетические алгоритмы, которые хорошо ложатся на переборные алгоритмы.

Мне так ощущается (умозрительно), что человек может достаточно хорошо предсказывать, куда примерно разместить тот или иной прямоугольник (двумерная укладка). Однако это предположение годится лишь в качестве приближенного решения для другого алгоритма, который "втискает" эти прямоугольники в полосу или минимальное пространство (в зависимости от формулировки задачи)...

Короче, можно взять "фирменные" уфимские блочные алгоритмы укладки, прогнать через методы МО, получить первоначальное приближение, затем добить с помощью ГА. Может быть мутации производить также с элементами МО? Приведет ли это к существенному повышению эффективности алгоритма?

-- 24.08.2021, 09:09 --

Укладка/раскрой несколько "агрессивная" среда для методов МО. Тут вроде есть элементы линейности, но они слабые. Произвольное решение не годится, так как функционал качества очень жесткий. Очень много дискретности и нелинейности.

Укладка заключается в выборе прямоугольника из списка и укладка его в пространстве. Вот выбор прямоугольника как-то еще ложится под МО, однако жадные алгоритмы тоже неплохи в этом деле...

[Rasool]

В диссертациях, которые защищались в УГАТУ по раскрою/упаковке, есть стандартный текст про актуальность проблемы:

Цитата:

Исследование технологических процессов в различных отраслях промышленности показывает, что многие из этапов заготовительного производства связаны с раскроем и размещением деталей. Эти процессы являются очень важными с точки зрения экономии ресурсов и сложными для принятия ре-шений. Возникают оптимизационные задачи раскроя и упаковки в процессе планирования и заказа материалов, а также на этапе оперативного проекти-рования карт раскроя и упаковки. Принятие оптимального или близкого к нему решения позволяет существенно сокращать расход материала и пони-зить себестоимость продукции.

Еще указывается, что

Цитата:

Задача упаковки прямоугольников в несколько полос заключается в следующем: имеется несколько полубесконечных вертикальных полос, вообще говоря, различной ширины, и набор открытых прямоугольников. Требуется найти ортогональное размещение этих прямоугольников в полосы (без пересечений и вращений, боковые стороны прямоугольников параллельны сторонам полос), имеющее минимальную высоту (высота есть максимум по всем прямоугольникам и по всем полосам расстояний от дна полосы до верхней грани прямоугольников). Эта задача возникает, например, при распределении ресурсов в глобальных вычислительных сетях GRID, объединяющих различные вычислительные ресурсы (кластеры). Проблема оптимального размещения задач на группе кластеров имеет простую геометрическую интерпретацию (см. [15]). Кластер можно представить как бесконечную в одну сторону полосу определенной ширины (ширина характеризует число процессоров кластера, другое измерение соответствует времени), а задачу - как прямоугольник с высотой и шириной, равными времени выполнения и требуемому числу процессоров соответственно. Тогда естественно возникает задача упаковки данного множества задач (прямоугольников) в несколько полос (кластеров), требование, что прямоугольники не должны пересекаться означает, что каждая задача на некоторое время (равное высоте прямоугольника) занимает некоторое число процессоров (равное ширине прямоугольника).

С. Н. Жук, "Об онлайн-алгоритмах упаковки прямоугольников в несколько полос".
Еще есть такое приложение:

Цитата:

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

http://intsys.msu.ru/invest/packer3d/
Пока все. Насчет теоретического применения задач раскроя/упаковки по типу применения задачи коммивояжера в теории NP-полных задач я не нашел.

[_Swetlana]

Из статьи 2011 года, где анализируются имеющиеся программы раскроя ленты холодного проката. Уфы там почему-то нет.
1. Китайские исследователи CuiYaodong и YuHongfang рассмотрели двумерную задачу оптимального раскроя материала при вырезке деталей
сложной конфигурации. Ими предложен алгоритм программирования раскроя, согласно которому детали вначале группируются в прямоугольные модули, которые далее располагаются в пределах разрезаемого материала с учетом минимума отходов.
2. Испанской компанией ManufacturasAlfe разработана программа автоматизированной подготовки производства для линий продольной резки рулонной стали. Программа называется системой PAC-L и преследует цель оптимизации процесса резки с улучшением качества, точности (в пределах 0,01 мм) и уменьшением производственных затрат.

Готовые программные продукты:
1. ПС: «Управление предприятием» является типовым (универсальным) решением для комплексной автоматизации функций учета и управления на предприятиях различных сфер деятельности. Модуль «Раскрой» обеспечивает автоматизацию учета и управления производственными операций, предполагающих раскрой и резку материалов. Интеграция с программами оптимизации раскроя (прямоугольный и фигурный раскрой) обеспечивает комплексную автоматизацию заготовительного производства.
2. Программа Астра Раскрой предназначена для оптимизации раскроя листовых материалов. Обеспечивает быстрый ввод информации о заказах и материалах; автоматическое и ручное формирование карт раскроя; полный учет мерных остатков и их раскрой в последующих заказах; печать карт раскроя и спецификаций.
3. Программа ТЕХТРАН Раскрой листового материала предназначена для комплексного решения задач прямоугольного раскроя листовых материалов. Она сочетает возможности системы подготовки управляющих программ с функциями организации производственного процесса. Может использоваться применительно к резке металла гильотинными ножницами, резке стекла, распиловке листового материала из дерева и пластика.
4. Программы семейства Cutting (Cutting 3, Cutting 3 GlassUnit, CuttingLine) предназначены для оптимального раскроя материала на прямоугольные или линейные детали. Программы могут быть использованы в деревообрабатывающем производстве, производстве мебели, рубки металла, резки стекла и т.д. В основу программ положен алгоритм, позволяющий быстро произвести раскрой с минимальными отходами. Основным критерием выбран принцип минимизации отходов.
5. Программа eCutout предназначена для автоматизации раскроя листовых материалов. Использование программы делает раскрой эффективным и экономит рабочее время технолога. Программа позволяет создавать и редактировать задание на раскрой, назначать технологические ограничения, формировать и распечатывать карты раскроя и статистическую информацию о задании. Поддерживается также ручное редактирование карт раскроя.

-- 24.08.2021, 19:53 --

Rasool в сообщении #1529494 писал(а):

Насчет теоретического применения задач раскроя/упаковки по типу применения задачи коммивояжера в теории NP-полных задач я не нашел.

А зачем вам это? У вас есть какая-то реальная задача, и вы хотите доказать её NP-полноту методом полиномиального сведения к ней именно какой-то известной задачи раскроя или упаковки?
Коммивояжера действительно часто используют для доказательства NP-полноты различных реальных задач, например, для задач планирования производства, план - та же последовательность. Не ради доказательства, а для уверенности, что рассматриваемую реальную задачу составления плана не решить за полиномиальное время.

[Mihaylo]

_Swetlana
Известно, ТС давно ищет научную тему для исследования, с целью написания диссертации и т.д.

[_Swetlana]

Коммивояжера ещё используют для тестирования различных эвристических алгоритмов, у немцев даже сайт специальный есть, с наборами данных.
Видимо, то же можно сделать и с задачей упаковки/раскроя, тестировать на ней разные эвристические алгоритмы.

[Rasool]

Mihaylo в сообщении #1529549 писал(а):

_Swetlana
Известно, ТС давно ищет научную тему для исследования, с целью написания диссертации и т.д.

Давно уже нет. Диссертация и ученая степень мне ни к чему (по крайней мере, российская), а вот публикация не помешает. Например, для резюме, CV, Researchgate, LinkedIn, Habr. Ну, если Хирш будет повышенный, будет совсем хорошо (только это маловероятно).
По поводу применения методов машинного обучения в раскрое-упаковке. Известный в среде ИИ профессор Горбань говорил, что при появлении новых технологий (как, например, Fuzzy-logic, генетические алгоритмы, многослойные нейронные сети обратного распространения ошибки, алгоритмов отжига и т.д.) кандидаты и доктора наук пересматривают старый материал своих диссертаций и начинают писать новые научные статьи о применении новых методов в старых задачах в соавторстве со своими учениками, которым еще нужна ученая степень. Сейчас тоже самое наблюдается в области машинного обучения, нейронных сетей глубокого обучения и т.д., поэтому нужно ковать железо, пока горячо, пока другие не опубликовали аналогичные статьи. Просто у меня вызывает сомнение научная и практическая значимость задач раскроя-упаковки. Ну, если расширить круг затрагиваемых задач до вообще задач комбинаторной оптимизации, то все может быть.

[Mihaylo]

Rasool в сообщении #1529554 писал(а):

Просто у меня вызывает сомнение научная и практическая значимость задач раскроя-упаковки.

Почему? Вот я сейчас занимаюсь потихоньку одним таким реальным проектом. Меня правда устроили простейшие эвристические жадные алгоритмы, т.к. они неплохие по результату, простые, быстрые.
https://www.cyberforum.ru/algorithms/thread2859162.html

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

[Rasool]

Rasool в сообщении #1529554 писал(а):

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

Да у меня появилась простецкая (и возможно глупая) идея для исследования:
Сделать возможную цепочку применений (проверить, возникают ли соответствующие задачи):
1. Попробовать применить машинное обучение в многошаговых (например, Марковских) процессах принятия решений (Reinforcement learning for combinatorial optimization).
2. Попробовать применить многошаговые процессы принятия решений в теории игр.
3. Есть статья по применению динамического программирования в теории игр (монография Б. И. Моделя "Элементы теории многошаговых процессов последовательного выбора решений").
4. Возможно, это удастся применить в маркетинге (хотя там вряд ли могут возникнуть задачи многошагового процесса принятия решений как, скажем, в шахматах).

[Rasool]

Rasool в сообщении #1530393 писал(а):

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

Во всяком случае, простое гугление запроса "multi-step decision making process" почти ничего не дал.

[Rasool]

Rasool в сообщении #1530427 писал(а):

Rasool в сообщении #1530393 писал(а):

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

Во всяком случае, простое гугление запроса "multi-step decision making process" почти ничего не дал.

Прошу прощения я делал запрос "multi-step decision making process in marketing".

[Mihaylo]

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