У додатку наведено загальні характеристики математичних моделей задач, що вирішуються у процесі управління в АСУ складами супермаркетів, показники ефективності функціонування АСУ складами супермаркетів, основні поняття складського господарства, діаграми робочого процесу системи, характеристики процесу управління типовим складом супермаркету на базі розроблених алгоритмів. Наведено тексти програмних виробів для рішення поставлених у дисертаційної роботі задач, а також акти про впровадження результатів дисертаційної роботи.
ВИСНОВКИ
У дисертаційній роботі вирішена актуальна науково-технічна задача підвищення оперативності оптимального планування рішення задач управління процесом функціонування АСУ складів супермаркетів з урахуванням обмежень на тимчасові та ресурсні витрати, за рахунок зниження тимчасової складності роботи алгоритмів, які виконують розрахунки з планування.
У ході досліджень отримані наступні результати:
1. Проведений аналіз діаграм функціонування АСУ складів супермаркетів показав, що - А, - В, - С задачі процесу оптимального планування вантажно-розвантажувальних робіт є задачами цілочислового булевого програмування (ЦЛП із БЗ):
- m-мірна задача 0,1-рюкзак;
- задача про найменше покриття;
- задача про найменшу розбивку;
- задача рішення систем діофантових рівнянь із булевими змінними.
Дані задачі ЦЛП із БЗ відносяться до класу NP-повних задач, що важко піддаються рішенню відомими алгоритмами, навіть при використанні сучасних ЕОМ і не забезпечують необхідну оперативність та точність рішення цих задач. Тому, як показано в розділі 1, виникає необхідність у розробці методів та алгоритмів, що дозволяє забезпечити оптимальне планування процесу управління в АСУ складами супермаркетів з необхідною оперативністю й точністю. 2. Вперше розроблено метод рішення приватного випадку задачі А й удосконалено метод рішення задачі В на основі рангового підходу. Отримані наближені й точні алгоритми рішення даних задач з низькою тимчасовою складністю і похибкою.
3. Вперше на основі розробленої узагальненої процедури рішення задач дискретної оптимізації і принципу виділення коридору в множині рішень розроблено метод рішення задачі С, що дозволяє з необхідною оперативністю складати розклад виконання робіт в АСУ супермаркетів.
4. Вперше на основі розроблених методів побудовані алгоритми оптимального планування функціонуванням складських АСУ реального часу, що забезпечують високу оперативність при рішенні приватного випадку задачі А і задачі С.
5. Удосконалено алгоритми рішення задачі А на основі ідей рангового підходу за рахунок використання двохетапної процедури оптимізації, що дозволило скоротити тимчасову складність рішення даної задачі та забезпечити при цьому похибку її рішення, що не перевищує 3 – 5 % .
6. Досліджено вплив сортувань векторів в узагальненій процедурі рангового підходу при рішенні задач дискретної оптимізації в дискретному просторі, обумовленому n-мірним одиничним кубом на похибку рішення задачі, сформульовано рекомендації з їхнього використання при рішенні А, - В, - С задач.
7. Розроблено інтерактивний програмний комплекс для реалізації та дослідження розроблених алгоритмів і порівняння їх з відомими, який дозволяє легко нарощувати кількість досліджуваних алгоритмів і застосовувати запропоновані алгоритми для широкого кола прикладних задач, описуваних розглянутими моделями.
8. Проведене моделювання процесу рішення задач оптимального планування управління АСУ супермаркетів і порівняльний аналіз ефективності застосування розроблених алгоритмів з відомими для рішення задач управління в АСУ складами супермаркетів показали, що оперативність рішення задач управління в АСУ складами супермаркетів на основі рангового підходу на порядок вище, чим у відомих методів. При цьому значення показника оперативності Р > Рд може бути забезпечене для задач, які містять від 250 до 500 змінних. Вірогідність і обґрунтованість отриманих результатів підтверджується збіжністю теоретично отриманих результатів з результатами проведеного експериментального дослідження.
СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ
1. Листровой С.В., Голубничий Д.Ю., Листровая Е.С. Метод решения задач целочисленного линейного программирования с булевыми переменными на основе рангового подхода // Электрон-ное моделирование. - 1998. - Т. 20, № 6. - С. 14 - 32.Кавун С.В., Листровая Е.С., Корнеев А.Н. Перераспределение заданий с отказавших узлов сети на основе решения транспортной задачи // Сборник научных трудов ХГПУ. - 1998. - Вып. 6. - С. 401 - 404.
- Листровой С.В., Гуль А.Ю., Листровая Е.С. Точный алгоритм решения задачи о наименьшем покрытии // Сборник научных трудов НАНУ “Информатика”. - 1998. - Вып. 5. - С. 33 - 37.
- Листровая Е.С., Гиневский М.И., Пивнев Д.С. Влияние сортировок вершин в графе 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, позволяет уменьшить погрешность решения взвешенных задач А и В.
В четвертом разделе приведены результаты экспериментального анализа временной сложности разработанных точных и приближенных алгоритмов решения А, - В, - С задач, а также погрешности приближённых алгоритмов и их сравнительного анализа с известными. Разработана обобщённая структурную схема алгоритма применения разработанных методов планирования функционированием АСУ складом супермаркета, позволяющая независимо от специализации склада осуществлять планирование управления работой склада на основе типовых алгоритмов функционирования АСУ складом, рассмотренных в разделе 1. Также разработан интерактивный программный комплекс для предложенных алгоритмов, позволяющий легко наращивать количество исследуемых алгоритмов и оценивать их временную сложность, на базе которого проведено имитационное моделирование и сравнение по выбранному показателю оперативности процесса оптимального планирования на основе разработанных алгоритмов с известными алгоритмами. Из проведенного сравнения следует, что разработанные алгоритмы по оперативности существенно превосходят известные. В приложениях приведены основные программные модули и необходимые справочные материалы.
Ключевые слова: АСУ реального времени, оптимальное планирование, NP-полные зада-чи, ранговый подход.
ANNOTATION
Listrovaya E.S. Models and methods in planning immediate collection and realization of goods in modern trading centers. – Manuscript.
This thesis is for obtaining a scientific degree of Candidate of Technical Sciences under the specialty: 05.13.06 – Automized control systems and progressive information technologies. – National Aerospace University “Kharkov Aviation Institute”, Kharkov, 2003.
This thesis is consecrated to the solution of topical scientific and technical problem – it’s increasing the drive in solving problems of optimum planning the process of functioning supermarket’s storage facilities, taking into consideration restrictions on time’s and resource’s expenses, problems of WPZP with BV (whole – numbered problems of linear programming with boolean variables) turn out to be the formal model of them. On the basis of rank approach ideas there have been worked out exact and approximate algorithms of solving A, - B, - C problems, which are the base formal models of optimum planning the process of dynamical control in ACS (Automized control systems) under supermarket’s storage, which enable to increase the drive of optimum planning process substantially, as well as to increase filling in the warehouses space and to reduce the exploitation cost of the warehouses space.
Key words: ACS of real time, optimum planning, NP- full problems, rank approach.
| 
