Комп'ютеризована система планування ремонтних робiт вагонного депо
Постановка проблеми
Всі організаційні і технологічні рішення в розподілі робіт на підприємствах повинні прийматися оперативно. При цьому неоптимальні рішення значно знижують ефективність побудови розкладів роботи виробничої дільниці. Абсолютно така ж ситуація спостерігається і в депо по ремонту вагонів.
Однак до сих пір мало вивчено рух робочих бригад безпосередньо у виробничому середовищі (на виробничій ділянці) відповідно до технологічного маршрутом в реальному масштабі часу. Особливо актуальним завданням є побудова оптимальних розкладів роботи вагоноремонтних бригад відповідно до технологічного маршрутом.
У зв'язку з виниклими проблемами перед системою поставлена наступна основне завдання: оптимізувати розподіл робіт по бригадах.
Розподіл робіт по бригадам
Розроблюваний алгоритм повинен ефективно розподіляти трудові ресурси ремонтного депо, що дозволить збільшити його продуктивність. Завдання розподілу необхідних робіт по ремонту вагонів серед бригад відноситься до завдань оперативно-календарного планування.
Оперативне планування охоплює не тільки встановлення завдань по виконанню робіт (хоча це найважливіша його частина), а й інші показники діяльності підприємства і його цехів: продуктивність праці, чисельність робітників і розмір фонду заробітної плати, використання виробничої потужності підприємства і його матеріальних ресурсів, зниження собівартості продукції, рентабельність виробництва.
Більшість розроблених до теперішнього часу методик для оперативно-календарного планування засноване на спрощених моделях, що знижує їх точність, або ці методики застосовуються лише для певних специфічних умов. Значну складність, крім того, являє проблема оцінки якості одержуваних розкладів. Аналіз сучасних робіт по комбінаторної оптимізації на графах (особливо динамічних задач) показує, що одним з найперспективніших підходів є використання мурашиних алгоритмів. Цей підхід дозволяє істотно поліпшити систему оперативного планування, тим самим скоротивши час побудови оптимальних або прийнятних виробничих розкладів.
Математична модель
Для оперативного планування розподілу робіт технологічний процес поділяється на технологічні операції.
Припустимо, що на даному виробничому ділянці ремонтується n вагонів di (i = 1,2, ..., n). Позначимо деяку довільну операцію, яку необхідно виконати над вагоном di, через Oij (j = 1,2, ..., m_i), де mi - загальна кількість операцій, які необхідно виконати над di. Під технологічним маршрутом бригади зазвичай розуміють порядок виконання бригадою роботи над вагоном або ж послідовність виконуваних операцій (1).
Mi=(O_i1,O_i2,…,O(imi )), (1)
При послідовному виконанні операцій передбачається сувора впорядкованість технологічного маршруту. Однак можна припустити (і це часто відповідає дійсності), що порядок виконання операцій змінюється (не є строгим), тобто впорядкованість виконання операцій частична. При цьому необхідно враховувати наступні обмеження:
1. Обмеження щодо термінів виготовлення (2):
Tпл ≤ Tф, (2)
де: Tф - фактичний термін ремонту вагона di,
Tпл - плановий термін ремонту вагона di.
2. Обмеження за обсягами виготовлення (3):
Nпл = Nф, (3)
де: Tф - фактичне відремонтоване кількість вагонів,
Tпл - заданий у виробничій програмі кількість вагонів.
Завдання оперативного планування розкладу робіт полягає в тому, щоб для виробничої дільниці з заданими технологічними маршрутами ремонту вагонів скласти деяке розклад, яке задовольняє сформульованим умовам, яке представляється у вигляді графа. Побудова такого графа еквівалентно визначенню чисел tij - моментів початку технологічної операції Oij.
Сукупність чисел {tij} (i = 1,2, ..., n; j = 1,2, ..., mi), яка задовольняє сформульованим умовам [9], називається розкладом робіт, або його графовой моделлю G (i) [2].
Для вирішення завдання складання оптимального розкладу задамося деякої числової функцією F (функцією-критерієм), визначеної на всіх графах G (i), що ставить у відповідність кожному графу G певне число F (G). При цьому найкращому графу повинен відповідати екстремум функції F. Таким чином, завдання зводиться до того, щоб побудувати граф, який задовольняє всім сформульованим у завданні умов і обмежень і на якому функція F (G) досягне свого екстремального значення (5).
T_опт = Tпл - Tф → min, (4)
Очевидно, що існує безліч графів, які задовольняють сформульованим умовам і обмеженням. Таким чином, необхідно побудувати найкращу графову модель відповідно до обраного критерію (4):s
F(G) = extr F(G), (5)
Графова модель
Графова модель складається з безлічі вузлів і орієнтованих дуг, що з'єднують вузли. При графові подання необхідних робіт вузли виступають як необхідні технологічні процеси, які потрібно провести над вагоном, а дуги показують напрямок руху працівників для виконання робіт по ремонту деталей вагона (рис.1).
Слід зазначити, що графовая модель не є структурною (функціональної) схемою реального депо. Залежно від поставленого завдання і досліджуваної функції змінюється число вузлів в мережі, їх склад і зв'язку між ними.
Вихідний вузол графа визначає початок виконання плану (стартову точку), в яку поміщаються мурахи, в кількості, що дорівнює числу робочих на виробничій ділянці. Решта вершини графа відповідають окремим технологічної операції Oij (згідно з технологічною картою).
Кожен вузол O_ij однозначно визначається наступними параметрами (6):
Oij = (Kmin,Kopt,Tvij,Tnij,Nij,Pr,D,Kv), (6)
де: Kmin - мінімальна кількість робітників, необхідних для виконання технологічної операції Oij;
Kopt - оптимальна кількість робітників, необхідних для виконання технологічної операції Oij;
Tvij - час виконання технологічної операції Oij;
Tnij - час підготовки бригади для виконання технологічної операції Oij;
Nij - номер робітника, який виконує роботу Oij;
Pr - пріоритет технологічної операції Oij;
D - доступність технологічної операції Oij;
Kv - кваліфікація робітника, необхідна для виконання технологічної операції Oij;
Таким чином, вузол графовой моделі - це умовне позначення виконуваної технологічної операції в рамках конкретної роботи, а ребро відображає послідовний перехід від однієї технологічної операції до іншої (жовтим відображені переходи від однієї технологічної операції до іншої в рамках однієї роботи, а синім - безліч можливих переходів між роботами).
При цьому мурахи мають ряд характеристик (7):
Mij =(Kv,T,W), (7)
де: Kv - кваліфікація мурашки (робочого);
T - кількість часу, який мураха (робочий) витратить на виконання всіх робіт в рамках однієї зміни;
W - список робіт, які мурашки (робочому) потрібно виконати за зміну;
Рисунок 1 - Графова модель
Розглянемо детальніше процес функціонування розподілу працівників по роботах в рамках графовой моделі.
Як уже згадувалося, вузли, представляють собою технологічні процеси, які на рис. 1 представлені жовтими точками. Шлях, по якому можуть переміщатися працівники, що рухаються по графу в пошуках підходящої для себе роботи, відзначений жовтими і синіми стрілками. В рамках виконання однієї роботи використовується спрямований граф, і працівники можуть рухатися тільки вперед, в той час як переходи між роботами можуть здійснюватися в довільному порядку.
Працівник, рухаючись по графу, зупиняються на відповідному їм технологічному процесі (жовтої точки), тим самим починаючи виконання технологічного процесу і блокуючи доступ інших працівників до нього, а сам він вважається зайнятим і не шукає інший вузол (технологічний процес), поки не закінчить поточну роботу. Закінчивши роботу, працівник вільний переміститися на інший технологічний процес, який йому підходить.
Таким чином, за допомогою задіяння теорії графів і мурашиних алгоритмів відбувається розподіл працівників по роботах, що дозволить оптимізувати роботу ремонтного депо і збільшити його ефективність.
Висновки
Рассмотренный алгоритм упорядочивает и рационализирует занятость работников вагонного депо и уменьшает задержки во времени, в следствии чего повышает производительность ремонтного депо.
Список литературы
1. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = Introduction to Algorithms. – 2-е изд. – М.: «Вильямс», 2006. – С. 1296.
2. M. Dorigo, V. Maniezzo, A. Colorni, 1996. "Ant System: Optimization by a Colony of Cooperating Agents", IEEE Transactions on Systems, Man, and Cybernetics-Part B, 26 (1): 29–41.
3. L. M. Gambardella, M. Dorigo, "Ant-Q: A Reinforcement Learning Approach to the Traveling Salesman Problem" // Twelfth International Conference on Machine Learning, Morgan Kaufmann, p. 252–260, 1995.
4. Ананий В. Левитин Глава 9. Жадные методы: Алгоритм Дейкстры // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. – М.: «Вильямс», 2006. – С. 189–195.
5. Рассел С. Дж., Норвиг, П. Искусственный интеллект: современный подход = Artificial Intelligence: A Modern Approach / Пер. с англ. и ред. К. А. Птицына. – 2-е изд. – М.: Вильямс, 2006. – С. 157–162.
6. Лорьер Ж.-Л. Системы искусственного интеллекта / Пер. с фр. и ред. В. Л. Стефанюка. – М.: Мир, 1991. – С. 238–244.
7. C. Blum, 2005 "Ant colony optimization: Introduction and recent trends". Physics of Life Reviews, 2: 353–373.
