В настоящее время в ФКУ НИИИТ ФСИН России обрабатывается более 120 форм ведомственной статистической отчетности. Сроки обработки форм регламентированы приказами. Одновременно в обработке может находиться более 50 статистических форм. Казалось бы целесообразным подготовить расписание по проведению технологических операций по сбору и обработке информации на основе ведомственных форм статистической отчетности с учетом минимизации трудоемкости выполнения работ.

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

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

Оценка качества сформированных расписаний может быть проведена на основании трех следующих основных параметров: трудоемкости

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

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

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

Порядок сбора и обработки статистической отчетности ФСИН России регламентируется приказом ФСИН России от 26.01.2012 г. № 45 «О совершенствовании организации и повышении эффективности информационного обеспечения деятельности Федеральной службы исполнения наказаний», которым утверждены Регламент организации работы по разработке форм статистической отчетности Федеральной службы исполнения наказаний» (Приложение № 1 к Приказу) и Регламент организации работы по формированию, обработке и представлению статистической информации в учреждениях и органах УИС» (Приложение № 2 к Приказу).

Общепринятой является следующая схема обработки данных [1]:

Восприятие информации (измерение величины)

Регистрация данных (документы первичного учета)

Предварительная обработка данных

Ввод данных

Подготовка данных

Передача данных

Ввод в средство обработки

Обработка информации

Выдача данных

Оценка результатов и их отображение (подготовка печатного отчета) При этом операции по позициям 1-6 выполняются в учреждении

территориального органа (нижний уровень сбора информации), затем позиции 2-6 выполняются в территориальном органе ФСИН России, и наконец, позиции 7-10 выполняются в ФКУ НИИИТ ФСИН России. Частичное дублирование операций на этапах 2-6 вызвано трехуровневой схемой сбора и обработки информации, существующей в настоящее время в ФСИН России.

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

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

Проведем постановку задачи. Пусть J - множество планируемых в отчетном периоде (месяц, квартал, полугодие или год) к выполнению работ (по сути дела речь идет о составлении не одного расписания, а как минимум 12 расписаний, с учетом минимальной ежемесячной периодичности сбора информации. В случае уменьшения периодичности количество расписаний еще больше возрастет), I - множество операторов, выполняющих работы по сбору и обработке информации (идеальной ситуацией была бы возможность составления расписания при изменяемом количестве операторов, поскольку их количество связано с отпусками, болезнями и т.д. Принципиально это возможно, если количество операторов сделать входным параметром для программы), K - множество стадий, объединяющих однотипные операции (формы). Работе j поставим в соответствие набор г[1] = (rj rj,..., rj), где г/ -

номер оператора, которым должна выполняться l - тая операция работы ,

ri e K, I = 1 kj , jeJ.

В настоящее время работа оператора в ФКУ НИИИТ ФСИН России, как правило, строится по принципу - один оператор - одна форма. Конечно, за одним оператором закреплено большее количество форм статистической отчетности, существуют и отклонения от правила, когда человек одновременно ведет и несколько форм отчетности, но в большинстве случаев оператор стремится полностью закончить работу с одной формой и лишь затем перейти к другой. Создание оптимального расписания, о котором ведется речь в статье, потребует коренной перестройки работы в случае его принятия.

Под операцией нами понимается процесс выполнения этапа работы на какой-либо стадии определенным оператором (в этом случае оператор не «привязан» к конкретной форме. Считается, что все операторы взаимозаменяемы и обладают примерно одинаковой квалификацией). Обозначим через tijl - время выполнения l - ой операции по сбору и обработке

информации j оператором i (стадия ry), Dj - заданный в приказе или ином нормативно-правовом акте срок завершения последней операции работы j (на практике он отклоняется от принятого в нормативно-правовом акте на 1-2 дня в сторону уменьшения), gj - коэффициент, определяющий отклонения,

связанные с нарушением определенного для данного вида работы j директивного срока, iel, l = 1, kj , jeJ, seJ.

Обозначим через X={xijU iel, l = 1,kj jeJ}, где xtJl- момент начала выполнения операции l работы j оператором i; Y={yiji, iel, l = 1,kj jeJ} где yijie{0,1}, Уу} =1, если l-ая операция j-ой данной работы выполняется i-ым

оператором; yji = 0, если l-ая операция j-ой данной работы не выполняется i-

ым оператором; Z={zijl, iel, l = 1, kj jeJ}, где zjfl - номер по порядку выполнения l-ой операции j -ой работы i -ым оператором, zlfl e{0,1,..., N }, N = 2kj, iel, l = Щ' jeJ.

jeJ

Очевидно, что

2 yijl =1 l = 1>ki’j e J.

iel j j

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

Если

yjl =1 и ysjl-1 =1,

то Xjl > Xjl-1 + tsfl-1, l = 2, kj , i e I, s e I, j e J.

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

Если

Уjl = 1 y*s = 1 zjl = ZrvS + 1 то Xjl > Xvs + tjl + Tvj ,

i e I, s = 1, kv, l = 1, kj, v e J, j e J.

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

xjl > 0, yjl e {0,1}, zjl e {0,1,...,N}, ie1, l = 1 kJ, jeJ-

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

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

набор критериев, определяемых сроками выполнения работ по сбору и обработке информации:

F11 (X, Y, Z) = Si max(0, Xj + к ,L - Dj ) ^ min

0

где l0 = kJ, y t = 1 отклонения, связанные с нарушением плановых сроков

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

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

kj

F2 j (X, Y, Z) = ^^ tjiyifl ^ min .

iel l=1

- суммарные затраты времени, связанные с выполнением всех операций по сбору и обработке информации по работе с номером j, j eJ.

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

F =Z F,j++Z F, j .

jeJ jeJ

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

Поставленная задача являются NP-трудной задачей дискретной оптимизации [3]. Возможна попытка прямого решения задачи путем прямого перебора всех возможных вариантов, но с учетов величины входных параметров машинное время, которое потребуется для ее решения может быть очень значительным. Поэтому для её решения удобнее всего использовать так называемые «жадные» алгоритмы. Это по сути дела, хорошо проработанные градиентные схемы для решения непрерывных задач, однако успешно перенесенные на задачи дискретной оптимизации. Под жадными алгоритмами, мы будем понимать алгоритмы [4], в которых однажды включенная в создаваемое расписание работа уже не может быть исключена из него на последующих шагах построения расписания. Указанные алгоритмы не всегда приводят к составлению лучшего расписания, однако существенно снижают временные затраты на его расчет, они также не гарантируют получения точного решения, но находят ряд допустимых решений, являющихся близкими к оптимальным. Поскольку
натурного эксперимента по подготовке к расчету указанного расписания еще не проводилось, то данный фактор по нашему мнению является не маловажным.

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

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

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

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

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

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

Литература:

Краус М., Кучбах Э., Вотттни О.Г. Сбор данных в управляющих вычислительных системах, М., Мир, 1987, с. 43.

Коффман Э.Г., Теория расписаний и вычислительные машины, М., «Наука», 1984, с. 82.

Танаев В.С., Шкурба В.В., Введение в теорию расписаний, М., изд. «Наука», 1975, с. 142.

Губарь Ю.В. Курс лекций «Введение в математическое

моделирование» проекта «Интернет университет информационных

технологий», http://www.intuit.ru/ department/ calculate/intromathmodel/1/

[1] если операция l работы j выполняется оператором i,

У =i

ijl 0, в противном случае,