Планирование сотрудников с запросами на смену

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

Проблема становится сложнее по нескольким причинам:

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

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

Постановка задачи

• Каждый день разделен на три смены по 8 часов;
• Каждый день за каждой сменой закреплена одна медсестра, и ни одна медсестра не работает более одной смены;
• Количество медсестер увеличось с 4 до 5;
• Количество дней увеличилось с 3 до 7.
• Необходимо равномерно распределить смены;
• Необходимо максимально удовлетворить запросы медсестер на конкретные смены.

Решение задачи

1. Выбор модели

В этой задаче, как и в предыдущей, используется модель ограничений. Причина выбора остаётся прежней, как в базовом варианте: бинарные решения «назначен/не назначен» и логические ограничения (покрытие, равномерность). Новое отличие — целевая функция по заявкам, что естественно формулируется линейным выражением поверх булевых переменных.

2. Создание модели

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

// создаем модель ограничений
Модель = О2
    .Модели()
    .МодельОграничений()
    .СоздатьМодель();

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

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

// Вводим данные
КоличествоМедсестер = 5;
КоличествоСмен      = 3;
КоличествоДней      = 7;

// Запросы медсестер на смены
Запросы = Новый Массив(КоличествоМедсестер);
Для Медсестра = 0 По КоличествоМедсестер - 1 Цикл
    Запросы[Медсестра] = Новый Массив(КоличествоДней);
    Для День = 0 По КоличествоДней - 1 Цикл
        Запросы[Медсестра][День] = Новый Массив(КоличествоСмен);
        Для Смена = 0 По КоличествоСмен - 1 Цикл
            Запросы[Медсестра][День][Смена] = 0;
        КонецЦикла;
    КонецЦикла;
КонецЦикла;

// Медсестра 0
Запросы[0][0][2] = 1;  // День 0, Смена 2
Запросы[0][4][2] = 1;  // День 4, Смена 2
Запросы[0][5][1] = 1;  // День 5, Смена 1
Запросы[0][6][2] = 1;  // День 6, Смена 2

// Медсестра 1
Запросы[1][2][1] = 1;  // День 2, Смена 1
Запросы[1][3][1] = 1;  // День 3, Смена 1
Запросы[1][4][0] = 1;  // День 4, Смена 0
Запросы[1][6][2] = 1;  // День 6, Смена 2

// Медсестра 2
Запросы[2][0][1] = 1;  // День 0, Смена 1
Запросы[2][1][1] = 1;  // День 1, Смена 1
Запросы[2][3][0] = 1;  // День 3, Смена 0
Запросы[2][5][1] = 1;  // День 5, Смена 1

// Медсестра 3
Запросы[3][0][2] = 1;  // День 0, Смена 2
Запросы[3][2][0] = 1;  // День 2, Смена 0
Запросы[3][3][1] = 1;  // День 3, Смена 1
Запросы[3][5][0] = 1;  // День 5, Смена 0

// Медсестра 4
Запросы[4][1][2] = 1;  // День 1, Смена 2
Запросы[4][2][1] = 1;  // День 2, Смена 1
Запросы[4][4][0] = 1;  // День 4, Смена 0
Запросы[4][5][1] = 1;  // День 5, Смена 1

Массив Запросы представляет собой трехмерную матрицу предпочтений медсестер, где:

• Первый индекс - [НомерМедсестры] - идентификатор медсестры;
• Второй индекс - [НомерДня] - день недели;
• Третий индекс - [НомерСмены] - номер смены.

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

4. Регистрация переменных

Структура переменных идентична базовому варианту — трёхмерный массив булевых переменных для назначений.

// Регистрируем переменные: назначение медсестёр по дням и сменам
СменыМедсестер = Новый Массив(КоличествоМедсестер);
Для Медсестра = 0 По КоличествоМедсестер - 1 Цикл
    СменыМедсестер[Медсестра] = Новый Массив(КоличествоДней);
    Для День = 0 По КоличествоДней - 1 Цикл
        // булевы переменные на все смены этого дня для данной медсестры
        СменыМедсестер[Медсестра][День] = Модель.МассивБулевыхПеременных(КоличествоСмен);
    КонецЦикла;
КонецЦикла;

5. Описание ограничений

Все три группы ограничений из базового варианта сохраняются без изменений.

Ни более одной смены в день.

// Каждая медсестра работает не более одной смены в день
Для Медсестра = 0 По КоличествоМедсестер - 1 Цикл
    Для День = 0 По КоличествоДней - 1 Цикл
        Модель.Ограничения().НиБолееОдного(СменыМедсестер[Медсестра][День]);
    КонецЦикла;
КонецЦикла;

Полное покрытие всех смен.

// Каждая смена в каждый день закрыта ровно одной медсестрой
Для День = 0 По КоличествоДней - 1 Цикл
    Для Смена = 0 По КоличествоСмен - 1 Цикл
        МедсестрыНаСмену = Новый Массив;
        Для Медсестра = 0 По КоличествоМедсестер - 1 Цикл
            МедсестрыНаСмену.Добавить(СменыМедсестер[Медсестра][День][Смена]);
        КонецЦикла;
        Модель.Ограничения().ТолькоОдин(МедсестрыНаСмену);
    КонецЦикла;
КонецЦикла;

Равномерная нагрузка по сменам.

// Равномерная нагрузка по сменам
ВсегоСмен                  = КоличествоСмен * КоличествоДней;
МинимальноСменНаМедсестру  = Цел(ВсегоСмен / КоличествоМедсестер);
Остаток                    = ВсегоСмен % КоличествоМедсестер;
МаксимальноСменНаМедсестру = ?(Остаток = 0, МинимальноСменНаМедсестру, МинимальноСменНаМедсестру + 1);

Для Медсестра = 0 По КоличествоМедсестер - 1 Цикл
    ВсеСмены = Новый Массив;
    Для День = 0 По КоличествоДней - 1 Цикл
        Для Смена = 0 По КоличествоСмен - 1 Цикл
            ВсеСмены.Добавить(СменыМедсестер[Медсестра][День][Смена]);
        КонецЦикла;
    КонецЦикла;

    СуммаСмен = Модель.Выражения().Сумма(ВсеСмены);
    Модель.Ограничения().ЗначениеБольшеИлиРавно(СуммаСмен, МинимальноСменНаМедсестру);
    Модель.Ограничения().ЗначениеМеньшеИлиРавно(СуммаСмен, МаксимальноСменНаМедсестру);
КонецЦикла;

6. Описание целевой функции

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

// Целевая функция: максимизировать удовлетворенные запросы
Цель = Модель.Выражения().СоздатьПостроительВыражений();
Для Медсестра = 0 По КоличествоМедсестер - 1 Цикл
    Для День = 0 По КоличествоДней - 1 Цикл
        Для Смена = 0 По КоличествоСмен - 1 Цикл
            Если Запросы[Медсестра][День][Смена] = 1 Тогда
                Цель.ДобавитьТерм(СменыМедсестер[Медсестра][День][Смена], 1);
            КонецЕсли;
        КонецЦикла;
    КонецЦикла;
КонецЦикла;

Модель.Максимизировать(Цель.ПолучитьВыражение());

7. Решение модели

Запускается процесс поиска оптимального решения.

// Решение модели
Решение = Модель.Решить();

8. Вывод результатов

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

// Вывод результатов
Если Не Решение.РешениеНайдено() Тогда
    Сообщить("Оптимальное решение не найдено!");
    Возврат;
КонецЕсли;

Сообщение = "График по дням" + Символы.ПС + Символы.ПС;

Для День = 0 По КоличествоДней - 1 Цикл
    Сообщение = Сообщение + СтрШаблон(
        "День %1:%2", 
        День + 1, 
        Символы.ПС
    );
    Для Смена = 0 По КоличествоСмен - 1 Цикл
        Назначенная = -1;
        БылЗапрос   = Ложь;
        Для Медсестра = 0 По КоличествоМедсестер - 1 Цикл
            Если Решение.ЗначениеПеременной(СменыМедсестер[Медсестра][День][Смена]) = 1 Тогда
                Назначенная = Медсестра;
                БылЗапрос   = (Запросы[Медсестра][День][Смена] = 1);
                Прервать;
            КонецЕсли;
        КонецЦикла;

        Если Назначенная >= 0 Тогда
            Метка = ?(
                БылЗапрос, 
                " (запрошено)", 
                " (не запрошено)"
            );
            Сообщение = Сообщение + СтрШаблон(
                "  Смена %1: Медсестра №%2%3%4",
                Смена + 1, 
                Назначенная + 1, 
                Метка, 
                Символы.ПС
            );
        Иначе
            Сообщение = Сообщение + СтрШаблон(
                "  Смена %1: не назначена%2",
                Смена + 1, 
                Символы.ПС
            );
        КонецЕсли;
    КонецЦикла;
    Сообщение = Сообщение + Символы.ПС;
КонецЦикла;

// Нагрузка и статистика по запросам
Сообщение       = Сообщение + "Нагрузка и удовлетворенные запросы" + Символы.ПС;
ВсегоНазначений = КоличествоДней * КоличествоСмен;
Удовлетворено   = 0;

Для Медсестра = 0 По КоличествоМедсестер - 1 Цикл
    СчетчикСмен     = 0;
    СчетчикЗапросов = 0;

    Для День = 0 По КоличествоДней - 1 Цикл
        Для Смена = 0 По КоличествоСмен - 1 Цикл
            Назн = Решение.ЗначениеПеременной(СменыМедсестер[Медсестра][День][Смена]);
            Если Назн = 1 Тогда
                СчетчикСмен = СчетчикСмен + 1;
                Если Запросы[Медсестра][День][Смена] = 1 Тогда
                    СчетчикЗапросов = СчетчикЗапросов + 1;
                КонецЕсли;
            КонецЕсли;
        КонецЦикла;
    КонецЦикла;

    Удовлетворено = Удовлетворено + СчетчикЗапросов;

    Сообщение = Сообщение + СтрШаблон(
        "Медсестра №%1: %2 смен, по запросам: %3%4",
        Медсестра + 1, 
        СчетчикСмен, 
        СчетчикЗапросов, 
        Символы.ПС
    );
КонецЦикла;

Процент   = ?(ВсегоНазначений = 0, 0, (Удовлетворено * 100.0) / ВсегоНазначений);
Сообщение = Сообщение + СтрШаблон(
    "%1%2%3",
    "Всего удовлетворено запросов: " + Удовлетворено + " из " + ВсегоНазначений,
    " (" + Формат(Процент, "ЧДЦ=1; ЧН=0; ЧГ=0") + "%).",
    Символы.ПС
);

Сообщить(Сообщение);

Полный код решения задачи

Ниже представлен полный код решения. Вы также можете скачать пример в виде готовой обработки.

// Создаем объект модели
Модель = О2
    .Модели()
    .МодельОграничений()
    .СоздатьМодель();

// Вводим данные
КоличествоМедсестер = 5;
КоличествоСмен      = 3;
КоличествоДней      = 7;

// Запросы медсестер на смены
Запросы = Новый Массив(КоличествоМедсестер);
Для Медсестра = 0 По КоличествоМедсестер - 1 Цикл
    Запросы[Медсестра] = Новый Массив(КоличествоДней);
    Для День = 0 По КоличествоДней - 1 Цикл
        Запросы[Медсестра][День] = Новый Массив(КоличествоСмен);
        Для Смена = 0 По КоличествоСмен - 1 Цикл
            Запросы[Медсестра][День][Смена] = 0;
        КонецЦикла;
    КонецЦикла;
КонецЦикла;

// Медсестра 0
Запросы[0][0][2] = 1;  // День 0, Смена 2
Запросы[0][4][2] = 1;  // День 4, Смена 2
Запросы[0][5][1] = 1;  // День 5, Смена 1
Запросы[0][6][2] = 1;  // День 6, Смена 2

// Медсестра 1
Запросы[1][2][1] = 1;  // День 2, Смена 1
Запросы[1][3][1] = 1;  // День 3, Смена 1
Запросы[1][4][0] = 1;  // День 4, Смена 0
Запросы[1][6][2] = 1;  // День 6, Смена 2

// Медсестра 2
Запросы[2][0][1] = 1;  // День 0, Смена 1
Запросы[2][1][1] = 1;  // День 1, Смена 1
Запросы[2][3][0] = 1;  // День 3, Смена 0
Запросы[2][5][1] = 1;  // День 5, Смена 1

// Медсестра 3
Запросы[3][0][2] = 1;  // День 0, Смена 2
Запросы[3][2][0] = 1;  // День 2, Смена 0
Запросы[3][3][1] = 1;  // День 3, Смена 1
Запросы[3][5][0] = 1;  // День 5, Смена 0

// Медсестра 4
Запросы[4][1][2] = 1;  // День 1, Смена 2
Запросы[4][2][1] = 1;  // День 2, Смена 1
Запросы[4][4][0] = 1;  // День 4, Смена 0
Запросы[4][5][1] = 1;  // День 5, Смена 1

// Регистрируем переменные: назначение медсестёр по дням и сменам
СменыМедсестер = Новый Массив(КоличествоМедсестер);
Для Медсестра = 0 По КоличествоМедсестер - 1 Цикл
    СменыМедсестер[Медсестра] = Новый Массив(КоличествоДней);
    Для День = 0 По КоличествоДней - 1 Цикл
        // булевы переменные на все смены этого дня для данной медсестры
        СменыМедсестер[Медсестра][День] = Модель.МассивБулевыхПеременных(КоличествоСмен);
    КонецЦикла;
КонецЦикла;

// Каждая медсестра работает не более одной смены в день
Для Медсестра = 0 По КоличествоМедсестер - 1 Цикл
    Для День = 0 По КоличествоДней - 1 Цикл
        Модель.Ограничения().НиБолееОдного(СменыМедсестер[Медсестра][День]);
    КонецЦикла;
КонецЦикла;

// Каждая смена в каждый день закрыта ровно одной медсестрой
Для День = 0 По КоличествоДней - 1 Цикл
    Для Смена = 0 По КоличествоСмен - 1 Цикл
        МедсестрыНаСмену = Новый Массив;
        Для Медсестра = 0 По КоличествоМедсестер - 1 Цикл
            МедсестрыНаСмену.Добавить(СменыМедсестер[Медсестра][День][Смена]);
        КонецЦикла;
        Модель.Ограничения().ТолькоОдин(МедсестрыНаСмену);
    КонецЦикла;
КонецЦикла;

// Равномерная нагрузка по сменам
ВсегоСмен                  = КоличествоСмен * КоличествоДней;
МинимальноСменНаМедсестру  = Цел(ВсегоСмен / КоличествоМедсестер);
Остаток                    = ВсегоСмен % КоличествоМедсестер;
МаксимальноСменНаМедсестру = ?(Остаток = 0, МинимальноСменНаМедсестру, МинимальноСменНаМедсестру + 1);

Для Медсестра = 0 По КоличествоМедсестер - 1 Цикл
    ВсеСмены = Новый Массив;
    Для День = 0 По КоличествоДней - 1 Цикл
        Для Смена = 0 По КоличествоСмен - 1 Цикл
            ВсеСмены.Добавить(СменыМедсестер[Медсестра][День][Смена]);
        КонецЦикла;
    КонецЦикла;

    СуммаСмен = Модель.Выражения().Сумма(ВсеСмены);
    Модель.Ограничения().ЗначениеБольшеИлиРавно(СуммаСмен, МинимальноСменНаМедсестру);
    Модель.Ограничения().ЗначениеМеньшеИлиРавно(СуммаСмен, МаксимальноСменНаМедсестру);
КонецЦикла;

// Целевая функция: максимизировать удовлетворенные запросы
Цель = Модель.Выражения().СоздатьПостроительВыражений();
Для Медсестра = 0 По КоличествоМедсестер - 1 Цикл
    Для День = 0 По КоличествоДней - 1 Цикл
        Для Смена = 0 По КоличествоСмен - 1 Цикл
            Если Запросы[Медсестра][День][Смена] = 1 Тогда
                Цель.ДобавитьТерм(СменыМедсестер[Медсестра][День][Смена], 1);
            КонецЕсли;
        КонецЦикла;
    КонецЦикла;
КонецЦикла;

Модель.Максимизировать(Цель.ПолучитьВыражение());

// Решение модели
Решение = Модель.Решить();

// Вывод результатов
Если Не Решение.РешениеНайдено() Тогда
    Сообщить("Оптимальное решение не найдено!");
    Возврат;
КонецЕсли;

Сообщение = "График по дням" + Символы.ПС + Символы.ПС;

Для День = 0 По КоличествоДней - 1 Цикл
    Сообщение = Сообщение + СтрШаблон(
        "День %1:%2", 
        День + 1, 
        Символы.ПС
    );
    Для Смена = 0 По КоличествоСмен - 1 Цикл
        Назначенная = -1;
        БылЗапрос   = Ложь;
        Для Медсестра = 0 По КоличествоМедсестер - 1 Цикл
            Если Решение.ЗначениеПеременной(СменыМедсестер[Медсестра][День][Смена]) = 1 Тогда
                Назначенная = Медсестра;
                БылЗапрос   = (Запросы[Медсестра][День][Смена] = 1);
                Прервать;
            КонецЕсли;
        КонецЦикла;

        Если Назначенная >= 0 Тогда
            Метка = ?(
                БылЗапрос, 
                " (запрошено)", 
                " (не запрошено)"
            );
            Сообщение = Сообщение + СтрШаблон(
                "  Смена %1: Медсестра №%2%3%4",
                Смена + 1, 
                Назначенная + 1, 
                Метка, 
                Символы.ПС
            );
        Иначе
            Сообщение = Сообщение + СтрШаблон(
                "  Смена %1: не назначена%2",
                Смена + 1, 
                Символы.ПС
            );
        КонецЕсли;
    КонецЦикла;
    Сообщение = Сообщение + Символы.ПС;
КонецЦикла;

// Нагрузка и статистика по запросам
Сообщение       = Сообщение + "Нагрузка и удовлетворенные запросы" + Символы.ПС;
ВсегоНазначений = КоличествоДней * КоличествоСмен;
Удовлетворено   = 0;

Для Медсестра = 0 По КоличествоМедсестер - 1 Цикл
    СчетчикСмен     = 0;
    СчетчикЗапросов = 0;

    Для День = 0 По КоличествоДней - 1 Цикл
        Для Смена = 0 По КоличествоСмен - 1 Цикл
            Назн = Решение.ЗначениеПеременной(СменыМедсестер[Медсестра][День][Смена]);
            Если Назн = 1 Тогда
                СчетчикСмен = СчетчикСмен + 1;
                Если Запросы[Медсестра][День][Смена] = 1 Тогда
                    СчетчикЗапросов = СчетчикЗапросов + 1;
                КонецЕсли;
            КонецЕсли;
        КонецЦикла;
    КонецЦикла;

    Удовлетворено = Удовлетворено + СчетчикЗапросов;

    Сообщение = Сообщение + СтрШаблон(
        "Медсестра №%1: %2 смен, по запросам: %3%4",
        Медсестра + 1, 
        СчетчикСмен, 
        СчетчикЗапросов, 
        Символы.ПС
    );
КонецЦикла;

Процент   = ?(ВсегоНазначений = 0, 0, (Удовлетворено * 100.0) / ВсегоНазначений);
Сообщение = Сообщение + СтрШаблон(
    "%1%2%3",
    "Всего удовлетворено запросов: " + Удовлетворено + " из " + ВсегоНазначений,
    " (" + Формат(Процент, "ЧДЦ=1; ЧН=0; ЧГ=0") + "%).",
    Символы.ПС
);

Сообщить(Сообщение);

  Скачать пример