ВКР: Математическое и программное обеспечение для исследования простых эвристик при решении задач линейного раскроя

Цель работы:
Сравнение эффективности различных алгоритмов для решения разных классов задач линейного раскроя на основе вычислительного эксперимента.
Задачи:
выполнить аналитический обзор методов решения целочисленных задач линейного раскроя;
реализовать в виде программного продукта алгоритмы линейного раскроя на базе метода простых эвристик;
провести вычислительный эксперимент для исследования влияния исходных данных на результат решения задачи линейного раскроя;
разработать рекомендации по выбору алгоритма в зависимости от исходных данных.

ПОСТАНОВКА ЗАДАЧИ

СТРУКТУРА РЕШЕНИЯ

КЛАССИФИКАЦИЯ ЗАДАЧ РАСКРОЯ

ЗАДАЧА ЛИНЕЙНОГО РАСКРОЯ В УСЛОВИЯХ ЕДИНИЧНОГО (МЕЛКОСЕРИЙНОГО) ПРОИЗВОДСТВА
ПОСТАНОВКА ЗАДАЧИ
МАТЕМАТИЧЕСКАЯ МОДЕЛЬ

КЛАССИФИКАЦИЯ МЕТОДОВ
. . .
. . .

МЕТОД ПРОСТЫХ ЭВРИСТИК

БЛОК-СХЕМА АЛГОРИТМОВ ЛИНЕЙНОГО РАСКРОЯ
Сортировка по длине
sort_length()

БЛОК-СХЕМА АЛГОРИТМОВ ЛИНЕЙНОГО РАСКРОЯ
Следующий подходящий (NF)
Next_Fit()
Первый подходящий (FF)
First_Fit()

СТРУКТУРА ПРОГРАММНОГО ПРОДУКТА

ИНТЕРФЕЙС ПРОГРАММЫ

установить параметры исходных данных (границу между большими и маленькими заготовками, долю больших заготовок в общем количестве заготовок);
сгенерировать исходные данные с учетом заданных параметров;
найти решение задачи линейного раскроя для каждого из классов задач четырьмя алгоритмами;
для каждого решения выводятся рациональный план раскроя, минимальное количество материала и коэффициент раскроя; проанализировать выходные данные и определить рекомендуемый алгоритм для каждого из классов задач;
рассчитать качество и стабильность работы каждого алгоритма для разных типов исходных данных.
выдать рекомендации к использованию алгоритмов для решения задач разных классов.
МЕТОДИКА ПРОВЕДЕНИЯ ИССЛЕДОВАНИЯ

ВЫЧИСЛИТЕЛЬНЫЙ ЭКСПЕРИМЕНТ

ВЫЧИСЛИТЕЛЬНЫЙ ЭКСПЕРИМЕНТ

Вывод:
при v = 0,5L алгоритм FFD работает качественнее остальных и находит лучшие коэффициенты раскроя при любом проценте больших заготовок;
при v = 0,5L алгоритм NF работает наименее качественно и находит худшие коэффициенты раскроя при любом проценте больших заготовок;
с увеличением доли больших заготовок падает качество решения.
КАЧЕСТВО РАБОТЫ АЛГОРИТМОВ

Вывод:
разброс оценки дисперсии минимален, это значит, что в целом все рассмотренные алгоритмы показывают высокую стабильность.
СТАБИЛЬНОСТЬ РАБОТЫ АЛГОРИТМОВ

РЕЗУЛЬТАТЫ ВКР
выполнен аналитический обзор методов решения целочисленных задач линейного раскроя и выбран для реализации метод простых эвристик;
рассмотрены и реализованы в виде программного продукта алгоритмы линейного раскроя на базе выбранного метода;
предложен способ разбиения множества заготовок на две группы: “большие” (длина которых больше половины длины стержня) и “маленькие” заготовки;
проведен вычислительный эксперимент, который показал влияние различных вариантов соотношения количества “больших” заготовок к общему числу заготовок на результат решения задачи: с повышением доли больших заготовок ухудшается качество решения;
разработаны рекомендации по выбору алгоритма для решения задач линейного раскроя: алгоритм FFD работает качественнее остальных и находит лучшие коэффициенты раскроя при любом проценте больших заготовок, при этом стабильность работы всех алгоритмов практически одинакова.