В практике автоматизации управления персоналом часто возникает задача оптимального планирования графиков. Одной из таких задач является распределение накопленных отгулов. Представим ситуацию: у группы сотрудников есть разное количество дней отгула, которые они должны отгулять в течение одного месяца (например, 30 дней). Основное ограничение — в любой выбранный день месяца количество одновременно отсутствующих сотрудников не должно превышать заданное число N. При этом каждый сотрудник должен забрать свои дни одним непрерывным блоком, и этот блок не может выходить за границы календарного месяца.
Рассмотрим подробно, как подойти к решению этой задачи, какие математические модели использовать и как реализовать алгоритм программно.
Проанализируем суть проблемы. Перед нами классическая задача комбинаторной оптимизации. Ее можно классифицировать как задачу упаковки в полосу (Strip Packing Problem) или вариацию задачи о контейнерах (Bin Packing Problem). В нашем контексте:
N (это наши доступные слоты для сотрудников) и «длину» 30 (дни месяца).Разберем условия разрешимости. Прежде чем запускать сложный алгоритм, проверим, возможно ли в принципе решение. Сумма всех дней отгулов всех сотрудников должна быть меньше или равна произведению N * 30. Если СуммаДней > (N * 30), задача не имеет решения. Однако, даже если условие выполняется, неделимость блоков (отгул одним куском) может привести к тому, что возникнут «пустоты», которые невозможно заполнить длинными блоками других сотрудников.
Одним из наиболее эффективных эвристических методов для подобных задач является алгоритм LPT. Его логика заключается в том, чтобы сначала распределять самые длинные интервалы, так как их сложнее всего «втиснуть» в остатки свободного времени в конце процесса.
Рассмотрим пошагово реализацию этого подхода:
N параллельных «потоков» или «очередей». Каждый поток имеет емкость 30 дней.Посмотрим на пример реализации алгоритма в среде 1С. Для этого удобно использовать двумерный массив или ТаблицаЗначений, которая будет выступать в роли сетки занятости. В этой сетке строками будут «потоки» (от 1 до N), а колонками — дни месяца (от 1 до 30).
Рассмотрим пример кода, реализующий «жадный» алгоритм поиска свободного места:
// Предположим, ТЗ_Сотрудники содержит колонки: Сотрудник, КоличествоДней
// N - максимальное количество отсутствующих
ТЗ_Сотрудники.Сортировать("КоличествоДней Убыв");
// Создаем карту занятости: Массив из N строк, в каждой массив из 30 булево
КартаЗанятости = Новый Массив;
Для Счетчик = 1 По N Цикл
ДниМесяца = Новый Массив(30); // Инициализируется Ложь
КартаЗанятости.Добавить(ДниМесяца);
КонецЦикла;
Для Каждого СтрокаСотрудник Из ТЗ_Сотрудники Цикл
ДнейОтгула = СтрокаСотрудник.КоличествоДней;
УдалосьРазместить = Ложь;
// Пытаемся найти место в одном из N потоков
Для НомерПотока = 0 По N - 1 Цикл
Поток = КартаЗанятости[НомерПотока];
// Ищем непрерывный участок свободных дней
Для ДеньНачала = 0 По (30 - ДнейОтгула) Цикл
МожноРазместить = Истина;
Для ПроверкаДня = ДеньНачала По (ДеньНачала + ДнейОтгула - 1) Цикл
Если Поток[ПроверкаДня] = Истина Тогда
МожноРазместить = Ложь;
Прервать;
КонецЕсли;
КонецЦикла;
Если МожноРазместить Тогда
// Занимаем дни в карте
Для ЗаполнениеДня = ДеньНачала По (ДеньНачала + ДнейОтгула - 1) Цикл
Поток[ЗаполнениеДня] = Истина;
КонецЦикла;
СтрокаСотрудник.ДатаНачала = ДеньНачала + 1; // Записываем результат
УдалосьРазместить = Истина;
Прервать;
КонецЕсли;
КонецЦикла;
Если УдалосьРазместить Тогда Прервать; КонецЕсли;
КонецЦикла;
Если Не УдалосьРазместить Тогда
Сообщить("Не удалось разместить сотрудника: " + СтрокаСотрудник.Сотрудник);
КонецЕсли;
КонецЦикла;
Проанализируем ситуацию, когда необходимо учитывать производственный календарь. Если 30 дней — это календарный месяц, но отгулы тратят только рабочие дни, алгоритм должен оперировать не просто индексами 0..29, а массивом дат, исключая выходные. В 1С для этого используется запрос к регистру сведений ДанныеПроизводственногоКалендаря.
Выясним причину, почему это усложняет задачу: рабочие дни в месяце идут не подряд. Если сотрудник берет 5 рабочих дней отгула, он фактически может отсутствовать 7 календарных дней (включая субботу и воскресенье). В этом случае длина нашего «прямоугольника» в сетке планирования должна соответствовать календарному периоду, а не количеству дней отгула, либо сетка должна строиться строго по рабочим дням.
Для проверки качества распределения рекомендуем использовать объект ДиаграммаГанта. Это позволит наглядно увидеть, как распределены «слои» сотрудников. По горизонтальной оси откладываются дни месяца, по вертикальной — номера потоков (от 1 до N).
Если после автоматического распределения остаются некрасивые зазоры, можно применить алгоритм Best-Fit. В отличие от «жадного» поиска (который берет первый подходящий интервал), Best-Fit ищет такое место, после размещения в котором остается минимальный остаток свободного места в данном потоке. Это помогает максимально плотно упаковать короткие отгулы в остатки времени после распределения длинных периодов.
Если задача дополняется новыми условиями (например, «Сотрудник А и Сотрудник Б не могут отсутствовать одновременно, так как они взаимозаменяемы»), обычные жадные алгоритмы могут не справиться. В таких случаях задача переходит в разряд Constraint Satisfaction Problem (CSP).
Для решения подобных задач в 1С часто применяют рекурсивный поиск с возвратом (backtracking):
Таким образом, для большинства повседневных задач распределения отгулов достаточно использовать комбинацию предварительной сортировки по длине (LPT) и последовательного заполнения слоев. Это обеспечивает быстрое и достаточно плотное распределение ресурсов в рамках установленного лимита N.