МОДЕЛЬ ПРОГНОЗУВАННЯ РАНЖУВАННЯ РОЗГАЛУЖЕНИХ ПРОЦЕДУР ПРИ ПЛАНУВАННІ ПРОЕКТУ З ОБМЕЖЕНИМИ РЕСУРСАМИ - Наукові конференції
Головна
UA RU EN

Вас вітає Інтернет конференція!

Вітаємо на нашому сайті

Рік заснування видання - 2011

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

19.09.2023 18:21

[1. Інформаційні системи і технології]

Автор: Сікач Богдан Ярославович, магістр кафедри інформаційно-обчислювальних систем і управління, Західноукраїнський національний університет


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

Метод розгалуження та зв’язку є найпоширенішим способом вирішення цієї проблеми для отримання оптимальних рішень [2]. Розроблено розгалужену процедуру, яка враховує всі найефективніші компоненти з літератури [1]. Це так звана композитна процедура розгалуження та зв'язку. 

Проблему планування проекту з обмеженим ресурсом можна сформулювати таким чином: набір дій N, пронумерованих від фіктивного початкового вузла 0 до фіктивного кінцевого вузла n+1, повинен бути запланований без випередження на наборі R видів відновлюваних ресурсів. Кожен відновлюваний ресурс k ∈ R має постійну доступність ak за період. Кожна нефіктивна діяльність i ∈ N має детерміновану тривалість di та потребує ri,k одиниць типу ресурсу k ∈ R. Початкова та кінцева фіктивні дії 0 та n+1 представляють початок та завершення проекту, у якому їх тривалість та потреба у відновлюваних ресурсах дорівнює нулю. Мережа проекту представлена у форматі топологічної впорядкованої активності на вузлі (AoN), де A – це набір пар дій, між якими існує зв’язок пріоритету завершення-початку з часовим лагом 0. Вважаємо граф G(N,A) ациклічним. Розклад S визначається вектором часу початку діяльності та вважається здійсненним, якщо задовольняються всі обмеження пріоритету та відновлюваних ресурсів. Мета типу проблеми полягає в тому, щоб знайти можливий графік у межах найнижчого можливого періоду виконання проекту, і, отже, тип проблеми можна представити як m,1T|cpm|Cmax за допомогою схеми класифікації [6]. 

Вивчення нещодавно привернуло значну увагу в дослідженнях штучного інтелекту. Ранжування міток мотивується програмами, у яких вихідні дані відображають інформацію про перевагу або порядок релевантності серед набору об’єктів. Він розширює звичайну класифікацію та класифікацію з кількома мітками в тому сенсі, що їй потрібно передбачити ранжування всіх міток класу замість лише однієї чи кількох міток класу [4]. Завдяки загальному ранжуванню міток його широко використовують у багатьох практичних застосуваннях, таких як аналіз шаблонів, аналіз настроїв, націлювання реклами, системи рекомендацій і метанавчання [5].

Метод розгалуження та зв’язку має чотири фази:

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

Фаза 2. Поділ даних. На цьому другому етапі весь набір контрольних даних ділиться на різні набори для всіх обчислювальних експериментів. Більш конкретно, набір даних поділяється на набір для навчання, набір для перевірки та набір для тестування. Навчальний набір використовується на етапі навчання для отримання зв’язку між показниками проекту (вхідні дані, характеристики) і повним рейтинговим списком продуктивності усіх конфігурацій процедури розгалуження та зв’язку (виходи, рейтинговий список усіх міток). Оскільки метою моделі передбачення є створення рейтингового списку для конфігурацій процедури розгалуження та зв’язку, рейтинговий список для кожного конкретного екземпляра в навчальному наборі повинен бути визначений за допомогою критерію якості. 

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

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

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

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

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

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

Література

1.J. Coelho, M. Vanhoucke, Going to the core of hard resource-constrained project scheduling instances. Computers & Operations Research, vol. 121, 104976, 2020. 

2.W. Guo, M. Vanhoucke, J. Coelho, J. Luo, Automatic detection of the best performing priority rule for the resource-constrained project scheduling problem. Expert systems with applications, vol. 167, 114116, 2021. 

3.A. Korba, A. Garcia, F. d’AlchéBuc, A structured prediction approach for label ranking. Advances in neural information processing systems, vol. 31, pp. 8994–9004, 2018. 

4.T.-H. Lee, A. Ullah, R. Wang, Bootstrap aggregating and random forest. In Macroeconomic forecasting in the era of big data, Springer, 2020, pp. 389–429. 

5.Y. Zhou, G. Qiu, Random forest for label ranking. Expert systems with applications, vol. 112, pp. 99–109, 2018.

___________________________________________________________________

Науковий керівник: Саченко Олег Анатолійович, доцент кафедри інформаційно-обчислювальних систем і управління, Західноукраїнський національний університет 

Creative Commons Attribution Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License
допомога Знайшли помилку? Виділіть помилковий текст мишкою і натисніть Ctrl + Enter

Інші наукові праці даної секції

Конференції

Конференції 2024

Конференції 2023

Конференції 2022

Конференції 2021



Міжнародна інтернет-конференція з економіки, інформаційних систем і технологій, психології та педагогіки

Наукова спільнота - інтернет конференції

:: LEX-LINE :: Юридична лінія

Інформаційне суспільство: технологічні, економічні та технічні аспекти становлення