ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Державний комітет зв’язку та інформатизації України
Національна академія наук України
Державний науково-дослідний інститут інформаційної інфраструктури
Марецький Януш
УДК 681.513
МОДЕЛЮВАННЯ ТА ОПТИМІЗАЦІЯ КОМПЛЕКСУ ОПЕРАЦІЙ ОБСЛУГОВУВАННЯ КОРАБЛІВ У ПОРТУ
Спеціальність: 01.05.02 – математичне моделювання та обчислювальні методи
Автореферат
дисертації на здобуття наукового ступеня
кандидата технічних наук
Львів – 2004
Дисертацією є рукопис
Робота виконана у Державному науково-дослідному інституті інформаційної інфраструктури Державного комітету зв’язку та інформатизації і Національної академії наук України
Науковий керівник:
Грицик Володимир Володимирович, чл.-кор. НАН України, доктор технічних наук, професор, Державний науково-дослідний інститут інформаційної інфраструктури, директор
Офіційні опоненти:
Сікора Любомир Степанович, доктор технічних наук, старший науковий співробітник, Державний науково-дослідний інститут інформаційної інфраструктури, пров. наук. співр.
Олексів Богдан Ярославович, кандидат технічних наук, старший науковий співробітник, Західноукраїнський інститут інформаційних технологій і управління при Донецькому державному університеті управління, зав.кафедрою
Провідна установа:
Національний університет “Львівська політехніка” Міністерства освіти і науки України, кафедра інформаційних систем та мереж
Захист відбудеться 04 січня 2005 р. о 14 год. на засіданні спеціалізованої вченої ради Д 35.813.01 Державного науково-дослідного інституту інформаційної інфраструктури (79601, м.Львів, вул.Тролейбусна, 11).
З дисертацією можна ознайомитись у бібліотеці Державного НДІ інформаційної інфраструктури (79601, м. Львів, вул. Тролейбусна, 11).
Автореферат розіслано 03 грудня 2004 р.
Вчений секретар Спеціалізованої вченої ради, докт. техн. наук, проф. |
Бунь Р.А.
Загальна характеристика роботи
Актуальність теми. Проблема моделювання та оптимізації обслуговування кораблів у портах в загальному випадку полягає у формуванні графіків взаємодії N об’єктів в системі, яка складається з M агрегатів з часовими, просторовими і логічними обмеженнями. З точки зору обчислень ця проблема є NP-складною. Тому актуальним є розроблення ефективних методів та алгоритмів для вирішення таких проблем, в яких беруться до уваги час, кошти та обчислювальні затрати.
В різноманітних практичних застосуваннях загальна задача обслуговування N об’єктів в M агрегатах породжує ряд специфічних і оригінальних математичних моделей. Такою є, зокрема, ситуація, з якою зустрічаємося у випадку обслуговування кораблів у порту. Запропоновані та опрацьовані моделі процесів обслуговування в порту є оригінальними та актуальними. Розв’язані в дисертаційній роботі задачі знаходяться на стику задач масового обслуговування (порт є місцем обслуговування суден, а рейд – місцем очікування) і задач оптимізації в комбінаториці. Складність проблеми полягає у встановленні підмножин об’єктів, які мають обслуговуватися системою агрегатів у послідовні інтервали часу. Виходячи з теоретичної цінності та різноманітного практичного застосування, вказані проблеми є предметом всесторонніх досліджень.
Актуальність проблеми обслуговування пароплавів в портах підтверджується багатьма доповідями на міжнародних конференціях (зокрема, на регулярних міжнародних конференціях „Marine Traffic Engineering”, Szczecin Meritime University, Swinoujњcie) ?а численними публікаціями (наприклад, монографія I.Janiszczak „Systemy sterowania i zarzadzania ruchem statkуw w porcie”, Szczecin, Wyїsza Szkoіa Morska, 2001).
Проблема обслуговування кораблів у портах є складною задачею комбінаторики з неповною інформацією. Для розв’язування цієї задачі в роботі використовуються нові методи моделювання (наприклад, семантичні мережі) i нові алгоритми (наприклад, інтелектуальні агенти). Реалізація отриманих розв’язків є можливою з використанням розробленого автором програмного забезпечення.
Зв’язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалася в рамках планових науково-дослідних робіт Академії інформатики та управління в м.Бєльско-Бяла (Польща), зокрема в рамках теми “Математичне моделювання систем обслуговування” (1999-2004 рр.). Результати досліджень автора, які отримано в рамках співпраці з Державним НДІ інформаційної інфраструктури (м.Львів) опубліковано в матеріалах ряду міжнародних та національних конференцій. Роботи з моделювання і оптимізації обслуговування пароплавів у портах проводилися також разом з Щецінською Політехнікою (Польща).
Мета та задачі дослідження. Метою дисертаційної роботи є розробка та дослідження математичних моделей, алгоритмів і програмних засобів для ефективної оптимізації сукупності операцій обслуговування кораблів у портах. Для реалізації поставленої мети проведено декомпозицію проблеми шляхом виділення моделей портів з різними структурами причалів і портових басейнів. Загальну проблему оптимізації обслуговування кораблів поділено на підпроблеми для портів із заданою структурою. Для кожної з виділених підпроблем розроблено математичні моделі та відповідні алгоритми оптимізації обслуговування суден.
У відповідності з поставленою метою дисертаційна робота включала розв’язання таких основних завдань:
·
аналіз відомих методів структурного моделювання комплексу операцій і розроблення на цій основі ефективних методів опису операцій обслуговування кораблів у порту;
·
аналіз алгоритмів оптимізації і розробка інтелектуального алгоритму знаходження розв’язку комбінаторних задач з неповною інформацією;
·
розробка математичних моделей та алгоритмів оптимізації обслуговування кораблів у портах для різних моделей портів, а також з врахуванням часових, логічних і просторових обмежень;
·
розробка програмного забезпечення для опису і моделювання сукупності операцій та оптимізації обслуговування кораблів у порту.
Об’єктом дослідження є порт, який розглядається як система з послідовно-паралельною структурою. З точки зору теорії масового обслуговування це є система як з зовнішнім (рейд), так і з внутрішнім (портовий басейн) місцями очікування. В системі наявні також місця обслуговування (причали), які сполучені каналами, що в сукупності утворюють послідовно-паралельну структуру.
Предметом дослідження є математичні моделі та алгоритми оптимізації процесів обслуговування кораблів у порту.
Методи дослідження. Для побудови математичних моделей та алгоритмів оптимізації обслуговування кораблів використано методи комбінаторики та теорію інтелектуальних агентів, методи симуляції на комп’ютері. З точки зору теорії оптимізації досліджувана система складається з M агрегатів, в яких необхідно оптимізувати процес обслуговування N об’єктів. Сформульована проблема є NP-складною і вимагає розробки нових ефективних алгоритмів для її розв’язування.
Наукова новизна одержаних результатів полягає в наступному:
·
вперше розроблено семантичні мережі для моделювання і оптимізації сукупності операцій обслуговування кораблів у порту, в яких вузли мережі представлено матрицями, залежними від структури порту, і які дають можливість відображати типові структури порту: базові, послідовні, паралельні, дерева, анти-дерева і послідовно-паралельні;
·
вперше розроблено математичні моделі та інтелектуальні алгоритми проходження семантичних мереж, які базуються на рекурсивних методах генерування нових вузлів мережі, що зберігають слід при поверненні, і дають можливість знаходити часткові розв’язки загальної проблеми оптимізації обслуговування кораблів;
·
запропоновано та обґрунтовано процедури генерування вузлів семантичної мережі (станів системи) з врахуванням хронологічного порядку, що дозволяє синхронно генерувати послідовні стани процесу, врахувати обмеження портових басейнів і уникнути повторного генерування вже знайдених часткових розв’язків;
·
розроблено методи паралельного проходження семантичних мереж, які відповідають послідовним, синхронним чи паралельним процесам обслуговування і дають можливість розпаралелити обчислення при знаходженні оптимального розв’язку.
Практичне значення та реалізація результатів. Практична цінність результатів дисертаційної роботи полягає в тому, що в ній запропоновано і розроблено методи моделювання та оптимізації сукупності операцій в системах з паралельно-послідовною структурою, які є основою для створення ефективних програмних засобів оптимізації процесів обслуговування кораблів у порту. Введення в математичні моделі та алгоритми процедур хронологічного впорядкування дає можливість здійснювати комп’ютерні симуляції реальних процесів прийняття диспетчерських рішень. Розроблені комп’ютерні симулятори дають можливість диспетчерам портів здійснювати обслуговування кораблів при змінних в часі параметрах середовища.
Симулятори обслуговування кораблів у портах можна використовувати для навчання диспетчерів з використанням наперед підготовлених чи згенерованих псевдовипадкових даних. Ряд розроблених методів та підходів використано в навчальному процесі Академії інформатики та управління в м.Бєльско-Бяла.
Особистий внесок здобувача. Всі результати, що складають зміст дисертаційної роботи, отримані автором дисертаційної роботи самостійно. У публікаціях, написаних у співавторстві, авторові дисертації належать: [11,15,18] – розроблення математичних моделей та алгоритмів оптимального обслуговування для різних варіантів портів; [10] – підходи до використання засобів штучного інтелекту для знаходження розв’язків.
Апробація роботи. Основні наукові результати та положення дисертаційної роботи доповідалися та обговорювалися на ряді міжнародних та національних науково-технічних конференцій, в тому числі на: Першій міжнар. конф. з індуктивного моделювання “МКІМ-2002” (Львів, 2002 р.); Intern. Conf. „Marine Traffic Engineering” (Swinoujњcie, 2003 ?.); Intern. Conf. „Intellectual and Multiprocessing Systems” (Геленджик, Краснодарський край, 2003 р.); міжнар. конф. “Мікропроцесорні пристрої та системи автоматизації виробничих процесів” (Хмельницький, 2003 р.); Бескидському фестивалі науки (Бєльско-Бяла, 2001 р.); міжнар. школі-семінарі “Моделювання та штучний інтелект” (Львів, 2002 р.); наукових семінарах Державного НДІ інформаційної інфраструктури, м.Львів та Академії інформатики та управління м.Бєльско-Бяла, Польща на протязі 1999-2004 рр.
Публікації. За матеріалами дисертаційної роботи опубліковано 20 наукових праць, серед яких 5 навчальних посібників, 4 статті у фахових наукових виданнях України, 2 статті в інших наукових збірниках, 2 препринти, 7 статей в працях наукових конференцій.
Структура та обсяг дисертації. Дисертаційна робота складається із вступу, чотирьох розділів, висновків, списку використаних джерел та додатку. Робота викладена на 228 сторінках, містить 148 сторінки основного тексту та список літератури із 170 найменувань.
Основний зміст роботи
У вступі наведено загальну характеристику роботи, обґрунтовано її актуальність, сформульовано мету та основні завдання досліджень, визначено наукову новизну та практичну цінність отриманих результатів, а також викладено короткий зміст роботи.
В першому розділі детально описано порт як об’єкт дослідження та сформульовано задачу моделювання і оптимізації обслуговування кораблів. Розглянуто питання моделювання структури порту, структури сукупності операцій обслуговування кораблів та структури мережі прийняття рішення в процесі оптимізації. На основі наукової літератури з цієї галузі, проаналізовано відомі підходи до розв’язування задач моделювання та оптимізації процесів обслуговування.
Порти розглядаються як змінні системи з паралельно-послідовною структурою, вони складаються з M1 розвантажувальних та M2 завантажувальних пристаней. Кожен корабель спочатку розвантажують на одній з M1 розвантажувальних пристаней, а потім завантажують на одній з M2 завантажувальних пристаней. Кораблі припливають до порту, будучи на рейді, а після обслуговування в порту, знову повертаються на рейд. В порту пароплави транспортують між пристанями та басейнами.
Паралельно-послідовну структуру порту показано на рис. . В ній відокремлено локальні вхідні басейни завантажувальних пристаней і локальні вихідні басейни розвантажувальних пристаней. Розвантажувальні пристані позначено як A1,m, m=1,...,M1, а завантажувальні пристані як A2,m, m=1,...,M2. Вихідні портові басейни (після розвантаження судна) позначено як B1,m, а вхідні завантажувальні басейни _B2,m.
Кількість суден, які можуть знаходитися одночасно в портовому басейні, є обмеженою величиною. В басейнах також можуть створюватися черги для обслуговування типу FIFO або LIFO.
Порт з паралельно-послідовною структурою складається з двох окремих підсистем, які співпрацюють послідовно. Кожна з цих підсистем окремо взята є паралельною структурою. В неоднорідних моделях портів з паралельно-послідовною структурою деякі судна тільки розвантажують, а інші тільки завантажують. Підсистеми в таких паралельно-послідовних системах повинні бути збалансованими, інакше портові басейни стають “вузьким місцем” в роботі системи або, навпаки, вони простоюють.
Сформульовані в першому розділі проблеми полягають у встановлені оптимальних підмножин суден, які знаходяться на рейді в послідовні часові інтервали (тижні). Кораблі, які порт не зміг обслужити у відведений час, формують початкові умови оптимізації для наступних інтервалів. В ролі критерію оптимізації прийнято максимальну економічну ефективність порту.
Другий розділ дисертації присвячено структурному моделюванню порту та процесів обслуговування кораблів. Здійснено аналіз підходів до моделювання структур сукупності операцій наступних типів: графи, семантичні мережі і мережі прийняття рішень.
Проаналізовано тенденції розвитку структурного моделювання сукупності операцій і показано, що в деяких застосуваннях структури сукупності операцій не є заданими, а ідентифікуються, наприклад, в процесі монтажу, будівництва, і т.п. Це є мережі з конверсією: операції у вершинах і обмеження на дугах. Такі структури, після ідентифікації, відображають певну інформацію про комплекс операцій (наприклад, обмеження черговості виконання операції). При моделюванні дискретних виробничих процесів часто використовуються мережі Петрі, які містять інформацію про реалізацію процесу, наприклад, у вузлах записано стан реалізації операцій. Це є мережі, які в загальному випадку надають інформацію про логічні, просторові чи часові обмеження реалізації сукупності операцій.
На основі проведеного аналізу показано, що семантичні мережі є структурами, які у вузлах містять бази знань. Ці знання можуть бути впорядковані різними способами, а в деяких випадках вони є закодовані. Важливою проблемою в таких мережах є пошук інформації. Прикладом такої семантичної мережі є Інтернет.
На основі проведеного аналізу структурного моделювання комплексу операцій в розділі введено означення семантичної мережі для проблеми прийняття рішень.
Термін “семантична мережа” для проблем формування графіків обслуговування є обґрунтований тим, що вузлами такої мережі є структури (матриці) символів. Кожний елемент цієї матриці приймає певне значення, наприклад, окремий елемент (число) може відображати номер причалу, або час закінчення обслуговування. Більше того, якщо корабель тільки розвантажують або тільки завантажують, то відповідний елемент матриці стану має бути кодом (наприклад, від’ємним числом), який свідчить про те, що відповідна операція не може здійснюватися. Аналогічно, за допомогою кодування часу (додатне або від’ємне число) можна записати інформацію про локалізацію судна, наприклад, перед пристанню, чи після неї.
В загальному випадку, стосовно процесу обслуговування кораблів, вузли семантичної мережі є матрицями X, які складаються з M стовпців і N рядків, де M дорівнює кількості пристаней в порту, а N – кількості суден, які необхідно обслужити. Стовпці матриці відповідають агрегатам (пристаням), а рядки – об’єктам (суднам). Елементи цих матриць є такими: |
якщо прийнято рішення про обслуговування n-го об’єкту в m-му агрегаті,
в іншому випадку.
Час tn,m закінчення обслуговування n-го об’єкту в m-у агрегаті можна обчислити на основі відомого попереднього стану системи і прийнятого рішення (на основі даних, що містяться в матриці стану).
Слід зауважити, що на основі довільного стану X можна скласти частковий графік роботи системи до момент часу T, який відповідає максимальному елементу матриці X. Можна також сформувати графік для довільного моменту часу , видаляючи з матриці стану елементи, для яких виконується умова , де – час обслуговування n-го об’єкту в m-му агрегаті.
Отже, вузол мережі, записаний у формі матриці X, містить інформацію про історію роботи системи. На її основі можна отримати графік роботи кожного агрегату або графік обслуговування кожного об’єкту. Обслуговування n-гo об’єкту закінчується в момент часу , для якого . Вважається, що m-й агрегат є незайнятим в момент часу , причому .
Економічна ефективність функціонування системи обчислюється за формулою:
,
причому
, для ;
, для ,
де – декларований портом термін закінчення обслуговування судна; – премія у випадку закінчення обслуговування судна за час швидший від , – штрафи за обслуговування судна після терміну . На основі матриці X можна отримати також інші звітні матеріали.
В матричному описі вузла мережі можна ввести відповідне кодування елементів для відображення локалізації агрегатів у вхідній чи вихідній послідовності, а також для зазначення певного сліду у випадку резиґнації даного вузла.
Результати, що отримані в цьому розділі, стали основою для розробки програмних процедур імплементації графів. Зокрема, створено процедури імплементації спускового, динамічного та табличного типів, а також за допомогою списків-сусідів. Розроблені процедури мають суттєве значення для процесів обслуговування морських суден (з обмеженнями на черговість їх обслуговування), оскільки множини суден можуть відрізнятися в різні часові інтервали. Структура порту з басейнами і каналами також змінюється з часом, наприклад, у зв’язку з аваріями, тому програма, яка дає інформацію про поточний стан порту, є особливо необхідною.
В третьому розділі розроблено математичні моделі та інтелектуальні алгоритми для розв’язування задач формування графіків обслуговування кораблів у порту. Ці алгоритми функціонують як інтелектуальні агенти, в їх основі лежать семантичні мережі прийняття рішень. Вузли мережі описуються матрицями, елементи яких є означені відповідним чином.
Кожен вузол мережі має відображати допустимий стан. В загальному випадку допустимі стани генеруються в хронологічному порядку. Тому, семантична мережа при формуванні графіків має динамічні властивості, тобто її вузли залежать від часу. Дуги семантичної мережі для задачі гармонограмування містять інформацію, яка дозволяє згенерувати наступні допустимі вузли (стани) на основі попереднього вузла. Така інформація включає номери суден, які необхідно розвантажити (завантажити), та номери пристаней, на яких судно має обслуговуватися.
Оскільки дуга повинна містити допустиму інформацію, яка дозволяє генерувати допустимі стани, тому необхідно переконатися, чи для вибраного судна з номером n і для вибраної пристані з номером m виконуються умови генерування стану. Наприклад, для того, щоб приписати дугу (n, m) для завантаження судна з номером n на пристані з номером m, необхідно пересвідчитися чи:
-
судно з номером n є розвантажене;
-
портовий басейн після пристані m є незаповненим;
-
судно з номером n ще не є завантажене;
-
пристань для завантаження з номером m є вільним.
Семантична мережа для задач гармонограмування не задається у явному вигляді, як, наприклад, мережа доріг чи залізниць. Вона генерується в процесі розв’язування задачі. При цьому задається початковий стан мережі. Один з кінцевих станів мережі задає оптимальний розв’язок задачі. Тому, необхідно визначити оптимальний кінцевий стан семантичної мережі.
Інтелектуальний агент – це програма, яка працює в певному середовищі. Причому, рішення, прийняті інтелектуальним агентом, змінюють параметри середовища, в якому він діє. Тому це не є традиційна програма, яка для заданих вхідних даних обчислює вихідний результат. Середовищем для інтелектуального агента є модель порту і множини кораблів з певними параметрами.
Враховуючи наведене, в дисертаційній роботі створено інтелектуальні алгоритми, які реалізовують діалог із середовищем функціонування. Концепція гармонограмування за допомогою інтелектуальних агентів ґрунтується на таких припущеннях:
·
генерування гармонограми полягає в багатоетапному прийнятті рішень щодо розподілу об’єктів (кораблів) до обслуговування в допустимих агрегатах (пристанях), що вимагає визначення стану системи;
·
після прийнятого рішення система переходить до наступного стану; послідовність станів утворює траєкторію; початковий стан кожної траєкторії є тим самим заданим станом; кожен кінцевий стан репрезентує допустимий розв’язок системи – допустиму гармонограму обслуговування;
·
кожна траєкторія станів дозволяє здійснити симуляцію процесів обслуговування об’єктів в системі, тобто хронологічне генерування станів; допустимі траєкторії вказують на допустимі шляхи реалізації процесу;
·
інтелектуальний агент почергово генерує допустимі стани (матриці) системи, які є частковими розв’язками задачі;
·
знання інтелектуального агента (часткові розв’язки задачі) представляються матрицями стану системи та значеннями параметрів цього стану (значення критеріїв оптимальності);
·
для врахування обмежень портових басейнів (їх місткість, регламент типу FIFO чи LIFO, тощо) інтелектуальний агент генерує стани згідно хронологічного порядку;
·
кожен згенерований стан оцінюється згідно прийнятих критеріїв оптимальності; якщо цей стан оцінюється як неперспективний, то інтелектуальний агент повертається з нього назад;
·
інтелектуальний агент генерує стани траєкторії семантичної мережі та усуває з неї неперспективні стани, залишаючи певний слід у формі закодованих даних в матриці стану;
·
для генерування допустимих гармонограм в діалоговому режимі необхідні комп’ютерні стимулятори; працюючи з стимулятором, оператор має можливість:
-
почергово приймати допустимі рішення в залежності від стану, в якому знаходиться система;
-
скасування останнього рішення (повернення до попереднього стану), якщо воно не дає перспективи отримання доброго графіку обслуговування;
-
використання при прийнятті рішень евристичних правил;
-
формування статистичних даних про параметри системи та ефективність алгоритмів гармонограмування.
В розділі показано, що інтелектуальний агент є інструментом для генерування допустимих гармонограм і накопичення знань про систему. З допомогою такого агента можна випадковим чином генерувати різні початкові стани системи, а далі визначати гармонограми, використовуючи різні ієрархічні алгоритми. Повторюючи такі експерименти, можна отримати статистичні оцінки ефективності застосовуваних алгоритмів.
Оцінки, отримані за даним алгоритмом, залежать від початкового стану системи, а, на практиці, від класу станів, які можуть бути початковими для даної системи. Далі, в системі гармонограмування можна використати таблицю алгоритмів ефективних рішень. Стрічками цієї таблиці є впорядковані стани класів системи, а стовпці _алгоритмами. Елементи цієї таблиці є імовірностями досягнення розв’язку для даного класу станів при застосування вибраного алгоритму.
В четвертому розділі роботи представлено створені математичні моделі та алгоритми обслуговування кораблів, які охоплюють різноманітні випадки структури порту: базовий порт з однією пристанню, модель порту з послідовною структурою, модель порту з паралельною структурою, модель порту з структурою дерева та модель порту з паралельно-послідовною структурою. В розроблених моделях враховуються обмеження портових басейнів.
Математичні моделі та алгоритми оптимізації обслуговування кораблів у потру базуються на означенні вузла семантичної мережі, який інтерпретує стан (часткову гармонограму) процесу обслуговування. Для кожного розробленого алгоритму для кожної моделі подано процедури проходження семантичної мережі, тобто процедури генерування нових станів або повернення з неперспективних станів. Для уникнення багаторазових генерувань однакових станів і дотримання обмежень на портові басейни, в цих алгоритмах передбачено процедури хронологічного порядку, а також сліди агента.
Для базової моделі порту стан системи описується матрицею-стовпцем
, ,
елементи якого рівні: |
якщо на етапі прийнято рішення про обслуговування корабля ,
в іншому випадку.
Стан інтерпретує початковий стан системи. Наприклад, початковий стан системи з нульовими елементами означає, що всі кораблі знаходяться на рейді. В протилежному випадку один з елементів матриці стану є додатнім. Він означає закінчення обслуговування судна, яке в початковий момент знаходиться біля пристані.
Для моделі порту з паралельною структурою стан системи описується матрицею
, , , (1)
елементи якої визначаємо з умов: |
якщо рішення про обслуговування судна на пристані m прийнято на етапі ,
в іншому випадку,
якщо ,
в іншому випадку.
Для моделі порту з послідовною структурою стан системи описується також матрицею (1), але її елементи визначаємо з умов: |
якщо рішення про розвантаження судна прийнято на етапі ,
в іншому випадку,
якщо рішення про завантаження судна прийнято на етапі ,
в іншому випадку.
Для моделі порту зі структурою дерева стан системи описується матрицею
, , , (2)
елементи якої визначаємо з умов: |
якщо на етапі прийнято рішення про відбір судна з рейду на розвантаження,
в іншому випадку,
якщо на етапі прийнято рішення про відбір судна з портового басейну на завантаження на пристані m,
в іншому випадку,
якщо ,
в іншому випадку.
Для моделі порту зі структурою анти-дерева стан системи описується також матрицею (2), але її елементи визначаємо з умов: |
якщо на етапі прийнято рішення про відбір судна з рейду на розвантаження на пристані m,
в іншому випадку,
якщо ,
в іншому випадку,
якщо на етапі прийнято рішення про завантаження судна ,
в іншому випадку.
Для моделі порту з паралельно-послідовною структурою стан системи описується матрицею
, , ,
елементи якої визначаємо з умов: |
якщо на етапі прийнято рішення про відбір судна з рейду на розвантаження на пристані m,
в іншому випадку,
якщо ,
в іншому випадку,
якщо на етапі прийнято рішення про відбір судна з портового басейну
на завантаження на пристані m’,
в іншому випадку,
якщо ,
в іншому випадку/
У випадку системи басейнів виникає проблема локалізації кораблів, які чекають на завантаження. Тому, при гармонограмуванні обслуговування суден в системі з паралельно-послідовною структурою з басейнами, які мають обмеження, у відповідності з розробленим підходом встановлюється хронологічний порядок операцій розвантаження і завантаження кораблів.
Основні результати та Висновки
В дисертаційній роботі розв’язано актуальну наукову задачу створення математичних моделей, алгоритмів і програмних засобів для ефективної оптимізації сукупності операцій обслуговування кораблів у портах. При цьому отримано наступні основні результати:
1.
На основі аналізу відомих підходів до оптимізації комплексу операцій паралельно-послідовного обслуговування показано необхідність розробки математичних моделей та ефективних алгоритмів оптимізації процесів розвантаження і завантаження кораблів у портах. Оптимізація цих процесів полягає у встановленні оптимальних підмножин операцій для послідовних часових інтервалів.
2.
Розроблено семантичні мережі для моделювання і оптимізації сукупності операцій обслуговування кораблів у порту, в яких вузли мережі представлено матрицями, залежними від структури порту, і які дають можливість відображати типові структури порту: базові, послідовні, паралельні, дерева, анти-дерева і паралельно-послідовні.
3.
Створено математичні моделі та інтелектуальні алгоритми проходження семантичних мереж, які базуються на рекурсивних методах генерування нових вузлів мережі, що зберігають слід при поверненні, і дають можливість знаходити часткові розв’язки загальної проблеми оптимізації обслуговування кораблів і уникати повторних генерувань однакових траєкторій.
4.
Запропоновано та обґрунтовано процедури генерування вузлів семантичної мережі (станів системи) з врахуванням хронологічного порядку, що дозволяє синхронно генерувати послідовні стани процесу і врахувати обмеження портових басейнів. Знання, які містяться у вузлах дерева рішень (матрицях стану), використовуються для генерування наступних станів, а рішення про генерування таких станів залежить від поточного стану та критеріїв оптимізації.
5.
Розроблено методи паралельного проходження семантичних мереж, які відповідають послідовним, синхронним чи паралельним процесам обслуговування і дають можливість розпаралелити обчислення при знаходженні оптимального розв’язку.
6.
На основі розроблених математичних моделей та оптимізаційних алгоритмів створено комп’ютерні симулятори комплексу операцій розвантаження і завантаження кораблів у портах, які враховують початкові умови та наявні обмеження і дають можливість знаходити оптимальні за критерієм економічних показників графіки обслуговування.
СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ
1.
Marecki J. Automaty, jкzyki formalne i algorytmy.- Bielsko-Biaіa: Wydawnictwo P.K. J.Skalmierskiego, 2004.- 120 s.
2.
Marecki J. Semantic networks and intelligent agents.- Network Integrates Associates, Parkland, Florida, USA, 2003.- 111 p.
3.
Marecki J. Struktury danych.- Gliwice: Wydawnictwo P.K. J.Skalmierskiego, 2000.- 104 s.
4.
Marecki J. Metody sztucznej inteligencji.- Gliwice: Wydawnictwo P.K. J.Skalmierskiego, 2001.- 115 s.
5.
Marecki J. Grafy i rekurencje.- Gliwice: Wydawnictwo P.K. J.Skalmierskiego, 2002.- 105 s.
6.
Марецький Я. Математичні моделі та процедури формування графіків для систем паралельно-послідовного обслуговування // Інформаційні технології і системи.- 2003.- Т. 6.- № 1-2.- С. 140-147.
7.
Марецький Я. Комп’ютерне моделювання системи паралельно-послідовного обслуговування // Вісник Технологічного університету Поділля.- 2003.- № 3.- Т.1.- С. 142-148.
8.
Marecki J. Planning semantic network using node nested grammars // Artificial Intelligence.- Donetsk, 2003.- N. 4.- P. 421-429.
9.
Марецький Я. Математична модель обслуговування кораблів в порту // Збірник наукових праць Інституту проблем моделювання в енергетиці.- 2002.- Вип. 18.- С. 198-209.
10.
Fr№ckiewicz Z., Marecki J. Zastosowanie sztucznej inteligencji do sterowania ruchem statkуw w porcie / Efektywnoњж Zastosowaс Systemуw Informatycznych.- Warszawa: Wydawnictwo Naukowo-Techniczne, 2004.- S. 453-466.
11.
Fr№ckiewicz Z., Marecki J. Logistical ships scheduling model in parallel port // Zeszyty Naukowe Wyїszej Szkoіy Morskiej.- Szczecin, 2003.- Nr 70.-S. 73-84.
12.
Марецький Я. Математичні моделі та алгоритми оптимізації комплексу операцій обслуговування кораблів у порту з базовою структурою.- Львів, 2003.- 32 с. (Препр. / Державний НДІ інформаційної інфраструктури; 1/11-2003).
13.
Марецький Я. Математичні моделі та алгоритми оптимізації комплексу операцій обслуговування кораблів у порту з паралельно-послідовною структурою.- Львів, 2004.- 34 с. (Препр. / Державний НДІ інформаційної інфраструктури; 1/5-2004).
14.
Marecki J. Modeling decision trees / Proc. of the Intern. Conf. on Inductive Modeling “ICIM-2002”.- V. 2.- Lviv, 2002.- P. 239-244.
15.
Fr№ckiewicz Z., Marecki J. Modelowanie obsіugi statkуw w porcie / Polish-Ukrainien Workshop on „Mathematical Modelling and Artifficial Intelligence”.- Lviv, 2002.- P. 78-90.
16.
Marecki J. Teoria funkcji informatycznych / Podstawy Informatyki i Sieci Komputerowych: Beskidzki Festiwal Nauki.- Bielsko-Biaіa: Akademia Techniczno-Humanistyczna, 2001.- S. 5-28.
17.
Marecki J. Metody sortowania / Podstawy Informatyki i Sieci Komputerowych: Beskidzki Festiwal Nauki.- Bielsko-Biaіa: Akademia Techniczno-Humanistyczna, 2001.- S. 29-54.
18.
Fr№ckiewicz Z., Marecki J. Logistical ships scheduling model in serial structure port / Intern. Conf. „Marine Traffic Engineering”.- Њwinoujњcie: Szczecin Meritime University, 2003.- P. 94-104.
19.
Marecki J. Modele grafуw / Badania operacyjne: Beskidzki Festiwal Nauki.- Bielsko-Biaіa: Akademia Techniczno-Humanistyczna, 2001.- S. 35-62.
20.
Marecki J. Algorytmy numeracji i grafуw / Badania operacyjne: Beskidzki Festiwal Nauki.- Bielsko-Biaіa: Akademia Techniczno-Humanistyczna, 2001.- S. 63-92.
Марецький Я. Моделювання та оптимізація комплексу операцій обслуговування кораблів у порту. – Рукопис.
Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 01.05.02 – математичне моделювання та обчислювальні методи, Державний науково-дослідний інститут інформаційної інфраструктури, Львів, 2004.
Дисертацію присвячено розробці математичних моделей, алгоритмів і програмних засобів для оптимізації сукупності операцій обслуговування кораблів у портах. Розроблено семантичні мережі для моделювання і оптимізації сукупності операцій, в яких вузли мережі представляються матрицями, залежними від структури порту, і які дають можливість відображати типові структури порту. Запропоновано інтелектуальні алгоритми проходження семантичних мереж, які базуються на рекурсивних методах генерування нових вузлів мережі і дають можливість знаходити часткові розв’язки загальної проблеми оптимізації обслуговування кораблів. Обґрунтовано процедури генерування вузлів семантичної мережі (станів системи) з врахуванням хронологічного порядку, що дозволяє синхронно генерувати послідовні стани процесу, врахувати обмеження портових басейнів і уникнути повторного генерування вже знайдених часткових розв’язків. Розроблено методи паралельного проходження семантичних мереж, які відповідають послідовним, синхронним чи паралельним процесам обслуговування і дають можливість розпаралелити обчислення при знаходженні оптимального розв’язку.
Ключові слова: обслуговування кораблів, математичне моделювання, оптимізація, семантична мережа, інтелектуальний агент, програмний засіб.
Марецкий Я. Моделирование и оптимизация комплекса операций обслуживания кораблей в порту. – Рукопись.
Диссертация на соискание учёной степени кандидата технических наук по специальности 01.05.02 – математическое моделирование и вычислительные методы, Государственный научно-исследовательский институт информационной инфраструктуры, Львов, 2004.
В диссертационной работе решена актуальная научная задача создания математических моделей, алгоритмов и программных средств для эффективной оптимизации совокупности операций обслуживания кораблей в портах.
На основе анализа известных подходов к оптимизации комплекса операций параллельно-последовательного обслуживания показана необходимость разработки математических моделей и эффективных алгоритмов оптимизации процессов разгрузки и погрузки кораблей в портах. Оптимизация этих процессов состоит в установлении оптимальных подмножеств операций для последовательных временных интервалов.
Разработаны семантические сети для моделирования и оптимизации совокупности операций обслуживания кораблей в порту, в которых узлы сети представлены матрицами, зависимыми от структуры порта, и которые дают возможность отображать типичные структуры порта: базовую, последовательную, параллельную, деревовидную, антидеревовидную и параллельно-последовательную.
Созданы математические модели и интеллектуальные алгоритмы прохождения семантических сетей, базирующиеся на рекурсивных методах генерирования новых узлов сети, которые сохраняют след при возвращении, дающие возможность находить частные решения общей проблемы оптимизации обслуживания кораблей и избегающие повторных генерирований одинаковых траекторий.
Предложены и обоснованы процедуры генерирования узлов семантической сети (состояний системы) с учетом хронологического порядка, которые дают возможность синхронно генерировать последовательные состояния процесса и учесть ограничения портовых бассейнов. Знания, имеющиеся в узлах дерева решений (матрицах состояния), используются для генерирования следующих состояний, а решение о генерировании таких состояний зависит от текущего состояния и критериев оптимизации.
Разработаны методы параллельного прохождения семантических сетей, которые соответствуют последовательным, синхронным или параллельным процессам обслуживания и дают возможность распараллелить вычисление при нахождении оптимального решения.
На основе разработанных математических моделей и оптимизационных алгоритмов созданы компьютерные симуляторы комплекса операций разгрузки и погрузки кораблей в портах, которые учитывают начальные условия и имеющиеся ограничения и дают возможность находить оптимальные по критерию экономических показателей графики обслуживания.
Ключевые слова: обслуживание кораблей, математическое моделирование, оптимизация, семантическая сеть, интеллектуальный агент, программное средство.
Marecki J. Modeling and optimization of ship service operation complexes in the port. – Manuscript.
Thesis for a candidate’s degree by speciality 01.05.02 – Mathematical Modelling and Numerical Methods, State Scientific and Research Institute of Information Infrastructure, Lviv, 2004.
Construction of mathematical models, algorithms and software resources for optimization of ship service operation complexes in the port has been presented in the dissertation. Semantic networks for the modeling and optimization of the complexes of operations in which network nodes are matrices depending on the standard port structures have been introduced. Intelligent semantic network exploration algorithms based on recursive methods for new network nodes generation, which allow for the determination of local solutions for the global ship service operations problem have been proposed. Methods for semantic network node generation with respect to chronological order, which allows for synchronous generation of non-redundant sequential process states consistent with port pool limits have been formalized. Parallel semantic network exploration methods corresponding to serial, synchronous or parallel service processes allowing for parallel computation of optimal solution have been introduced.
Keywords: ship service, mathematical modelling, optimization, semantic network, intelligent agent, software.
