Правдивое планирование работы

Правдивое планирование работ — это механизма решения вариант планирования цеха, задачи основанный на исследовании операций .

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

Проблема правдивого планирования заданий была представлена ​​Нисаном и Роненом в их статье 1999 года о разработке алгоритмических механизмов .

Определения

Есть $n$ рабочие места и $m$ рабочие («м» означает «машина», поскольку проблема связана с планированием заданий для компьютеров). Рабочий $i$ могу сделать работу $j$ вовремя $T_{i,j}$. Если рабочий $i$ назначается набор работ $J_{i}$, то он сможет выполнить их вовремя:

$T_{i}(J_{i})=\sum _{j\in J_{i}}t_{i,j}$

Учитывая распределение $J_{1},\dots ,J_{m}$ рабочих мест для работников. Продолжительность проекта составляет:

$MakeSpan(J_{1},\dots ,J_{n})=\max _{i}{T_{i}(J_{i})}$

Оптимальное распределение — это распределение рабочих мест между работниками, при котором продолжительность рабочего времени минимальна. Минимальный период ремонта обозначается $MinMakeSpan$.

Механизм – это функция, которая принимает на вход матрицу $T$ (время, необходимое каждому работнику для выполнения каждой работы) и возвращает результат:

• Распределение рабочих мест между работниками, $J_{1},\dots ,J_{n}$;
• Оплата каждому работнику, $p_{1},\dots ,p_{n}$.

Полезность работника $i$, согласно такому механизму, это:

$u_{i}=p_{i}-T_{i}(J_{i})$

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

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

Коэффициент аппроксимации механизма – это наибольшее соотношение между $Makespan$ и $MinMakespan$ (чем меньше, тем лучше; коэффициент аппроксимации, равный 1, означает, что механизм оптимален).

Исследование правдивого планирования работы направлено на поиск верхних (положительных) и нижних (отрицательных) границ коэффициентов аппроксимации правдивых механизмов.

Положительная граница – m – механизм VCG

Первое решение, которое приходит на ум, — это механизм VCG , который представляет собой общий правдивый механизм. Для минимизации суммы затрат можно использовать механизм VCG. Здесь мы можем использовать VCG, чтобы найти распределение, которое минимизирует «общую сумму», определяемую как:

$MakeTotal(J_{1},\dots ,J_{n})=\sum _{i}{T_{i}(J_{i})}$

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

Пусть OPT будет распределением, которое минимизирует время обработки. Затем:

$MakeSpan[VCG]\leq MakeTotal[VCG]\leq MakeTotal[OPT]\leq m\cdot MakeSpan[OPT]$

(где последнее неравенство следует из принципа «ячейки» ). Следовательно, коэффициент аппроксимации решения ВКГ не превосходит $m$ – количество рабочих.

Следующий пример показывает, что коэффициент аппроксимации решения VCG действительно может быть точно $m$. Предположим, есть $n=m$ Вакансии и график работы работников следующие:

• Рабочий 1 может выполнить любую работу за время 1.
• Остальные работники могут выполнить любую работу вовремя. $1+\epsilon$, где $\epsilon >0$ является небольшой константой.

Затем механизм VCG распределяет все задачи работнику 1. И «общая сумма», и период выполнения равны $n=m$. Но когда каждая работа назначается отдельному работнику, продолжительность рабочего времени $1+\epsilon$.

Коэффициент аппроксимации $m$ не очень хорош, и многие исследователи пытались улучшить его в последующие годы.

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

Отрицательная граница – 2

Коэффициент аппроксимации каждого истинного детерминированного механизма равен не менее 2.

Доказательство типично для нижних оценок в конструкции механизмов. Мы проверяем конкретные сценарии (в нашем случае конкретные тайминги воркеров). По правде говоря, когда один рабочий меняет свое заявление, он не должен иметь от этого никакой выгоды. Это накладывает некоторые ограничения на распределения, возвращаемые механизмом в различных сценариях.

В следующем наброске доказательства для простоты мы предполагаем, что имеется 2 рабочих и что количество рабочих мест четное: $n=2k$. Мы рассматриваем следующие сценарии:

1. Тайминги обоих рабочих для всех заданий равны 1. Поскольку механизм детерминирован, он должен возвращать уникальное распределение. $J_{1},J_{2}$. Предположим, не ограничивая общности, что $|J_{1}|\leq |J_{2}|$ (работнику 1 назначено не более столько же рабочих мест, сколько работнику 2).
2. Время прибытия рабочего 1 на рабочие места в $J_{1}$ являются $\epsilon$ (очень маленькая положительная константа); время рабочего 1 на рабочие места в $J_{2}$ являются $1+\epsilon$; и время выполнения всех заданий работником 2 по-прежнему равно 1. Рабочий 1 знает, что, если он солжет и скажет, что его время выполнения всех заданий равно 1, (детерминированный) механизм распределит ему задания в $J_{1}$ и его стоимость будет очень близка к 0. Чтобы оставаться правдивым, механизм должен делать то же самое и здесь, чтобы рабочий 1 не выигрывал от лжи. Однако продолжительность рабочего времени можно уменьшить вдвое, разделив рабочие места на $J_{2}$ поровну между агентами.

Следовательно, коэффициент аппроксимации механизма должен быть не менее 2.

Монотонность и правдивость

Рассмотрим частный случай планирования Uniform-machines , в котором рабочие являются однопараметрическими: для каждого работника существует скорость, а время, необходимое работнику для выполнения работы, равно длине задания, деленной на скорость. Скорость — это личная информация работника, и мы хотим стимулировать машины раскрывать свою истинную скорость. Арчер и Тардос докажите, что алгоритм планирования истинен тогда и только тогда, когда он монотонен . Это означает, что если машина сообщает о более высокой скорости, а все остальные входные данные остаются прежними, то общее время обработки, выделенное машине, незначительно увеличивается. Для этой проблемы:

• Аулетта, Де Приско, Пенна и Персиано представил монотонный алгоритм с 4 приближениями, который работает за политайм при фиксированном количестве машин.
• Амбросио и Аулетта доказал, что алгоритм наибольшего времени обработки является монотонным, когда скорости машины являются степенями некоторого c ≥ 2, но не когда c ≤ 1,78. Напротив, планирование списков не является монотонным для c > 2.
• Андельман, Азар и Сорани представил монотонный алгоритм с 5 приближениями, который работает в политайме, даже когда количество машин варьируется.
• Ковач представил 3-приближенный монотонный алгоритм.