Содержание к диссертации
Введение
Глава 1. Постановка задачи составления рабочих графиков в аудиторской организации 11
1.1. Данные, используемые при планировании работы аудиторской организации 11
1.2. Требования, предъявляемые к рабочим графикам в аудиторской организации 17
1.3. Формальная постановка задачи составления рабочих графиков в аудиторской, организации 18
1.4. Выводы по главе 1 26
Глава 2. Обзор методов, применяемых для решения задач теории расписаний 27
2.1. Общая характеристика задач теории расписаний 27
2.1.1. Задачи составления машинных расписаний 27
2.1.2. Задача составления расписания занятий 28
2.1.3. Задача составления расписания работы персонала 29
2.1.4. Задача RCPSP 30
2.2. Методы решения задач теории расписаний 32
2.2.1. Простые эвристические алгоритмы 32
2.2.2. Генетические алгоритмы 33
2.2.3. Общая характеристика методов локального поиска 34
2.2.4. Локальный спуск 35
2.2.5. Алгоритм поиска с запретами 35
2.2.6. Метод моделирования отжига 37
2.3. О сетевых методах планирования... 38
2.4. Выводы по главе 2 41
Глава 3. Использование методов локального поиска для решения задачи составления рабочих графиков в аудиторской организации 42
3.1. Определение окрестности текущего решения 42
3.1.1. Отношение соседства на множестве рабочих графиков 42
3.1.2. Вычисление допустимого интервала проведения операции 43
3.1.3. Сокращение просматриваемой окрестности 45
3.2. Уменьшение временных затрат на вычисление значения целевой функции 47
3.3. Получение начальной точки работы алгоритма 48
3.4. Алгоритм локального спуска 48
3.5. Алгоритм поиска с запретами 49
3.6. Практические испытания алгоритма 52
3.6.1. Размерность тестовых задач 52
3.6.2. Значения параметров алгоритма 53
3.6.3. Результаты 53
3.7. Выводы по главе 3 56
Глава 4. Оценка эффективности алгоритма 57
4.1. Актуальность задачи оценки эффективности эвристических алгоритмов 57
4.2. Разработка равновероятного генератора индивидуальных задач составления рабочих графиков в аудиторской организации 59
4.2.1. Определение подмножества индивидуальных задач для генерации59
4.2.2. Процедура генерации периодов недоступности сотрудников 61
4.2.3. Процедура равновероятной генерации целочисленных векторов фиксированной длины при наличии ограничения на сумму компонент генерируемого вектора 65
4.2.4. Процедура генерации множества операций и времен исполнения операций 71
4.2.5. Процедура генерации сроков выполнения работ 74
4.2.6. Процедура равновероятной генерации индивидуальных задач составления рабочих графиков в аудиторской организации 76
4.3. Оценка эффективности работы алгоритма 76
4.4. Выводы по главе 4 78
Глава 5. Программная реализация алгоритма решения задачи ASP. Численные эксперименты 79
5.1. Комплекс программ «Аудит-S» 79
5.2. Технические характеристики и условия использования 79
5.3. Программа «Планировщик работы аудиторской организации» 81
5.4. Программа «Tester» 82
5.5. Результаты тестирования 83
5.6. Выводы по главе 5 86
Заключение 87
Список литературы 89
- Данные, используемые при планировании работы аудиторской организации
- Задача составления расписания работы персонала
- Вычисление допустимого интервала проведения операции
- Актуальность задачи оценки эффективности эвристических алгоритмов
- Технические характеристики и условия использования
Введение к работе
Актуальность задачи автоматизации планирования работы аудиторской организации
Сущность аудиторской проверки заключается в независимой экспертизе и анализе бухгалтерского учета и финансовой отчетности проверяемого предприятия с целью определения ее достоверности и соответствия текущему законодательству. Аудит предприятий и индивидуальных предпринимателей производится в соответствии с Федеральным Законом «Об аудиторской деятельности», и принятыми в соответствии с ним другими нормативно-правовыми актами, регулирующими отношения, возникающие при осуществлении аудиторской деятельности.
В диссертационной работе рассматривается задача составления рабочих графиков в аудиторской организации.
При наличии большого количества проверяемых предприятий в условиях ограниченности штата аудиторской организации возникает актуальная задача повышения эффективности использования персонала. Одним из способов решения этой задачи может быть использование рационально составленных рабочих графиков работы аудиторов. Однако, составление такого графика само по себе представляет трудную задачу в силу большого количество операций и сложных связей между различными операциями.
В этих условиях встает вопрос о разработке эффективных средств автоматизации процесса планирования работы аудиторской организации, завершающегося составлением графиков работы персонала. В условиях отсутствия известных методов решения данной задачи, работающих за полиномиальное время, целесообразным представляется разработка эвристического алгоритма, предназначенного для решения данной задачи.
Цель работы
Целью диссертационной работы является разработка эффективных эвристических алгоритмов для решения одной из труднорешаемых задач теории расписаний - задачи составления рабочих графиков в аудиторской организации. Для этого необходимо поставить и решить следующие задачи:
разработать математическую модель задачи составления рабочих графиков в аудиторской организации;
разработать алгоритм решения задачи составления рабочих графиков в аудиторской организации;
разработать методику оценки эффективности предложенного алгоритма;
разработать программное обеспечение, реализующее предложенный алгоритм;
исследовать эффективность разработанного алгоритма при помощи численного эксперимента.
На защиту выносятся
Математическая модель задачи составления рабочих графиков в аудиторской организации.
Эвристический алгоритм, предназначенный для решения задачи составления рабочих графиков в аудиторской организации, основанный на метаэвристике поиска с запретами.
Процедура равновероятной генерации индивидуальных задач составления рабочих графиков в аудиторской организации, используемая для проведения статистического исследования эффективности работы алгоритма.
Комплекс программ, предназначенный для решения рассматриваемой задачи и оценки эффективности предложенного алгоритма.
Результаты вычислительного эксперимента, демонстрирующие эффективность предложенного подхода (доля задач, имеющих размерность, близкую к встречающимся на практике, для которых были найдены допустимые решения, составила 94,25%).
Научная новизна
Математическая модель задачи составления рабочих графиков в аудиторской организации отличается от существующих моделей задач планирования работы персонала учетом ограничений, специфических для организаций, занимающихся аудиторской деятельностью: введением дополнительных ограничений на сроки сдачи аудиторского заключения и отчета, разбивкой сотрудников на группы по уровню квалификации, а также особым видом целевой функции.
Для разработанного эвристического алгоритма, основывающегося на методе поиска с запретами, предложен способ сокращения просматриваемой окрестности, не приводящий к потере допустимых решений.
Разработана процедура равновероятной генерации индивидуальных задач составления рабочих графиков в аудиторской организации, гарантирующая одинаковую вероятность появления каждой индивидуальной задачи из некоторой области, заданной рядом параметров, основывающаяся на результатах решения следующих подзадач:
разработке процедуры равновероятной генерации бинарных векторов фиксированной длины;
разработке процедуры равновероятной генерации целочисленных векторов, удовлетворяющих ряду ограничений.
Практическая ценность
Полученные в диссертационной работе результаты позволяют эффективно решать задачи, возникающие при планировании работы аудиторских организаций. Проведенные численные эксперименты, показали высокую эффективность работы алгоритма при решении задач, размерность которых близка к размерностям задач, встречающимся на практике.
Следует отметить, что предложенные в работе подходы к решению поставленной задачи могут быть использованы при решении широкого класса задач, возникающих при управлении персоналом.
Программная реализация разработанного в рамках выполнения работы алгоритма составления рабочих графиков в аудиторской организации используется в ООО «Аудиторская фирма «Прогресс-Сервис», г. Уфа.
Апробация работы
Основные результаты докладывались на:
III Всероссийской научно-практической конференции «Информационные технологии и математическое моделирование» (Анжеро-Судженск, 2004).
VII международной конференции «Computer Science and Information Technologies» (Уфа, 2005).
Ill Международной научно-практической конференции «Управление в социальных и экономических системах» (Пенза, 2005).
Международной научно-практической конференции «Информационно-вычислительные технологии и их приложения» (Пенза, 2005).
Зимней школе аспирантов и молодых ученых (Уфа, 2006).
Научных семинарах «Модели искусственного интеллекта» кафедры ВМиК УГАТУ (Уфа, 2003-2006).
По теме диссертации опубликовано 15 работ, в том числе 1 статья в рецензируемом журнале из списка ВАК и 2 программы для ЭВМ.
Структура и объем работы
Данные, используемые при планировании работы аудиторской организации
Сущность аудиторской проверки заключается в независимой экспертизе и анализе бухгалтерского учета и финансовой отчетности проверяемого предприятия с целью определения ее достоверности и соответствия текущему законодательству. Аудит предприятий и индивидуальных предпринимателей производится в соответствии с Федеральным Законом «Об аудиторской деятельности» [1], и принятыми в соответствии с ним другими нормативно-правовыми актами, регулирующими отношения, возникающие при осуществлении аудиторской деятельности [2, 3].
Аудиторские организации при выполнении своих обязанностей руководствуются федеральными правилами (стандартами) аудиторской деятельности, которые утверждаются Правительством Российской Федерации и другими компетентными органами, кроме того, аудиторские организации вправе принимать собственные стандарты аудиторской деятельности, при условии их соответствия федеральным стандартам [2], [3]. В соответствии с федеральными правилами аудиторской деятельности, итогом аудиторской проверки является составление аудиторского заключения - официального документа, содержащего выраженное в установленной законодательством форме мнение аудиторской организации или индивидуального аудитора о достоверности финансовой отчетности и бухгалтерского учета проверяемого предприятия. Составлению аудиторского заключения сопутствует подготовка отчета по результатам аудиторской проверки.
В процессе работы аудиторская организация заключает договоры на осуществление аудиторской проверки предприятий, в дальнейшем такие договоры будем называть работами. Процесс проверки предприятия - это сложный процесс, который состоит из множества операций, связанных с проверкой различных видов отчетности. Количество операций, их сложность и продолжительность выполнения могут в значительной степени варьироваться в зависимости от специфики проверяемого предприятия [4, 5,6].
В каждой работе в обязательном порядке присутствуют две операции: «Составление аудиторского заключения» и «Подготовка отчета». В договоре на осуществление аудиторской проверки предприятия для этих операций устанавливаются сроки, до наступления которых они должны быть выполнены (обычно срок сдачи аудиторского заключения предшествует сроку сдачи отчета), кроме того, договор определяет и срок, ранее которого нельзя начинать выполнение данной работы - время начала работы.
Задача составления расписания работы персонала
Задачи составления расписания работы персонала (ЕТР - Employee Timetabling Problem) состоит в распределении сотрудников организации по рабочим сменам и может быть описана следующим образом [42, 44, 45, 47].
Для каждой смены определено время начала и окончания, а также набор работ (ролей), которые должны выполнять сотрудники, работающие в данную смену, в общем случае периоды, приходящиеся на разные смены, могут накладываться друг на друга. Также задан список сотрудников, для каждого из которых определен его тип и набор ролей, которые он может выполнять.
Задача состоит в назначении для каждой одного или нескольких сотрудников таким образом, чтобы выполнялись следующие требования:
- на каждую смену было назначено достаточное количество сотрудников нужного типа, чтобы выполнить все работы, назначенные на данную смену;
- каждый сотрудник в любой момент времени был назначен не более чем на одну смену;
- для каждого сотрудника выделялся период для отдыха между сменами достаточно продолжительности;
- каждый сотрудник был задействован не более определенного количества часов в неделю.
Постановка задачи может значительно изменяться в зависимости от специфики организации, что обычно выражаться в добавлении новых требований, которым должны удовлетворят расписания работы персонала.
Вычисление допустимого интервала проведения операции
Для каждой работы Jk (к=1,..п) задаются срок Тк , ранее которого нельзя приступать к выполнению любой операции данной работы, и сроки Г/ и Т к , к которым должны быть выполнены операции «подготовка аудиторского заключения» 0\ и «подготовка отчета» 0[ соответственно.
Очевидно, что для получения допустимого расписания начало выполнения любой операции работы Jk должно начинаться не раньше, чем Тк , и заканчиваться, не позднее, чем тах( Тк, Тк ).
Однако в виду того, что между операциями задано отношение предшествования, для многих операций этот интервал можно сократить.
Например, если работа Jk должна начаться не ранее периода рю, а операция 0 к предшествует операции 0}к, причем операция 0 к может быть выполнена аудитором за 4 часа или помощником аудитора за 8 часов, то очевидно, что для получения допустимого рабочего графика необходимо, чтобы B(Olk, S) 14.
Аналогично, если для работы Jk max(Tk ,Тк) pm, и операция 0 к предшествует операции 0[, причем операция 0{ может быть выполнена аудитором за 16 часов или помощником аудитора за 20 часов, а операция 0[ может быть выполнена аудитором за 6 часов, то необходимым условием для получения допустимого рабочего графика является В(0 к , ) 78.
Учитывая, что каждой операции может предшествовать несколько других операций, а работа может быть представлена в виде связанного ациклического орграфа, можно определить следующую процедуру расчета минимального и максимального времени начала выполнения операций, относящихся к работе Jk.
Актуальность задачи оценки эффективности эвристических алгоритмов
Как отмечалось в разделе 3.6, использование разработанного алгоритма на наборах данных, взятых их реальной аудиторской организации, позволило построить рабочие графики, характеристики которых оказались достаточно хорошими для возможности их практического использования. Более того, на одном из тестовых наборов удалось получить рабочий график, значительно превосходящий график, составленный вручную. Таким образом, эффективность алгоритма представляется достаточно высокой.
Вместе с тем, объем проведенных испытаний не позволяет судить о применимости алгоритма для решения широкого круга задач: так как данный алгоритм является эвристическим, то его использование не может гарантировать отыскание не только оптимального, но даже допустимого решения. Однако широкое использование эвристических алгоритмов во всех отраслях человеческой деятельности показывает, что во многих случаях они позволяют найти достаточно близкие к оптимуму решения. Таким образом, возникает проблема оценки эффективности предложенного алгоритма решения задачи ASP.
Для некоторых задач и алгоритмов удается аналитическим путем рассчитать различные характеристики, позволяющие точно судить об эффективности алгоритма, например, максимальное отклонение решения, полученного алгоритмом, от оптимального решения. Однако для большинства задач, встречающихся на практике, этого сделать не удается ввиду их высокой сложности.
Другим способом оценки эффективности эвристического алгоритма может быть проведение статистического тестирования алгоритма на выборке индивидуальных задач решаемой массовой задачи, и использование результатов такого тестирования для вычисления оценок, характеризующих эффективность алгоритма. При использовании такого подхода одной из ключевых проблем является состав тестовой выборки индивидуальных задач.
Во-первых, само получение достаточного количества задач представляет собой трудную задачу: например, в случае рассматриваемой задачи ASP, в пределах одной аудиторской организации, каждая новая индивидуальная задача возникает один раз в год. Таким образом, создание тестовой выборки достаточного объема на основе реальных данных представляется весьма проблематичным, а часто и вообще невозможным.
Для некоторых хорошо изученных задач существуют специальные тестовые наборы, содержащие большое количество индивидуальных задач, которые используются исследователями для оценки эффективности и сравнительного анализа разрабатываемых алгоритмов, однако, во-первых, использование таких наборов не позволяет судить об эффективности работы тестируемого алгоритма на задачах, отличных от задач, входящих в набор, во-вторых, для многих задач, представляющих практический интерес, таких наборов просто не существует.
Технические характеристики и условия использования
Описанный в главе 3 алгоритм решения задачи ASP, а также процедуры, предложенные для исследования его эффективности, были реализованы в рамках комплекса программ «Аудит-S», состоящего из следующих модулей (рис. 8):
1) программы «Планировщик работы аудиторской организации Audit- S», предоставляющей пользовательские средства для ввода данных, автоматического составления рабочих графиков и их последующего просмотра и редактирования;
2) программы «Tester», предназначенной для исследования эффективности работы эвристических алгоритмов решения задачи ASP;
3) библиотеки «AuditS.Logic», содержащей реализацию общих структур данных и подпрограмм, использующихся в остальных частях комплекса;
4) библиотеки «Audits.Descend», реализующей алгоритм решения задачи ASP на основе метода локального спуска, описанный в п. 3.4;
5) библиотеки «Audits.Tabu», реализующей алгоритм решения задачи ASP на основе метода поиска с запретами, описанный в п. 3.5.
Все части комплекса «Аудит-S» выполнены на языке программирования С# 2.0 и предназначены для использования совместно со средой выполнения Microsoft .NET Framework версии 2.0.
Для возможности нормальной эксплуатации пользовательская система должна удовлетворять следующим требованиям.
Операционная система:
- Windows 98;
- Windows 98 SE;
- Windows ME;
- Windows 2000 Service Pack 3;
- Windows 2003 Server;
- Windows XP Service Pack 2.
Наличие установленной среды исполнения Microsoft .NET Framework 2.0;
Дисковое пространство - 2 Mb;
Объем оперативной памяти 128 Mb;
Центральный процессор Intel Pentium III или выше.
