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

Скорочена інформація про документ
dc.contributor.authorДанильченко, А. О.
dc.date.accessioned2020-11-13T09:50:16Z
dc.date.available2020-11-13T09:50:16Z
dc.date.issued2012
dc.description.abstractenThe purpose of this study is to develop an algorithm for solving the nurse scheduling problem for home patients who receive treatment that will provide a lower computational complexity than the method of exhaustive search and will allow finding a solution that meets the specified limit for the procedures. The proposed new algorithm for solving the application problem of scheduling treatment of patients who receive nursing home as an extended mathematical problem of finding the maximum matching in a bipartite graph with vanishing edges. In contrast to the known ones, the algorithm can take into account the limited compatibility of treatment and has a lower computational complexity than the method of exhaustive search by reducing the number of matches to be analyzed. In addition, we conduct the comparative computational experiment relying on a series of the task random environment obtained from real home patients based on the hourly sampling. It shows that the proposed algorithm provides optimal reduction time scheduling from 4,48 times to 8,87 times compared to exhaustive search method. Time scheduling is directly proportional to the number of vertices of bipartite graphs.uk
dc.description.abstractruПредложен новый алгоритм решения прикладной задачи составления расписания приема лечебных процедур пациентами санатория как расширенной математической задачи поиска максимального паросочетания в двудольном графе с исчезающими дугами. В отличие от известных, алгоритм позволяет учесть ограничения совместимости лечебных процедур и имеет меньшую вычислительную сложность по сравнению с методом полного перебора за счет сокращения количества паросочетаний, которые будут анализироваться. Алгоритм гарантирует нахождение решения задачи составления расписания приема процедур пациентами санатория, если оно существует. Проведено вычислительный эксперимент на серии случайных условий задачи, полученных от реальных пациентов санатория по временной выборке. Он показал, что предложенный оптимальный алгоритм обеспечивает уменьшение времени составления расписания от 4,48 раз до 8,87 раза по сравнению с методом полного перебора и время составления расписания прямо пропорционально зависит от количества вершин двухдольного графа.uk
dc.description.abstractukЗапропоновано новий алгоритм розв’язання прикладної задачі складання розкладу приймання лікувальних процедур пацієнтами санаторію як розширеної математичної задачі пошуку максимального паросполучення у дводольному графі зі зникаючими дугами. На відміну від відомих, алго- ритм дає змогу врахувати обмеження сумісності лікувальних процедур і має меншу обчислювальну складність порівняно з методом повного перебору за рахунок скорочення кількості паросполучень, що аналізуються. Алгоритм гарантує знаходження розв’язку задачі складання розкладу приймання процедур пацієнтами санаторію, якщо він існує. Проведено порівняльний обчислювальний експеримент на серії випадкових умов задачі, отриманих від реальних пацієнтів санаторію за часовою вибіркою. Він засвідчив, що запропонований оптимальний алгоритм забезпечує зменшення часу складання розкладу від 4,48 до 8,87 разу порівняно з методом повного перебору і що час складання розкладу прямо пропорційно залежить від кількості вершин дводольного графа.uk
dc.format.pagerangeС. 46–53uk
dc.identifier.citationДанильченко, А. О. Складання оптимального розкладу за наявності заданих обмежень на основі теорії графів / А. О. Данильченко // Наукові вісті НТУУ «КПІ» : міжнародний науково-технічний журнал. – 2012. – № 6(86). – С. 46–53. – Бібліогр.: 8 назв.uk
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/37369
dc.language.isoukuk
dc.publisherНТУУ «КПІ»uk
dc.publisher.placeКиївuk
dc.sourceНаукові вісті НТУУ «КПІ»: міжнародний науково-технічний журнал, № 6(86)uk
dc.subject.udc519.161uk
dc.titleСкладання оптимального розкладу за наявності заданих обмежень на основі теорії графівuk
dc.title.alternativeOn Optimal Scheduling in the Presence of Defined Limits Based on Graph Theoryuk
dc.title.alternativeСоставление оптимального расписания при наличии заданных ограничений на основе теории графовuk
dc.typeArticleuk

Файли

Контейнер файлів
Зараз показуємо 1 - 1 з 1
Ескіз
Назва:
2012-6-6.pdf
Розмір:
210.58 KB
Формат:
Adobe Portable Document Format
Опис:
Завантажити
Ліцензійна угода
Зараз показуємо 1 - 1 з 1
Ескіз недоступний
Назва:
license.txt
Розмір:
8.98 KB
Формат:
Item-specific license agreed upon to submission
Опис:
Завантажити

Зібрання

Наукові вісті НТУУ «КПІ»: міжнародний науково-технічний журнал, № 6(86)