Українська  English
   

Реферат по теме выпускной работы

Содержание

Введение

Эффективность функционирования предприятия или организации любой отрасли и сферы деятельности напрямую зависит от скорости, точности и своевременности обмена данными, как внутри этого предприятия, так и вне его. Поэтому наиболее важной является проблема организации и контроля большого объема информации.

Внедрение КСУ позволяет систематизировать обмен данными, регламентировать состав и формы представления данных, а также структуру информационных потоков в системе, значительно повысить точность и четкость их ведения, гарантировать их сохранность, предоставлять полную взаимоувязанную информацию по всем субъектам санатория. Все это приводит к слаженной работе сотрудников организации и во много раз увеличивает эффективность функционирования предприятия в целом.

В рамках данной работы рассматривается формирование графиков прохождения лечебно-оздоровительных процедур, оптимальность составления которых сказывается на качестве работы санаторно-курортного комплекса. Качественно составленное расписание должно обеспечить равномерную нагрузку процедурных кабинетов и оборудования, а также комфортную работу медперсонала и гибкий график для пациентов.

1. Актуальность темы

График прохождения лечебно-оздоровительных процедур должен учитывать большое количество ограничений, связанных с предметной областью. В первую очередь должны быть соблюдены нормы диагностических и лечебно-реабилитационных услуг (процедур). Необходимо придерживаться последовательности проведения процедур, назначенных врачом, а также правильно распределять нагрузку на оборудование. Из-за множества ограничений и специфических особенностей, не характерных другим отраслям, составление расписание прохождения лечебно-оздоровительных процедур вручную является очень трудоемкой и затратной по времени работой. А автоматизация данной задачи позволит добиться более оптимального решения.

Существуют различные классические методы решения задачи составления расписания. Однако, из-за большой размерности задачи, добиться оптимального расписания данными способами довольно проблематично. В последние годы особое распространение получили исследования методов эволюционного поиска. Их применение приводит к получению хороших результатов, однако имеет место высокая вычислительная трудоёмкость и относительная неэффективность на заключительных этапах эволюции.

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

2. Цель и задачи исследования

Целью проводимых исследований является повышение эффективности функционирования лечебного-отделения. Это позволит достигнуть минимизации времени простоя оборудования и времени ожидания обслуживания, что в результате приведёт к увеличению количества обслуживаемых клиентов.

Для достижения поставленной цели необходимо решить следующие задачи, которые будут выполнены в разделах магистерской работы:

  1. Исследовать существующие методы и алгоритмы формирования расписаний.
  2. Выполнить формализацию задачи формирования оптимального графика с применением модифицированного генетического алгоритма.
  3. Создать программное обеспечение формирования оптимального графика прохождения процедур на основе разработанного алгоритма.

Объект исследования: методы теории расписаний.

Предмет исследования: составление оптимального расписания с применением модифицированного генетического алгоритма.

3. Научная новизна и практическая ценность

Сформулирована математическая постановка задачи формирования оптимального графика лечебно-оздоровительных процедур, с учетом всех ограничений, связанных со спецификой задачи.

Разработана динамическая модель процесса прохождения лечебно-оздоровительных процедур, представленная в виде сети Петри [1].

Предложен модифицированный генетический алгоритм, отличительной особенностью которого является представление особи, состоящей из двух хромосом (в дальнейшем возможно представление в виде трех хромосом, в случае усложнения задачи и учета мед персонала процедурных кабинетов), со специальными операторами скрещивания и мутации [2].

4. Математическая постановка задачи

Для формирования графика прохождения лечебно-оздоровительных процедур необходимо иметь определённый набор входных данных. Санаторно-курортный комплекс рассчитан на определённое количество пациентов, представленное множеством P = {pi}, где i ∈ [1, n]. Лечащий врач пациента, в соответствии с его диагнозом, назначает перечень обязательных процедур, исходя из множества всех возможных: Proc = {procj}, где j ∈ [1, m], а также периодичность сеансов и их количество. Пациент также имеет право на посещение дополнительных процедур общего назначения, согласовав это с лечащим врачом.

Процедурные кабинеты работают по графику и имеют определенное количество оборудования, представленное множеством Eq = {eqz}, где z ∈ [1, f]. При этом каждое оборудование предназначено для определённой процедуры или вида процедур. Поэтому оборудование eqz(eqznum, eqztype) характеризуется номером eqznum и типом проводимых процедур eqztype. Проведение каждой процедуры занимает какой-то промежуток времени. Соответственно, предполагается множество временных интервалов T = {tk}, где k ∈ [1, h]. Каждый временной интервал характеризуется двумя параметрами tk(tkdate, tktime), где tkdate – дата проведения лечебно-оздоровительной процедуры (номер дня), tktime – время (номер временного интервала в течении дня) [3].

Исходя из изложенной ранее информации, можно сделать вывод, что проведение процедуры procj для пациента pi характеризуется оборудованием eqz, на котором будет предоставлена процедура, а также временным интервалом tk.

Для реализации поставленной задачи необходимо составить оптимальный график (расписание) с учетом ряда ограничений:

  1. По срокам предоставления процедур: Tф ≤ Tпр,
    где Tпр - время пребывания пациента pi в санатории;
    Tф - фактическое время проведения процедур procj пациенту pi.
  2. По количеству проведения процедур : Nпл = Nф,
    где Nпл - количество запланированных процедур procj;
    Тф - фактическое количество проведенных процедур procj.
  3. По времени непрерывной работы оборудования: Nпр * Tпр ≤ Tнр,
    где Nпр - количество проведенных процедур procj за день, на оборудовании eqz;
    Tпр - время проведения (длительность) процедуры procj;
    Tнр - время непрерывной работы оборудования eqz.
  4. По количеству процедур за день: Nд ≤ Nдоп,
    где Nд - количество процедур, назначенных пациенту pi за день;
    Nдоп - допустимое количество процедур за день для пациента pi.
  5. По времени простоя оборудования: 0 ≤ ΔTожид об ≤ Tпрост,
    ΔTожид об - разница во времени между окончанием процедуры procj и началом следующей на оборудовании eqz;
    Tпрост - допустимое время простоя оборудования eqz.
  6. По временному разбросу между процедурами: 0 ≤ ΔTожид п ≤ Tсв,
    ΔTожид п - разница во времени между окончанием процедуры процедуры procj и началом следующей, назначенной пациенту pi;
    Tсв - свободное время между процедурами pi.

Математическое выражение другой группы ограничений, которые также влияют на алгоритм составления расписания:

  1. Отсутствие накладок на работу оборудования: ∀ (eqz, tk) ∃! (pi, procj),
    означает, что для каждой упорядоченной двойки элементов оборудование и временной промежуток существует либо единственная двойка пациент и процедура, что означает проведение процедуры procj для пациента pi на оборудовании eqz во время интервала времени tk, либо отсутствие назначения.
  2. Соответствие типа оборудования проводимой процедуре: ∀(pi, procj) ∃ eqz, where procjtype ∈ eqztype,
    означает, что для каждого назначения процедуры procj пациенту pi нужно выбирать такое оборудование, чтобы тип процедуры procjtype соответствовал типу процедур, проводимых на данном оборудовании eqztype.

Для того, чтобы фиксировать свободные интервалы времени работы оборудования, необходима матрица занятости, которая формируется таким образом:

Матрица занятости оборудования

Целевой функцией для данной задачи является сумма значений критериев потери качества К для всех назначенных процедур пациенту pi. Требуется найти такое решение, которое минимизирует значение целевой функции:

Целевая функция

где Kp – значение критерия потери качества для одной из назначенных процедур пациенту. При этом Kp вычисляется по формуле:

Формула критерия потери качества

где koefq - значение коэффициента штрафа за невыполнение q-го частного критерия, ci - оценка, определяющая степень невыполнения q-го частного критерия, eqz - оборудование, tk - временной интервал.

Таким образом, задача сводится к тому, чтобы разработать алгоритм, который удовлетворяет всем сформулированным ранее условиям и ограничениям [3].

5. Динамическая модель процесса

Для построения динамической модели процесса прохождения лечебно-оздоровительных процедур была выбрана сеть Петри. Это математический аппарат для моделирования динамических дискретных систем. Процесс функционирования сети Петри может быть наглядно представлен графом достижимых маркировок. Они позволяют определить общую структуру и принципы работы системы. Сети-Петри рассматриваются как вспомогательный инструмент анализа систем. Проблемы анализа указывают на изъяны в проекте [1].

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

Динамическая модель процесса

Рисунок 1 – Динамическая модель процесса

В рамках решаемой проблемы сети Петри являются удобным инструментом, для создания высокоуровневой модели работы процесса. На рис. 1 представлена динамическая модель процесса прохождения лечебно-оздоровительных процедур в виде сети Петри второго рода, с иерархической композицией объектов. Имея информацию о назначенной процедуре необходимо понимать, на каком типе оборудования её можно проводить (выбор кабинета). Далее следует выбрать свободное оборудование в данный момент времени. Для наглядности оборудование отмечено в виде закрашенного круга. Это связано с тем, что оборудованием в данный момент времени может пользоваться лишь один клиент. После предоставления процедуры клиенту, он возвращается к моменту выбора кабинета, для следующей процедуры. Это будет длится до тех пор, пока перечень процедур не закончится. В случае, если нет свободного оборудования, клиент дожидается его освобождения.

6. Анализ методов решения

Существуют следующие методы решения задачи календарного планирования: математическое программирование, комбинаторные методы, статистические методы и эвристические методы (рис. 2).

Методы календарного планирования

Рисунок 2 – Методы календарного планирования

Анализ приведенных методов показал, что сложность использования как комбинаторного метода, так и метода динамического программирования связана с экспоненциальным ростом длительности вычислений от размерности задачи. К тому же в задачах календарного планирования на каждом шаге планирования изменяется система ограничений, что затрудняет применение симплекс-метода, как части метода ветвей и границ. Для использования имитационного моделирования необходим большой объем статистических данных, доступ к которым на предприятии обычно затруднен [4].

Основой для разработки соответствующего заданным требованиям алгоритма формирования графика прохождения лечебно-оздоровительных процедур могут стать метаэвристики, которые хорошо себя показали при решении оптимизационных, комбинаторных, а также других видов задач. Алгоритм метаэвристик основан на случайном поиске возможных решений задачи, оптимальных или близких к оптимальным, пока не будет выполнено некое условие или достигнуто заданное число итераций. [5]

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

Муравьиный алгоритм - алгоритм для нахождения приближённых решений задачи коммивояжёра, а также решения аналогичных задач поиска маршрутов на графах [6].

В виде муравья в данном случае можно рассматривать пациента, тогда вершинами графа будет выступать оборудование. Каждая вершина содержит информацию о процедурах, которые могут проводиться на данном типе оборудования, и массив промежутков времени. В основе муравьиного алгоритма лежит поведение муравьиной колонии – маркировка более удачных путей большим количеством феромона. Когда муравей находит подходящее назначенной процедуре оборудование, то занимает интервал времени на её проведение. Затем, он возвращается в начало, оставляя за собой след из феромона.

Генетический алгоритм - это эвристический алгоритм поиска путём последовательного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию [7].

Решение задачи на основе ГА можно представить следующей последовательностью действий:

  1. Установка параметров эволюции. Инициализация начальной популяции для одного пациента. Особь представлена в виде двух хромосом, где информация 1-ой - оборудование, а 2-ой – сеансы (промежутки времени) [3].
    В предлагаемом генетическом алгоритме не требуется кодирования генов хромосом в виде нулей и единиц, как это принято в существующих генетических алгоритмах. Гены принимают целочисленные значения, которые кодируют номера оборудования, временные интервалы.
    В обеих хромосомах одинаковое количество генов равное pi, равное количеству назначенных процедур пациенту. Следовательно, i гену 1-ой хромосомы соответствует оборудование (из числа допустимых), выбранное для предоставления процедуры, а i гену 2-ой хромосомы - время её проведения (рис. 3).
    2. Структура особи

    Рисунок 3 – Структура особи

  2. Оценка особей, входящих в популяцию, отбор наиболее приспособленных особей (селекция), имеющих более предпочтительные значения функции пригодности по сравнению с остальными особями.
    Оператор отбора является важнейшим фактором, влияющим на эффективность генетического алгоритма, поскольку неудачный выбор метода селекции может привести к сужению области поиска и к потере наиболее приспособленных особей популяции. Для предотвращения потери лучших особей в качестве метода отбора предлагается использовать метод, турнирного отбора, дополненный принципом элитизма. Из предыдущей популяции выбирается L отдельных особей (число L определено изначально, и имеет фиксированное числовое значение), имеющих максимальное значение функции пригодности (функцией пригодности в данном случае является целевая функция (10), описанная в математической постановке задачи) [8].
  3. Создание потомков выбранных пар родителей – выполнение оператор кроссинговера. Для каждой пары отобранных особей случайным образом выбираются позиции гена G1 и G2 и производится обмен участками генетического кода между соответствующими хромосомами родительских особей. Если такие гены уже встречаются в потомке, то они пропускаются, а оставшуюся часть потомка дополняют генами первого родителя [3].
    4. Выполнение оператора кроссинговера

    Анимация – Выполнение оператора кроссинговера
    (анимация: 4 кадра, 150 килобайт)

  4. Мутация новых особей. Мутация играет достаточно важную роль в работе генетического алгоритма: вносит дополнительное разнообразие в текущую популяцию и тем самым расширяет пространство поиска оптимального решения. В результате мутации n-му 1-ой хромосомы будет присвоен z-ый номер оборудования, из допустимого набора оборудований, предназначенных для проведения данной процедуры, а для n-го гена 2-ой хромосомы будет выбрано k-e свободное значение временного интервала для данного оборудования [8].
  5. Проверка значений функции конфликтов. Если этот ген не равен нулю, значит в хромосоме или одинаковым временным интервалам соответствуют разные процедуры, или одному оборудованию соответствует разные процедуры, такое расписание содержит конфликт, который обязательно должен быть разрешен. В том случае следует заменить номер оборудования или временного интервала.
    Ген «конфликтов» позволяет сократить время проведения вычислительного эксперимента на порядок, то есть он ускоряет процесс сходимости алгоритма и получения оптимального решения [8].
  6. Расширение популяции новыми порожденными особями. Оператор отбора выполняет функции фильтрующего инструмента, который выделяет в составе популяции особи, имеющие низкое значение функции пригодности. Выделенные найденные слабые особи удаляются из популяции, происходит сокращение расширенной популяции до исходного размера.
  7. Обнаружена сходимость или достигнуто максимальное количество итераций. Если критерий останова алгоритма выполнен, то выбор лучшей особи в конечной популяции – результат работы алгоритма. Иначе переход на шаг 2 [3].
  8. Результирующую особь необходимо проверить на существование. Последовательность прохождения процедур проверяем на ранее разработанной динамической модели. Для хранения информации о загрузке оборудования необходимо занести информацию о новых назначениях в матрицу занятости.

Выводы

На данном этапе выполнения магистерской работы был проведён анализ процесса формирования графика прохождения лечебно-оздоровительных процедур на основе динамической модели. Сформулирована математическая постановка поставленной задачи. Также, были проанализированы основные алгоритмы составления расписаний: муравьиный и генетический.

Муравьиный алгоритмы, не смотря на свою динамичность, использование памяти колоний и сходимости к оптимальному решению имеет ряд недостатков. Графовое представление данной задачи не является оптимальным. Результаты работы методы сильно зависят от начальных параметров поиска. [9]

Генетический алгоритм является более гибким в процессе поиска решения, поскольку использует несколько точек поискового пространства, а не переходит от точки к точке. Для решения поставленной задачи предложено использовать модифицированный генетический алгоритм, который позволит получать оптимальные решения с учетом особенностей лечебно-оздоровительных учреждений. [10]

В дальнейшем, предполагается программная реализация разрабатываемого модифицированного генетического алгоритма и нахождение эффективных параметров для уменьшения временных затрат для поиска оптимального решения.

На момент написания данного реферата магистерская работа еще не завершена. Окончательное завершение: май 2018 года. Полный текст работы и материалы по теме могут быть получены у автора или его руководителя после указанной даты.

Список источников

  1. Tadao Murata Petri Nets: Properties, Analysis and Applications // Department of Electrical Engineering and Computer Science, University of Illinois, Chicago, IL 60680, USA.
  2. Branimir Sigl Solving Timetable Scheduling Problem by Using Genetic Algorithms / Branimir Sigl, Marin Golub, Vedran Mornar // Faculty of Electrical Engineering and Computing, University of Zagreb Unska 3, Zagreb, Croatia.
  3. Ю.С. Кабальнов Композиционный генетический алгоритм составления расписания учебных занятий /Ю.С. Кабальнов, Л.И. Шехтман, Г.Ф. Низамова, Н.А. Земченкова // Вестник УГАТУ / Научные статьи и доклады / Информационные технологии - Уфа: УГАТУ, 2006 г. - Том 7, № 2 (15). - с. 99–107.
  4. К.С. Мышенков Метод решения задачи календарного планирования ремонтов технологического оборудования предприятия с использованием генетического алгоритма / К.С. Мышенков, А.Ю. Романов // Наука и образование / Электронное научно-техническое издание - Москва: ФГБОУ ВПО "МГТУ им. Н.Э. Баумана", 2011г.
  5. А.С. Аничкин Современные модели и методы теории расписаний / А. С. Аничкин, В. А. Семенов // Труды Института системного программирования РАН - Москва,2014 г. - Том 26, выпуск 3.
  6. В.А. Светличная Использование алгоритмов муравьиных колоний при решении задач оптимизации календарного планирования / Светличная В.А., Червинская Н.В., Хаустова Д.А. // ДонНТУ, г. Донецк.
  7. А.Б. Сидорин Методы автоматизации составления расписания занятий Часть 2. Эвристические методы оптимизации / А.Б. Сидорин, Л.В. Ликучева, А. М. Дворянкин // Известия ВолгГТУ / Актуальные проблемы управления, вычислительной техники и информатики в технических системах - Волгоград, 2009г. - № 12 (60) с. 120-123.
  8. И.Ф. Астахова Составление расписания учебных занятий на основе генетического алгоритма /И.Ф. Астахова, А.М. Фирас //Вестник ВГУ / Системный анализ и информационные технологии – Воронеж: ВГУ, 2013г., - № 2, с. 93-99.
  9. Т.В. Панченко Генетические алгоритмы: Учебно-методическое пособие / под ред. Ю.Ю. Тарасевича. - Астрахань: АГУ, 2007. - 87 с.
  10. А.А. Лазарев Теория расписаний. Задачи и алгоритмы /А.А. Лазарев, Е.Р. Гафаров - М.: Московский государственный университет им. М.В. Ломоносова (МГУ), 2011. — 222 с.
  11. Е.Г. Задорожная Метаэвристические алгоритмы формирования оптимального графика прохождения лечебно-оздоровительных процедур / Е.Г. Задорожная, Е.О. Савкова //Информатика, управляющие системы, математическое и компьютерное моделирование (ИУСМКМ – 2017) / Материалы VIII международной научно-технической конференции - Донецк: ДонНТУ, 2017г. - с. 270-275.