Задача о назначении минимального количества исполнителей

Задача о назначении минимального количества исполнителей — задача комбинаторной оптимизации в прикладной математике и исследовании операций, в которой требуется выполнить все заданные работы при минимальном числе различных привлечённых исполнителей (работников, экипажей, бригад, ресурсов), соблюдая ограничения компетенций, бюджета и доступности. Задача обобщает задачу о покрытии множества (set cover problem) и имеет сходство с задачей о назначениях (assignment problem), но отличается возможностью назначения одному исполнителю нескольких работ при ограничении общего бюджета на затраты. Множество исполнителей и множество работ могут иметь произвольные размеры; цель — минимизировать число задействованных исполнителей при точном назначении каждой работы ровно одному исполнителю и соблюдении бюджетного ограничения.

В базовой постановке, когда каждому исполнителю разрешено выполнять любое число совместимых задач, задача сводится к задаче покрытия множеств: требуется выбрать минимальное подмножество «наборов возможностей» исполнителей, чьё объединение покрывает все работы. В практических приложениях цель «минимизировать число исполнителей» часто выступает как суррогат минимизации фиксированных затрат (стоимость привлечения экипажа, активизации ресурса, ввода смены). Такой критерий естественным образом приводит к бинарным переменным выбора исполнителей и, как следствие, к моделям целочисленного линейного программирования (ILP) и смешанного целочисленного программирования (MILP).

История и предпосылки

Классические основы

Фундаментальные идеи задачи восходят к классическим задачам комбинаторной оптимизации середины XX века. Задача о назначениях в классической форме (равное число исполнителей и работ, минимизация суммарной стоимости) сформулирована в 1930–1950-х годах; полиномиальный алгоритм решения — венгерский метод — предложен Гарольдом Куном в 1955 году на основе более ранних результатов Дэнеша Кёнига и Йено Эгервари о паросочетаниях в двудольных графах.

Задача о покрытии множества, являющаяся теоретическим фундаментом для задачи о минимальном числе исполнителей, известна с 1960-х годов в контексте задач размещения и комбинаторной оптимизации. Её NP-полнота доказана Ричардом Карпом в 1972 году в рамках 21 NP-полной задачи.

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

Задачи сменного планирования (1970–1990-е)

В 1970–1990-х годах задачи сменного планирования и minimum shift design активно исследовались в контексте транспортной отрасли, здравоохранения и сервисных служб, где требовалось конструировать набор смен и одновременно определять минимальное число работников на смену для покрытия временных требований. В эти же десятилетия в литературе закрепляется термин «workforce sizing and scheduling» для задач определения необходимого числа работников и составления расписаний.

Развитие в 2000–2020-х годах

В 2000-е и 2010-е годы развиваются специализированные постановки: задача минимизации смен (Minimum Shift Design Problem), задачи совместного планирования смен и задач (integrated shift and task scheduling), задачи минимизации числа работников при жёстко заданных временных окнах задач. В последние годы задачи размерирования персонала и минимизации числа исполнителей активно изучаются в транспортной логистике, деповском планировании локомотивных и маневровых бригад, а также в сфере умных систем планирования персонала (intelligent staff scheduling).

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

Теоретические основы

NP-трудность

Задача относится к классу NP-трудных комбинаторных задач, поскольку её подзадача выбора минимального подмножества исполнителей, способных покрыть все работы в рамках бюджета, обобщает NP-полную задачу о покрытии множества. При установке бесконечных затрат на несовместимые пары «исполнитель — работа» и достаточно большом бюджете задача точно совпадает с задачей покрытия множеств.

Из NP-полноты вытекает типичная практика решений: (i) точные методы на основе ILP/MILP применимы к умеренным размерностям и к структурам с сильной релаксацией, (ii) для больших или «плохо обусловленных» экземпляров используются эвристики/метаэвристики и гибридные схемы, (iii) прикладные постановки часто решаются по декомпозиции (разделение на подзадачи выбора/назначения/построения пакетов).

Связь с задачей покрытия множеств

В базовой «компетенционной» модели задано множество работ $U=\{1,\dots ,m\}$ и множество исполнителей $E=\{1,\dots ,n\}$. Для каждого исполнителя $i\in E$ задано множество работ $S_i\subseteq U$, которые он способен выполнить. Требуется выбрать минимальное по мощности множество исполнителей $E^{\prime }\subseteq E$ такое, что:

$\bigcup _{i\in E^{\prime }}{S}_i=U$

то есть каждая работа покрыта хотя бы одним выбранным исполнителем. Во взвешенной версии каждому исполнителю приписывается стоимость $c_i>0$, и минимизируется $\sum _{i\in E^{\prime }}{c}_i$.

Связь с задачей назначения и максимальной одновременной загрузкой

В простейшей однородной постановке, когда все исполнители эквивалентны, а каждая задача характеризуется интервалом времени $[s_i,e_i)$ и требует одного исполнителя, минимальное количество исполнителей эквивалентно максимальному числу попарно пересекающихся задач (maximum concurrency). В этом случае задача сводится к оценке хроматического числа интервального графа или к вычислению максимальной нагрузки по времени. Классический алгоритм решения основан на сортировке временных точек начала и окончания задач и подсчёте максимальной одновременной занятости и обеспечивает полиномиальное время работы $O(n\log n)$.

Связь с частичными порядками

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

Тотальная унимодулярность и полиномиальные случаи

Для ряда структурированных классов задач точное целочисленное решение совпадает с решением линейной релаксации, если матрица ограничений обладает свойством тотальной унимодулярности (totally unimodular, TU) и правая часть целочисленна. Важный достаточный признак TU-структуры для практики планирования: интервальные матрицы (0–1 матрицы, в каждой строке единицы идут подряд) являются тотально унимодулярными. Это связывает частные случаи «назначить минимальное число исполнителей при интервальных ограничениях» с точной разрешимостью через линейное программирование.

Методология

Формальная постановка (модель покрытия множеств)

В общей постановке с бинарными переменными выбора исполнителей и матрицей совместимости $a_{ij}\in \{0,1\}$, формулировка принимает вид:

$\min \sum _{i=1}^n{x}_i\text{при}\sum _{i:j\in S_i}{x}_i\ge 1\mathrm{\forall }j\in U,x_i\in \{0,1\}$

Модель покрытия требований по периодам

При дискретизации времени по периодам $t\in T$ и заданных требованиях по численности $b_t$ для каждого периода, а также заданном множестве допустимых смен $S$, каждая смена $s\in S$ покрывает подмножество периодов $T_s\subseteq T$. Задача минимизации числа исполнителей или смен сводится к модели покрытия:

$\min \sum _{s\in S}{x}_s\text{при}\sum _{s\in S}{a}_{ts}{x}_s\ge b_t,t\in T,x_s\in {\mathbb{\mathbb{Z}}}_{+}$

где $a_{ts}=1$, если смена $s$ покрывает период $t$, и 0 иначе.

Точные методы

Модель ЦЛП решается стандартными ILP-солверами (CPLEX, Gurobi, LPSolve, Excel Solver) методами ветвей и границ, отсечений или их комбинаций. Для малых размерностей ($n,m\le 20\text{–}30$) применим полный перебор подмножеств исполнителей с последующим решением задачи о назначениях внутри подмножества (венгерский алгоритм или транспортная задача). Для умеренных размерностей ($n,m\le 50\text{–}100$) задача решается солверами напрямую.

Жадные алгоритмы для покрытия множеств

Для невзвешенного покрытия множеств стандартный жадный алгоритм на каждом шаге выбирает множество, покрывающее максимальное число ещё не покрытых элементов. Он обеспечивает логарифмическую гарантию: если оптимум использует $k$ множеств и $|U|=n$, то жадный алгоритм выбирает не более $k\ln n$ множеств. Для взвешенного варианта стоимость покрытия ограничивается сверху множителем порядка $\mathrm{\Theta }(\log d)$ от оптимума, где $d$ — максимальный размер множества.

Барьеры аппроксимации

Существуют строгие результаты о трудности улучшения логарифмического порядка аппроксимации: показано, что $(1-o(1))\ln n$ является порогом, ниже которого аппроксимация покрытия множеств не достигается полиномиальными алгоритмами при стандартных предположениях теории сложности.

Колонковая генерация и декомпозиция

При наличии очень большого числа потенциальных смен или расписаний работников применяется колонковая генерация (column generation) и декомпозиция по Данцигу–Вулфу. Мастер-задача обычно представляет собой задачу покрытия, где каждая колонка — допустимое расписание работника, а стоимость — 1 (минимизация числа работников). Подзадача представляет собой модели типа «shortest path» или задачи целочисленного программирования, генерирующие новые колонки с отрицательной приведённой стоимостью. Процедура повторяется до оптимальности релаксации.

Метаэвристики и гибридные методы

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

Двухэтапные подходы

Распространённым является двухэтапный подход: на первом этапе проводится размерирование персонала (определение минимального числа работников), а на втором — детальное назначение работников на конкретные задания, смены и дни. На первом этапе применяются агрегированные модели, статистическая регрессия и симуляция; на втором — детальные ILP-модели для составления расписаний.

Ключевые результаты и эмпирические данные

Результаты для интервальных задач

Для задач с интервальными заданиями минимальное число работников $m^{*}$ равно максимальному числу перекрывающихся задач в любой момент времени. Алгоритм на основе сортировки временных точек работает за $O(n\log n)$ и широко используется в инженерной практике.

Результаты для задачи SMPTSP

В задаче минимизации смен для персонального планирования задач (Shift Minimization Personnel Task Scheduling Problem, SMPTSP) предложены модели целочисленного программирования и процедуры получения нижних границ, протестированные на наборах тестовых данных. Численные эксперименты показали улучшенные нижние границы по сравнению с ранее опубликованными методами.

Результаты для размерирования экипажей

В исследовании двухэтапного подхода к назначению маневровых машинистов в железнодорожном депо построенная регрессионная модель для оценки необходимого количества работников демонстрирует коэффициент детерминации $R^2=0,905$, что означает, что 90,5 % вариации оптимального размера экипажей объясняется включёнными признаками.

Бенчмарки для задачи покрытия множеств

В вычислительной литературе широко используются смешанные наборы тестов. В одном из крупных эмпирических исследований экземпляры группировались в классы: евклидовы/коррелированные задачи (320 экземпляров), задачи расписаний экипажей (16 экземпляров), железнодорожные экземпляры крупного масштаба (7 экземпляров), «hard cost and coverage correlated» (30 экземпляров) и невзвешенные экземпляры (21 экземпляр). Показано, что использование ограниченной постановки (restricted SCP) с опорой на двойственную информацию из LP-релаксации может существенно сократить время решения: для одного из классов задач среднее время уменьшалось с 53,8 с до менее 1 с при среднем разрыве 1,33 %. Отдельный индикатор масштаба «индустриальных» экземпляров — число столбцов порядка $10^6$ при тысячах строк в матрице покрытия.

Классификация задач

Задачи минимизации числа исполнителей классифицируются по нескольким измерениям:

Измерение	Варианты
Структура времени	Непрерывные интервалы; дискретные слоты; многопериодные горизонты
Однородность исполнителей	Однородные (identical workers); гетерогенные (heterogeneous workforce) с различными навыками и производительностью
Структура задач	Одиночные работы; наборы заданий с фиксированным временем начала и окончания; совокупности микрозаданий в рамках смен
Бюджетные ограничения	Без ограничения; с общим бюджетом; с индивидуальными бюджетами исполнителей
Уровень интеграции	Чистое размерирование штата; интегрированное размерирование и планирование (sizing and scheduling); совместное планирование смен и заданий

Применение

Транспорт и логистика

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

Здравоохранение и услуги

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

Производство и сервисные центры

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

Интеллектуальные системы планирования

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

Ограничения и открытые проблемы

• Вычислительная сложность. Большинство формулировок задач минимизации числа исполнителей, включающих реалистичные ограничения (смены, навыки, перерывы, многопериодность), относятся к NP-трудным задачам, что ограничивает возможность получения строгих оптимальных решений для крупных инстансов.
• Аппроксимационные ограничения. Логарифмический порядок гарантии жадных алгоритмов для покрытия множеств согласуется с доказанными порогами трудности аппроксимации. Улучшения обычно достигаются за счёт использования структуры (специальные классы матриц/графов) либо через гибридизацию без строгих универсальных гарантий.
• Ограничения модельных допущений. «Исполнитель покрывает задачу» часто является упрощением: реальные ограничения включают нормативы отдыха, обучение, предпочтения, неравномерность нагрузок.
• Динамическая и стохастическая природа спроса. Большинство классических моделей предполагают детерминированный спрос, тогда как в практических приложениях спрос носит стохастический характер. Необходимы стохастические и робастные модели размерирования.

Перспективы и направления исследований

Направления дальнейших исследований, обозначенные в литературе:

• Разработка аппроксимационных алгоритмов с гарантированным отношением (аналогично set cover $\ln m$-приближению).
• Развитие интегрированных моделей, объединяющих размерирование персонала, планирование смен и назначение задач в единую многоуровневую структуру с учётом неопределённости.
• Стохастические и многоцелевые версии (минимизация числа исполнителей и затрат одновременно, учёт неопределённости бюджета).
• Разработка более эффективных методов декомпозиции и колонковой генерации, адаптированных к крупномасштабным задачам.
• Включение данных о производительности и усталости работников в модели, переход к адаптивным и динамическим подходам.
• Использование методов машинного обучения для предсказания будущих требований к персоналу и интеграции прогнозов в оптимизационные модели.
• Применение метаэвристик (генетические алгоритмы, муравьиные колонии) и машинного обучения для инициализации решений ЦЛП.
• Расширение на задачи маршрутизации, планирования и облачных вычислений (минимизация числа виртуальных машин).
• Применение квантовых алгоритмов для решения комбинаторных задач.

См. также

• Задача о покрытии множества
• Задача о назначениях
• Обобщённая задача о назначениях
• Задача о минимальном вершинном покрытии
• Задача о коммивояжёре

Литература

• Kuhn H. W. The Hungarian method for the assignment problem // Naval Research Logistics Quarterly. — 1955. — Vol. 2. — P. 83–97.
• Karp R. M. Reducibility among Combinatorial Problems // Complexity of Computer Computations. — 1972. — P. 85–103.
• Garey M. R., Johnson D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. — Freeman, 1979.
• Chvátal V. A Greedy Heuristic for the Set-Covering Problem // Mathematics of Operations Research. — 1979. — Vol. 4, No. 3. — P. 233–235.
• Feige U. A Threshold of ln n for Approximating Set Cover // Journal of the ACM. — 1998. — Vol. 45, No. 4. — P. 634–652.
• Ernst A. T., Jiang H., Krishnamoorthy M., Sier D. Staff scheduling and rostering: A review of applications, methods and models // European Journal of Operational Research. — 2004. — 153. — P. 3–27.
• Dantzig G. B., Wolfe P. Decomposition Principle for Linear Programs // Operations Research. — 1960. — 8(1). — P. 101–111.
• Schrijver A. A Course in Combinatorial Optimization. — CWI, 2017.
• Dasgupta S., Papadimitriou C. H., Vazirani U. V. Algorithms. — Draft textbook, 2006.

Ссылки

• https://en.wikipedia.org/wiki/Assignment_problem — Assignment problem (англ. Википедия)
• https://ormm.readthedocs.io/en/latest/mathprog/employee.html — Employee Scheduling Problem (ORMM)