On Optimal Scheduling in the Presence of Defined Limits Based on Graph Theory


The 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.

Publication year: 
С. 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 с.

2012-6-6.pdf210.58 KB

Тематичні розділи журналу