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

На правах рукописи

СУЛТАНБЕКОВ Дамнр Габдрашитович

ИСПОЛЬЗОВАНИЕ МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ И АЛГОРИТМОВ ЛОКАЛЬНОГО ПОИСКА ДЛЯ ПЛАНИРОВАНИЯ РАБОТЫ ' АУДИТОРСКОЙ ОРГАНИЗАЦИИ

Специальность 05.13.1$ Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Уфа 2006

Работа выполнена на кафедре вычислительной математики и кибернетики Уфимского государственного авиационного технического университета

Научный руководитель

канд. техн. наук, доц. Орехов Юрий Васильевич

Официальные оппоненты

д-р. физ.-мат. наук, проф. Житпнков Владимир Павлович

канд. техн. наук, доц. Григорчук Татьяна Ивановна

Ведущая организация

Башкирская академия государственной службы и управления

Защита состоится

2006 г. в

часов

на заседании диссертационного совета Д - 212.288.03 при Уфимском государственном авиационном техническом университете по адресу: 450000, Уфа-центр, ул. К. Маркса 12, УГАТУ

(

С диссертацией можно ознакомиться в библиотеке университета.

Автореферат разослан «_»

2006 г.

Ученый секретарь диссертационного совета д-р. техн. наук, проф.

* Миронов

Общая характеристика работы

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

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

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

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

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

Цель работы

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

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

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

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

4) разработать программное обеспечение, реализующее предложенный алгоритм; РОС. НАЦИОНАЛЬНАЯ

БИБЛИОТЕКА С.-Петербург ОЭ 200^^9.9

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Содержание работы

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

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

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

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

Штат аудиторской организации состоит из сотрудников, каждый из которых относится к одной из четырех групп: 1) аудиторы - специалисты высшей квалификации; 2} помощники аудиторов - это, как правило, специалисты с бухгалтерским образованием, принимают участие в проверке бухгалтерской и финансовой отчетности предприятия; 3) юристы - привлекаются к проверке юридической документации проверяемого предприятия; 4) техперсонал - сотрудники, привлекаемые к выполнению сопутствующих работ, не связанных непосредственно с аудиторской проверкой, к квалификации которых не предъявляется особых требований.

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

■грудниками, относящимися к разным группам, может различаться. Для каждой пары (<группа сотрудников^ <операция>) задается время, необходимое для выполнения этой операции сотрудником, относящимся к данной группе.

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

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

1) любая операция каждой работы начинает выполняться после заданной даты начала этой работы; '

2) выполнение любой операции начинается не раньше, чем будут завершены все операции, предшествующие ей;

3) операция «подготовка отчета» любой работы завершена не позднее указанного момента сдачи отчета;

4) операция «составление аудиторского заключения» любой работы завершена не позднее указанного момента сдачи аудиторского заключения;

3) ни один исполнитель не выполняет более одной работы одновременно.

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

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

2) минимизация времени, затрачиваемого на выполнение работ;

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

4) минимизация количества операций, выполнение которых происходит в течение нескольких дней;

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

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

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

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

1. Временной интервал, на который проводится планирование, в виде списка Г периодов продолжительностью I час: fauPi»... рт)- Каждый период задается как пара (<день>, <чаО), характеризующая дату и время, соответствующую началу данного периода.

2. Список из m исполнителей А А& ..., Ат, каждый из которых относится к одной из четырех групп: G¡, G¡, G¡, G¡\ (аудитор, помощник аудитора, юрист, техработник).

3. Список из « работ Ji, -■4

4. Для каждой работы Jk заданы:

• Ní-количество операций, входящих в работу;

• множество операций 0't ,0¡7...,0"', образующих работу, причем любая работа обязательно включает в себя две операции: «подготовка отчета», которую будем обозначать как 0¿, и «составление аудиторского заключения», которую будем обозначать как 0¡;

• Г/ - момент времени, раньше которого нельзя начинать выполнение этой работы;

• Ту - момент сдачи отчета;

• Т/ - момент сдачи аудиторского заключения.

5. Для каждой операции 0'к заданы

• 4-хмерный вектор (í^,/,2,,...,^), где t"kJ - это время, необходимое для выполнения операции 0[ исполнителем, относящемся к группе G¡, (если t"kJ = да, то это означает, что операция <УЛ не может быть выполнена исполнителями, относящимися к группе G¿};

• список 4 состоящий из операций, относящихся к той же работе, задающий те операции, которые должны быть завершены к началу операции 0[.

6. Для кавдого сотрудника A¡ задан бинарный вектор U' ={и\,и\,..мт) длины Т определяющий периоды в которые данный сотрудник недоступен: если и[ - 1, то сотрудник A¡ недоступен в течение периода pt, в противном случае - доступен.

Введем следующие обозначения:

« B(0¡ ,S) - номер периода, на который назначено начало выполнения операции 0{ в соответствии с рабочим графиком S;

• E(0'j ,S) - номер периода, в котором должно завершиться выполнение операции О,' в соответствии с рабочим графиком

• R(0¡ ,S) - сотрудник, который должен выполнять операцию О' в соответствии с рабочим графиком

• /„(OJ) - минимальное время, которое требуется для выполнения операции О/,т.е. '„(Op^rain J&J;

• — максимальное время, которое может потребоваться для выполнения операции С^,т.е. 1^(0';)= max [i^J;

• W(Ank,S) - количество операций, которое должен выполнять сотрудник А( в период рк согласно рабочему графику S;

• Q(A„J^S) - количество операций, относящихся к работе Jki которые должен выполнять сотрудник At согласно рабочему графику S.

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

(1)

шах[Б(0;,5)]< В{01), к=1,...щ (2)

£(С>;, 5) £7;%Ы,...«; (3)

E(o;,S)<T;,h=u...n; (4)

W(A„k,S)Z 0,1=1,... т, А=1,...,Г. (5)

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

В работе предлагается целевая функция, отображающая множество расписаний на множество числовых пар вида (X, Y), где Охарактеризует количество нарушений обязательных требований, a Y— количество нарушений факультативных требований в оцениваемом рабочем графике.

Значение компоненты X вычисляется как

ад = xflig/A^SJ+x, * ±ig2(0/,S)+* ±gl(JnS)+

>1 1 I-t /-1 1.1

(■1 M

где X), хг, x$ - весовые коэффициенты, а компоненты gugi,---, %ь - ппра-фы, вычисляемые следующим образом.

1 at л » [О, если W(A,J,S) < 1,

О, если шах[£(0,5) - B(0/,S)] < О,

2. gl(Of,S) = J r ^ .

max[£09,S) - 5(0/,S)], иначе.

ГО, если тш[в(0;,5)]- Т? 2: О,

. Го, если

иначе. $)-Т,г<, О, иначе.

Значение комлоненгы У вычисляется как

(-1 /о) (=1 Ы

где уь )>2, - это весовые коэффициенты, а Аь Ь2,..., Ы - штрафы, налагаемые за нарушение факультативных требований.

I. ^,з)=в(р!,з)~в'(р1).

* ь,, « [5-Д(0;>Яи,5), если£ЩО;,5),У,,5)<5, [О, иначе.

, иначе.

4. /1,(Д,5) - это количество ситуаций, когда сотрудник Аь закончив выполнение операции, относящейся к одной работе, выполняет одну несколько операций, относящихся к другим работам, после чепЬ снова выполняет операции, относящиеся к первой работе.

5. Ьй(А„5) - это количество ситуаций, когда сотрудник А{ выполняет в один день операции, относящиеся к разным работам.

6. А,(У„5) - это количество сотрудников, привлекаемых к выполнению операций работы У;.

Если (Х^УО и (ЛУг) - это значения целевой функции, вычисленной в двух точках, то (Л"1,У)) < (Х2,¥2), если выполняется одно из следующих условий: 1)Х,<Хг; 7)Х^Х2 и Г,< У2.

Рабочий трафик представляет собой отображение

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

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

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

Во влгорой главе рассматриваются подходы, использующиеся для решения различных задач теории расписаний (задачи составления машинных расписаний, задачи составления расписаний занятий, задачи RCPSP).

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

Рассматривается связь задачи составления рабочих графиков в аудиторской организации с задачей RCPSP (Resource Constrained Project Scheduling Problem) - одной из наиболее сложных «классических» задач теории расписаний. Замечено, что задача составления рабочих графиков в аудиторской организации может быть с пекоторыми упрощениями представлена как частный случай многорежимной задачи RCPSP с частично обновляемыми ресур-* сами.

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

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

Среди достоинств алгоритма отмечены:

1) высокая эффективность, показанная при решении различных задач; ' 2) относительная простота реализации;

3) возможность организации итеративного процесса построения рабочего графика, каждая итерация которого будет состоять из двух шагов: авто-

^ магического составления рабочих графиков на основе поиска с запретами и последующей ручной правки построенного графика;

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

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

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

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

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

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

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

Список запретов состоит из троек вида (<Операция>, <Время начала выполнения^ <Исцолнятель>). На каждой итерации алгоритма в список запретов заносится тройка, отражающая произведенные на данной итерации изменения текущего рабочего графика.

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

1. Ввод данных.

2. Дня каждой операции каждой работы вычисляется допустимый интервал проведения операции.

3. В качестве текущего решения принимается рабочий график, сгенерированный случайным образом.

4. Случайным образом формируется подмножество окрестности текущего решения.

5. Дня каждого решения сформированной окрестности вычисляется значение целевой функции.

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

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

7. В список запретов заносится значение измененного при переходе в новую точку назначения.

8. Если выполняется критерий останова, то работа алгоритма заканчивается и в качестве результата выдается лучшее из просмотренных в ходе работы алгоритма решений, в противном случае производится возврат на шаг 4.

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

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

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

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

1) количество работ т;

2) список из п исполнителей Л;, Аз, Ап> каждый из которых относится к одной из четырех групп: G\, Gb,..y GA (аудитор, помощник аудитора, юрист, тех работник);

3) (р\>рг> ••• рт) - временной интервал, на который проводится планирование;

4) fmtn. 'max - минимально и максимально возможное время, выделяемое на выполнение операции;

5) , Т^ - минимально и максимально возможное время, которое может выделяться на выполнение операции «Подготовка аудиторского заключения»;

6) — минимально и максимально возможное время, которое может отделять момент окончания операции «Подготовка аудиторского заключения» от момента окончания операции «Подготовка отчета»;

7) н„ц„ и ища1 - минимально и максимальное количество временных периодов в течении которых может быть недоступен каждый из сотрудников.

Процедура генерации индивидуальных задач ASP основывается на итеративном использовании двух предложенных в диссертации процедур:

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

. , а <$>,<6;

Dt ^(jc^Xj,...,*,):-! i-i к где а, Ь, к - заданные целые неотрица-

[x,=0,l;z=l,..X-тельные числа, а<Ь;

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

D =

xt eZ,*, >0,

i = l,..fc; к

, для заданных целых неотрицательных к, s.

s е Z,s > О

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

Результаты использования описанной в четвертой главе процедуры равновероятной генерации индивидуальных задач ASP представлены в таблице 1 (здесь N' - количество задач, для которых были найдены допустимые решения, Р - доля задач, для которых были найдены допустимые решения).

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

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

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

Таблица 1

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

Количество работ N локальный спуск поиск с запретами

№ Р 1Г Р

10 100 97 0.97 100 1

12 100 79 0.79 96 0.96

14 100 57 0.57 93 0.93

16 100 23 0.23 58 0.88

18 50 0 0 34 0.68

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

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

Учитывая, что на практике количество работ обычно находится в пределах от 10 до 16, доля задач, имеющих размерность близкую к встречающимся на практике, для которых были найдены допустимые решения, составила 94,25%.

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

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

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

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

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

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

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

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

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

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

Список публикаций В рецензируемых зкурнаяах из списка ВАК

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

В других изданиях

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

3. Случайная равновероятная генерация целочисленных векторов при наличии ограничений / Т.В. Еникеев, IO.B. Орехов, Д.Г. Султанбеков // Информационные технологии и математическое моделирование : сб. матер. 3-й Всерос. науч.-практ. конф. Анжеро-Судженск, 2004. Ч. 2. С. 16-17.

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

5. Задача составления рабочих графиков в аудиторской организации У Д.Г. Султанбеков И Управление в социальных и экономических системах : сб. матер. Ш Междунар. науч.-практ. конф. Пенза : ПГСХА, 2005. С. 133-134.

6. Процедура равновероятной генерации индивидуальных задач составления рабочих графиков в аудиторской организации У Д.Г. Султанбеков УУ Информационно-вычислительные технологии и их приложения : сб. матер. Междунар. науч.-практ. конф. Пенза: ПГСХА, 2005. С.196-199.

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

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

9. Планирование работы персонала в аудиторской организации ! Д.Г, Султанбеков // Компьютерные науки и информационные технологии : сб. матер. 7-й МеЖдунар. науч.-практ. конф. Уфа : УГАТУ, ООО «Виртуал», 2005. Т. 3. С. 196-197 (Статья на англ. языке).

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

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

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

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

14.Иснользование мета-эвристики поиска с запретами в планировании работы аудиторской организации / Д.Г, Султанбеков // Интеллектуальные системы обработки информации и управления: сборник статей региональной зимней школы-семинара аспирантов и молодых ученых. Уфа: «Технология», 2006. Т. 1.С. 134-139.

15.Процедура равновероятной генерации индивидуальных задач составления рабочих графиков в аудиторской организации / Д.Г. Султанбеков // Социально-экономические и технические системы: исследование, проектирование, оптимизация : электронный журнал. №7 (23). 2006. (Электронный адрес: http://www.kampi.nj/sets/index2.php?arhiv/23nomer.php# )

Диссертант

СУЛТАНБЕКОВ Дамир Габдрадштович

ИСПОЛЬЗОВАНИЕ МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ И АЛГОРИТМОВ ЛОКАЛЬНОГО ПОИСКА ДЛЯ ПЛАНИРОВАНИЯ РАБОТЫ АУДИТОРСКОЙ ОРГАНИЗАЦИИ

Специальность 05.13.18 Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Подписано к печати 24,11.2006. Формат 60x84 1/16. Бумага офсетная. Печать плоская. Гарнитура Тайме. Усл. печ. л. 1,0. Усл.кр.-отт. 1,0. Уч.-изд. л. 0,9. Тираж 100 экз. Заказ № 612,

ГОУВПО Уфимский государственный авиационный технический университет Центр оперативной полиграфии 450000, Уфа-центр, ул. К.Маркса, 12

Введение.

Глава 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 названия.

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

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

Заключение

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