Размещено на http://www.allbest.ru/

УДК 004.422.81

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

REVIEW OF THE ALGORITHMS OF THE SCHEDULE THEORY AND THEIR APPLICATION TO OPTIMIZE THE SCHEDULE OF RECEPTION OF CLIENTS IN A NOTARY OFFICE

Кононова М.В., Филиппов С.А. Национальный исследовательский ядерный университет «МИФИ»

Аннотация

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

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

In this article various algorithms of the theory of schedules are considered: shortest processing time sequencing, permutation schedules, ordering in accordance with the planned term, random ordering and ordering with incomplete information, also cases of their application are considered. Based on the shortest processing time sequencing algorithm, a software system for optimizing the scheduling of client acceptance in a notary's office has been developed. This system will increase the number of notarial actions and solve the problem of queues in notary offices.

Keywords: scheduling, scheduling theory, software system development, shortest processing time sequencing, registration of clients, notarial office

Введение

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

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

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

Рассмотрим их более подробно применительно к предметной области.

Упорядочивание по минимуму длительности работ

Упорядочивание по минимуму длительности работ для системы, состоящей из n работ и одной машины, представлено на рисунке 1. [5]

Рисунок 1. Упорядочивание по минимуму длительности работ.

программный сайт нотариальный расписание

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

Каждый из прямоугольников, как представлено на рисунке 2, можно заменить векторами pi, равными по длине диагоналям прямоугольников, с угловыми коэффициентами 1/ pi.

Рисунок 2. Замена прямоугольников векторами.

Исходя из этого, любое расписание будет представлять собой последовательность векторов, расположенных таким образом, что конец одного вектора совпадает с началом другого. Очевидно, что площадь под данной векторной кривой будет минимальна в том случае, если кривая выпукла вниз, т.е. кривая должна начинаться с вектора, имеющего максимальный модуль углового коэффициента, а все последующие векторы должны быть расположены в порядке уменьшения модуля их угловых коэффициентов (p[1]? p[2]?…?p[n]). Такой алгоритм упорядочивания называется упорядочивание по минимум длительности работ (shortest processing time sequencing - SPT). Он основывается на следующем утверждении: среднее время пребывания работ в системе из одной машины и n работ минимально, если после упорядочивания длительности работ не убывают: p[1]? p[2]?…?p[n], и максимально, если после упорядочивания длительности работ не возрастают: p[1]? p[2]?…?p[n]) [4]. Следовательно, для того чтобы минимизировать среднее время пребывания работ в системе, необходимо упорядочить их длительности в порядке неубывания.

Перестановочные расписания

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

Пример такого расписания представлен на рисунке 3.

Для такого класса задач поиск оптимального решения для данного класса задач проводится в классе перестановочных расписаний. Существуют расписания, определяемые полностью порядком выполнения работ, т.е. в случае n работ они задаются одной из n! возможных перестановок. Таким образом, можно вычислить значение Wi и найти все остальные свойства расписания, задав эту перестановку и длительность каждой работы [3].

Рисунок 3. Расписание с прерываниями и простоями.

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

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

С точки зрения практического приложения наиболее важным критерием оценки расписаний является критерий своевременного выполнения работ. В связи с тем, что оценкой расписания в данном случае служит нарушение планового срока работ, то очевидно, что упорядочивание необходимо осуществлять с учетом информации о наборе величин {di}-плановые сроки выполнения работ. Наиболее простым и очевидным использованием плановых сроков является упорядочивание: d[1]? d[2]?…?d[n], что подтверждается следующей теоремой: расписание, минимизирующее максимум временного смещения и максимум запаздывания работ таково, что работы выполняются в порядке неубывания плановых сроков [6].

Кроме того, информацию, которая содержится в наборе величин {di} также можно использовать для упорядочивания в соответствии с резервом времени каждой работы. Резерв времени работы i в момент времени t равняется di - pi-t и представляет собой максимально допустимую длительность ожидания, при которой не произойдёт задержки. Таким образом, работа с минимальным резервом времени имеет больше шансов быть задержанной, поэтому при установлении очередности она должна обладать высоким приоритетом исполнения. Т.к. время t является общим для всех работ, то упорядочивание должно иметь следующий вид: d[1]- p[1]? d[2] - p[2]?…?d[n] - p[n]. Данный результат является следствием теоремы, которая звучит следующим образом: расписание, максимизирующее минимальное временное смещение и минимальное запаздывание работ в системе с одной машиной и n работами таково, что работы выполняются в порядке неубывания резерва времени [1]. Данный алгоритм целесообразно использовать при наличие заранее определенных плановых сроков работ. Результат в этом случае достигается путем упорядочивания работ в порядке неубывания плановых сроков.

Случайное упорядочивание

Рассмотрим упорядочивание для системы из одной машины и n работ при случайной их длительности. Очередность выполнения работ в данном случае устанавливается исходя из признаков, которые не зависят от длительности работ. К примеру, если предположить, что плановые сроки работ не зависят от их длительности, то упорядочивание в соответствии с плановыми сроками приведет к случайному упорядочиванию длительностей работ. В том случае, если упорядочивание производится в соответствии с резервом времени, то полученная последовательность длительностей работ не будет носить случайный характер [10].

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

E (???) = ,

где ??? - среднее арифметическое длительности работ, если они известны заранее, и

E (???) = ,

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

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

Упорядочивание при неполной информации

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

Предположим, что в системе из одной машины и n работами все работы имеют различные длительности, а нумерацию работ можно представить следующим образом: p1? p]?…?pn [4]. Кроме того, предположим, что множество X1, X2, …, Xn образует набор априорных оценок длительностей работ, на которых основывается упорядочивание SPT. Тогда очередность будет представлять собой: Х[1]? Х[2]?…?Х[n]. В случае, если величины Х и р положительно коррелированы с коэффициентом корреляции 1, то упорядочивание, которое проведено на основании оценок, будет соответствовать упорядочиванию SPT, при заранее известных длительностях работ. В том случае, если величины Х и р независимы, то проведенное упорядочивание будет случайным. Наконец, если величины Х и р отрицательно коррелированы с коэффициентом корреляции -1, то проведенное упорядочивание будет соответствовать упорядочивание, обратное к SPT при заранее известных длительностях работ. В общем случае можно полагать, что на основании оценок результат будет соответствовать области положительной корреляции, поскольку обычно есть возможность измерить p после окончания работ и уточнить упорядочивание [9].

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

Выбор алгоритма, наиболее применимого к решаемой задаче

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

Таблица 1. Применение алгоритмов теории расписаний

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

Создание интернет-приложения для сайта нотариальной конторы