Одноетапні задачі теорії розкладів у багаторівневій системі планування (стр. 5 )

Проаналізовано якість розв'язків, одержаних за допомогою розроблених евристичних методів, на основі порівняння з точним розв'язком, що дає метод гілок і границь. Досліджено, що запропоновані методи дають змогу одержати розв'язки, наближені до оптимальних з невеликим відхиленням. Це важливо, оскільки розроблені методи (алгоритми А1-А4) дають можливість одержання ефективного розв'язку задачі 1-МВЗН з розмірністю до 500 завдань, у той час як відомий точний метод гілок і границь можна застосувати для розв'язування цієї задачі з розмірністю не більше 20 завдань. У табл. 6, 7 показано середнє відхилення значення функціоналу від оптимального у відсотках. Відсоток відхилення D обчислюється у такий спосіб:

,

де – сумарне випередження/запізнення розв’язку, зробленого алгоритмом гілок і границь, а Z – сумарне випередження/запізнення розв’язку, одержаного одним з розроблених евристичних алгоритмів (А1-А4).

Таблиця 6

Середнє відхилення значення функціоналу від оптимального

для алгоритмів А1, А2, %

Комбінація параметрів	I	II	III	I	II	III
		Алгоритм А1	Алгоритм А2
2	3	0.00	0.00	0.00	7.33	2.37	1.01
2	4	1.34	1.26	0.18	12.78	10.42	1.79
2	5	2.03	1.57	0.12	15.95	10.26	1.23
3	3	2.67	1.34	0.08	13.54	13.50	1.84
3	4	2.25	1.33	0.19	13.44	11.41	1.93
3	5	2.46	1.46	0.30	14.76	8.92	3.03

Результати табл. 6 показують, що алгоритм А1 виконується краще, ніж алгоритм А2 з погляду середнього відсотка відхилення для всіх комбінацій параметрів задачі. Фактично для задачі з , алгоритм А1 знайшов оптимальний розв’язок для всіх комбінацій параметрів. Середній відсоток відхилення для алгоритму А1 становив близько 1% на всіх множинах задач і менше 2% для 14 з 18 множин задач. Середній відсоток відхилення для алгоритму А2 становив близько 8% на всіх множинах задач і менше 10% для половини множин задач.

Таблиця 7

Середнє відхилення значення функціоналу від оптимального

для алгоритмів А3, А4, %

Комбінація параметрів	I	II	III	I	II	III
	Алгоритм А3	Алгоритм А4
10	0.0	0.0	0.0	0.0	0.0	0.0
15	4.1	5.0	2.5	0.1	0.1	0.0
20	8.9	7.4	12.3	0.8	0.7	1.2
25	21.3	20.4	18.1	7.0	5.0	9.0

Результати табл. 7 показують, що для всіх задач з розмірністю 10 алгоритми знайшли оптимальний розв’язок. Середній відсоток відхилення для алгоритму А3 становив близько 8.3% на всіх множинах задач і менше 9% для 8 з 12 множин задач. Середній відсоток відхилення для алгоритму А4 становив близько 2% на всіх множинах задач і менше 1% для 8 з 12 множин задач.

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

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

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

На діаграмі компонентів (рис. 4) зображено основні модулі, з яких складається система планування. Діаграма показує місце модуля розв’язання задач мінімізації сумарного випередження та запізнення в багаторівневій системі планування, а також модулі, з яких він складається.

Покажемо, коли задача 1-МВЗН може бути використана при складанні розкладів робіт на третьому рівні. Для цього необхідно, щоб існував мультиресурс, представлений одним приладом, що потребує переналагоджень, тривалість яких істотно впливає на якість розкладу. У відповідності до розкладу другого рівня визначено послідовність агрегованих робіт, для яких необхідно скласти розклад на третьому рівні. Тривалість переналагоджень усереднено враховується в тривалості виконання робіт при плануванні на другому рівні. У цій послідовності агрегованих робіт існує хоча б одна така робота, що складається з окремих робіт. Директивні строки виконання робіт однозначно визначаються директивними строками виготовлення виробів, до яких вони відносяться при плануванні за критерієм точно в строк. Послідовність робіт, які слідують за кожною роботою, що входить до агрегованої роботи, однозначно задається технологією виготовлення виробів. У цьому випадку складання розкладу робіт даної агрегованої роботи зводиться до задачі 1-МВЗН, що розв’язується за алгоритмами А1-А4. При цьому побудова розкладу третього рівня повинна починатися з побудови розкладу визначених вище робіт (розклад робіт, що входять в агреговану роботу та робіт, які слідують за ними). Очевидно, що ефективний розв’язок задачі 1-МВЗН істотно підвищить імовірність виготовлення відповідних виробів точно в строк. Таким чином, узагальнення трирівневої моделі планування з використанням мультиресурсів, представлених одним приладом з переналагодженнями, зводиться до моделей, що розглядаються в багаторівневій системі планування з мережевим представленням технологічних процесів та обмеженими ресурсами.

Рис. 4. Діаграма компонентів

До третього рівня моделі включені такі задачі: мінімізації сумарного випередження та запізнення при виконанні груп завдань одним приладом з налагодженнями (для випадків, коли простої як дозволені, так і заборонені); мінімізації сумарного випередження та запізнення при виконанні завдань одним приладом з налагодженнями, залежними від послідовності завдань.

У роботі представлено детальні діаграми діяльності, що відповідають алгоритмам А1–А4 розв’язання задач 1-МВЗН.

Система розроблена за об’єктно-орієнтованою технологією з використанням мови програмування високого рівня C# 4.0 на платформі. NET.

ОСНОВНІ РЕЗУЛЬТАТИ І ВИСНОВКИ

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

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

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

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

4. Вперше показано взаємозв’язок між методами розв’язання задач мінімізації сумарного запізнення завдань відносно директивних строків (МСЗ), мінімізації сумарного випередження і запізнення відносно директивних строків при виконанні незалежних завдань одним приладом (МВЗ), мінімізації сумарного випередження та запізнення при виконанні завдань одним приладом з налагодженнями (1-МВЗН), що дало змогу на основі методів розв’язання задач МСЗ та МВЗ побудувати нові ефективні евристичні методи розв’язання задачі 1-МВЗН, які, на відміну від існуючих, дають можливість одержати розв’язок задач великої розмірності.

5. Розроблено нові евристичні методи мінімізації сумарного випередження та запізнення при виконанні завдань одним приладом з налагодженнями для таких задач: у разі, коли простої обладнання дозволені (алгоритм А1), для випадку, коли простої обладнання заборонені (алгоритм А2), у разі, коли налагодження залежать від послідовності завдань (алгоритми А3, А4), що дало змогу отримати високоякісні наближені розв’язки з невеликими часовими витратами, у тому числі для задач великої розмірності.

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

7. Обгрунтовано, що розроблені евристичні методи забезпечують одержання розв’язків оптимізаційних задач з урахуванням налагодження приладів з високою якістю за значно менший час порівняно з методом гілок і границь (близько 17–407.5 разів для досліджених задач розмірністю 10-25 завдань, для яких можливе застосування точного методу; середнє відхилення значення функціоналу від оптимального знаходиться в межах 1-8.3%).

8. Обґрунтовано, що ефективність алгоритмів А3, А4 якісно залежить від визначення околу поточних рішень. Алгоритм А3, який базується на розробленій евристиці, забезпечує одержання розв’язку за середній час менший у 23.8 разів порівняно з алгоритмом А4. Алгоритм А4, який базується на розробленій евристиці та відомому методі локального пошуку, дає змогу одержати точніші результати, оскільки розглядає більший окіл поточних рішень (середнє відхилення значення функціоналу від оптимального для алгоритму А4 становить близько 2%, для А3 − близько 8,3%).

9. Формалізовано змістову постановку задачі 1-МВЗН, що дало змогу вдосконалити модель багаторівневої системи планування з мережевим представленням технологічних процесів та обмеженими ресурсами шляхом включення до її третього рівня методів розв’язання задачі 1-МВЗН, реалізованих у вигляді алгоритмів А1–А4 .

10. Розроблено інформаційні технології та вдосконалено програмне забезпечення багаторівневої системи планування з мережевим представленням технологічних процесів та обмеженими ресурсами шляхом включення до її складу задачі 1-МВЗН та методів її розв’язання (алгоритмів А1–А4), що дало змогу підвищити ефективність системи, розширити її функції та коло прикладних задач її застосовування.

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

1. Інформаційне забезпечення алгоритмів мінімізації сумарного випередження і запізнення із налагодженнями / , О. Б. Місюра,
// Системи обробки інформації. - Харків: Харківський університет Повітряних сил імені Івана Кожедуба, 2012. – Випуск 2 (100). – С. 250-259.

2. Ващук ідження ефективності алгоритму складання розкладів сумарного випередження і запізнення із налагодженнями, що залежать від послідовності /
, // Бионика интеллекта. Информация, язык, интеллект. − Х.: ХНУРЭ, 2012. − №1(78). − С. 49-52.

3. Складання розкладів сумарного випередження і запізнення із налагодженнями, що залежать від послідовності / , , Місюра О. Б.,
// Вісник Національного технічного університету України "КПІ". Інформатика, управління та обчислювальна техніка : зб. наук. пр. – К. : Век+, 2011. - №53. - С.192-194.

4. Складання розкладів груп для одного приладу із налагодженнями за критерієм мінімізації сумарного випередження і запізнення / , , Місюра О. Б., // Вісник Національного технічного університету України "ХПІ". Тематичний випуск "Системний аналіз, управління та інформаційні технології". – Х. : НТУ "ХПІ", 2011. - №32. - С.8-18.

5. Мельник ідження властивостей алгоритмів складання розкладів груп для одного приладу із налагодженнями за критерієм сумарного випередження і запізнення / // Вісник Східноукраїнського національного університету імені Володимира Даля. − 2012. − № 2 (173). − С. 2

6. Мельник ідження ефективності алгоритмів складання розкладів груп для одного приладу із налагодженнями за критерієм сумарного випередження і запізнення / // Інформатика та системні науки (ІСН-2012): матеріали ІІІ Всеукраїнської науково-практичної конференції (м. Полтава,
1-3 березня 2012 р.) / За ред. О. О. Ємця. – Полтава : ПУЕТ, 2012. – С. 192 – 194.

7. Інформаційне забезпечення алгоритмів мінімізації сумарного випередження і запізнення із налагодженнями / // Тези доповідей Міжнародної науково-практичної конференції "Інформаційні технології в науці, освіті і техніці" (ІТОНТ-2012) : Черкаси, 25-27 квітня 2012 р. – У 2 т. – Черкаcи: ЧДТУ, 2012. – Т.1. – С.39.

8. Мельник ідження властивостей алгоритмів розв'язування задачі складання розкладів із часами налагоджень сімейств / // Сучасні інформаційні системи та технології : матеріали Першої міжнародної науково-практичної конференції [AIST-2012] (м. Суми, 15-18 травня 2012 р.). − Суми : СумДУ, 2012. − С. 156-157.

9. Ващук 'язання задачі складання розкладів сумарного випередження і запізнення із налагодженнями, що залежать від послідовності / , // Міжнародне співробітництво у впровадженні інноваційних технологій навчання у вищій школі: міжнародний науковий вісник : зб. наук. доповідей за матеріалами ХХ міжнар. наук.–практ. конференції, 11 – 14 травня 2010 р. (Словацька Республіка) / [упоряд. ]. − Ужгород : ЗакДУ, 2010. − Вип.1 (20). − С. 115–118.

10. Ващук подход к описанию структуры сети программно-технических комплексов (ПТК) / , , // Тези доповідей міжнародної алгебраїчної конференції (м. Ужгород, 27-29 серпня
2001 р.).— Ужгород: УжНУ, 2001. — С. 29.

11. Vaschuk F. Research of efficiency of algorithm machine scheduling of minimizing the total earliness and tardiness that depend on sequence / Vaschuk F., Melnyk O. // Міжнародний науковий вісник Закарпатського державного університету. Наукові праці кафедри виробничої техніки та робототехніки Кошицького технічного університету / Ред. кол. (голова), Вархола Міхал, Дубровка Мігаль, І. та ін. – Ужгород: ЗакДУ, 2012. – С. 258 – 266.

АНОТАЦІЇ

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

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.06 - інформаційні технології. – Національний університет "Львівська політехніка", Львів, 2013.

Робота присвячена розробленню нових методів вирішення задач теорії розкладів за критерієм мінімізації сумарного випередження і запізнення з урахуванням налагодження приладів в багаторівневій системі планування з мережевим представленням технологічних процесів та обмеженими ресурсами. Вперше показано взаємозв’язок між методами розв’язання задач мінімізації сумарного запізнення завдань відносно директивних строків (МСЗ), мінімізації сумарного випередження і запізнення відносно директивних строків при виконанні незалежних завдань одним приладом (МВЗ), мінімізації сумарного випередження та запізнення при виконанні завдань одним приладом з налагодженнями (1-МВЗН), що дало змогу на основі методів розв’язання задач МСЗ та МВЗ побудувати нові ефективні евристичні методи розв’язання задачі 1-МВЗН, які, на відміну від існуючих, дають можливість одержати розв’язок задач великої розмірності. Розроблені та статистично обґрунтовані нові ефективні методи для розв’язання задач мінімізації сумарного випередження і запізнення при виконанні груп завдань одним приладом з налагодженнями та мінімізації сумарного випередження і запізнення при виконанні завдань одним приладом з налагодженнями, залежними від послідовності. Створено систему моделювання для статистичного дослідження ефективності розроблених методів. Досліджено, що запропоновані методи дали змогу отримати високоякісні наближені розв’язки з невеликими часовими витрат.

Удосконалено програмне забезпечення системи за рахунок включення до її складу задачі 1-МВЗН та методів її розв’язання. Це дало змогу підвищити ефективність системи, розширити її функції та коло прикладних задач її застосовування. Розроблено інформаційні технології та реалізовано у вигляді алгоритмів методи розв’язання досліджуваних задач у багаторівневій системі планування з мережевим представленням технологічних процесів та обмеженими ресурсами.

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

Мельник задачи теории расписаний в многоуровневой системе планирования. – На правах рукописи.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.06 - информационные технологии. – Национальный университет "Львовская политехника", Львов, 2013.

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

Производства с сетевым представлением технологических процессов и ограниченными ресурсами охватывают около 80% всех видов производственных систем. Эффективность процесса планирования с учетом технологий производства существенно зависит от наличия переналадок оборудования. В некоторых случаях время наладки прибора может быть более длительным по сравнению со временем выполнения прибором работы.

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

На основе методов решения задач минимизации суммарного запаздывания заданий относительно директивных сроков (МСЗ), минимизации суммарного опережения и запаздывания относительно директивных сроков при выполнении независимых заданий одним прибором (МОЗ) разработаны четыре новых метода решения задач минимизации суммарного опережения и запаздывания при выполнении групп заданий одним прибором с наладками (1-МОЗН).

Методы решения задач минимизации суммарного опережения и запаздывания при выполнении групп заданий одним прибором с наладками реализованы в виде алгоритмов: А1 – для случаев, когда простои оборудования разрешены, А2 − при запрещенных простоях оборудования, А3 и А4 – для наладок, зависимых от последовательности заданий.

Создана система моделирования для статистического исследования эффективности разработанных методов. Результаты исследований показали, что разработанные эвристические методы позволили получить близкие к оптимальным решения задач большой размерности (от 50 до 500 заданий), для которых точные методы не применимы.

Установлено, что разработанные эвристические методы обеспечивают получение решений оптимизационных задач з учетом наладок приборов с высоким качеством за значительно меньшее время сравнительно с методом ветвей и границ (в 17–407.5 раз для исследованных задач размерностью 10-25 заданий, для которых возможно применение точного метода; среднее отклонение значения функционала от оптимального находится в пределах 1-8.3%). Эффективность алгоритмов А3, А4 качественно зависит от определения окрестности текущих решений. Алгоритм А3, основанный на разработанной эвристике, дает решение за меньшее в 23.8 раз среднее время по сравнению с алгоритмом А4. Алгоритм А4, который основан на разработанной эвристике и известном методе локального поиска, позволяет получить более точные результаты, так как рассматривает более широкую окрестность текущих решений (среднее отклонение значения функционала от оптимального для алгоритму А4 составляет около 2%, для А3 − около 8,3%).

Все предложенные методы и алгоритмы имеют самостоятельное значение, а также являются основой для создания эвристик для применения в более сложных моделях. Например, практические задачи для нескольких приборов раскладываются на подзадачи для одного прибора, которые решаются отдельно, что существенно упрощает решение многоприборных задач. Разработанные методы и модели могут широко применяться в многоуровневых производственных системах различного назначения.

Модифицировано программное обеспечение системы за счет включения в ее состав задачи 1-МОЗН и методов ее решения. Это позволило расширить функции системы, повысить ее эффективность, а также расширить прикладную область ее применения.

Разработаны информационные технологии и реализованы алгоритмы решения исследуемых задач в многоуровневой системе планирования объектов с сетевым представлением технологических процессов и ограниченными ресурсами.

Ключевые слова: информационные технологии, теория расписаний, одноэтапные задачи, системы планирования, наладка оборудования, критерий минимизации суммарного опережения и запаздывания.

Melnyk O. О. One-stage Task Scheduling Theory in a Multi-level System Planning. − Manuscript.

Ph. D. thesis (candidate of Technical Science) in specialty 05.13.06 - Information Technologies. − Lviv Polytechnic National University, Lviv, 2013.

This thesis is a complex research devoted to the developing of new methods for solving scheduling theory on the criterion of minimizing the total earliness and tardiness in the system with a network representation of processes and limited resources.

For the first time the relationship between methods of solving problems of minimizing the total tardiness of the tasks concerning the directive terms, minimizing the total earliness and tardiness directive terms in solving the independent tasks with one device adjustment, minimizing the total earliness and tardiness of the tasks with one device adjustment.

The author statistically confirmed and developed new efficient methods for solving the problems of minimizing the total earliness and tardiness in the process of doing the group tasks with one device adjustment and the problems of minimizing the total earliness and tardiness of the tasks with one device adjustment depending on the sequence.

A system of modeling for statistical study of the effectiveness of the developed methods is created.

Software system is modified by means of incorporating into its structure the problem of minimizing the total earliness and tardiness of the tasks with one device adjustment and methods of its solution. This allows us to expand the functions of the system and increase its efficiency.

The information technologies are developed and algorithms are implemented as methods of the studied problems in a multi-level system planning facilities with a network representation of technological processes and limited resources.

Keywords: information technologies, scheduling theory, one-stage problem, planning systems, device adjustment, criteria of minimizing of the total earliness-tardiness.