Прямоугольный негильотинный раскрой на основе алгоритма поиска оптимальных элементов тема диссертации и автореферата по ВАК РФ 05.13.16, кандидат физико-математических наук Ефимова, Татьяна Евгеньевна

• Ефимова, Татьяна Евгеньевна
• кандидат физико-математических наук
• 1999

Оглавление диссертации кандидат физико-математических наук Ефимова, Татьяна Евгеньевна

Введение.

Общая характеристика работы.

Содержание диссертации.

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

Точные методы решения задачи прямоугольного негильотинного раскроя.

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

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

ГлаваЗ. Постановка задачи прямоугольного негильотинного раскроя и описание алгоритмов ее решения.

3.1. Постановка задачи.

3.2. Алгоритм поиска оптимального раскроя.

3.2.1. Описание алгоритма поиска оптимального раскроя.

3.2.2. Применение алгоритма поиска оптимального раскроя для получения оптимального раскроя на сетке.

3.2.3. Правила о порядке размещения сравнимых прямоугольников алгоритмом поиска оптимального раскроя и о порядке размещения прямоугольников.

3.2.4. Сокращение перебора при замене функции, определяемой критерием укладки, на оценочную функцию.

3.2.5. Применение алгоритма поиска оптимального раскроя для получения оптимальной плотной укладки.

3.2.6. Правила сокращения перебора при работе АПОР на множестве плотных укладок.

3.2.7. Оценочные функции.

3.2.8. Генератор задач прямоугольного раскроя.

3.3. Алгоритм поиска плотной укладки.

3.3.1. Описание алгоритма поиска плотной укладки.

3.3.2. Правило о порядке размещения прямоугольников.

3.3.3. Сравнение работы АППУ со способом последовательно-одиночного размещения Стояна Ю.Г. на конкретном примере.

3.4. Алгоритм поиска оптимального раскроя с верхней границей.

Глава 4. Тестирование.

Введение диссертации (часть автореферата) на тему «Прямоугольный негильотинный раскрой на основе алгоритма поиска оптимальных элементов»

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

В настоящее время достаточно хорошо изучены задачи нефигурного (линейного и прямоугольного гильотинного) раскроя. Это объясняется простой формой заготовок и тем, что разрешаются только сквозные резы, параллельные кромкам листа.

Задача прямоугольного негильотинного раскроя, которая рассматривается в диссертации, относится к классу МР-полных проблем, поэтому поиск оптимального решения этой задачи является весьма трудоемким. Несмотря на это, на практике часто возникает необходимость в его получении (например, при раскрое дорогостоящих материалов).

Для получения оптимального решения задачи прямоугольного негильотинного раскроя на множестве размешений п, п=0,1,.,т прямоугольников (т - количество прямоугольников) на заданном листе, покрытом сеткой, и на множестве плотных укладок, полученных плотным размещением п, п=0,1,.,т прямоугольников на листе, в данной работе предлагается применять Алгоритм Поиска Оптимального Раскроя модификацию алгоритма минимизации функций, заданных на нормально разворачиваемых частично упорядоченных множествах (алгоритма поиска оптимальных элементов), и показано, что такое применение возможно.

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

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

Разработанные к настоящему времени точные и приближенные алгоритмы решения задачи прямоугольного негильотинного раскроя ориентированы в основном на получение одного оптимального или близкого к нему решения. В действительности эта задача обычно имеет множество решений, поэтому представляет интерес возможность получения всех решений и дальнейшего выбора "лучшего" из них, относительно какого-либо дополнительного критерия. Предлагаемый в данной работе Алгоритм Поиска Оптимального Раскроя дает такую возможность. Достоинствами данного алгоритма являются также 1). возможность включения в алгоритм новых эффективных правил сокращения перебора, 2). возможность выбора критерия качества упаковки, исходя из требований задачи, 3). возможность при определенном критерии качества упаковки изменять минимизируемую функцию с целью сокращения перебора.

Цель работы. Постановка задачи прямоугольного негильотинного раскроя в терминах алгоритма минимизации функций, заданных на нормально разворачиваемых, частично упорядоченных множествах А(Р,Ц,:Г); разработка и анализ алгоритмов решения задачи прямоугольного негильотинного раскроя на основе алгоритма А(Р,Ц,^ и их программная реализация.

На защиту выносятся:

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

2. Алгоритм решения задачи прямоугольного негильотинного раскроя на основе алгоритма минимизации функций, заданных на нормально разворачиваемых, частично упорядоченных множествах - Алгоритм Поиска Оптимального Раскроя (АПОР).

3. Правила сокращения перебора при решении задачи прямоугольного негильотинного раскроя Алгоритмом Поиска Оптимального Раскроя на множестве размещений прямоугольников на листе, покрытом сеткой, и на множестве плотных укладок:

-правило о допустимой остановке алгоритма при получении по крайней мере одного оптимального элемента; -правила отсечения неперспективных элементов; -правило о порядке размещения сравнимых прямоугольников; -правила о порядке прямоугольников и об условиях их размещения; -правило отсечения одинаковых и симметричных элементов; -условия замены функции, соответствующей определенному критерию качества укладки ^рит(0 на оценочную функцию В(1), определяемую этим же критерием укладки и, кроме того, учитывающую путь, который осталось пройти до цели;

-конкретные функции, удовлетворяющие условиям замены.

4. Результаты исследования влияния выбора минимизируемой функции при определенном критерии качества упаковки на сложность решения задачи поиска оптимальной плотной укладки.

5. Алгоритм получения приближенного решения задачи прямоугольного негильотинного раскроя на подмножестве Р* множества Р плотных укладок, полученных последовательным плотным размещением прямоугольников, начиная с нижнего левого угла листа (на очередном шаге размещается только один из неразмещенных прямоугольников) - АЛЛУ. Правило о порядке размещения прямоугольников АЛЛУ и правило отсечения одинаковых элементов (при наличии одинаковых прямоугольников).

6. Алгоритм Поиска Оптимального Раскроя с верхней границей.

7. Программа, реализующая разработанные алгоритмы и генератор задач прямоугольного негильотинного раскроя.

Научная новизна. Новыми в работе являются: постановка задачи прямоугольного негильотинного раскроя в терминах, связанных с алгоритмом минимизации функций, заданных на нормально разворачиваемых, частично упорядоченных множествах (алгоритмом поиска оптимальных элементов), предлагаемый алгоритм решения задачи прямоугольного негильотинного раскроя на основе алгоритма минимизации функций, заданных на нормально разворачиваемых, частично упорядоченных множествах - Алгоритм Поиска Оптимального Раскроя (АПОР), предлагаемые правила сокращения перебора при решении задачи прямоугольного негильотинного раскроя Алгоритмом Поиска Оптимального Раскроя, результаты исследования влияния выбора минимизируемой функции при определенном критерии качества упаковки на сложность решения задачи прямоугольного негильотинного раскроя, алгоритм получения приближенного решения задачи прямоугольного негильотинного раскроя на подмножестве Р* множества Р плотных укладок, полученных последовательным плотным размещением прямоугольников, начиная с нижнего левого угла листа (на очередном шаге размещается только один из не размещенных прямоугольников),

Алгоритм Поиска Оптимального Раскроя с верхней границей, генератор задач прямоугольного раскроя.

Практическая ценность.

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

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

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

Апробация работы.

Основные результаты диссертации докладывались на

• Всероссийской молодежной научно-технической конференции «Информационные и кибернетические системы управления и их элементы» (1995, г.Уфа),

• Х1-ой Всероссийской конференции «Математическое программирование и приложения» (1999, г.Екатеринбург),

• семинарах кафедры Высшей Математики и Кибернетики Уфимского государственного авиационного технического университета (1998-1999, г.Уфа),

• семинаре Института Математики с Вычислительным Центром УНЦ РАН (1999, г.Уфа),

• семинаре Башкирского государственного университета (1999, г.Уфа).

Публикации. По теме диссертации опубликовано 10 работ. Работы [15-19],[42],[43] написаны соискателем; работы [2],[20],[33] - в соавторстве с научным консультантом Ореховым Юрием Васильевичем. В работах [2],[33] постановка задачи выполнена совместно с Ореховым Ю.В., диссертанту принадлежат доказательства утверждений и теорем. В работе [20] на основе предложенных Ореховым Ю.В. идеи выделения из множества размещаемых прямоугольников подмножества объектов, которые могут быть последовательно уложены один в другой без пересечения сторон, и дополнительного условия, которому должна удовлетворять минимизируемая функция, диссертантом было введено понятие сравнимых прямоугольников, сформулировано правило о порядке размещения сравнимых прямоугольников, сформулирована и доказана теорема о результатах применения данного правила.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и приложений. Полный ее объем составляет 101 страницу машинописного текста, включая 5 рисунков на 5 страницах, 8 примеров с рисунками на 10 страницах, приложения на 7 страницах, библиографию, содержащую 43 названия.

Заключение диссертации по теме «Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях (по отраслям наук)», Ефимова, Татьяна Евгеньевна

Основные результаты диссертации состоят в следующем.

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

2. Предложен алгоритм решения задачи прямоугольного негильотинного раскроя на основе алгоритма минимизации функций, заданных на нормально разворачиваемых, частично упорядоченных множествах - Алгоритм Поиска Оптимального Раскроя (АПОР).

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

4. Сформулированы правила сокращения перебора при решении задачи прямоугольного негильотинного раскроя Алгоритмом Поиска Оптимального Раскроя на множестве размещений прямоугольников на листе, покрытом сеткой, и на множестве плотных укладок:

-правило о допустимой остановке алгоритма при получении по крайней мере одного оптимального элемента; -правила отсечения неперспективных элементов; -правило о порядке размещения сравнимых прямоугольников; -правила о порядке прямоугольников и об условиях их размещения; -правило отсечения одинаковых элементов (при наличии одинаковых прямоугольников);

-условия замены функции, соответствующей определенному критерию качества укладки ^ритО) на оценочную функцию Щ), определяемую этим же критерием укладки и, кроме того, учитывающую путь, который осталось пройти до цели;

-конкретные функции, удовлетворяющие условиям замены.

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

6. Приведены результаты исследования возможности сокращения перебора при замене функции, соответствующей определенному критерию качества укладки ^ритО) на оценочную функцию Щ), определяемую этим же критерием укладки и, кроме того, учитывающую путь, который осталось пройти до цели.

7. Предложен алгоритм нахождения приближенного решения задачи прямоугольного негильотинного раскроя на подмножестве Р* множества Р плотных укладок, полученных последовательным плотным размещением прямоугольников, начиная с левого нижнего угла листа (АППУ). Предложено правило о порядке размещения прямоугольников при работе АППУ, согласно которому на очередном шаге алгоритма предлагается размещать наибольший по площади из неразмещенных прямоугольников.

8. Предложен Алгоритм Поиска Оптимального Раскроя с верхней границей.

9. Разработанные алгоритмы реализованы программно. Проведены вычислительные эксперименты с использованием генератора задач прямоугольного раскроя, подтверждающие их эффективность.

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

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

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

Доказательство утверждения 1) Теоремы 1 [36].

2. Покажем теперь, что И=Мор{. Пусть

1 е Мор1 (1) и 10,.,1„ - цепочка непревосходящих элементов для 1. По лемме 6, учитывая, что Мор1 сЦсР,

Нкп{1о,.,1п}=0. (2)

Допустим, что 1П = 1 € Нк. (3)

Тогда, согласно (2), найдется такой номер Кп, что ^ е Нк, следовательно, по лемме 4. Нк п Ц * 0.

Так как (см.(1)) Ц(1)=1, то Ц(1,)=0, кроме того, благодаря возрастанию снизу относительно Р функции f на МорЬ < £(1). Итак, для 1; выполняется : еНь Ц(1)=0, т<Ш 1еМор1. Но это невозможно, ибо противоречит пункту 3 леммы 4.

Таким образом, допущение (3) неверно, т.е. 1е Нк . Причем, поскольку для всех ГеЦ Щ')>Т(1) (см.(1)), а для любого элемента Г'е Нк и йЦ £(1")>Т(1) ( пункт 3 леммы 4), то наименьшего значения в Нк £ достигает на 1, а это, с учетом равенства Ц(1)=1, показывает, что 1еИ (см. пункт В) алгоритма). Итак, любой элемент 1е Мор1 принадлежит И, т.е.

Мор1 с И. (4)

Докажем обратное включение. По условию Мор1 ^ 0 и, значит, существует элемент 10е Мор1. Тогда, согласно (4), 10еИ. Рассмотрим произвольный элемент 1еИ. Так как для всех элементов 1'еИ значение £ одинаково и Ц(Г)=1 (см. пункт В) алгоритма), то

Ц(1)=1 и Щ) = Г(10) = Щ"), т.е. 1е Мор1. Включение Ис Мор1 доказано.

3. Для завершения доказательства пункта 1) теоремы остается показать, что Ма=Ро, т.е., с учетом леммы 7, надо лишь обосновать включение Рос Ма (то, что включение Мор{с Р0 , нужное для применения леммы 7, справедливо, ясно из условия в)).

Пусть 1е Р0 и 10,.,1П - цепочка непревосходящих элементов для 1. Если 1П=1 е Нк, то 1е Ма.

Если же 1П£ Нк, то 1; при 1<п тоже не принадлежат Нк, так как в противном случае (см. определение Р0) имели бы Ц(11)=0, < Щ*) для любого 1* е МорЬ что невозможно в силу леммы 4. Следовательно, к-1

Нкп{ 1о,—Дп }=0, так что по лемме 5 опять-таки получим 1п=1е ^ Нт сМа.

Доказательство утверждения 2) Теоремы 1 [36].

2. В рассматриваемом случае Р, а значит и ЦсР (см. условие б) теоремы) конечно, поэтому

Ц = 0 (5) т.к. в противном случае среди конечного числа его элементов был бы такой элемент 1, для которого справедливо

1еЦ, т.е. оказалось бы, что Мор^0, а это противоречит условию пункта 3) теоремы.

Таким образом, Ис=Ц (согласно пункту В) алгоритма) тем более пусто, т.е. И =0= Мор1.

3. Остается доказать, что Ма = Р. Так как включение Ма = УН; с Р очевидно, то докажем обратное включение. Пусть элемент 1еР и к - номер последнего шага шагового процесса. Согласно (5), НкпЦ=0 и, следовательно, по лемме 4 Нг=0. Таким образом, ни 1, ни любой другой элемент из цепочки непревосходящих 1 элементов не принадлежат Нк, значит, по лемме 5

1е и Нтс=Ма.

7И = О

Заключение

Список литературы диссертационного исследования кандидат физико-математических наук Ефимова, Татьяна Евгеньевна, 1999 год

1. H.Gehring, A.Bortfeldt Genetic algorithm for the packing problem design. 1997 1.ORS, Elsevir Science Ltd, 20p.

2. Yu.Orekhov, T.Efimova Laws of reduced search for optimum dense packing problems based on an optimum elements search algorithm. // Decision marking under conditions of uncertainty: The International Scientific Collection.-Ufa:1. USATU, 1997.P.244-250.

3. G.Scheithauer, J.Terno The G4-Heuristic for the Pallet Loading Problem. //Journal of the Operational Research Society, № 47, 1996. P.511-522.

4. P.Schwerin and G.Wascher The Bin-Packing Problem: A Problem Generator and Some Numerical Experiments with FFD Packing and MTP. Int.Trans.Opt.Res. Vol4. N5/6, 1997. P.337-389.

5. Аккуратов Г.В., Березнев B.A., Брежнева O.A. О методе решения уравнения с булевыми переменными // Принятие решений в условиях неопределенности: Межвуз. научный сборник. Уфа, 1990.- С.145-154.

6. Болотовская Т.К., Верхотуров М.А. Некоторые аспекты проблемы построения рационального плана нерегулярного раскроя на заготовки сложных форм // Принятие решений в условиях неопределенности: Межвуз. научный сборник. Уфа, 1990.- С. 117-120.

7. Бухвалова В.В. Реализация метода зон Липовецкого для прямоугольного раскроя // Математическое обеспечение рационального раскроя в системах автоматизированного проектирования: Тез. докл. научно-технич. Конференции. ч.1. -Уфа: УАИ, 1987. -С. 16-17.

8. Вайнштейн А.Д. Задачи об упаковке прямоугольников в полосу (обзор) // Управляющие системы, ИМ СОАН СССР, 1984, вып.25.-С.4-25.

9. Вайнштейн А.Д. Приближенные алгоритмы упаковки прямоугольников с априорными оценками погрешности // Математическое обеспечениерационального раскроя в системах автоматизированного проектирования.: Тез. докл. Всесоюзной конференции. -Уфа, 1987. -С.26-27.

10. Валеева А.Ф., Мухаметзянов Р.З., Тихомиров С.К., Юлдыбаева * Ж.JI. Алгоритмы решения задачи плотной упаковки геометрических объектов // Принятие решений в условиях неопределенности: Межвуз. научный сборник. Уфа, 1996.- С.30-34.

11. П.Вапник В.Н, Глазкова Т.Г., Кощеев В.А., Михальский А.И., Червоненкис А .Я. Алгоритмы и программы восстановления зависимостей. -Москва: Наука, 1984. 815с.

12. Гутер Г.С. Оптимизация методом частичного улучшения по группам переменных. -В кн.: Математические методы решения экономических задач. М., 1969.-С.21-38.

13. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. -М.: Мир, 1982.-416 с.

14. Давыдова И.М. Схемы перебора в задачах размещения. -Л.: Изд.ЛГУ, 1985. 129с.

15. Ефимова Т.Е. Точные и приближенные методы укладки прямоугольников. //Уфа: УГАТУ, 1998.-19с. Деп. в ВИНИТИ, 08.01.98, №5-В98.

16. Ефимова Т.Е. Исследование возможности сокращения перебора при решении задачи прямоугольного негильотинного раскроя путем замены функции, определяемой критерием укладки, на оценочную функцию. //Уфа: УГАТУ, 1998.-21С. Деп. в ВИНИТИ, 20.11.98, №3402-В98.

17. Ефимова Т.Е. Об одном методе построения плотной укладки. // Принятие решений в условиях неопределенности. -Уфа: УГАТУ, 1999. -С.118-123/

18. Ефимова Т.Е. Двумерный раскрой и плотная упаковка прямоугольников./ Регистрационный номер программы 50980000043. //Информационный бюллетень «Алгоритмы и программы».-Москва: ВНТИЦ, 1999, №1.-С.7-8.

19. Ефимова Т.Е. Правило о допустимой остановке алгоритма поиска оптимальных элементов. // Информационный бюллетень № 8. Конференция

20. Математическое программирование и приложения». Тезисы докладов. Екатеринбург, 22-26 февраля 1999. -С.104-105.

21. Ефимова Т.Е., Орехов Ю.В. О порядке размещения прямоугольников при решении задачи прямоугольного негильотинного раскроя. // Принятие решений в условиях неопределенности. -Уфа: УГАТУ, 1999. -С. 124-127.

22. Карманов В.Г. Математическое программирование. Москва «Наука», 1986. -286с.

23. Картак В.М. Модели и методы оптимизации упаковки 1М-мерных параллелепипедов. Авт.реф.дис.канд.ф.м.наук. Уфа: УГАТУ, 1999.-22с.

24. Липовецкий А.И. Свойства прямоугольных укладок и алгоритмы оптимального раскроя : Препринт. -Свердловск: Уро АН СССР, 1988. -50с.

25. Липовецкий А.И. К оптимизации свободного размещения прямоугольников // Автоматизация проектирования в машиностроении. Минск: ИТК АН БССР, 1985. -С.80-87.

26. Липовецкий А.И. Алгоритмы негильотинного прямоугольного раскроя // Математическое обеспечение рационального раскроя в системах автоматизированного проектирования: Тез. докл. научно.-технич. конференции, ч.2. Уфа: УАИ, 1987. -С. 106.

27. Михайлов Г.А. Некоторые вопросы теории методов Монте-Карло. Новосибирск: Наука, 1974. 143с.

28. Мухачева Э.А., Белякова Л.В. Задачи планирования рационального раскроя промышленных материалов и их комплексное решение // Принятие решений в условиях неопределенности: Межвуз. научный сборник. Уфа, 1990.-С.99-108.

29. Мухачева Э.А., Верхотуров М.А., Мартынов В.В. Модели и методы расчета раскроя-упаковки геометрических объектов. -Уфа: УГАТУ, 1998. -217с.:ил.

30. Мухачева Э.А. Рациональный раскрой промышленных материалов. Применение в АСУ. М.: Машиностроение, 1984. -176с.

31. Нильсон Н. Искусственный интеллект. -Москва: МИР, 1973. -270с.

32. Новожилова M.B. Решение задачи поиска глобального экстремума линейной функции цели на структуре линейных неравенств. -Харьков, 1988. -48 с. -(Препринт/ АН УССР, Ин-т пробл. машиностроения: 292).

33. Орехов Ю.В. Об условиях эффективности эвритстики первоочередного размещения более крупных объектов данного набора в заданной области // Принятие решений в условиях неопределенности: Межвуз. научный сборник. Уфа, 1990.- С. 139-144.

34. Орехов Ю.В., Тоцкова Т.Е. Рациональное решение задачи прямоугольного негильотинного раскроя на основе алгоритма поиска оптимальных элементов // Принятие решений в условиях неопределенности. -Уфа: УГАТУ, 1996. -С.66-70.

35. Петунин A.A. Методы укладки прямоугольников в заданной последовательности и их программная реализация // Матем. обеспечение расчетов линейного и прямоугольного раскроя. Матер, всесоюзного семинара 22-27 июня 1980 г. -Уфа: УАИ, 1981. -С. 142-145.

36. Романовский И.В. Алгоритмы решения экстремальных задач. -М.: Наука, 1977.-351 с.

37. Соломещ И.А., Рудерман С.Ю. Минимизация функций, заданных на нормально разворачиваемых, частично упорядоченных множествах // Модели организации, управления, и методы их исследования. Межвузовский науч. Сборник. -Уфа: БГУД975.-С.9-35.

38. Стоян Ю.Г. Размещение геометрических объектов. -Киев: Наук, думка, 1975.-239с.

39. Стоян Ю.Г., Гиль Н.И. Методы и алгоритма размещения плоских геометрических объектов. -Киев: Наук, думка , 1976. -247 с. -В надзаг.: АН УССР. Ин-т пробл. машиностроения.

40. Стоян Ю.Г., Соколовский В.З. Решение некоторых многоэкстремальных задач методом сужающихся окрестностей. -Киев: Наук, думка, 1980. -206 с.

41. Стоян Ю.Г., Яковлев C.B. Математические модели и оптимизационные методы геометрического проектирования. -Киев: Наук, думка, 1986. -268 с.

42. Тарасова Т.Д., Розанова Л.Ф. Метод последовательного уточнения оценок для решения задач раскроя в условиях единичного и мелкосерийного производства // Принятие решений в условиях неопределенности: Межвуз. научный сборник. Уфа, 1990.- С. 112-116.

43. Тоцкова Т.Е. Модификация алгоритма поиска оптимальных элементов для решения задачи прямоугольного негильотинного раскроя // Математическое моделирование в решении научных и технических задач. -Уфа: Технология, 1994. С.10-13.

44. Тоцкова Т.Е. Об одном подходе к решению задачи рационального негильотинного раскроя. // Всероссийская молодежная научно-техническая конференция «Информационные и кибернетические системы управления и их элементы». Тезисы докладов. Уфа, 1995. -С. 13-14.