Control Systems and Computers, N5, 2019, Статья 5
https://doi.org/10.15407/csc.2019.05.039
Witkowski T. The DABC and TLBO Algorithms for Solve Job Shop Scheduling Problem. Control Systems and Computers. 2019. № 5. С. 39-47.
УДК 004.493
Тадеуш Витковский, Факультет технологий производства,
Варшавская политехника, Площадь Политехники, 1, 00-661, Варшава, Польша
Применение алгоритмов DABC и TLBO в задаче календарного планирования работы цеха
Введение. Задача календарного планирования работы цеха (ЗПРЦ, Job Shop Scheduling Problem, JSSP) является классической задачей теории расписаний. Она связана, главным образом, с промышленным производством, хотя находит применение и в других отраслях. Теория расписаний находится на стыке таких дисциплин, как информатика, исследование операций, управление и производство. Задачи теории расписаний в общем случае являются NP-полными, то есть не существует метода получения их решения за полиномиальное время.
JSSP заключается в оптимальном назначении каждой технологической операции ресурса и начала времени выполнения, чтобы минимизировать общее время выполнения. Для определения наилучшего подхода решения этой задачи проведено много исследований.
В статье применен алгоритм дискретной искусственной пчелиной колонии (ДШБК, Discrete Artificial Bee Colony, DABC) и метод оптимизации на основе преподавания/обучения (ООВН, Teaching-Learning-Based Optimization, TLBO).
Целью исследования является оценить эффективность алгоритма DAВС и метода TLBO на многих тестовых задачах календарного планирования работы цеха.
Методы. Для поиска наилучшего решения используются стохастические методы поиска, такие как эволюционные алгоритмы, с которыми сравниваются методы дискретной искусственной пчелиной колонии и оптимизации на основе преподавания/обучения.
Результаты. Показано использование алгоритмов дискретной искусственной пчелиной колонии и метода оптимизации на основе преподавания/обучения для решения проблемы планирования рабочих мест с целью минимизации времени выполнения (значение Cmax).
Выводы. Сравниваются методы дискретной искусственной пчелиной колонии и оптимизации на основе преподавания/обучения. Вычислительные тестовые эксперименты показывают, что результаты, полученные для DABC со значениями текущих параметров управления и TLBO, близкие к оптимальным результатам известного генетического алгоритма.
Эксперименты с алгоритмами DABC и TLBO для различных параметров и критериев остановки показывают, что TLBO продемонстрировал лучшие значения Cmax, чем DABC, и хуже, чем генетический алгоритм. Вычислительный эксперимент показывает, что результаты, полученные DABC и TLBO для задач календарного планирования поточной линии (реальные производственные системы), дали оптимальные значения Cmax.
Загрузить полный текст в PDF (на английском).
Ключевые слова: алгоритм дискретной искусственной пчелиной колонии; оптимизация на основе преподавания/обучения; задача календарного планирования работы цеха; время выполнения.
Поступила 10.10.2019
