Назначение с размерами задач
Данный вариант расширяет базовую задачу назначения, добавляя понятие объёма или размера задач и ограничения на суммарную нагрузку каждого работника. В реальной практике задачи часто имеют различную трудоёмкость, и каждый сотрудник может выполнить лишь ограниченный объём работы за период. Например, в IT-компании задачи оцениваются в story points или часах, и каждый разработчик имеет недельную пропускную способность в 40 часов.
Такая постановка более реалистична по сравнению с классической задачей назначения, где предполагается, что каждый работник может выполнить только одну задачу. Здесь работник может взять несколько небольших задач или одну крупную, главное — не превысить свою максимальную нагрузку. Это типично для проектного управления, планирования спринтов в agile-разработке, распределения заказов между производственными линиями с различной мощностью.
Постановка задачи
Имеется 10 работников и 8 задач. Каждая задача характеризуется размером (трудоёмкостью).
- Размеры задач: 10, 7, 3, 12, 15, 4, 11, 5;
- Суммарный размер задач каждого работника не должен превышать 15 единиц;
- Каждая задача должна быть выполнена ровно одним работником;
- Требуется минимизировать суммарные затраты на выполнение всех задач;
- Работник может выполнять несколько задач, пока их суммарный размер не превысит максимальную нагрузку.
Решение задачи
1. Выбор модели
Используется линейная смешанно-целочисленная модель (MILP). Задача формулируется через булевы переменные назначения и линейные ограничения на взвешенные суммы, что естественным образом подходит для MILP-решателей.
2. Создание модели
Инициализируется объект линейной смешанно-целочисленной модели.
// Создаем линейную смешанно-целочисленную модель
Модель = О2.Модели()
.ЛинейнаяСмешанноЦелочисленнаяМодель()
.СоздатьМодель();
3. Ввод данных
Помимо матрицы затрат, задаются размеры задач и максимальная нагрузка на работника.
// Вводим данные
ЗатратыНаЗадачу = Новый Массив();
ЗатратыНаЗадачу.Добавить("90, 76, 75, 70, 50, 74, 12, 68");
ЗатратыНаЗадачу.Добавить("35, 85, 55, 65, 48, 101, 70, 83");
ЗатратыНаЗадачу.Добавить("125, 95, 90, 105, 59, 120, 36, 73");
ЗатратыНаЗадачу.Добавить("45, 110, 95, 115, 104, 83, 37, 71");
ЗатратыНаЗадачу.Добавить("60, 105, 80, 75, 59, 62, 93, 88");
ЗатратыНаЗадачу.Добавить("45, 65, 110, 95, 47, 31, 81, 34");
ЗатратыНаЗадачу.Добавить("38, 51, 107, 41, 69, 99, 115, 48");
ЗатратыНаЗадачу.Добавить("47, 85, 57, 71, 92, 77, 109, 36");
ЗатратыНаЗадачу.Добавить("39, 63, 97, 49, 118, 56, 92, 61");
ЗатратыНаЗадачу.Добавить("47, 101, 71, 60, 88, 109, 52, 90");
Затраты = Новый Массив(ЗатратыНаЗадачу.Количество());
Для К = 0 По ЗатратыНаЗадачу.Количество() - 1 Цикл
Затраты[К] = О2.Утилиты().МассивЧиселИзСтроки(ЗатратыНаЗадачу[К]);
КонецЦикла;
РазмерыЗадач = О2.Утилиты().МассивЧиселИзСтроки("10, 7, 3, 12, 15, 4, 11, 5");
МаксимальнаяНагрузка = 15;
КоличествоРаботников = Затраты.Количество();
КоличествоЗадач = Затраты[0].Количество();
4. Регистрация переменных
Структура переменных аналогична базовому варианту — булева переменная для каждой пары (работник, задача).
// Регистрируем булевы переменные для каждой комбинации (работник, задача)
РаботникиЗадач = Новый Массив(КоличествоРаботников);
Для Р = 0 По КоличествоРаботников - 1 Цикл
РаботникиЗадач[Р] = Модель.МассивБулевыхПеременных(КоличествоЗадач);
КонецЦикла;
5. Описание ограничений
Ограничение на нагрузку работников. Суммарный размер задач, назначенных работнику, не должен превышать максимальную нагрузку. Каждая булева переменная умножается на размер соответствующей задачи.
// Ограничение: суммарный размер задач работника не превышает максимальную нагрузку
Для Р = 0 По КоличествоРаботников - 1 Цикл
НагрузкаРаботника = Модель.Выражения().СоздатьПостроительВыражений();
Для З = 0 По КоличествоЗадач - 1 Цикл
НагрузкаРаботника.ДобавитьТерм(РаботникиЗадач[Р][З], РазмерыЗадач[З]);
КонецЦикла;
Модель.Ограничения().ЗначениеМеньшеИлиРавно(НагрузкаРаботника.ПолучитьВыражение(), МаксимальнаяНагрузка);
КонецЦикла;
Ограничение на задачи. Каждая задача должна быть выполнена ровно одним работником.
// Ограничение: каждая задача выполняется ровно одним работником
Для З = 0 По КоличествоЗадач - 1 Цикл
РаботникиНаЗадачу = Новый Массив(КоличествоРаботников);
Для Р = 0 По КоличествоРаботников - 1 Цикл
РаботникиНаЗадачу[Р] = РаботникиЗадач[Р][З];
КонецЦикла;
СуммаРаботников = Модель.Выражения().Сумма(РаботникиНаЗадачу);
Модель.Ограничения().ЗначениеРавно(СуммаРаботников, 1);
КонецЦикла;
6. Описание целевой функции
Целевая функция представляет собой сумму произведений переменных назначения на соответствующие затраты. Использование метода ДобавитьТерм позволяет добавлять слагаемые вида (переменная × коэффициент). Минимизация данной функции обеспечивает поиск назначения с наименьшими общими затратами.
// Целевая функция: минимизируем общие затраты
ОбщиеЗатраты = Модель.Выражения().СоздатьПостроительВыражений();
Для Р = 0 По КоличествоРаботников - 1 Цикл
Для З = 0 По КоличествоЗадач - 1 Цикл
ОбщиеЗатраты.ДобавитьТерм(РаботникиЗадач[Р][З], Затраты[Р][З]);
КонецЦикла;
КонецЦикла;
Модель.Минимизировать(ОбщиеЗатраты.ПолучитьВыражение());
7. Решение модели
Для получения решения достаточно вызвать метод Решить объекта модели.
// Решение модели
Решение = Модель.Решить();
8. Вывод результатов
Результаты выводятся с указанием назначений, затрат и размеров задач:
// Вывод результатов
Если Решение.РешениеНайдено() Тогда
ФорматВывода = "ЧДЦ=2; ЧН=0; ЧГ=0";
ЗначениеЗатрат = Решение.ЗначениеВыражения(ОбщиеЗатраты.ПолучитьВыражение());
Сообщение = "Оптимальное распределение работников" + Символы.ПС + Символы.ПС;
Сообщение = Сообщение + СтрШаблон("Общая стоимость: %1%2", Формат(ЗначениеЗатрат, ФорматВывода), Символы.ПС);
Сообщение = Сообщение + Символы.ПС + "Назначения:" + Символы.ПС;
Для Р = 0 По КоличествоРаботников - 1 Цикл
Для З = 0 По КоличествоЗадач - 1 Цикл
Если Решение.ЗначениеПеременной(РаботникиЗадач[Р][З]) > 0.5 Тогда
Сообщение = Сообщение + СтрШаблон(
"Работник %1 → Задача %2 (затраты: %3, размер: %4)%5",
Р,
З,
Формат(Затраты[Р][З], ФорматВывода),
Формат(РазмерыЗадач[З], ФорматВывода),
Символы.ПС
);
КонецЕсли;
КонецЦикла;
КонецЦикла;
Сообщить(Сообщение);
Иначе
Сообщить("Решение не найдено!");
КонецЕсли;
Полный код решения задачи
Ниже представлен полный код решения задачи. Вы также можете скачать пример в виде готовой обработки.
// Создаем линейную смешанно-целочисленную модель
Модель = О2.Модели()
.ЛинейнаяСмешанноЦелочисленнаяМодель()
.СоздатьМодель();
// Вводим данные
ЗатратыНаЗадачу = Новый Массив();
ЗатратыНаЗадачу.Добавить("90, 76, 75, 70, 50, 74, 12, 68");
ЗатратыНаЗадачу.Добавить("35, 85, 55, 65, 48, 101, 70, 83");
ЗатратыНаЗадачу.Добавить("125, 95, 90, 105, 59, 120, 36, 73");
ЗатратыНаЗадачу.Добавить("45, 110, 95, 115, 104, 83, 37, 71");
ЗатратыНаЗадачу.Добавить("60, 105, 80, 75, 59, 62, 93, 88");
ЗатратыНаЗадачу.Добавить("45, 65, 110, 95, 47, 31, 81, 34");
ЗатратыНаЗадачу.Добавить("38, 51, 107, 41, 69, 99, 115, 48");
ЗатратыНаЗадачу.Добавить("47, 85, 57, 71, 92, 77, 109, 36");
ЗатратыНаЗадачу.Добавить("39, 63, 97, 49, 118, 56, 92, 61");
ЗатратыНаЗадачу.Добавить("47, 101, 71, 60, 88, 109, 52, 90");
Затраты = Новый Массив(ЗатратыНаЗадачу.Количество());
Для К = 0 По ЗатратыНаЗадачу.Количество() - 1 Цикл
Затраты[К] = О2.Утилиты().МассивЧиселИзСтроки(ЗатратыНаЗадачу[К]);
КонецЦикла;
РазмерыЗадач = О2.Утилиты().МассивЧиселИзСтроки("10, 7, 3, 12, 15, 4, 11, 5");
МаксимальнаяНагрузка = 15;
КоличествоРаботников = Затраты.Количество();
КоличествоЗадач = Затраты[0].Количество();
// Регистрируем булевы переменные для каждой комбинации (работник, задача)
РаботникиЗадач = Новый Массив(КоличествоРаботников);
Для Р = 0 По КоличествоРаботников - 1 Цикл
РаботникиЗадач[Р] = Модель.МассивБулевыхПеременных(КоличествоЗадач);
КонецЦикла;
// Ограничение: суммарный размер задач работника не превышает максимальную нагрузку
Для Р = 0 По КоличествоРаботников - 1 Цикл
НагрузкаРаботника = Модель.Выражения().СоздатьПостроительВыражений();
Для З = 0 По КоличествоЗадач - 1 Цикл
НагрузкаРаботника.ДобавитьТерм(РаботникиЗадач[Р][З], РазмерыЗадач[З]);
КонецЦикла;
Модель.Ограничения().ЗначениеМеньшеИлиРавно(НагрузкаРаботника.ПолучитьВыражение(), МаксимальнаяНагрузка);
КонецЦикла;
// Ограничение: каждая задача выполняется ровно одним работником
Для З = 0 По КоличествоЗадач - 1 Цикл
РаботникиНаЗадачу = Новый Массив(КоличествоРаботников);
Для Р = 0 По КоличествоРаботников - 1 Цикл
РаботникиНаЗадачу[Р] = РаботникиЗадач[Р][З];
КонецЦикла;
СуммаРаботников = Модель.Выражения().Сумма(РаботникиНаЗадачу);
Модель.Ограничения().ЗначениеРавно(СуммаРаботников, 1);
КонецЦикла;
// Целевая функция: минимизируем общие затраты
ОбщиеЗатраты = Модель.Выражения().СоздатьПостроительВыражений();
Для Р = 0 По КоличествоРаботников - 1 Цикл
Для З = 0 По КоличествоЗадач - 1 Цикл
ОбщиеЗатраты.ДобавитьТерм(РаботникиЗадач[Р][З], Затраты[Р][З]);
КонецЦикла;
КонецЦикла;
Модель.Минимизировать(ОбщиеЗатраты.ПолучитьВыражение());
// Решение модели
Решение = Модель.Решить();
// Вывод результатов
Если Решение.РешениеНайдено() Тогда
ФорматВывода = "ЧДЦ=2; ЧН=0; ЧГ=0";
ЗначениеЗатрат = Решение.ЗначениеВыражения(ОбщиеЗатраты.ПолучитьВыражение());
Сообщение = "Оптимальное распределение работников" + Символы.ПС + Символы.ПС;
Сообщение = Сообщение + СтрШаблон("Общая стоимость: %1%2", Формат(ЗначениеЗатрат, ФорматВывода), Символы.ПС);
Сообщение = Сообщение + Символы.ПС + "Назначения:" + Символы.ПС;
Для Р = 0 По КоличествоРаботников - 1 Цикл
Для З = 0 По КоличествоЗадач - 1 Цикл
Если Решение.ЗначениеПеременной(РаботникиЗадач[Р][З]) > 0.5 Тогда
Сообщение = Сообщение + СтрШаблон(
"Работник %1 → Задача %2 (затраты: %3, размер: %4)%5",
Р,
З,
Формат(Затраты[Р][З], ФорматВывода),
Формат(РазмерыЗадач[З], ФорматВывода),
Символы.ПС
);
КонецЕсли;
КонецЦикла;
КонецЦикла;
Сообщить(Сообщение);
Иначе
Сообщить("Решение не найдено!");
КонецЕсли;