Подписаться

Правдивое планирование заданий

Последняя правка сделана 2021-06-11 13:03:41 Править

Правдиво планирование заданий - это разработка механизма вариант задачи планирования цеха из исследования операций.

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

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

Содержание

  • 1 Определения
  • 2 Положительная граница - m - Механизм VCG
  • 3 Отрицательная граница - 2
  • 4 Ссылки

Определения

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

T i (J i) = ∑ j ∈ J iti, j {\ displaystyle T_ {i} (J_ {i}) = \ sum _ {j \ in J_ {i}} t_ {i, j} }{\ displaystyle T_ {i} (J_ {i}) = \ sum _ {j \ в J_ {i}} t_ {i, j}}

Учитывая распределение J 1,…, J m {\ displaystyle J_ {1}, \ dots, J_ {m}}{\ displaystyle J_ {1}, \ точки, J_ {m}} рабочих мест для работников, делает период проекта:

M ake S pan (J 1,..., J n) = max i T i (J i) {\ displaystyle MakeSpan (J_ {1}, \ dots, J_ {n}) = \ max _ {i} {T_ {i} (J_ {i})}}{\ displaystyle MakeSpan (J_ {1}, \ dots, J_ { n}) = \ max _ {i} {T_ {i} (J_ {i})}}

Оптимальное распределение - это распределение заданий между рабочими, в котором время изготовления минимизировано. Минимальное время изготовления обозначается M в M ake S pan {\ displaystyle MinMakeSpan}{\ displaystyle MinMakeSpan} .

Механизм - это функция, которая принимает в качестве входных данных матрицу T {\ displaystyle T}T ( время, необходимое каждому рабочему для выполнения каждого задания) и возвращается в виде вывода:

  • Распределение заданий по рабочим, J 1,…, J n {\ displaystyle J_ {1}, \ dots, J_ {n} }{\ displaystyle J_ {1}, \ dots, J_ {n}} ;
  • Выплата каждому работнику, p 1,…, pn {\ displaystyle p_ {1}, \ dots, p_ {n}}{\ displaystyle p_ {1}, \ dots, p_ {n}} .

Полезность работника i {\ displaystyle i }i при таком механизме:

ui = pi - T i (J i) {\ displaystyle u_ {i} = p_ {i} -T_ {i} (J_ {i}) }{\ displaystyle u_ {i} = p_ {i} -T_ {i} (J_ {i})}

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

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

Коэффициент приближения механизма - это наибольшее соотношение между M akespan {\ displaystyle Makespan}{\ displaystyle Ma kespan} и M akespan {\ displaystyle MinMakespan}{\ displaystyle MinMakespan} (чем меньше, тем лучше; коэффициент приближения 1 означает, что механизм оптимален).

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

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

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

M ake T otal (J 1,…, J n) = ∑ i T i (J i) {\ displaystyle MakeTotal (J_ {1}, \ dots, J_ {n}) = \ sum _ {i} {T_ {i} (J_ {i})}}{\ displaystyle MakeTotal (J_ {1}, \ dots, J_ {n}) = \ sum _ {i} {T_ {i} (J_ {i})}}

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

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

Создать панораму [VCG] ≤ M ake T otal [VCG] ≤ M ake T otal [OPT] ≤ m ⋅ M ake S pan [OPT] {\ displaystyle MakeSpan [VCG] \ leq MakeTotal [VCG ] \ leq MakeTotal [OPT] \ leq m \ cdot MakeSpan [OPT]}{ \ displaystyle MakeSpan [VCG] \ leq MakeTotal [VCG] \ leq MakeTotal [OPT] \ leq m \ cdot MakeSpan [OPT]}

(где последнее неравенство следует из принципа голубятни ). Следовательно, коэффициент аппроксимации решения VCG составляет не более m {\ displaystyle m}m - количество рабочих.

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

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

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

Коэффициент приближения m {\ displaystyle m}m не очень хорошо, и многие исследователи пытались улучшить его в последующие годы.

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

Отрицательная оценка - 2

Фактор приближения каждого правдивого детерминированного механизма составляет не менее 2.

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

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

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

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

Ссылки

Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: mail@alphapedia.ru
Соглашение
О проекте
Список материалов:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26