Національний аерокосмічний університет ім. М.Є. Жуковського

“Харківський авіаційний інститут”

ЛІСТРОВА Олена Сергіївна

УДК: 519.854 ;681.324 ;519.7 (043)

МОДЕЛІ ТА МЕТОДИ ПЛАНУВАННЯ, ОПЕРАТИВНОГО НАКОПИЧЕННЯ

ТА РЕАЛІЗАЦІЇ ТОВАРІВ В СУЧАСНИХ ТОРГОВИХ ЦЕНТРАХ

Спеціальність 05.13.06 - автоматизовані системи управління та прогресивні інформаційні технології

Автореферат

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

кандидата технічних наук

Харків-2003

Дисертацією є рукопис.

Робота виконана у Національному аерокосмічному університеті ім. М.Є. Жуковського “Харківський авіаційний інститут”, Міністерство освіти і науки України.

Науковий керівник:

кандидат технічних наук, доцент

Кожухов Валерій Дмитрович,

Національний аерокосмічний університет ім. М.Є. Жуковського

“Харківський авіаційний інститут”,

завідувач кафедрою економіко-математичного моделювання

Офіційні опоненти:

- доктор технічних наук, професор Жихарев Володимир Якович,

Національний аерокосмічний університет ім. М.Є. Жуковського

Харківскький авіаційний інститут”, професор кафедри виробництва

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

- кандидат технічних наук, доцент Кузьменко Віктор Михайлович, Харківський національний університет радіоелектроніки, професор кафедри системотехніки.

Провідна установа: Національний технічний університет “Харківський політехнічний інститут”, кафедра систем інформації, Міністерство освіти і науки України, м. Харків.

Захист відбудеться “30” січня 2004р. о 1200 годині на засіданні спеціалізованої вченої ради Д64.062.01 у Національному аерокосмічному університеті ім. М.Є. Жуковського “Харківський авіаційний інститут” за адресою: 61070, м. Харків, вул. Чкалова, 17, радіотехнічний корпус, ауд. 232.

З дисертацією можна ознайомитись у бібліотеці Національного аерокосмічного університету ім. М.Є. Жуковського “Харківський авіаційний інститут” за адресою: 61070, м. Харків, вул. Чкалова, 17.

Автореферат розісланий “18” грудня 2003 р.

Вчений секретар

спеціалізованої вченої ради _______________ Чумаченко І.В.

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

Актуальність теми. Аналіз автоматизованих систем управління (АСУ) сучасними торговими центрами (супермаркетами) показує, що роль функціональних підсистем управління складським господарством торгових центрів перетерпіли істотні зміни. Ці зміни обумовлені тим, що АСУ складами супермаркетів стали безпосередньо впливати на ефективність процесу нагромадження і реалізації товарів. На відміну від класичних АСУ складами виробничих об'єднань, що відіграють роль автономних систем управління, нові АСУ складами супермаркетів, стали частиною системи управління торговими центрами, оперативність роботи якої фактично безпосередньо й динамічно почали впливати на ефективність функціонування самих торгових центрів. Динаміка процесів управління в АСУ складами супермаркетів спричинила широке застосування для опису процесів функціонування АСУ торговими центрами нових математичних моделей, що відносяться до класу задач цілочислового програмування. Це призвело до необхідності розробки спеціального математичного і програмного забезпечення, що реалізує підтримку динамічного процесу оптимального планування в процесі управління АСУ складами супермаркетів. Останнім часом побудова АСУ складським господарством супермаркетів здійснюється на основі обчислювальних мереж, процес управління якими вимагає рішення цілого комплексу задач динамічного управління потоками інформації в мережі в масштабі реального часу. Чітка і надійна робота складу, оснащеного АСУ, багато в чому визначається прийнятою функціональною й організаційною структурою даної АСУ. Істотний вплив на функціональну структуру роблять характеристики складу як об'єкта управління: його місце і роль у виробничому процесі; особливості складського вантажопотоку; тип і кількість транспортуючих і складуючих механізмів; місця перевантаження; тип тари і т.д. Для складських АСУ супермаркетів характерне використання наступних функціональних підсистем: оперативно-календарного планування; управління вантажопотоками; управління вантажно-розвантажувальними механізмами, ведення інформаційно-пошукової бази даних; формування складської і дорожньої документації; аналізу роботи складу. Особливістю алгоритмів управління для рішення задач, що виникають у процесі функціонування складських АСУ, є необхідність виконання твердих обмежень на час виконання окремих операцій зі збору, обробки вихідної інформації і вироблення рішення з видачі керуючих впливів у залежності від стану об'єктів управління. Іншою особливістю алгоритмізації задач складських АСУ супермаркетів є необхідність обліку взаємозв'язку задач, що в ряді випадків викликає необхідність складання єдиного алгоритму для рішення декількох задач управління. Організаційна структура складських АСУ супермаркету повинна задовольняти наступним основним вимогам: забезпечити оперативність і надійність управління транспортно-складською системою при найменших витратах; виключати можливість появи некерованих ділянок і процесів;

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

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

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

Зв’язок роботи з науковими програмами, планами, темами. Роботу виконано на кафедрі економіко-математичного моделювання Національного аерокосмічного університету ім. М.Є. Жуковського “Харківський авіаційний інститут” у межах державної науково-технічної програми №7 “Перспективні інформаційні технології, пристрої комплексної автоматизації, системи зв’язку” ДКНТПП (постанова Верховної Ради України від 16.10.1992 р. 27-05-ХІІ “Про пріоритетні напрямки розвитку науки і техніки”) відповідно до плану науково-дослідних робіт Національного аерокосмічного університету в період із 1992 по 2001 рр., зокрема за темою Д 603-41/2000 “Створення методології штучного інтелекту для ідентифікації та управління складними системами аерокосмічного призначення” (ДР № 0100U003442) (2000 - 2001 рр.), а також у рамках співробітництва з Харківським військовим університетом при виконанні НДР з розробки АСУ реального часу підрозділами РВ і А (Ракетних військ і артилерії), створеної відповідно до рішення секції АПСУ РВ і А (Автоматизовані перспективні системи управління ракетними військами і артилерією) і Координаційної Ради МО України, затвердженої Начальником Генерального штабу РВ України від 23.02.1995 і наказом Командуючого РВ і А РВ України (Вхідн. № 9823, - ХВУ, 1998. 87 с.).

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

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

1. Розробка методів і алгоритмів рішення задач оптимального планування в АСУ складами торгових центрів:

- оптимального завантаження лотів (комірок) складу (А - задача);

- оптимального розвантаження лотів (комірок) складу (В - задача);

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

2. Розробка ефективних методів рішення А, - В, - С - задач на основі ідей рангового підходу.

3. Розробка алгоритмів і програм рішення А, - В, - С - задач на основі ідей рангового підходу.

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

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

Предметом дослідження є моделі, методи, інформаційні технології планування та управління потоками товарів в торгових центрах.

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

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

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

- удосконалені алгоритми рішення задачі А на основі рангового підходу, що дозволили на 20 - 30 % зменшити тимчасову складність рішення задачі А;

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

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

- застосування розроблених методів рішення задач цілочислового програмування для розглянутого в роботі комплексу задач оптимального планування при динамічному управлінні в складських АСУ торгових центрів (супермаркетів) дозволяє забезпечити необхідну оперативність управління і точність рішення задач управління;

- запропоновані алгоритми рішення А, - В задач на основі рангового підходу дозволяють

підвищити оперативність і точність рішення задач динамічного розподілу товарів у складських АСУ супермаркетів;

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

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

Розроблене спеціальне математичне і програмне забезпечення впроваджене в 2000 році в Сумському військовому інституті артилерії ім. Б. Хмельницького, м. Суми (акт впровадження від 25.05.2000 р.), у 2002 році в НПО “Комунар”, при розробці АСУ складами реального часу (акт впровадження від 05.02.2002 р.), у 2003 році в Приватній промислово-торговельній фірмі “ЮСИ” (акт впровадження від 23.01.2003 р.), у 2002 - 2003 роках у навчальному процесі Національного аерокосмічного університету ім. М.Є. Жуковського “Харківський авіаційний інститут” (кафедра економіко-математичного моделювання) (акт впровадження від 07.03.2003 р.).

Особистий внесок здобувача. Всі результати дисертаційної роботи отримані за особистою участю автора. В статтях, написаних у співавторстві, дисертанту належать: [1] - дослідження багатоетапних алгоритмів рішення багатомірних задач типу 0,1-рюкзак на основі рангового підходу; [2] - розгляд різних моделей рішення задач перерозподілу задач у мережі на основі методів цілочислового програмування; [3] - запропоновано визначення зваженого оптимістичного негарантованого прогнозу; [4] - розробка алгоритму рішення ЗНП на основі рангового підходу і досліджений вплив сортувань ваг вершин n-мірного одиничного куба на похибку рішення для наближених алгоритмів; [6] - дослідження алгоритму рішення задачі 3-виконання; [7] - розробка алгоритму рішення діофантових рівнянь на основі ідей рангового підходу; [8] - розробка наближених і точних алгоритмів рішення ЗНР на основі ідей рангового підходу;

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

Апробація результатів дисертації. Результати досліджень доповідалися і були схвалені: на 15-й Міжнародній школі-семінарі “Перспективні системи управління на залізничному, промисловому і міському транспорті” 2002 р., а також на конференціях молодих вчених Національного аерокосмічного університету ім. М.Є. Жуковського “ХАІ”: 1998 р., 1999 р., 2000 р.

Публікації. Результати роботи відображені в 2-х статтях у наукових журналах, 8-и збірниках наукових праць, 1-х тезах конференцій.

Структура роботи. Дисертаційна робота виконана на 221 сторінках, ілюстрована 29

рисунками на 8 сторінках, 7 таблицями на 1 сторінці. Робота складається зі вступу, чотирьох розділів, висновків, 6 додатків (на 82 сторінках) і списку літератури, що включає 174 найменування, розміщених на 15 сторінках.

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

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

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

Як основний показник якості вибрано о

оперативність рішення задач динамічного управління в АСУ складами за час, що не перевищує деякий припустимий час Тд, що оцінюють кількісно імовірністю рішення розглянутого комплексу задач управління, Р(Т) за час Т, не перевищуючий Тд :

Р (Т) = 1-е (1)

В АСУ складами супермаркетів на сучасному етапі час відновлення інформації визначається режимами функціонування АСУ супермаркетів і може знаходитись в діапазоні від десятків хвилин до декількох годин.

Проведений у розділі аналіз комплексу задач, розв'язуваних в АСУ складами супермаркетів, показав, що можна виділити наступні основні задачі, які необхідно вирішувати багаторазово в процесі функціонування АСУ складу:

- задачу оптимального завантаження лотів (комірок) складу (задача А);

- задачу оптимального розвантаження лотів (комірок) складу (задача В);

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

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

Нехай вантаж i характеризується: довжиною - di; висотою - hi; шириною - Рi; вагою - Vi ступенем важливості i. Лот j характеризується: довжиною - dj; висотою - hj; шириною - Рj; вагою-Vj. Задано часи доставки |tij|, вартості доставки |cij| та припустимі значення часів доставки і вартості доставки кожного вантажу в j-й лот (Тдопj, Сдопj). Позначимо через F - кількість вантажів, яку можна помістити у всіх лотах.

Потрібно максимізувати F. При цьому сумарний час доставки повинен або не перевищувати якийсь час Тдоп, заданий умовами навантаження, або бути мінімальним. Вартість навантаження не повинна перевищувати Сдоп , задану умовами навантаження. Формально дані вимоги можна записати в наступному вигляді:

, (2)

при обмеженнях

(3)

де

Обмеження означає, що один вантаж може бути поміщений тільки в один лот.

При дуже великих розмірностях задач (2 - 3) (коли необхідний рівень показника Р(Т) не забезпечується) їх рішення можна здійснити таким способом. Для забезпечення мінімального часу завантажування нумерацію лотів будемо здійснювати за порядком зростання часу находження вантажів із навантажувального майданчика. Далі (рис. 2), послідовно, починаючи з першого лота, визначається максимально можливе завантаження першого лота на повному вихідному списку вантажів. Крім вантажів, завантажених в перший лот із загального списку вантажів, визначається

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

, (4)

при обмеженнях

(5)

де

У процесі управління в АСУ через обмеженість обсягів її ресурсів може виникати необхідність у визначенні мінімальної кількості об'єктів управління (ОУ), за допомогою якої можна забезпечити обслуговування всіх об'єктів обслуговування (ОО) на даний момент часу, тобто ми приходимо до приватної задачі А і задачі В, що мають широке прикладне значення при рішенні різних задач АСУ реального часу. Так, наприклад, якщо в АСУ складами супермаркетів за годину пік на навантажувальному майданчику зібрано велику кількість вантажів і при цьому є розвантажувальні засоби, що відмовили, то виникає задача визначення мінімальної кількості засобів, за допомогою яких можна виконати всі роботи. Якщо в матриці B з 1 і 0 кожному стовпчику відповідає вантажно-розвантажувальний засіб, а рядку - вантаж, що знаходиться на вантажно-розвантажувальному майданчику складу, і при цьому елемент матриці буде дорівнювати 1, якщо j-й засіб може бути використаний для транспортування відповідного i-го вантажу і 0 у противному разі, то ми приходимо до задачі перебування такої найменшої множини стовпців у матриці B, що кожен рядок матриці містить одиницю хоча б в одному з обраних стовпчиків. У відповідність стовпчикам так само можна ставити комірки, а рядкам - товари, які необхідно витягти з цих комірок. При цьому можна мінімізувати не тільки число комірок, але і час доставки чи вартість доставки, а так само враховувати термін придатності товарів.

Таким чином, необхідно мінімізувати цільову функцію:

, (6)

при обмеженнях

(7)

де

Для приватної задачі А нерівності в обмеженнях (7) обертаються на рівності

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

Важливим комплексом задач при динамічному управління в АСУ складами є розподіл робіт з формування груп товарів на основі складання розкладів їхнього виконання. У загальному випадку є N однотипних робіт, на ділянці формування груп товарів для вантажно-розвантажувальних робіт, що поєднує L однотипних каналів обслуговування. У цьому випадку задача визначення реалізованості оптимального розкладу зводиться до задачі С. Припустимо, що задано значення зайнятості кожного каналу Тl > 0 . Виникає питання: чи можна указати варіант завантаження ділянки N роботами, що відповідають прийнятим Тl. Відповідь на питання буде стверджувальною, якщо існують ненегативні рішення системи діофантових рівнянь

де t1, t2, …,tN - відомі тривалості виконання робіт.

Розглянуті моделі рішення задач при динамічному управлінні АСУ реального часу є задачами цілочислового програмування (ЦЛП) з булевими змінними (БЗ) і відносяться до класу NP-повних задач. Задачі класу NP важко піддаються рішенню навіть при використанні сучасних електронно обчислювальних машин (ЕОМ). Тому виникає необхідність у розробці нових ефективних методів і алгоритмів, що дозволяють зменшити тимчасову складність розв'язуваних задач з використанням ЕОМ і обчислювальних засобів АСУ.

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

-

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

-

Другий розділ присвячений розробці й обґрунтуванню моделей та методів для рішення приватних науково-технічних задач, на основі ідей рангового підходу, сформульованих у розділі 1. Формальною моделлю приватних науково-технічних А, - В, - С задач (2 - 5) і (6 - 7) є m-мірна задача 0,1-рюкзак, що у загальному випадку може бути представлена в наступному вигляді

(8)

при обмеженнях

(9)

В основі рангового підходу до рішення задач дискретної оптимізації лежить представлення n-мірного одиничного куба Вn у вигляді графу G [1].

У графі G кожному ребру, що входить до вершини j, відповідає m + 1 вага: вага сj, дорівнює коефіцієнту при xj у функціоналі (8), і m ваг аij, рівних коефіцієнтам при xj в обмеженнях (9). Тоді, шлях у графі G з вершини s у вершину j характеризується m + 1 довжинами: - довжиною за вагою функціонала і - довжинами за вагою обмежень.

Таким чином, граф G представляє собою упорядкований за рангами еквівалент n-мірного одиничного куба Bn, у якому шляху відповідають вершини Bn. Довжина кожного шляху за вагою функціонала визначає значення функціонала (8) у вершинах одиничного куба Bn. Довжина за вагою обмежень визначає, чи відповідає дана вершина Bn обмеженням (9), чи належить вершина n-мірного одиничного куба Bn відповідній гіперплощині (9). Якщо то вершина належить відповідній гіперплощині. Оптимальному рішенню задачі (8) - (9) у G відповідає самий довгий шлях за вагою функціонала. В основу математичної моделі рангового підходу для побудови алгоритмів рішення задач ЦЛП із БП покладений принцип оптимізації за напрямком в дискретному просторі станів, заданому графом G [1].

У розділі проаналізовані різні алгоритми рішення задачі (8 - 9) на основі ідей рангового підходу і показано, що найбільш ефективними можна вважати багатоетапні алгоритми, що дозволяють одержувати точне рішення на основі попереднього етапу одержання наближеного

рішення і використання наближеного рішення першого етапу для відсіву безперспективних варіантів рішення на другому етапі. У розділі 2 на основі ідей рангового підходу розглянута можливість рішення приватного випадку задачі А і задачі В як задач про найкоротший шлях на графі G на основі застосування системи каліброваних векторів. Довільний калібрований вектор H(n-1) будується на основі вектора H(n) і поточного значення вектора B(n-1). У загальному випадку на k-й ітерації процес формування вектора H(k) можна записати у вигляді наступної функціональної залежності:

.

Введення каліброваних векторів дозволило визначати песимістичний гарантований і оптимістичний негарантований прогноз довжин шляхів у G як вагових характеристик diп вектора H(i). Запропоновані правила визначення песимістичного й оптимістичного прогнозів дозволили розробити стратегії відсікання безперспективних варіантів і будувати точні та наближені алгоритми рішення приватного випадку задачі А і задачі В.

У розділі 2 також розглянута можливість рішення на основі ідей рангового підходу задачі С

.

Відомі алгоритми (на основі ідей методу гілок і границь (МГГ)) здійснюють тільки повний перебір варіантів на бінарному дереві рішень.

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

У третьому розділі представлені точні та наближені алгоритми рішення А, - В, - С задач на основі стратегій відсікання неперспективних варіантів, розглянутих в розділі 2. В розділі 3 так само визначено правила об'єднання висот каліброваних векторів рішення, що дозволяють на основі розроблених алгоритмів, приватного випадку задачі А вирішувати і задачу В. Для зважених задачі В і приватного випадку задачі А було введено коефіцієнт j, який визначає кількість одиниць у векторі B(i) і , характеризуючий те, яка частина вагової характеристики Сj приходиться на кожну одиницю вектора B(i). Показано, що застосування сортувань у порядку 1 2 … n-1 n, дозволяє зменшити похибку рішення зважених задач В і приватного випадку задачі А.

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

експериментальних досліджень результатів експериментального аналізу тимчасової складності розроблених точних і наближених рішень А, - В, - С задач, а також похибок наближених алгоритмів і їхнього порівняльного аналізу з відомими. На рис. 3 показана залежність похибок при рішенні задачі оптимального планування для випадку, коли група товарів сумісна за умовами збереження і процес описується на основі рішення задачі А при різних сортуваннях коефіцієнтів у функціоналі. Кращим є сортування в порядку зменшення коефіцієнтів. При цьому забезпечується похибка, що не перевищує 3 %. Порівняння точних алгоритмів здійснювалося з алгоритмами Балаша, вектора спаду, Р-методом. Кількість виконуваних елементарних операцій розробленими алгоритмами практично на порядки менше, ніж у кращих відомих.

Оцінка тимчасової складності роботи алгоритмів показала, що в середньому з довірчою імовірністю 0,95 вона для задачі А не перевищує для точних O(n3m) і O(n2m) - для наближених алгоритмів. Порівняння алгоритмів рішення приватного випадку задачі А і задачі В здійснювалось з кращими алгоритмами на основі ідей методу гілок і границь. Як видно з рис. 6, 7, використання рангового підходу для рішення приватного випадку задачі А і задачі В дозволило розробити точні та наближені алгоритми із тимчасовою складністю, яка не перевищує O(n3m) для наближених алгоритмів і O(n4m) - для точних. Похибка розроблених наближених алгоритмів була оцінена в другій умовно виділеній зоні (ранг рішення знаходився в районі ), і не перевищувала 14 %. Зі зростанням розмірності задачі похибка стабілізується, починаючи з n = 50, ?f < 3 %. Використання сортування векторів у порядку зменшення відношення ваг стовпчиків до щільності одиниць у стовпчику дозволяють зменшити похибку рішення приватного випадку задачі А і задачі В (рис. 4, 5). При рішенні задачі формування партій вантажів на основі рішення задачі С вдалося одержати тимчасову складність рішення, що не перевищує О(n5).

Важливим достоїнством розроблених алгоритмів є те, що в процесі їхньої роботи формування шляхів може здійснюватись одночасно, що, у свою чергу, дозволяє ефективно розпаралелити процес обчислень. У розділі 4 так само проведено моделювання процесу рішення задач оптимального планування управління АСУ супермаркетів і порівняльний аналіз розроблених алгоритмів з відомими за обраним показником оперативності рішення даних задач (1). Основні результати оцінки оперативності (1), рішення задач планування процесом управління складом супермаркету, наведено на рис. 8, 9, 10 (на рис. 8 індекси означають: 1 – алгоритм Балаша; 2 – багатоетапний, точний алгоритм на основі рангового підходу; 3 – багатоетапний, наближений алгоритм на основі рангового підходу). З наведених результатів видно, що оперативність рішення задач управління в АСУ складами на основі рангового підходу на порядки вище, ніж у відомих методів. При цьому значення показника оперативності Р 0,9 може бути забезпечене для задач, що мають від 150 до 250 змінних (при Тдоп= 3 хвилини). Теоретичні дослідження стали основою розробленого інтерактивного програмного комплексу рішення задач

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

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

ВИСНОВКИ

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

У ході досліджень отримані наступні результати:

1. Проведений аналіз діаграм функціонування АСУ складів супермаркетів показав, що - А, - В, - С задачі процесу оптимального планування вантажно-розвантажувальних робіт є задачами цілочислового булевого програмування (ЦЛП із БЗ):

- m-мірна задача 0,1-рюкзак;

- задача про найменше покриття;

- задача про найменшу розбивку;

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

Дані задачі ЦЛП із БЗ відносяться до класу NP-повних задач, що важко піддаються рішенню відомими алгоритмами, навіть при використанні сучасних ЕОМ і не забезпечують необхідну оперативність та точність рішення цих задач. Тому, як показано в розділі 1, виникає необхідність у розробці методів та алгоритмів, що дозволяє забезпечити оптимальне планування процесу управління в АСУ складами супермаркетів з необхідною оперативністю й точністю.

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

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

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

5. Удосконалено алгоритми рішення задачі А на основі ідей рангового підходу за рахунок використання двохетапної процедури оптимізації, що дозволило скоротити тимчасову складність рішення даної задачі та забезпечити при цьому похибку її рішення, що не перевищує 3 – 5 % .

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

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

8. Проведене моделювання процесу рішення задач оптимального планування управління АСУ супермаркетів і порівняльний аналіз ефективності застосування розроблених алгоритмів з відомими для рішення задач управління в АСУ складами супермаркетів показали, що оперативність рішення задач управління в АСУ складами супермаркетів на основі рангового підходу на порядок вище, чим у відомих методів. При цьому значення показника оперативності Р Рд може бути забезпечене для задач, які містять від 250 до 500 змінних. Вірогідність і обґрунтованість отриманих результатів підтверджується збіжністю теоретично отриманих результатів з результатами проведеного експериментального дослідження.

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Листровой С.В., Голубничий Д.Ю., Листровая Е.С. Метод решения задач целочисленного линейного программирования с булевыми переменными на основе рангового подхода // Электрон-ное моделирование. - 1998. - Т. 20, № 6. - С. 14 - 32.

2. Кавун С.В., Листровая Е.С., Корнеев А.Н. Перераспределение заданий с отказавших узлов сети на основе решения транспортной задачи // Сборник научных трудов ХГПУ. - 1998. - Вып. 6. - С. 401 - 404.

3. Листровой С.В., Гуль А.Ю., Листровая Е.С. Точный алгоритм решения задачи о наименьшем покрытии // Сборник научных трудов НАНУ “Информатика”. - 1998. - Вып. 5. - С. 33 - 37.

4. Листровая Е.С., Гиневский М.И., Пивнев Д.С. Влияние сортировок вершин в графе n-мерного единичного куба на погрешность при решении задачи о взвешенном минимальном пок-рытии // Збірник наукових праць ХВУ “Системи обробки інформації”. - 2000. - Вип. 4(10). - С. 172 - 174.

5. Листровая Е.С. Итерационный подход к решению m-мерной задачи 0,1-рюкзак на основе рангового подхода // Збірник наукових праць ХВУ “Системи обробки інформації”. - 2001. - Вип. 3(13). - С. 52 - 55.

6. Листровой С.В., Листровая Е.С., Яблочков С.В. Алгоритм решения задачи "3-выполни-мость" // Вестник НТУ (ХПИ). - 2001. - Вып. 4. - С. 146 - 151.

7. Кожухов В.Д., Листровая Е.С., Вешкин Д.М. Определение выполнимости расписаний при управлении сложными системами // Вісті академії інженерних наук. - 1998. - С. 103 - 107.

8. Кожухов В.Д., Лістрова О.С. Методи рішення задачі про найменший поділ на основі ран-гового підходу // Вісті академії інженерних наук. - 1999. - № 4. - С. 117 - 123.

9. Корнеев А.И., Листровая Е.С. Метод решения задачи ЦЛП на основе рангового подхода // Сборник ХВУ “Модели и системы”. - 1999. - № 1. - С. 40 - 44.

10. S.V.LISTROVOY, D. Yu. GOLUBNICHIY and E.S.LISTROVAYA Solution Method on the Basis of Rank Approach for integer Linear Programming Problems with Boolean Variables // Engineering Simulation. - 1999. - Vol.16. - Р. 707 - 725.

11. Листровая Е.С. Автоматизация складских хозяйств супермаркетов // Материалы высту-плений (тезисы докладов) участников 15-й Международной школы-семинара “Перспективные си-стемы управления на железнодорожном, промышленном и городском транспорте”. - Дополнение к том. 4, 5. - Алушта: Крым. - 2002. С. 32.

АНОТАЦІЯ

Лістрова О.С. Моделі та методи планування, оперативного накопичення та реалізації товарів в сучасних торгових центрах. - Рукопис.

Дисертаційна робота на здобуття наукового ступеня кандидата технічних наук за фахом: 05.13.06 - Автоматизовані системи управління і прогресивні інформаційні технології. - Наці-

ональний аерокосмічний університет ім. Н.Е. Жуковського “Харківський авіаційний інститут” Харків, 2003 р.

Дисертаційна робота присвячена рішенню актуальної науково-технічної задачі - розробці спеціального математичного та програмного забезпечення, що підвищує оперативність рішення задач оптимального планування процесом функціонування складів супермаркетів, з урахуванням обмежень на тимчасові та ресурсні витрати, формальною моделлю яких є задачі ЦЛП з БЗ. На основі ідей рангового підходу розроблені точні й наближені методи та алгоритми рішення А, - В, - С задач, які являються основними формальними моделями оптимального планування процесом динамічного управління в АСУ складами супермаркетів, що дозволили істотно підвищити оперативність процесу оптимального планування, а також підвищити завантаженість складських приміщень та знизити вартість експлуатації складських приміщень.

Ключові слова: АСУ реального часу, оптимальне планування, NP-повні задачі, ранговий підхід.

АННОТАЦИЯ

Листровая Е.С. Модели и методы планирования, оперативного накопления и реализации товаров в современных торговых центрах. – Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.06 - Автоматизированные системы управления и прогрессивные информационные технологии Национального аэрокосмического университета им. Н.Е. Жуковского “Харьковский авиационный институт” Харьков, 2003 г.

Диссертация посвящена решению актуальной научно-технической задачи – разработке специального математического и программного обеспечения для повышения оперативности решения задач оптимального планирования процессом управления АСУ складов супермаркетов, с учетом ограничений на временные и ресурсные затраты, формальной моделью которых являются задачи ЦЛП с БП.

В первом разделе проведен анализ особенностей функционирования АСУ складами супермаркетов как системы управления реального времени и их показателей качества. Проанализированы обобщённые типовые диаграммы и схемы функционирования современных АСУ складами супермаркетов.

В разделе 1 показано, что можно выделить следующие основные задачи, которые необходимо решать многократно в процессе функционирования АСУ склада:

- оптимальной загрузки лотов (ячеек) склада (А - задача);

- оптимальной разгрузки лотов (ячеек) склада (В - задача);

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

Основными формальными моделями этих задач являются следующие задачи целочисленного булевого программирования: m-мерная задача 0,1-рюкзак; задача о наименьшем покрытии (ЗНП); задача о наименьшем разбиении (ЗНР); задача решения систем диофантовых уравнений с булевыми переменными.

Решение сформулированной научно-технической задачи может быть достигнуто путём решения следующих частных задач: разработка точных и приближённых методов и алгоритмов решения А, - В, - С задач на основе рангового подхода, позволяющих повысить оперативность их решения и обеспечить требуемую точность решений; применение разработанных методов и алгоритмов для решения задач оптимального планирования в АСУ складами супермаркетов; оценка оперативности процесса оптимального планирования на основе разработанных методов и алгоритмов; разработка интерактивного программного комплекса решения задачи оптимального планирования процессом функционирования складов супермаркетов.

Второй раздел посвящён разработке и обоснованию моделей и методов для решения частных научно-технических задач, сформулированных в разделе 1, на основе идей рангового подхода. В разделе проанализированы различные методы решения задачи 0,1-рюкзак на основе идей рангового подхода и показано, что наиболее эффективными можно считать многоэтапные методы, позволяющие получать точное решение на основе предварительного этапа получения приближенного решения и использования приближенного решения первого этапа для отсева неперспективных вариантов решения на втором этапе. В разделе 2 на основе идей рангового подхода рассмотрена возможность решения частного случая задачи А и задачи В как задач о кратчайшем пути на графе G на основе применения системы калибровочных векторов и рассмотрена возможность решения на основе идей рангового подхода задачи С.

В третьем разделе представлены точные и приближенные алгоритмы решения А, - В, - С задач на основе стратегий отсечения неперспективных вариантов, рассмотренных в разделе 2. В разделе 3 также определены правила объединения высот калибровочных векторов, позволяющие на основе разработанных алгоритмов решения частного случая задачи А осуществлять и решение задачи В. Для взвешенных задач А и В был введен коэффициент j, определяющий число единиц в векторе B(i) и , характеризующий то, какая часть весовой характеристики Сj приходится на каждую единицу вектора B(i). Показано, что применение сортировок в порядке 1 2 … n-1 n, позволяет уменьшить погрешность решения взвешенных задач А и В.

В четвертом разделе приведены результаты экспериментального анализа временной сложности разработанных точных и приближенных алгоритмов решения А, - В, - С задач, а также

погрешности приближённых алгоритмов и их сравнительного анализа с известными. Разработана