Использование математического моделирования и алгоритмов локального поиска для планирования работы аудиторской организации тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат технических наук Султанбеков, Дамир Габдрашитович

• Султанбеков, Дамир Габдрашитович
• кандидат технических наук
• 2006

Оглавление диссертации кандидат технических наук Султанбеков, Дамир Габдрашитович

Введение.

Глава 1. Постановка задачи составления рабочих графиков в аудиторской организации.

1.1. Данные, используемые при планировании работы аудиторской организации.

1.2. Требования, предъявляемые к рабочим графикам в аудиторской организации.

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

1.4. Выводы по главе 1.

Глава 2. Обзор методов, применяемых для решения задач теории расписаний.

2.1. Общая характеристика задач теории расписаний.

2.1.1. Задачи составления машинных расписаний.

2.1.2. Задача составления расписания занятий.

2.1.3. Задача составления расписания работы персонала.

2.1.4. Задача RCPSP.

2.2. Методы решения задач теории расписаний.

2.2.1. Простые эвристические алгоритмы.

2.2.2. Генетические алгоритмы.

2.2.3. Общая характеристика методов локального поиска.

2.2.4. Локальный спуск.

2.2.5. Алгоритм поиска с запретами.

2.2.6. Метод моделирования отжига.

2.3. О сетевых методах планирования.

2.4. Выводы по главе 2.

Глава 3. Использование методов локального поиска для решения задачи составления рабочих графиков в аудиторской организации.

3.1. Определение окрестности текущего решения.

3.1.1. Отношение соседства на множестве рабочих графиков.

3.1.2. Вычисление допустимого интервала проведения операции.

3.1.3. Сокращение просматриваемой окрестности.

3.2. Уменьшение временных затрат на вычисление значения целевой функции.

3.3. Получение начальной точки работы алгоритма.

3.4. Алгоритм локального спуска.

3.5. Алгоритм поиска с запретами.

3.6. Практические испытания алгоритма.

3.6.1. Размерность тестовых задач.

3.6.2. Значения параметров алгоритма.

3.6.3. Результаты.

3.7. Выводы по главе 3.

Глава 4. Оценка эффективности алгоритма.

4.1. Актуальность задачи оценки эффективности эвристических алгоритмов.

4.2. Разработка равновероятного генератора индивидуальных задач составления рабочих графиков в аудиторской организации.

4.2.1. Определение подмножества индивидуальных задач для генерации

4.2.2. Процедура генерации периодов недоступности сотрудников.

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

4.2.4. Процедура генерации множества операций и времен исполнения операций.

4.2.5. Процедура генерации сроков выполнения работ.

4.2.6. Процедура равновероятной генерации индивидуальных задач составления рабочих графиков в аудиторской организации.

4.3. Оценка эффективности работы алгоритма.

4.4. Выводы по главе 4.

Глава 5. Программная реализация алгоритма решения задачи ASP. Численные эксперименты.

5.1. Комплекс программ «Аудит-S».

5.2. Технические характеристики и условия использования.

5.3. Программа «Планировщик работы аудиторской организации»

5.4. Программа «Tester».

5.5. Результаты тестирования.

5.6. Выводы по главе 5.

Введение диссертации (часть автореферата) на тему «Использование математического моделирования и алгоритмов локального поиска для планирования работы аудиторской организации»

Актуальность задачи автоматизации планирования работы аудиторской организации

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

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

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

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

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

Цель работы

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

1) разработать математическую модель задачи составления рабочих графиков в аудиторской организации;

2) разработать алгоритм решения задачи составления рабочих графиков в аудиторской организации;

3) разработать методику оценки эффективности предложенного алгоритма;

4) разработать программное обеспечение, реализующее предложенный алгоритм;

5) исследовать эффективность разработанного алгоритма при помощи численного эксперимента.

На защиту выносятся

1. Математическая модель задачи составления рабочих графиков в аудиторской организации.

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

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

4. Комплекс программ, предназначенный для решения рассматриваемой задачи и оценки эффективности предложенного алгоритма.

5. Результаты вычислительного эксперимента, демонстрирующие эффективность предложенного подхода (доля задач, имеющих размерность, близкую к встречающимся на практике, для которых были найдены допустимые решения, составила 94,25%).

Научная новизна

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

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

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

• разработке процедуры равновероятной генерации бинарных векторов фиксированной длины;

• разработке процедуры равновероятной генерации целочисленных векторов, удовлетворяющих ряду ограничений.

Практическая ценность

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

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

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

Апробация работы

Основные результаты докладывались на:

1. III Всероссийской научно-практической конференции «Информационные технологии и математическое моделирование» (Анжеро-Судженск, 2004).

2. VII международной конференции «Computer Science and Information Technologies» (Уфа, 2005).

3. Ill Международной научно-практической конференции «Управление в социальных и экономических системах» (Пенза, 2005).

4. Международной научно-практической конференции «Информационно-вычислительные технологии и их приложения» (Пенза, 2005).

5. Зимней школе аспирантов и молодых ученых (Уфа, 2006).

6. Научных семинарах «Модели искусственного интеллекта» кафедры ВМиК УГАТУ (Уфа, 2003-2006).

По теме диссертации опубликовано 15 работ, в том числе 1 статья в рецензируемом журнале из списка ВАК и 2 программы для ЭВМ.

Структура и объем работы

Диссертация состоит из введения, пяти глав и заключения. Объем составляет 95 страниц машинописного текста, включая 11 рисунков, 5 таблиц, библиографию, содержащую 63 названия.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Султанбеков, Дамир Габдрашитович

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

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

Заключение

Список литературы диссертационного исследования кандидат технических наук Султанбеков, Дамир Габдрашитович, 2006 год

1. Федеральный закон «Об аудиторской деятельности» от 7 августа 2001 года № 119-ФЗ.

2. Сложные задачи теории расписаний / П. Брукер // CiteSeer : Электронная библиотека научной литературы. 1999. (Статья на англ. языке; эл. адрес <http://citeseer.ist.psu.edu/brucker99complex.html>).

3. Поиск с запретами для планирования с ограниченными ресурсами / М.Г.А. Верхоевен. // Европейский журнал по исследованию операций. Амстердам : Elsevier Science, 1998. Т. 106, № 2/3. С. 266-276 (Статья на англ. языке).

4. Составление расписаний экзаменов в университетах Британии : обзор / Э.К. Буркэ, Д.Г. Эллиман, П.Х. Форд // Практика и теория автоматического составления расписаний : сб. матер. 1-ой междунар. конф., Эдинбург, 1995. С. 423-434 (Статья на англ. языке).

5. Свид. о гос. per. программы для ЭВМ №2003611408. Мастер составления расписания занятий в учебных заведениях среднего образования / Д.Г. Султанбеков М.: РосАПО, 2003.

6. Конкурентоспособный генетический алгоритм для решения задачи планирования проекта с ограниченными ресурсами / С. Хартман // Naval Research Logistics : междунар. журнал по исследованию операций. 1998. Т. 45. С. 733750 (Статья на англ. языке).

7. Применение метода поиска с запретами для больших задач составления расписания школьных занятий / А. Шаэрф // Искусственный интеллект : сб. матер. 14-ой нац. конф. Портлэнд, 1996. С. 363-368 (Статья на англ. языке).

8. Искусственный интеллект: современный подход, изд. 2-е / С. Рассел, П. Норвиг. М. : Издательский дом «Вильяме», 2006.

9. Графики охлаждения для решения задачи составления расписания занятий методом моделирования отжига / Д. Абрамсон, X. Данг, М. Кришнамурти // Азиатско-Тихоокеанский журнал по исследованию операций. Сингапур, 1999. Т. 16. С. 1-22 (Статья на англ. языке).

10. Использование методов локального поиска для составления расписанияшкольных занятий / А. Шаэрф, М. Шаэрф // Практика и теория автоматического составления расписаний : сб. матер. 1-ой междунар. конф., Эдинбург, 1995. С. 313-323 (Статья на англ. языке).

11. Вычислительные машины и трудноразрешимые задачи / М. Гери, Д. Джонсон-М.: Мир. 416 с.

12. Описание и генерация задач планирования проекта с ограниченными ресурсами общего вида / А. Дрексль, Р. Колиш, А. Шпрехер // Методы управления : научн. журнал, Линтикам, 1995. Т. 41. С. 693-1703 (Статья на англ. языке).

13. Алгоритм составления расписания зачетно-экзаменационной сессии. /Еникеев Т.В., Султанбеков Д.Г.: Уфим. гос. авиац. техн. ун-т; Уфа, 2003. 7 с. Библиогр. : 4 назв. Рус. Деп. в ВИНИТИ. 17.02.2003, №305-В2003.

14. Составление плана-графика работы и отдыха летного состава / Ю.А. Бату-ринец, Э.Ю. Орехов // Информационные и кибернетические системы управления и их элементы: сб. матер. Всеросс. молодежная научн.-техн. конф. Уфа : УГАТУ, 1997. С. 13.

15. Случайная равновероятная генерация бинарных векторов при наличии ограничений / Т.В. Еникеев, Ю.В. Орехов, Д.Г. Султанбеков // Информационные технологии и математическое моделирование : сб. матер. 3-й

16. Всерос. науч.-практ. конф. Анжеро-Судженск, 2004. Ч. 2. С. 15-16.1.. Свид. о гос. per. программы для ЭВМ № 50200500472. Равновероятный генератор целочисленных векторов при наличии ограничений / Т.В. Еникеев, Д.Г. Султанбеков. М.: ВНТИЦ, 2005.

17. Свид. о гос. per. программы для ЭВМ № 50200500473. Равновероятный генератор бинарных векторов при наличии ограничений / Т.В. Еникеев, Д.Г. Султанбеков. М. : ВНТИЦ, 2005.

18. Ю. О генерации целочисленных векторов при наличии ограничений / Т.В. Еникеев, Ю.В. Орехов, Д.Г. Султанбеков // Принятие решений в условиях неопределенности : межвуз. науч. сб. Уфа : УГАТУ, 2005. Вып. 2, ч. 1. С. 193-198.

19. Теория расписаний / Р. В. Конвей, В. J1. Максвелл, JT. В. Миллер М. : Наука, 1975.

20. Задача flow-shop с параллельными машинами: решение методом поиска с запретами / Е. Новицки, К. Смутницки // Европейский журнал по исследованию операций. Амстердам : Elsevier Science, 1998. Т. 106. С. 226-253 (Статья на англ. языке).

21. Улучшение эвристик локального поиска для некоторых задач построения расписаний ( часть 1) / П. Брукер, Ф. Вернер, Д. Хуринк // Прикладная дискретная математика : научн. журнал. Амстердам, 1996. Т. 65. С. 97-122 (Статья на англ. языке).

22. Улучшение эвристик локального поиска для некоторых задач построения расписаний ( часть 2) / П. Брукер, Ф. Вернер, Д. Хуринк // Прикладная дискретная математика : научн. журнал. Амстердам, 1996. Т. 72. С. 47-69 (Статья на англ. языке).

23. Обзор современных методов решения задачи job-shop / А.С. Джэйн, С. Ми-рэн // CiteSeer : Электронная библиотека научной литературы, 1998 (Статьяна англ. языке; эл. адрес <http://citeseer.ist.psu.edu/jain98stateart.html>).

24. Ю. Генетический алгоритм для решения задачи составления расписания занятий / М. Дориго, А. Колорни, В. Маньезо // CiteSeer : Электронная библиотека научной литературы, 1993 (Статья на англ. языке; эл. адрес <http://citeseer.ist.psu.edu/182445.html>).

25. Модели и постановки задач планирования работы персонала / А. Мэйзельс, А. Шаэрф // CiteSeer : Электронная библиотека научной литературы, 1999 (Статья на англ. языке; эл. адрес <citeseer.ist.psu.edu/meisels99model.html>).

26. Машинные расписания / Э. Д. Андерсен, С.А. Гласс, К.Н. Поттс; ред. Э. Аартс, Д.К. Ленстра // Локальный поиск в задачах комбинаторной оптимизации. Нью Йорк : John Wiley & Sons, 1997. С. 361-414 (на англ. языке).

27. Эксперименты на сетях задач составления расписания работы персонала / Н. Люстерник, А. Мэйзельс. // Автоматическое составление расписаний : сб. матер. 2-ой научн. конф. Торонто, 1997, С. 93-105 (Статья на англ. языке).

28. Решение задачи job-shop методами локального поиска / Э. Аартс, Р. Вэс-сенс, Д.К. Ленстра // COSOR Memorandum 94-05, Эйндховен, 1994 (Статья на англ. языке).

29. Алгоритм поиска с запретами для решения задачи составления расписаний open-shop / Л. Чин-Фанг // Компьютеры и исследование операций : научн. журнал, Оксфорд, 1999. Т. 26. № 2. С. 109-126 (Статья на англ. языке).

30. Численные методы Монте-Карло / И.М. Соболь, М.: Наука, 1973. 312 с.

31. Таблицы интегралов, сумм, рядов и произведений. / И.С. Градштейн, И.М. Рыжик, -М.: Наука, 1971. 1108 с.

32. Об одном способе равновероятной генерации целочисленныхвекторов при наличии ограничений / Т.В. Еникеев, Ю.В. Орехов, Д.Г. Султанбеков ; Уфим. гос. авиац. техн. ун-т. Уфа, 2005. 40 с. Библиогр. : 1 назв. Рус. Деп. в ВИНИТИ. № 246-В2005.

33. Использование алгоритма поиска с запретами для решения задачи составления рабочих графиков в аудиторской организации / Д.Г. Султанбеков // Принятие решений в условиях неопределенности : межвуз. науч. сб. Уфа : УГАТУ, 2006. Вып. 3. С. 148-153.

34. Алгоритм решения задачи составления рабочих графиков в аудиторской организации и исследование его эффективности / Д.Г. Султанбеков // Вестник УГАТУ : научн. журнал Уфимск. гос. авиац. техн. ун-та. Уфа, 2006. Т.8, № 1 (17). С. 48-51.

35. Сетевые методы планирования. Применение системы ПЕРТ и её разновидностей при управлении производственными и научно-исследовательскими проектами / А. Кофман, Г. Дебазей. М.: Прогресс, 1967. - 184 с.