Українська   Русский
   

Abstract

Content

Introduction

The introduction of the automated management system allows you to systematize data exchange, regulate the composition and presentation of data, as well as the structure of information flows in the system, significantly improve the accuracy and accuracy of their maintenance, ensure their safety, provide complete interrelated information for all subjects of the sanatorium. All this leads to the coordinated work of the staff and many times increases the efficiency of functioning of the enterprise as a whole.

Within this work is considered creation of the most suitable schedule for the passing of health-related procedures the optimal composition of which affects the quality of work of the sanatorium complex. A well-prepared schedule should ensure uniform loading of treatment rooms and equipment, and comfortable work of medical staff and flexible schedule for patients of the sanatorium.

1. Theme urgency

The schedule of passing of medical and improving procedures has to consider a large number of the restrictions connected with subject domain. First of all the rules of diagnostic and medical and rehabilitation services (procedures) have to be respected. It is necessary to adhere to the sequence of holding the procedures appointed by the doctor and also it is correct to distribute load of the equipment. Because of the many limitations and specific features that are not typical for other industries, the scheduling of treatment and wellness procedures manually is a very laborious and time-consuming work. And automation of this task will make it possible to achieve a more optimal decision.

There is a need to find a decision that would be able to take into account all the specific aspects of the subject area and to give the most optimal results. Since an effective genetic algorithm has not been found, the formation of a modified algorithm is actual. Based on the analysis and identified shortcomings of existing research in this paper conducted a study aimed at solving the problem of creation of the most suitable schedule for the passing of health-related procedures, using aggregated genetic algorithm.

2. Goal and tasks

The purpose of the conducted researches is increase in efficiency of functioning medical - offices. It will allow to reach minimization of idle time of the equipment and waiting time of service that as a result will lead to increase in number of the served clients.

To achieve this goal, it is necessary to solve the following tasks, which will be performed in the sections of master's work:

  1. To explore existing methods and algorithms of formation of schedules.
  2. To perform the formalization of the problem of the optimal schedule using a modified genetic algorithm.
  3. To create the software for the formation of the optimal schedule for the treatment and health procedures on the basis of the developed algorithm.

Research object: methods of the scheduling theory.

Research subject: compilation of the optimal schedule using a modified genetic algorithm.

3. Mathematical formulation of the problem

For realization of this task, it is necessary to create an optimal schedule with consideration of several limitations:

  1. By the time of provision procedures: Tф ≤ Tпр,
    where Tпр - time of stay of the patient piin the sanatorium;
    Tф - actual time of procedures procj of the patient pi.
  2. By the number of procedures: Nпл = Nф,
    where Nпл - number of planned procedures procj;
    Тф - the actual number of procedures performed procj.
  3. By the time of continuous operation of equipment: Nпр * Tпр ≤ Tнпр,
    where Nпр - number of procedures performed procj for the whole day, on equipment eqz;
    Tпр - time (duration) of the procedure procj;
    Tнпр - time of continuous operation of equipment eqz.
  4. By the number of procedures in a day: Nд ≤ Nдоп,
    где Nд - the number of the procedures appointed to the patient pi in a day;
    Nдоп - the admissible number of procedures in a day for the patient pi.
  5. By equipment downtime: 0 ≤ ΔTожид об ≤ Tпрост,
    ΔTожид об - the difference in time between the end of the procedure procj and the beginning of the following procedure on this equipment eqz;
    Tпрост - allowable downtime of equipment eqz.
  6. By the time difference between the procedures: 0 ≤ ΔTожид п ≤ Tсв,
    ΔTожид п - the difference in time between the end of the procedure procj and the beginning of the next, assigned to the patient pi;
    Tсв - free time between procedures pi.

The objective function for this task is the sum of the values of the quality loss criteria K for all assigned procedures to the patient pi. It is required to find a solution that minimizes the value of the objective function:

Objective function

where K p is the value of the quality loss criterion for one of the prescribed procedures to the patient. In this case, K p is calculated by the formula:

Quality Loss Criterion Formula

where koefq - value of the penalty coefficient for non-fulfillment of the q-th partial criterion, ci - estimate determining the degree of non-fulfillment of the q-th private criterion, eqz - equipment, tk - time interval. [1]

Thus, the problem is reduced to developing an algorithm that satisfies all previously described conditions and constraints.

4. Method of solution

The genetic algorithm is a heuristic search algorithm by sequential selection, combination and variation of the desired parameters using mechanisms that resemble biological evolution [2].

The solution of the problem based on GA can be submitted the following sequence of actions:

  1. Installation of parameters of evolution. Initialization of initial population for one patient. The individual is presented in the form of two chromosomes where information of the 1st - the equipment, and the 2nd – sessions (periods) [3].
    2. Structure of individual

    Picture 1 – Structure of individual

  2. Assessment of the individuals entering population, selection of the most adapted individuals (selection) having more preferable values of function of suitability in comparison with other individuals.
  3. Create children of the selected pairs of parents – perform the crossover operator.
  4. Mutation of new individuals.
  5. Checking the values of the conflict function [3].
  6. Expansion of population by the new generated individuals.
  7. Convergence is detected or the maximum number of iterations is reached.
  8. The resultant individual needs to be checked for existence.

Conclusion

At this stage of the master's work was made an analysis of the process of forming the schedule for the passing of health-related procedures on the basis of the dynamic model. A mathematical formulation of the problem is formulated. Also, the main algorithms for scheduling were analyzed: ant and genetic.

The genetic algorithm is more flexible in the process of finding a solution, because it uses several points of the search space, and does not go from point to point. To solve this problem, it is suggested to use a modified genetic algorithm that will allow to obtain optimal solutions taking into account the peculiarities of medical-improving establishments [4].

In the future, it is assumed the program realization of the developed modified genetic algorithm and finding of effective parameters for reduction of time expenditure for search of an optimal solution is supposed.

Work is not completed yet. Completion is scheduled for May 2018. The full text and materials on the topic can be obtained from a student or his supervisor only after the specified date.

References

  1. Ю.С. Кабальнов Композиционный генетический алгоритм составления расписания учебных занятий /Ю.С. Кабальнов, Л.И. Шехтман, Г.Ф. Низамова, Н.А. Земченкова // Вестник УГАТУ / Научные статьи и доклады / Информационные технологии - Уфа: УГАТУ, 2006 г. - Том 7, № 2 (15). - с. 99–107.
  2. А.Б. Сидорин Методы автоматизации составления расписания занятий Часть 2. Эвристические методы оптимизации / А.Б. Сидорин, Л.В. Ликучева, А. М. Дворянкин // Известия ВолгГТУ / Актуальные проблемы управления, вычислительной техники и информатики в технических системах - Волгоград, 2009г. - № 12 (60) с. 120-123.
  3. И.Ф. Астахова Составление расписания учебных занятий на основе генетического алгоритма /И.Ф. Астахова, А.М. Фирас //Вестник ВГУ / Системный анализ и информационные технологии – Воронеж: ВГУ, 2013г., - № 2, с. 93-99.
  4. А.А. Лазарев Теория расписаний. Задачи и алгоритмы /А.А. Лазарев, Е.Р. Гафаров - М.: Московский государственный университет им. М.В. Ломоносова (МГУ), 2011. — 222 с.
  5. Е.Г. Задорожная Метаэвристические алгоритмы формирования оптимального графика прохождения лечебно-оздоровительных процедур / Е.Г. Задорожная, Е.О. Савкова //Информатика, управляющие системы, математическое и компьютерное моделирование (ИУСМКМ – 2017) / Материалы VIII международной научно-технической конференции - Донецк: ДонНТУ, 2017г. - с. 270-275.