Control Systems and Computers, N5, 2019, Стаття 5
https://doi.org/10.15407/csc.2019.05.038
Witkowski T. The DABC and TLBO Algorithms for Solve Job Shop Scheduling Problem. Control Systems and Computers. 2019. № 5. С. 38-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
