Введение 3
Основная часть 5
1. Математическое описание постановки задачи 5
2. Описание алгоритма 6
2.1. Рекурсивная часть алгоритма 8
2.2. Задача максимально плотной упаковки набора деталей на листе 10
2.3. Задача максимизации площади наибольшего остатка 11
3. Реализация алгоритма и анализ экспериментов 13
3.1. Структура данных 13
3.2. Реализация алгоритма. Параметры для анализа 14
3.3. Анализ экспериментов 17
Заключение 35
Литература 36
Приложение
Задачи рационального раскроя материалов уже на протяжении долгого времени привлекают различных исследователей [1-3]. Постановку данной задачи можно объяснить следующим способом:
Дан прямоугольный лист с размерами 0 X й и набор 0, который состоит из n типов деталей по | с размерами 0ВX ^, при 1 <0 <0, где 0В, -, | - длина, ширина и количество 0-го типа детали, при 0В> Щ. Требуется выяснить, размещается ли набор деталей на листе для последующего гильотинного раскроя, и если набор размещается, то построить карту гильотинного размещения.
В ходе выполнения данной работы нужно было разработать эвристический алгоритм гильотинного размещения набора прямоугольников на листе, создать его программную реализацию и провести экспериментальные расчеты по проверке работоспособности и эффективности алгоритма. При разработке алгоритма желательно учесть возможные специфические ограничения на раскрой (например, ограничение ориентации некоторых деталей на листе).
В связи с тем, что данная задача относится к классу NP-сложных [4], точное ее решение на больших объемах данных может быть получено за большой временной промежуток. Поэтому в литературе большое внимание уделяется эвристическим алгоритмам решения этой задачи [5-9].
В данной работе предлагается эвристический алгоритм, основной идеей которого является последовательное гильотинное вырезание деталей.
Целью данной работы является разработка алгоритма, разработка приложения обеспечивающего различные варианты алгоритма с визуализацией размещений, проведение тестовых расчетов для установления возможностей метода. Для достижения данной цели необходимо будет выполнить следующие задачи:
• разработать варианты метода гильотинного размещения набора прямоугольников на листе;
• запрограммировать варианты метода гильотинного размещения набора прямоугольников на листе;
• провести экспериментальные сравнения вариантов алгоритма;
• выполнить анализ результатов экспериментов и сделать выводы.
Итак, в работе предложен эвристический метод для гильотинного размещения набора прямоугольников на листе и рассмотрены его возможные программные реализации. Программный продукт, полученный в результате, позволяет достаточно быстро получать карты гильотинного размещения набора прямоугольников на листе, но заметим, что если метод не дал размещения, то это не означает, что размещение невозможно. В случае наличия нескольких вариантов размещения, предложен способ выбора размещения, обеспечивающего хорошие деловые остатки.
Данный алгоритм имеет ограниченную практическую ценность, поскольку при отсутствии размещения полного набора деталей метод ничего не дает. Поэтому в качестве возможного развития метода можно реализовать возможность фиксации вариантов размещения поднабора деталей на листе, имеющих максимальную площадь. После такой модификации метода можно будет предложить метод размещения набора деталей при условии использования нескольких листов материала и деловых остатков.
