Введение 2
Глава 1. Задача комплектовки однотипных деталей 4
1.1. Формальная постановка задачи 4
1.2. Примеры задач 6
1.3. Свойства задачи комплектовки однотипных деталей 8
Цель работы 9
Глава 2. Методы решения задачи 10
2.1. Методы решения задачи 10
2.2. Сравнение методов решения задачи 22
2.3. Подведение итогов: 35
Глава 3. Программная реализация 37
Заключение 41
Список литературы 42
Приложение 1. Таблицы экспериментов 43
В машиностроении одним из этапов производства механизмов и машин является этап сборки. На этом этапе может возникнуть задача комплектовки однотипных деталей — задача подбора деталей для комплекта (комплектов), в то время как имеется множество однотипных деталей, но не все из них подходят друг к другу, то есть не могут составить комплект друг с другом. Отдельно стоит отметить, что все предлагаемые для комплектовки детали не являются бракованными, для любой детали могут существовать другие детали, такие что эта деталь составит с ними комплект. В качестве примера однотипных деталей можно привести: лопасти для пропеллеров, лопатки для турбин. Сформированный комплект (комплекты) будет частью конечного механизма или машины. Детали могут не подходить друг к другу (несмотря, но то, что они не являются бракованными) из-за ограничений, налагаемых на механизм в сборе: для того, чтобы механизм удовлетворял требованиям, необходимо, чтобы детали не отличались друг от друга слишком сильно. Приведу пример подобных ограничений: пропеллер для вертолета должен быть уравновешен, чтобы в процессе его эксплуатации не возникало биение и он не разрушался. Для этого требуется, например, чтобы лопасти, составляющие пропеллер, не отличались друг от друга по массе более, чем на некоторую величину.
В качестве примера задач комплектовки однотипных деталей можно привести: подбор лопастей для пропеллеров, подбор лопаток для турбин, подбор поршней для ДВС.
Количество деталей, необходимых для комплекта, может быть разным: 2, 3, 4 и более. В качестве примеров вариантов задачи можно привести двух лопастные вертолеты и трех лопастные вертолеты. Ограничений, налагаемых на детали, также может быть несколько: это могут быть, например, ограничения по массе, по размерам.
Успешное решение задачи комплектовки однотипных деталей может быть очень важно с экономической точки зрения: от того, сколько комплектов удалось сформировать из данного набора деталей, зависит, сколько однотипных деталей потребуется произвести для того, чтобы сформировать необходимое количество комплектов. Таким образом, при высокой стоимости однотипной детали, экономическая выгода будет весьма значительной. Примером однотипной детали с высокой стоимостью можно привести лопасть для винта вертолета.
Задачей, решаемой в рамках данной работы, является разработка алгоритмов решения задачи комплектовки однотипных деталей.
Таким образом, в ходе работы получены следующие результаты:
- Формально поставлена рассматриваемая задача — задача комплектовки однотипных деталей.
- Выполнен анализ задачи.
- Разработано 8 эвристических алгоритмов решения задачи комплектовки однотипных деталей.
- Реализовано 10 алгоритмов решения задачи.
- Выполнен анализ алгоритмической сложности всех алгоритмов.
- Протестированы все реализованные алгоритмы, на предмет, какой их них лучше.
- Для тестирования алгоритмов разработана программа-стенд.
- По итогам тестирования сделаны выводы о том, какие алгоритмы и когда лучше применять.
