Назначение с бригадами рабочих

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

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

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

Имеется 6 работников и 4 задачи. Работники разделены на две бригады.

• Бригада 1: работники 0, 2, 4;
• Бригада 2: работники 1, 3, 5;
• Для каждой комбинации "работник-задача" известны затраты на выполнение;
• Каждый работник может быть назначен не более чем на одну задачу;
• Каждая задача должна быть выполнена ровно одним работником;
• Каждая бригада может выполнить не более 2 задач;
• Требуется минимизировать суммарные затраты на выполнение всех задач.

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

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

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

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

Инициализируется объект модели ограничений.

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

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

Помимо матрицы затрат, задаётся состав бригад и ограничение на максимальное количество задач для каждой бригады.

// Вводим данные
ЗатратыНаЗадачу = Новый Массив();
ЗатратыНаЗадачу.Добавить("90, 76, 75, 70");
ЗатратыНаЗадачу.Добавить("35, 85, 55, 65");
ЗатратыНаЗадачу.Добавить("125, 95, 90, 105");
ЗатратыНаЗадачу.Добавить("45, 110, 95, 115");
ЗатратыНаЗадачу.Добавить("60, 105, 80, 75");
ЗатратыНаЗадачу.Добавить("45, 65, 110, 95");

// Оцифровываем массивы входных данных с помощью вспомогательной функции
Затраты = Новый Массив(ЗатратыНаЗадачу.Количество());
Для К = 0 По ЗатратыНаЗадачу.Количество() - 1 Цикл
    Затраты[К] = О2.Утилиты().МассивЧиселИзСтроки(ЗатратыНаЗадачу[К]);
КонецЦикла;

Бригада1               = О2.Утилиты().МассивЧиселИзСтроки("0, 2, 4");
Бригада2               = О2.Утилиты().МассивЧиселИзСтроки("1, 3, 5");
МаксимумЗадачНаБригаду = 2;

КоличествоРаботников = Затраты.Количество();
КоличествоЗадач      = Затраты[0].Количество();

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

Структура переменных аналогична базовому варианту — булева переменная для каждой пары (работник, задача).

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

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

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

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

Ограничение на задачи. Каждая задача назначается ровно одному работнику.

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

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

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

Если Бригада2.Количество() > 0 Тогда
    ЗадачиБригады2 = Новый Массив();
    Для Каждого Р Из Бригада2 Цикл
        Для З = 0 По КоличествоЗадач - 1 Цикл
            ЗадачиБригады2.Добавить(РаботникиЗадач[Р][З]);
        КонецЦикла;
    КонецЦикла;
    СуммаЗадачБригады2 = Модель.Выражения().Сумма(ЗадачиБригады2);
    Модель.Ограничения().ЗначениеМеньшеИлиРавно(СуммаЗадачБригады2, МаксимумЗадачНаБригаду);
КонецЕсли;

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

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

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

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

Для получения решения достаточно вызвать метод Решить объекта модели.

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

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

Результаты выводятся с указанием назначений и общей стоимости.

// Вывод результатов
Если Решение.РешениеНайдено() Тогда
    ФорматВывода   = "ЧДЦ=2; ЧН=0; ЧГ=0";
    ЗначениеЗатрат = 0;
    
    Для Р = 0 По КоличествоРаботников - 1 Цикл
        Для З = 0 По КоличествоЗадач - 1 Цикл
            Если Решение.ЗначениеПеременной(РаботникиЗадач[Р][З]) = 1 Тогда
                ЗначениеЗатрат = ЗначениеЗатрат + Затраты[Р][З];
            КонецЕсли;
        КонецЦикла;
    КонецЦикла;
    
    Сообщение = "Оптимальное распределение работников" + Символы.ПС + Символы.ПС;
    Сообщение = Сообщение + СтрШаблон("Общая стоимость: %1%2", Формат(ЗначениеЗатрат, ФорматВывода), Символы.ПС);
    Сообщение = Сообщение + Символы.ПС + "Назначения:" + Символы.ПС;
    
    Для Р = 0 По КоличествоРаботников - 1 Цикл
        Для З = 0 По КоличествоЗадач - 1 Цикл
            Если Решение.ЗначениеПеременной(РаботникиЗадач[Р][З]) = 1 Тогда
                Сообщение = Сообщение + СтрШаблон(
                    "Работник %1 → Задача %2 (затраты: %3)%4",
                    Р,
                    З,
                    Формат(Затраты[Р][З], ФорматВывода),
                    Символы.ПС
                );
            КонецЕсли;
        КонецЦикла;
    КонецЦикла;
    
    Сообщить(Сообщение);
Иначе
    Сообщить("Решение не найдено!");
КонецЕсли;

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

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

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

// Вводим данные
ЗатратыНаЗадачу = Новый Массив();
ЗатратыНаЗадачу.Добавить("90, 76, 75, 70");
ЗатратыНаЗадачу.Добавить("35, 85, 55, 65");
ЗатратыНаЗадачу.Добавить("125, 95, 90, 105");
ЗатратыНаЗадачу.Добавить("45, 110, 95, 115");
ЗатратыНаЗадачу.Добавить("60, 105, 80, 75");
ЗатратыНаЗадачу.Добавить("45, 65, 110, 95");

// Оцифровываем массивы входных данных с помощью вспомогательной функции
Затраты = Новый Массив(ЗатратыНаЗадачу.Количество());
Для К = 0 По ЗатратыНаЗадачу.Количество() - 1 Цикл
    Затраты[К] = О2.Утилиты().МассивЧиселИзСтроки(ЗатратыНаЗадачу[К]);
КонецЦикла;

Бригада1               = О2.Утилиты().МассивЧиселИзСтроки("0, 2, 4");
Бригада2               = О2.Утилиты().МассивЧиселИзСтроки("1, 3, 5");
МаксимумЗадачНаБригаду = 2;

КоличествоРаботников = Затраты.Количество();
КоличествоЗадач      = Затраты[0].Количество();

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

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

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

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

Если Бригада2.Количество() > 0 Тогда
    ЗадачиБригады2 = Новый Массив();
    Для Каждого Р Из Бригада2 Цикл
        Для З = 0 По КоличествоЗадач - 1 Цикл
            ЗадачиБригады2.Добавить(РаботникиЗадач[Р][З]);
        КонецЦикла;
    КонецЦикла;
    СуммаЗадачБригады2 = Модель.Выражения().Сумма(ЗадачиБригады2);
    Модель.Ограничения().ЗначениеМеньшеИлиРавно(СуммаЗадачБригады2, МаксимумЗадачНаБригаду);
КонецЕсли;

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

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

// Вывод результатов
Если Решение.РешениеНайдено() Тогда
    ФорматВывода   = "ЧДЦ=2; ЧН=0; ЧГ=0";
    ЗначениеЗатрат = 0;
    
    Для Р = 0 По КоличествоРаботников - 1 Цикл
        Для З = 0 По КоличествоЗадач - 1 Цикл
            Если Решение.ЗначениеПеременной(РаботникиЗадач[Р][З]) = 1 Тогда
                ЗначениеЗатрат = ЗначениеЗатрат + Затраты[Р][З];
            КонецЕсли;
        КонецЦикла;
    КонецЦикла;
    
    Сообщение = "Оптимальное распределение работников" + Символы.ПС + Символы.ПС;
    Сообщение = Сообщение + СтрШаблон("Общая стоимость: %1%2", Формат(ЗначениеЗатрат, ФорматВывода), Символы.ПС);
    Сообщение = Сообщение + Символы.ПС + "Назначения:" + Символы.ПС;
    
    Для Р = 0 По КоличествоРаботников - 1 Цикл
        Для З = 0 По КоличествоЗадач - 1 Цикл
            Если Решение.ЗначениеПеременной(РаботникиЗадач[Р][З]) = 1 Тогда
                Сообщение = Сообщение + СтрШаблон(
                    "Работник %1 → Задача %2 (затраты: %3)%4",
                    Р,
                    З,
                    Формат(Затраты[Р][З], ФорматВывода),
                    Символы.ПС
                );
            КонецЕсли;
        КонецЦикла;
    КонецЦикла;
    
    Сообщить(Сообщение);
Иначе
    Сообщить("Решение не найдено!");
КонецЕсли;

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