Составление оптимального расписания при наличии заданных ограничений на основе теории графов

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

Год издания: 
2012
Номер: 
6
УДК: 
519.161
С. 46—53. Іл. 3. Табл.. 3. Бібліогр.: 8 назв.
Литература: 

1. Данильченко О.М., Данильченко А.О., Ібрагім С.А. Розв’язання одного класу задач складання розкладів генетичними алгоритмами на кластерних системах // Вісник ЖІТІ, 2004. – № 4. – С. 130–135.
2. Панішев А.В., Данильченко А.М., Данильченко А.А. Задача про паросполучення зі “зникаючими” дугами” // Моделювання та інформ. технол.: Зб. наук. пр. – К., 2012 – С. 75–81.
3. Рыбников К.А. Введение в комбинаторный анализ. – М.: Изд-во МГУ, 1985. – 312 с.
4. Ope О. Теория графов. – М.: Наука, Гл. ред. физ.- мат. лит., 1980. – 336 с.
5. Майника Э. Алгоритмы оптимизации в сетях и графах: Пер. с англ. – М.: Мир, 1981. – 324 с.
6. Харари Ф. Теория графов / Пер. с англ. и предисл. В.П. Козырева; под ред. Г.П. Гаврилова. – 2-е изд. – М.: Едиториал УРСС, 2003. – 296 с.
7. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. – М.: Мир, 1985. – 512 с.
8. Данильченко О.М., Данильченко А.О. Інтелектуальний аналіз даних (Data Mining): Навч. посібник. – Жито- мир: ЖДТУ, 2009. – 406 с.

Полнотекстовый документSize
2012-6-6.pdf210.58 KB