ОБЩИЕ СВЕДЕНИЯ
ИРНAP05133090, Номер госрегистрации0118РК00155
НаименованиеВычислительная сложность задач гильотинного прямоугольного раскроя
Приоритетное направлениеИнформационные, телекоммуникационные и космические технологии, научные исследования в области естественных наук/Научные исследования в области естественных наук
Вид исследованияФундаментальное
ЗаявительРеспубликанское государственное предприятие на праве хозяйственного ведения "Институт информационных и вычислительных технологий"
Научный руководительArslanov Marat Z.
Балл ГНТЭ23
Общая одобренная сумма36000000
Решение ННС
Ожидаемые результаты
Разработка математических моделей, численных методов, эффективных алгоритмов задачи определения выпуклой комбинации допустимых решений для гильотинного раскроя прямоугольника на меньшие прямоугольники с двумя высотами при наличии ограничений на количество каждого прямоугольника (2D cutting stock problem) с целью определения вычислительной сложности этой задачи, т.е. принадлежности ее или классу задач P (задачи, решаемые за время, ограниченное полиномом от размеров задачи на детерминированной машине Тьюринга) или классу задач NP (задачи, решаемые за время, ограниченное полиномом от размеров задачи на недетерминированной машине Тьюринга)
Разработка математических моделей, численных методов, эффективных алгоритмов задачи гильотинного раскроя прямоугольника на меньшие равные прямоугольники при наличии ограничений на ширину гильотины для определения вычислительной сложности этой задачи, т.е. принадлежности ее или классу задач P или классу задач NP.
Реферат (Абстракт) - 2018 год
Объект исследования, разработки или проектирования
задачи прямоугольного раскроя, алгоритмы уменьшения параметров в прямоугольном раскрое.
Цель работы
Разработка математических моделей, численных методов, эффективных алгоритмов задачи определения выпуклой комбинации допустимых решений для гильотинного раскроя прямоугольника на меньшие прямоугольники с двумя высотами при наличии ограничений на количество каждого прямоугольника с целью определения вычислительной сложности этой задачи.
Методы исследования
выбор соответствующего аппарата теории чисел (метод непрерывных дробей, дроби Фарея), теории графов (задача о кратчайшем пути), теории алгоритмов и методов линейного целочисленного программирования, коммутативной алгебры.
Полученные результаты и новизна
задачи построения выпуклой оболочки множества допустимых решений для прямоугольного раскроя были сформулированы впервые. Получены существенные результаты в этой области: полиномиальные алгоритмы для задачи построения выпуклой оболочки множества допустимых решений для раскроя прямоугольника на прямоугольники с двумя высотами.
Разработаны и исследованы методы, модели и полиномиальные алгоритмы построения выпуклой оболочки решений задачи раскроя прямоугольника на прямоугольники с двумя высотами. Определена вычислительная сложность задачи построения выпуклой оболочки множества допустимых решений для раскроя прямоугольника на прямоугольники с двумя высотами.
Основные конструктивные и технико экономические показатели
получен 1 патент и 1 авторское свидетельство.
Область применения
экономия материальных ресурсов типа стекла, фанеры, бумаги, проката; модели раскроя, связанные с экономией финансовых ресурсов, вычислительных ресурсов процессорного времени и памяти, а также в области проектирование сверхбольших интегральных схем.
Реферат (Абстракт) - 2019 год
Объект исследования, разработки или проектирования
задачи прямоугольного раскроя, алгоритмы уменьшения параметров в прямоугольном раскрое.
Цель работы
Разработка математических моделей, численных методов, эффективных алгоритмов задачи оптимального гильотинного раскроя прямоугольника на равные меньшие прямоугольники при наличии ограничения на ширину лезвия гильотины с целью определения вычислительной сложности этой задачи.
Методы исследования
выбор соответствующего аппарата теории чисел (метод непрерывных дробей, дроби Фарея), теории графов (задача о кратчайшем пути), теории алгоритмов и методов линейного целочисленного программирования, коммутативной алгебры.
Полученные результаты и новизна
впервые доказана принадлежность задачи оптимального гильотинного раскроя прямоугольника на равные меньшие прямоугольники при наличии ограничения на ширину лезвия гильотины множеству задач, решаемых полиномиальным алгоритмом на недетерминированной машине Тьюринга.
Основные конструктивные и технико экономические показатели
получен 3 патент и 2 авторское свидетельство.
Область применения
экономия материальных ресурсов типа стекла, фанеры, бумаги, проката; модели раскроя, связанные с экономией финансовых ресурсов, вычислительных ресурсов процессорного времени и памяти, а также в области проектирование сверхбольших интегральных схем.
Реферат (Абстракт) - 2020 год
Объект исследования, разработки или проектирования
задачи прямоугольного раскроя, алгоритмы уменьшения параметров в прямоугольном раскрое.
Цель работы
Разработка математических моделей, численных методов, эффективных алгоритмов задачи определения выпуклой комбинации допустимых решений для гильотинного раскроя прямоугольника на меньшие прямоугольники с двумя высотами и на два прямоугольника при наличии ограничений на количество каждого прямоугольника с целью определения вычислительной сложности этой задачи
Методы исследования
выбор соответствующего аппарата теории чисел (метод непрерывных дробей, дроби Фарея), теории графов (задача о кратчайшем пути), теории алгоритмов и методов линейного целочисленного программирования, коммутативной алгебры.
Полученные результаты и новизна
впервые доказана принадлежность задачи оптимального гильотинного раскроя прямоугольника на равные меньшие прямоугольники при наличии ограничения на ширину лезвия гильотины множеству задач, решаемых полиномиальным алгоритмом на недетерминированной машине Тьюринга.
Основные конструктивные и технико экономические показатели
2 авторских свидетельства.
Область применения
экономия материальных ресурсов типа стекла, фанеры, бумаги, проката; модели раскроя, связанные с экономией финансовых ресурсов, вычислительных ресурсов процессорного времени и памяти, а также в области проектирование сверхбольших интегральных схем.
Реферат (Абстракт) - 2020 год
Объект исследования, разработки или проектирования
задачи прямоугольного раскроя, алгоритмы уменьшения параметров в прямоугольном раскрое.
Цель работы
Разработка математических моделей, численных методов, эффективных алгоритмов задачи определения выпуклой комбинации допустимых решений для гильотинного раскроя прямоугольника на меньшие прямоугольники с двумя высотами и на два прямоугольника при наличии ограничений на количество каждого прямоугольника с целью определения вычислительной сложности этой задачи
Методы исследования
выбор соответствующего аппарата теории чисел (метод непрерывных дробей, дроби Фарея), теории графов (задача о кратчайшем пути), теории алгоритмов и методов линейного целочисленного программирования, коммутативной алгебры.
Полученные результаты и новизна
впервые доказана принадлежность задачи оптимального гильотинного раскроя прямоугольника на равные меньшие прямоугольники при наличии ограничения на ширину лезвия гильотины множеству задач, решаемых полиномиальным алгоритмом на недетерминированной машине Тьюринга.
П
Основные конструктивные и технико экономические показатели
2 авторских свидетельства.
Область применения
экономия материальных ресурсов типа стекла, фанеры, бумаги, проката; модели раскроя, связанные с экономией финансовых ресурсов, вычислительных ресурсов процессорного времени и памяти, а также в области проектирование сверхбольших интегральных схем.