В общем случае, задача «m станков» будет звучать следующим образом: n деталей обрабатываются последовательно на m станках, т.е. очередность выполнения операций для всех станков соблюдается. Операция на g-ом станке не может начаться, пока он занят выполнением предыдущей операции, а так же, пока не закончилась операция на g-1-вом. Последовательность обработки деталей оптимальна, если общее время обработки деталей минимальна.
Задача «об одном станке» в реальности практически не имеет места, т.к. время зачастую уходит не только для того, чтобы обработать деталь, но и наладить или переналадить станок, в зависимости от того, какая деталь обрабатывалась до нее, а так же учесть возникающие задержки. Эти три временные характеристики длительности производственного цикла превращают задачу «об одном станке» в задачу о трех станках, т.е. в NP-трудную.
Идея использования основных факторов эволюции - естественного отбора, наследственной изменчивости, мутации - в задачах поиска оптимальных решений позволила создать широкий спектр методов эволюционных вычислений.
Наибольшее распространение получил генетический алгоритм, основной областью применения которого являются задачи комбинаторной оптимизации [2], в которую также входит задача размещения. Применим его для решения задачи загрузки станков.
Решение задачи загрузки станков сводится к поиску оптимальной последовательности обрабатываемых деталей.
Следовательно, хромосома состоит из n генов, каждый ген несет в себе уникальную для хромосомы информацию. В данном случае это индекс обрабатываемой детали, т.е. - хромосома, а ij - это i - ый ген хромосомы σn. Заметим, что в данном случае необходим метод скрещивания, не нарушающий уникальность информации генов.
Метод генетического алгоритма позволяет решить проблему загрузки станков не только для синхронных, но и асинхронных процессов за конечное число итераций, причем целевая функция задачи может быть нелинейной.
СПИСОК ЛИТЕРАТУРЫ
- В.В. Шкурба. Задача трех станков: М.76.
- А.В.Григорьев Генетические алгоритмы оптимизации многомерных, многокритериальных задач с нелинейной целевой функцией//Материалы междунар. конф. студ. и асп. по фундаментальным наукам "Ломоносов-2002". Секция "Вычислительная математика и кибернетика". - М.: МАКС-Пресс, 2002.
Работа представлена на II научную конференцию с международным участием «Технические науки и современное производство», 3-10 октября, 2004 г., о. Крит, Греция.
Библиографическая ссылка
Ефимов М. И., Желтов В. П. ОПТИМИЗАЦИЯ МЕХАНОСБОРОЧНОГО ПРОИЗВОДСТВА С ПОМОЩЬЮ ГЕНЕТИЧЕСКОГО АЛГОРИТМА // Современные наукоемкие технологии. – 2004. – № 5. – С. 93-94;URL: https://top-technologies.ru/ru/article/view?id=22004 (дата обращения: 17.08.2024).