Математичні моделі та обчислювальні методи планування процесу обслуговування ієрархічними багатостадійними системами

Размещено на http://www.allbest.ru/

Харківський національний університет імені В. Н. Каразіна

Автореферат

дисертації на здобуття наукового ступеня кандидата технічних наук

01.05.02 - математичне моделювання та обчислювальні методи

МАТЕМАТИЧНІ МОДЕЛІ ТА ОБЧИСЛЮВАЛЬНІ МЕТОДИ ПЛАНУВАННЯ ПРОЦЕСУ ОБСЛУГОВУВАННЯ Ієрархічними багатостадійними СИСТЕМАМИ

Алі Найф Халіл Альхжуж

Харків - 2011

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ.

Актуальність теми дисертаційної роботи. Бурхливий розвиток систем, керуючих різного роду об'єктами в реальному масштабі часу змушує розробників активно удосконалювати способи та засоби їх проектування. В даний час велика увага приділяється питанням комплексного підходу до розробки багатостадійних обслуговуючих систем, включаючи синтез їх структур та створення математичних моделей і методів планування і управління.

Метою функціонування багатостадійних обслуговуючих систем є обслуговування деякого розрахункового портфеля зовнішніх вимог, тобто переліку результатів обслуговування із зазначенням їх кількості, одержувачів та періоду часу на їх формування.

Досить давно з'явилися і успішно вдосконалюються в даний час методи комплексного підходу до управління виробничими об'єктами, для яких також існує мета функціонування -- виконання певного плану постачань готової продукції в заданий термін.

Величезне значення надається завданням комплексного управління виробничими об'єктами, починаючи від невеликих майстерень і закінчуючи великими заводами. У цьому напрямку розроблено безліч методологій, які отримали загальну назву MRP \ CRP (Material \ Capacity Requirements Planning) і ERP (Enterprise Resource Planning) систем.

Обслуговуючі системи цифрового управління та виробничі з точки зору процесу обслуговування вимог, відрізняються одна від одної тільки різновидом і складом обслуговуючих приладів, а також масштабом тривалості стадій обслуговування.

Більшість багатостадійних обслуговуючих систем створюються, існують і функціонують з цілком певною метою. Цією метою є формування деякого набору зовнішніх вимог з відповідного набору вхідних вимог.

Планування та управління обслуговуванням вимог у багатостадійних обслуговуючих системах з портфелем зовнішніх вимог є комплексним завданням, для вирішення якого використовуються різні математичні та організаційні методи.

Особливо слід зазначити, що реальні багатостадійні обслуговуючі системи є багаторівневими. Відомо, що для багаторівневих систем використовуються різні критерії ефективності на різних рівнях управління. Таким чином виникає задача планування процесу обслуговування за умов використання різних критеріїв на різних рівнях. Ця задача не має остаточного розв'язку.

Зважаючи на це, дисертаційна робота, що присвячена побудові математичних моделей дворівневих багатостадійних обслуговуючих систем та розробці методів планування обслуговування такими системами є актуальною.

Зв'язок роботи з науковими програмами, планами, темами.

Дисертаційна робота виконана у відповідності до плану науково-дослідних робіт Харківського національного університету імені В. Н. Каразіна: в межах держбюджетної теми №11-21-10, Обґрунтування методології індикативного стратегічного планування на галузевому та регіональному рівнях в моделі інноваційного розвитку. Номер державної реєстрації 0110U000587.

Мета дослідження. Метою дослідження є підвищення ефективності використання приладів дворівневих багатостадійних обслуговуючих систем за рахунок забезпечення інтеграції тягнучої та штовхаючої стратегій планування обслуговування, що базується на використанні розрахункових параметрів обслуговуючої системи і розробці математичних моделей процесів планування обслуговування і обчислювальних методів їх аналізу.

Задачі дослідження. Для досягнення цієї мети в роботі поставлені і вирішені такі завдання:

- розробити математичні моделі дворівневої багатостадійної системи обслуговування і входять до її складу обслуговуючих комплексів;

- сформулювати принципи та критерії забезпечення інтеграції тягнучої і штовхає стратегій планування;

- розробити і обґрунтувати обчислювальні методи реалізації сформульованих принципів;

- побудувати прототип програмного забезпечення для експериментальної оцінки алгоритмів планування, що реалізують розроблені методи;

- оцінити ефективність розроблених методів з використанням прототипу програмного забезпечення.

Об'єктом дослідження є ієрархічні багатостадійні обслуговуючі системи.

Предметом дослідження є моделі ієрархічних багатостадійних обслуговуючих систем та обчислювальні методи планування процесу обслуговування.

Методи дослідження - методи теорії множин, теорії алгоритмів, XML-технології, теорії імітаційного моделювання використовувалися для побудови математичних і програмних моделей обслуговуючих систем, маршрутів вимог, методів збалансованого планування та синтезу розкладів.

Наукова новизна отриманих результатів.

Наукова новизна отриманих результатів полягає в тому, що в роботі:

1) уперше поставлено і вирішено задачу синтезу розкладів для завантаженого обслуговуючого комплексу;

2) уперше розроблено обчислювальний метод синтезу розкладів для комплексів дворівневої багатостадійної обслуговуючої системи, що забезпечує виконання графіка обслуговування зовнішніх вимог, за рахунок інтеграції стратегій обслуговування «точно в строк» і «вузьке місце»;

3) дістав подальший розвиток метод комп'ютерного експерименту для вирішення задач оцінки ефективності розкладів обслуговування;

4) удосконалено математичну модель дворівневої багато стадійний обслуговуючої системи, що дозволило уніфікувати підхід до задач планування обслуговування для систем різної природи.

Практичне значення отриманих результатів полягає в тому, що на підставі математичних моделей обслуговуючої системи, складових її комплексів і маршрутів вимог, а також методу збалансованого планування та синтезу розкладів розроблено:

- схему сховища даних про структуру обслуговуючої системи і маршрутах обслуговування вимог, і її реалізація засобами XML-технології;

- методи збалансованого планування та синтезу розкладів;

- імітаційну систему моделювання процесу обслуговування.

Результати роботи були впроваджені в ТОВ «Константинівский завод механічного обладнання».

Особистий внесок здобувача. Всі результати дисертаційної роботи отримані автором самостійно. У публікаціях автору належать такі результати: побудовано математичну модель і розроблено метод інтерактивне-нормативної балансування портфеля зовнішніх вимог багатостадійної обслуговуючої системи [5,7], запропоновані моделі і методи планування обслуговування комплексів багатостадійної системи [1-4], побудована математична модель стану приладів багатостадійного обслуговуючого комплексу і на її основі розроблено систему моделювання процесу обслуговування для перевірки ефективності методів синтезу розкладів шляхом порівняння з методом повного перебору [6].

Апробація результатів дисертації. Основні результати діссертації доповідалися, обговорювалися і отримали позитивну оцінку на міжнародній науково-практична конференція «Сучасні інформаційні технології в управлінні та професійній підготовці операторів складних систем» в грудні 2003р. у Кіровограді, III- ій міжнародній науково-практичній конференції «Динаміка наукових досліджень 2004» у червні 2004 р. у Дніпропетровську, VI1-ій всеукраїнській науково-практічній Конференції "Комп'ютерне моделювання та Інформаційні Технології в науці, економіці та освіті" У квітні 2005 р.. у Кривому розі, II-й міжнародній науково-практичній Конференції «Сучасні Наукові Дослідження - 2006» у лютому 2006 р., XIV-ій міжнародній науково-практичній конференції «Інформаційні технології: наука, техніка, освіта, здоров'я» у травні 2006 р. у Харкові, I -й міжнародній науково-практичній конференції «Новини наукової думки - 2006» в листопаді 2006 р. в Дніпропетровську.

Публікації. Основні положення дисертації викладені в 7-ми науково-технічних статтях, які входять до спеціальних видань ВАК України.

Структура та обсяг роботи. Дисертація складається з вступу, чотирьох розділів з висновками в кінці кожного з них, загальних висновків, списку використаних джерел та додатків. Загальний обсяг дисертації становить 228 сторінок, включаючи 28 малюнків, 9 таблиць, список використаних джерел у кількості 121 назва на 13 сторінках і трьох додатків на 100 сторінках.

ОСНОВНИЙ ЗМІСТ РОБОТИ

багатостадійний обслуговуючий інтеграція планування

Введення до дисертаційної роботи містить: актуальність теми і наукові завдання; зв'язок роботи з науковими програмами, планами, темами; мета і завдання дослідження: об'єкт, предмет і методи дослідження; наукову новизну і практичне значення отриманих результатів; особистий внесок здобувача; інформацію про реалізацію, апробації і публікації результатів.

Перший розділ роботи присвячений оглядовому аналізу теоретичних і прикладних робіт з питань синтезу структури планування і управління багатостадійним обслуговуючими системами і містить основні визначення, що використовуються в дисертаційному дослідженні.

У теорії систем цифрового керування об'єктами в реальному масштабі часу існують і описані комплексні підходи до вирішення завдань планування і управління ними та синтезу їх архітектури, описані в роботах Смілянського Р. Л., Костенко В. А., Marco Caccamo.

Створення мереж, керуючих групами алгоритмічно подібних об'єктів, на базі спецобчислювача з використанням RISC і CISC процесорів є ще більш складним завданням. Збільшення продуктивності та підвищення якості мереж вбудованих систем в першу чергу досягається за рахунок комплексного підходу до синтезу, планування та управління ними. Такий підхід грунтується на методах теорії масового обслуговування в роботах Michael S. Branicky, Смілянського Р. Л., Костенко В. А., Christos G. Panayiotou, або з використанням генетичних алгоритмів Трекін А. Г., Костенко В. А. З іншого боку досить давно з'явилися і успішно розвиваються методи комплексного підходу до управління виробничими системами, в яких також існує і багатостадійність технологічних процесів і мета - виконання певного плану постачань готової продукції певної конструктивної складності в задані терміни.

У плануванні та управлінні виробничими багатостадійним обслуговуючими системами широко відомі методології комплексного підходу MRP \ CRP (Material \ Capacity Requirements Planning) і ERP (Enterprise Resource Planning).

У публікаціях Олівера Уайта та Американського товариства з управління запасами і управління виробництвом були сформульовані методи планування, сьогодні відомі як MRP (Material Requirements Planning) - планування потреб у матеріалах - наприкінці 60-х років, і MRP II (Manufacturing Resource Planning) - планування ресурсів виробництва - в кінці 70-х-початку 80-х рр.

У 50-х роках на підприємствах автомобільного концерну з'явився метод планування та управління Just-in-time (JIT - Точно вчасно).

Методи OPT (Optimised Production Technology - оптимізована технологія виробництва) створені в Ізраїлі у 70-х роках. Методи OPT призначені для максимізації випуску продукції при скороченні обсягу запасів і виробничих витрат. В їх основі лежить визначення «вузьких місць» «BottleNeck». Роботи Chakravorty S. S., Yeh M.-L., Pegels.

Особливе місце в теорії управління багатостадійним обслуговуючими системами займає завдання синтезу оптимальних розкладів обслуговування вимог приладами безпосередньо.

У 30-х роках ХХ сторіччя з'явилася постановка загальної Nр-повної задачі теорії розкладів (Scheduling Theory).

Для «швидкого» вирішення цього завдання традиційно використовують:

подання приладів і маршрутів вимог у вигляді графів з навантаженими вершинами або ребрами і застосовують різні методи оптимізації шляхів на графах Танаєв В. С., Соцький Ю. М., Струсевич В. А., Прилуцький М. Х., Blazewicz J., Прус В. В.;

ѕ евристичні пріоритетні правила Steinhofel A.;

ѕ стохастичні методи Mastrolilli M., Gambardella LM, Jansen K., Vukobratovic M., Dauzere-Peres S.;

ѕ генетичні алгоритми Kacem I., Hammadi S., Gonsalves J.F., Mendes J. J., Borne P.

У загальній постановці цього завдання і запропонованих методів її розв'язання, прилади вважаються вільними, а набір вимог і набір приладів ніяк не пов'язані системно, що завжди може призвести до ситуації, коли деякі прилади будуть перевантажені вимогами, а деякі будуть велику частину часу простоювати через відсутність вимог до них.

У той же час існує безліч додатків цього завдання, в яких на момент прийняття рішень обслуговують прилади зайняті обслуговуванням попередніх вимог, а самі вимоги мають цілком певний характер, як по порядку і тривалості обслуговування приладами, так і за їх угруповання. Аналіз існуючих підходів показав, що в більшості реалізацій планування обслуговування багатостадійним системами використовує метод «точно вчасно» «Just-in-time» або метод визначення «вузьких місць» «BottleNeck»]. Застосування методу «точно в строк» цілком відповідає реалізації тягнучої стратегії і забезпечує виконання портфеля зовнішніх вимог багатостадійної обслуговуючої системою. Однак його застосування на всіх стадіях процесу обслуговування призводить до формування довгострокових і зайво деталізованих розкладів, які в дійсності практично ніколи не виконуються точно, в силу недосконалості технічної обслуговуючої бази системи (відмови обслуговуючих приладів, елементів транспортних систем, помилки персоналу і т.п.)

Аналогічним чином метод визначення «вузьких місць» відповідає реалізації штовхає стратегії планування і дозволяє максимально можливим чином завантажити елементи багатостадійної обслуговуючої системи, але його тотальне застосування може внести дисбаланс у підсумкові стадії обслуговування і призвести до порушення термінів обслуговування портфеля зовнішніх вимог системи.

У роботі Olhager J. «An integrated push-pull manufacturing strategy» запропонована ідея підходу до вирішення цих суперечностей шляхом створення методу дворівневого планування для забезпечення синтезу тягнучої і штовхає стратегій. На верхньому рівні планування, рівні комплексів системи, застосовується тягне стратегія, що забезпечує виконання портфеля зовнішніх вимог, а на нижньому рівні, рівні планування обслуговування приладами кожного комплексу, застосовується штовхає стратегія, що забезпечує максимально можливу завантаження приладів.

Розрахункові характеристики задаються інвесторами і розраховуються на етапах технологічної та організаційної підготовки процесу обслуговування і включають в себе розрахунковий портфель зовнішніх вимог із зазначенням загального часу їх повного обслуговування і прибороємкості обслуговування кожного типу зовнішніх вимог та їх складових. Математичні моделі цих характеристик використовуються в даній роботі в якості вихідних даних для розробки дворівневої ієрархічної моделі планування багатостадійної обслуговуючої системою.

Для вирішення завдань планування обслуговування необхідне створення адекватних математичних моделей, а також розробка відповідних обчислювальних методів.

Другий розділ роботи присвячений розробці математичних моделей портфеля зовнішніх тренованій і структури багатостадійної обслуговуючої системи, а також методу розрахунку збалансованого портфеля зовнішніх вимог.

Нехай - час обслуговування розрахункового портфеля зовнішніх вимог.

Розрахунковий портфель портфеля зовнішніх вимог це множина пар

, де:

- код результату обслуговування.

- кількість яке многостадійна обслуговуваюча система може обслугувати за час .

- загальна кількість типів зовнішніх вимог у номенклатурі багатостадійної обслуговуючої системи.

Розрахункова множина прибороємності обслуговування

де:

- сумарний час обслуговування всіх стадій всіх вимог, що входять до , усіма типами приладів системи, тобто прибороємність.

На підставі обчислень розрахункового спектру і розрахункового коефіцієнта паралельності обслуговування зовнішніх вимог Із введено визначення збалансованості:

Планування багатостадійної обслуговуючої системи на деякий період часу називається збалансованим якщо виконані дві умови:

1. . Спектри планованого і розрахункового портфелів зовнішніх вимог збігаються, що означає збіг якісного складу обслуговуючих приладів системи.

2. . Коефіцієнти паралельності збігаються, що означає збіг кількісного складу обслуговуючих приладів системи.

На підставі цього визначення обчислюється оптимальний інтервал збалансованого планування обслуговування і будується математична модель багатостадійної обслуговуючої системи на рівні обслуговуючих комплексів у вигляді трійки

, де:

- інтервал сбалансованого планувания;

- обслуговуючий комплекс у складі системи;

- кількість обслуговуючих комплексів;

- граф опису обслуговуючих ланцюжків, вершинами якого є обслуговуючі комплекси системи.

Орієнтований граф опису обслуговуючих ланцюжків системи представляється матрицею суміжності розмірності з нульовою діагоналлю.

Елементами матриці суміжності є описи множин , вимог, які входять і виходять, та їх належності типам зовнішніх вимог, а також час їх транспортування . Строчка матриці описує всі вихідні вимоги, що обслуговуються і передаються комплексом іншим комплексам системи. Стовпчик матриці описує всі вхідні вимоги, одержувані комплексом , від інших комплексів системи. Якщо комплекси і один з одним не пов'язані, то відповідний елемент матриці представляється порожнім елементом. Математична модель елементів матриці :

, . де:

- код зовнішньої вимоги.

- код вимоги, у складі зовнішньої вимоги . Визначається графом складу зовнішньої вимоги .

- приладоємність обслуговування вимоги приладами комплексу . Визначається технологами.

- кількість екземплярів вимог у складі зовнішньої вимоги . Визначається графом складу зовнішньої вимоги .

- коефіцієнт браку і запасних частин вимоги . Визначається технологами и організаторами обслуговування.

- кількість типів вимог у складі , переданих від комплексу до комплексу .

- загальна кількість зовнішніх вимог у номенклатурі багатостадійної обслуговуючої системи.

- час транспортування вимог, що обслужені комплексом , на вхід комплексу . Визначається організаторами процесу обслуговування, виходячи з можливостей транспортної підсистеми.

- величина інтервалу часу власного запізнювання управління комплексу . Розрахункова величина.

По всіх рядках матриці суміжності обчислюється набір величин:

.

Інтервал часу є максимальний час від початку обслуговування до моменту виходу з комплексу першого з відповідних вимог множини по матриці суміжності , оскільки кожний екземпляр будь-якої вимоги обслуговується приладами комплексу послідовно.

Звідси випливає, що величина , є величиною інтервалу власного запізнювання управління комплексу без врахування транспортування. Величини и представляють собою вагові параметри ребер графа , тобто граф стає зваженим органом..

Для визначення величини повного інтервалу часу запізнювання управління усієї системи , включно з між комплексним транспортуванням, використовується відомий метод Дейкстра, модифікований для пошуку максимального шляху на зваженому оргафі .

За інформацією про розрахунковий портфелі зовнішніх вимог і на підставі визначення збалансованого планування розроблено метод балансування множини зовнішніх вимог багатостадійної обслуговуючої системи:

, де:

- календарний термін (дата) кінця обслуговування;

- код зовнішньої вимоги;

- потрібна кількість ( якщо вимога відсутня);

- загальна кількість зовнішньої вимог у номенклатурі системи;

- кількість дат у множині .

Сутність методу полягає в тому, що при послідовному балансуванню множини зовнішніх вимог на плановані періоди , , …, деякі зовнішні вимоги запозичуються з більш пізніх періодів планування, а при необхідності перенесення будь-яких зовнішніх вимог на більш пізні періоди метод видає відповідні рекомендації плануючим службам. Час запізнювання управління системи використовується методом балансування для визначення принципової можливості дотримання термінів обслуговування вимог множини .

Третій розділ містить опис математичних моделей і методів нижнього рівня планування, рівня приладів комплексу, тобто методу синтезу розкладів обслуговування вимог приладами багатостадійних обслуговуючих комплексів. Обслуговуючий комплекс може бути представлений у вигляді четвірки

,, де:

- коефіцієнт перерв в обслуговуванні ( при наявності обслуговуючого персоналу, у протилежному випадку );

- номер (код) модел1 приладу;

- коефіцієнт профілактичних (регламентних) простоїв приладу ( причому його конкретне значення визначається паспортними характеристиками приладу, встановленими виробником);

- кількість приладів моделі в складі комплексу;

- кількість різних моделей приладів комплексу;

- кількість обслуговуючих комплексів у складі системи.

Комплекс призначений для обслуговування вхідних вимог, зазначених у відповідному стовпці матриці суміжності системи , і перетворення їх у вихідні вимоги, зазначені у відповідному рядку матриці суміжності системи .

Таким чином, маршрути обслуговування вихідних вимог (кадрів керуючих впливів, призначених для користувача вихідних форм, деталей, вузлів, виробів) цього комплексу є множина:

, де:

- унікальний номер (код) вихідної вимоги;

- транспортний пакет (кількість вимог у транспортному пакеті);

- опис стадій обслуговування вимоги приладами комплексу .

- кількість вимог у номенклатурі комплексу;

Опис стадій обслуговування вимоги приладами комплексу є множина, включає такі параметри їх обслуговування, які можуть істотно вплинути на час обслуговування кожної стадії:

,

де:

- номер стадії;

- множина вхідних та допоміжних вимог, необхідних для обслуговування даної стадії;

- номер (код) моделі приладу ;

, , , , , , , , - параметри, які впливають на час обслуговування відповідної стадії вимоги ;

- кількість стадій обслуговування вимоги .

Сума

,

, ,

являє собою повний фонд часу обслуговування всієї групи приладів моделі , необхідний для обслуговування всіх вимог з .

У враховані втрати часу на загальні перерви в обслуговуванні, профілактичне обслуговування приладів, розмір транспортного пакета, час транспортування, встановлення і заміни інструментальних і платформних вимог.

На основі , побудуємо:

множину часів повного завантаження одного приладу групи ,

,.

и множину

де: .

Множина являє собою множину інтенсивностей обслуговування вимог кожним приладом групи , , вимірювану у вимогах за одиницю часу.

Розглянемо групу приладів , таку, що

.

Визначення.

Група називається критичною (аналог Bottle Neck) для обслуговування пакета вимог .

На підставі визначення критичної групи сформульовано і доведено твердження про критичну групу приладів:

Нехай у мінімальному, отриманому повним перебором усіх варіантів послідовностей запуску вимог з , розкладі інтенсивність обслуговування приладами критичної групи дорівнює . Тоді .

І виведено наслідок:

Для розклад, мінімальний по загальному часу обслуговування розташований у множині розкладів з мінімальними простоями критичної групи приладів.

Побудовано динамічну модель процесу обслуговування комплексу .

Припустимо, що на вхід комплексу , в момент часу надійшов пакет вихідних вимог з у вигляді множини .

Побудуємо формальну модель оперативного стану обслуговування приладів комплексу на поточний момент часу .

Розглянемо множину обслуговування вимог попередніх ітерацій:

, де

;

- умовний номер, який присвоюється системою управління в момент початку першої стадії і звільняється після виконання останньої для будь-якого.. ;

- початок кінець повного обслуговування вимоги приладами комлексу , причому .

Множина поточного стану обслуговування вимог приладами комплексу :

, где,

де:

- інтервал простою приладу моделі .

- інтервал обслуговування -м приладом -ої моделі вимоги з системним номером .

В якості основного інструменту оптимізації процесу обслуговування розроблено обчислювальний метод синтезу розкладу обслуговування одиничної вимоги.

На підставі визначення критичної групи приладів розроблений жадібний метод синтезу оптимального розкладів обслуговування вимог приладами комплексу .

Метод полягає в послідовному аналізі змін простоїв критичної групи приладів, з використанням методу синтезу розкладу обслуговування одиничної вимоги, для кожної з тих вимог, які залишилися в пакеті вихідних вимог та прийнятті рішень про обслуговування того з них, яке забезпечує мінімум простоїв критичної групи приладів. Вимога, прийнята до обслуговування на черговому кроці методу, виключається із множини .

Метод виконується в моменти зміни інтервалів зайнятості множини .

Четвертий розділ присвячений розробці імітаційної системи та аналізу з її допомогою ефективності методів синтезу розкладів, розроблених в розділі 3.

На підставі формальних описів множин обслуговуючої системи , обслуговуючого комплексу , номенклатури и маршрутів вихідних вимог , пактів вихідних вимог , поточного динамічного стану завантаження приладів та зв'язків між ними була побудована модель зберігання та засоби супроводу відповідних XML-документів.

На мові програмування JAVA були реалізовані:

- алгоритм синтезу розкладу обслуговування одиничної вимоги;

- жадібний алгоритм синтезу розкладів обслуговування вимог приладами комплексу , розроблений на підставі динамічного визначення критичною групи приладів та мінімізації її простоїв;

- алгоритм повного перебору послідовностей запуску вимог (модифікований алгоритм 2-го методу Д. Е. Кнута) і визначення послідовності з мінімальною довжиною розкладу;

- загальний алгоритм управління режимами моделювання.

Режим «Прогін з зупинкою за часом» використовується при моделюванні для забезпечення деякого початкового стану зайнятості приладів обслуговуючого комплексу.

Режим «Дослідження алгоритмів оперативного управління » застосуються для перевірки ефективності, за критерієм мінімізації загального часу обслуговування, будь-яких алгоритмів синтезу розкладів в порівнянні з алгоритмом повного перебору послідовностей запуску вимог.

Результатом роботи є таблиці, які містять підсумкові послідовності запуску вимог досліджуваного алгоритму та алгоритму повного перебору і порівняння довжини цих розкладів у відсотках.

Общ. к-во приборов = 9. Р-р загр. пакета = 11.

Шаги: перебора = 498119, алгоритма = 46.

CPU-Time(мс.): перебора = 2219, алгоритма = 31.

Длина расписания:

Полный перебор: min 302max 501

Проверяемый алгоритм 320

Расхождение 5.96026 %

Приклад таблиці результатів дослідження.

Режим «Розробка об'ємних план-графіків» використовується для складання реальних розкладів обслуговування вимог по тим алгоритмам, які досліджувалися у попередніх режимах і показали достатню ефективність. Результатом роботи режиму є таблиця завантаження приладів комплексу із зазначенням вимоги, стадії обслуговування, абсолютного часу початку і кінця стадії і відносного часу транспортування до приладу наступної стадії. Таблиця відсортована за назвами груп приладів і по номерах приладів у групі.

Планируемая длина расписания: 4 час 30 мин

Приклад таблиці моделі план-графіку.

Результати моделювання.

Відбувалося моделювання процесу обслуговування вимог для двох комплексів к1 і к2. За браком місця розглянемо моделювання комплексу к1. Комплекс к1 складається з приладів моделей р1 -2 шт., р2 - 4 шт., р3 - 3шт.

Для комплексів к1та к2 були задані множини маршрутів обслуговування вимог у вигляді:

На вхід комплексу подавалися різні варіанти пакетів заявок на обслуговування вимог і проводився аналіз довжини розкладу.



Приклади таблиць з результатами моделювання жадібного методу синтезу розкладів на основі визначення критичної групи приладів наведені у Додатках А, Б.

Моделювалися два варіанти обслуговування.

У першій серії експериментів моделювалося обслуговування набору з 11 вимог у випадкових поєднаннях.

Рис. 2. Діаграма тривалості розкладів.

У другій серії експериментів збільшення вхідного пакету для наступного етапу моделювання відбувалося шляхом послідовного додавання однієї вимоги, випадково обраної з відповідної номенклатури.

На рис. 2 та 3 показані результати першої серії експериментів для комплексу к1 у вигляді діаграм.



Рис. 3. Відхилення у % довжини мінімального розкладу.

У другій серії експериментів збільшення вхідного пакету для наступного етапу моделювання відбувалося шляхом послідовного додавання однієї вимоги, випадково обраної з відповідної номенклатури.

На рис. 4 та 5 показані результати другої серії експериментів для комплексу к1 у вигляді діаграм.

Рис. 4. Діиаграма тривалості розкладів.

Рис. 5. Відхилення у % довжини мінімального розкладу.

Моделювання показало, що довжина мінімальних жадібних розкладів при одних і тих же початкових станах завантаження приладів комплексів к1 і к2 відрізняється від довжини розкладів, отриманих за допомогою алгоритму повного перебору не більше ніж на 0-10% в 70-100% випадків по відношенню до загальної кількості експериментів.

Було проведено близько двох тисяч експериментів, які показали досить стабільні результати.

Результати моделювання наведені у додатках А і Б до дисертаційної роботи.

ВИСНОВКИ ПО РОБОТІ

Основні результати, які були отримані в роботі, полягають у наступному:

1. Розглянуто дворівневу обслуговуючу систему і обгрунтовано вибір стратегій планування: «тягнучий» для підсистеми верхнього рівня (рівень комплексів системи) і «штовхаючий» для підсистем нижнього рівня (рівень приладів комплексу). Для реалізації «тягнучої» стратегії обрано метод «точно в строк». Для реалізації «штовхачої» стратегії обрано метод «вузьке місце».

2. Побудовано математичну модель портфеля зовнішніх вимог і їх розрахункових часових характеристик. Розроблено методи обчислення спектральної характеристики розрахункового і довільного портфелів зовнішніх вимог і коефіцієнта паралельності.

3. На основі спектральної характеристики і коефіцієнта паралельності дано визначення збалансованості довільного портфеля зовнішніх вимог та розроблений метод його балансування.

4. Розроблено обчислювальний метод визначення величини запізнювання планування для кожного багатостадійного обслуговуючого комплексу і для системи в цілому.

5. Розроблено та обґрунтовано обчислювальний метод синтезу збалансованої за часом програми обслуговування пакетів зовнішніх вимог обслуговуючими комплексами з урахуванням запізнювання планування системи і відповідно до «тягнучої стратегії» планування з використанням методу її реалізації «точно в строк».

6. Побудовано математичну модель обслуговуючого комплексу, пакетів вихідних вимог, розкладів обслуговування вимог приладами комплексу і на їх основі обраний клас жадібних розкладів.

7. Сформульовано визначення критичної групи приладів і доведено твердження про необхідність мінімізації її простоїв. На підставі слідства з цього твердження розроблено обчислювальний метод синтезу жадібних розкладів, який реалізує «штовхає» стратегію планування процесу обслуговування приладами комплексу, що базується на мінімізації простоїв критичної групи приладів (розвиваючий метод «вузьке місце ») і зроблено оцінку його обчислювальної складності.

Для оцінки ефективності обчислювальних методів синтезу розкладів розроблена і реалізована система імітаційного моделювання, що використовує XML-технологію для представлення моделей обслуговуючого комплексу, пакету вихідних вимог, стадій обслуговування вимог, розкладів обслуговування вимог і результатів моделювання.

9. Шляхом постановки серій комп'ютерних експериментів для запропонованого в роботі методу синтезу жадібних розкладів з використанням системи імітаційного моделювання, оцінена ефективність цього методу з точки зору мінімізації простоїв приладів. Оцінка проводилася за допомогою програми Microsoft Excel шляхом експорту результатів моделювання, подальших розрахунків і побудови графіків.

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ

1. Али Найф Халил Альхжуж. Моделирование многофазных обслуживающих комплексов/ Али Найф Халил Альхжуж, Игнатов С. Ю. // Системи обробки інформації. - Х.: Харківський університет повітряних сил ім. Івана Кожедуба. Збірник наукових праць - Випуск 6(55), 2006. - С. 164-174.

2. Али Найф Халил Альхжуж. Оперативное планирование многофазных обслуживающих комплексов. / Жолткевич Г. Н., Игнатов С. Ю. // Харківський університет повітряних сил ім. І. Кожедуба. Збірник наукових праць. - Випуск 6(12), 2006. - С. 53-57.

3. Али Найф Халил Альхжуж.Оперативное управление многофазными обслуживающими комплексами. / Али Найф Халил Альхжуж, Жолткевич Г.Н., Игнатов С. Ю. // Радіоелектронні комп'ютерні системи. - Випуск 4(16), 2006.- Харків, “ХАІ”. - С. 109-118.

4. Али Найф Халил Альхжуж. Моделирование многофазных обслуживающих комплексов с постоянным циклом. / Али Найф Халил Альхжуж, Игнатов С. Ю. // Вісник Харківського національного університету ім. В. Н. Каразіна, Серія “Математичне моделювання. Інформаційні технології. Автоматизовані системи управління.”. - № 733, 2006, - С. 17-24.

5. Али Найф Халил Альхжуж. Моделирование статического и динамического портфелей заявок для многофазных обслуживающих систем. / Али Найф Халил Альхжуж, Игнатов С. Ю // - Системи обробки інформації..- Х.: Харківський університет повітряних сил ім. І. Кожедуба. Збірник наукових праць - Випуск 9(58), 2006. - С. 115-119.

6. Али Найф Халил Альхжуж, Гончаров И. Е., Игнатов С. Ю., Моделирование процессов оперативного управления многостадийными обслуживающими системами. / Али Найф Халил Альхжуж, Гончаров И. Е., Игнатов С. Ю // Системи обробки інформації. Х.: МОУ, ISSN 1681-7710, Харківський університет повітряних сил ім. Івана Кожедуба. Збірник наукових праць, Випуск 2(60), 2007. - С.2-6.

7. Али Найф Халил Альхжуж. Моделирование и синтез сбалансированных программ обслуживания / Али Найф Халил Альхжуж, Жолткевич Г.Н., Игнатов С. Ю // Системи управління, навігації та зв'язку, - Випуск 1(17), 2011. - С.165-168.

Размещено на Allbest.ru