정확한 작업 스케줄링

진실된 작업 스케줄링은 작업 연구에서의 작업 숍 스케줄링 문제의 메커니즘 설계 변형입니다.

우리는 몇 가지 "작업"(작업)으로 구성된 프로젝트를 가지고 있습니다.일꾼이 몇 명 있어요.작업자마다 모든 작업을 수행할 수 있지만 작업자마다 작업 완료에 걸리는 시간이 다릅니다.우리의 목표는 프로젝트의 총 제작 시간을 최소화할 수 있도록 직원들에게 일자리를 할당하는 것입니다.표준 잡샵 스케줄링 문제에서는 모든 작업자의 타이밍이 알려져 있기 때문에 표준 최적화 문제가 있습니다.반면, 진실된 작업 스케줄링 문제에서는 작업자의 타이밍을 알 수 없습니다.각 작업자에게 작업 시간을 묻지만, 작업자가 거짓말을 할 수도 있습니다.따라서, 우리는 근로자들에게 일정 금액을 지불함으로써 그들의 진정한 타이밍을 알려주도록 동기를 부여해야 한다.과제는 인센티브 호환 가능한 지급 메커니즘을 설계하는 것이다.

Nisan과 Ronen은 알고리즘 메커니즘 ^[1]설계에 관한 1999년 논문에서 진실된 작업 스케줄링 문제를 소개했습니다.

정의들

$작업에는$ n개의 $n$ 작업 $m개$ 의 $m$ $작업자$ 가 $있습니다$ ("m"은 "머신"을 나타냅니다. 이는 컴퓨터로의 작업 스케줄에서 문제가 발생하기 때문입니다). $worker$ i(\displaystyle $i)$ 는 $i$ $j$ $T_{i,j}$ $T_{i,j}$ $,$ $T_{i,j}$ (\ $displaystyle T_{i,j$ 에 j $(\$ $displaystyle$ i) $작업$ 을 $수행할$ 수 $있습니다.$ worker i(\ $displaystyle$ i $J_{i}$ 에 $i$ 일련의 $J_{i}$ 이 할당되어 있는 경우 시간 내에 작업을 실행할 수 있습니다.

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

$J_{1},\dots ,J_{m}$ , $(\$ 의 $J_{1},\dots ,J_{m}$ 작업을 작업자에게 $J_{1},\dots ,J_{m}$ 하면 프로젝트의 소요 시간은 다음과 같습니다.

\displaystyle MakeSpan(J_{1},\dots,J_{n})=\max_{i}{T_{i}(J_{i})}}

최적의 할당은 작업자에게 작업을 할당하는 것으로, 작업 소요 시간이 최소화됩니다.최소 makespan은 $Mi$ $n$ M $a$ $k$ $e$ $S$ $p$ a n \ $displaystyle$ MinMakeSpan $}$ 로 $MinMakeSpan$ 됩니다.

메커니즘은 $매트릭스$ T $(각 작업자$ 가 각 작업을 수행해야 하는 시간) $T$ 를 입력으로 받아 출력으로 반환하는 함수입니다.

작업자에 대한 작업 할당( $J_{1},\dots ,J_{n}$ 1, $J_{1},\dots ,J_{n}$ $J_{1},\dots ,J_{n}$ n { $displaystyle J_{1},\dots, J_{n$
$p_{1},\dots ,p_{n}$ 워커(p 1, $p_{1},\dots ,p_{n}$ $p_{1},\dots ,p_{n}$ { $displaystyle p_{1},\dots,p_{n$ 에 대한 지불.

이러한 메커니즘 하에서 $worker$ i $displaystyle$ i의 유틸리티는 다음과 같습니다.

\displaystyle u_{i}=p_{i}-T_{i}(J_{i})

즉, 에이전트는 지불은 얻지만 작업 실행에 소요되는 시간은 손실됩니다.급여와 시간은 동일한 단위로 측정된다는 점에 유의하십시오(예: 급여는 달러로 계산되며 시간 단위당 근로자에게 1달러의 비용이 든다고 가정할 수 있습니다).

모든 근로자가 자신의 진정한 타이밍 벡터를 보고함으로써 최대 효용을 달성할 수 있는 경우(즉, 어떤 근로자도 자신의 타이밍에 대해 거짓말을 할 동기가 없다) 메커니즘은 진실(또는 인센티브 호환)이라고 불린다.

메커니즘의 근사 계수는 M $a$ k $e$ $p$ $a$ $n$ n \ $displaystyle$ $Makespan$ $\$ $\min$ $makespan$ $MinMakespan$ \ $displaystyle$ \（ min $Makespan$ \ displaystyle ）의 $최대$ 비율입니다(작은 것이 좋습니다.근사 계수가 1이면 메커니즘이 최적임을 의미합니다).

진실한 작업 스케줄링에 대한 연구는 진실한 메커니즘의 근사 인자에 대한 상한(양)과 하한(음)을 찾는 것을 목표로 한다.

플러스 바운드– m – VCG 메커니즘

가장 먼저 떠오르는 해결책은 VCG 메커니즘입니다. VCG 메커니즘은 일반적인 진실 메커니즘입니다.VCG 메커니즘을 사용하여 비용 합계를 최소화할 수 있습니다.여기서는 VCG를 사용하여 다음과 같이 정의된 "make-total"을 최소화하는 할당을 찾을 수 있습니다.

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

여기서 합계를 최소화하는 것은 각 작업을 해당 작업에 가장 짧은 시간을 필요로 하는 작업자에게 할당하는 것만으로 가능합니다.이 메커니즘을 진실하게 유지하기 위해, 일을 수락한 각 근로자는 그 일에 대해 두 번째로 짧은 시간(빅레이 경매에서처럼)을 지급받는다.

OPT를 제조 시간을 최소화하는 할당으로 합니다.그 후, 다음과 같이 입력합니다.

\displaystyle MakeSpan [ VCG ]\leq MakeTotal [ VCG ]\leq MakeTotal [OPT]\leq m\cdot Make Span[OPT]}

(여기서 마지막 부등식은 비둘기구멍 원칙에서 비롯된다.)따라서 VCG 솔루션의 근사 계수는 $최대$ m ${displaystyle$ m $}($ 종업원 수)입니다.

다음 예시는 VCG 솔루션의 근사 계수가 $정확히$ m ${displaystyle$ m $m$ 임을 나타냅니다.n $n=m$ { $displaystyle$ n $= m$ }개의 $n=m$ 작업이 $n=m$ 워커의 타이밍은 다음과 같습니다.

워커 1은 모든 작업을 시간 1로 수행할 수 있습니다.
다른 워커는 모든 $1+\epsilon$ 을 시간 $1+\epsilon$ $1+\epsilon$ {\(\ $displaystyle$ 1 $+\epsilon$ 로 수행할 수 있습니다. $\epsilon >0$ 서 $\epsilon >0$ $(\displaystyle \epsilon$ > $0)$ 은 $\epsilon >0$ 작은 상수입니다.

다음으로 VCG 메커니즘은 모든 태스크를 워커1에 할당합니다.「make-total」과 makespan은 $n=m$ n $=m입니다.$ 단, 각 작업을 다른 워커에 할당하면 makespan은 1 + $（$ \ $display style$ 1 + \ $silon$ 이 $1+\epsilon$ .

$m의$ 계수는 그다지 좋지 않으며, 그 후 몇 년 동안 많은 연구자들이 이를 개선하기 위해 노력해왔다.

한편, 근사 계수가 너무 작을 수 없다는 것을 증명하는 몇 가지 불가능한 결과도 있습니다.

음의 한계 – 2

모든 진실한 결정론적 메커니즘의 근사 계수는 최소 ^[1]^{: 177-}2이다.

그 증명은 메커니즘 설계의 하한을 대표한다.특정 시나리오(이 경우 워커의 특정 타이밍)를 확인합니다.정직하게 말해서, 한 명의 근로자가 선언을 바꿀 때, 그는 그것으로부터 이익을 얻을 수 없어야 한다.이는 다른 시나리오에서 메커니즘에 의해 반환되는 할당에 대한 몇 가지 제약을 유발합니다.

다음 입증 스케치에서는 단순성을 위해 작업자가 2명이고 작업 수가 짝수인 $n=2k$ $n=2k$ $(\displaystyle$ n $=2k$ 라고 가정합니다. 다음과 같은 시나리오를 고려합니다.

모든 작업에 대한 두 작업자의 타이밍은 1입니다.메커니즘은 결정론적이므로 J1, $(\$ 2 $J_{1},J_{2}$ 를 반환해야 합니다.일반성을 잃지 않고 J1 $|J_{1}|\leq |J_{2}|$ $displaystyle J_{1} \leq$ J_ ${2}$ })( $|J_{1}|\leq |J_{2}|$ 워커 1은 최대 2개의 작업자만큼 $J_{1},J_{2}$ 됩니다).
작업자 1의 작업 $J_{1}$ 은 $J1$ 의 $J_{1}$ 타이밍 $({displaystyle$ $J_{$ $1$ $\epsilon$ 입니다.작업자 1의 작업 타이밍은 $J_{2}$ 의 $J_{2}$ 타이밍은 $+({$ $2})$ 이며 $J_{2}$ , 작업자 2의 작업 타이밍은 여전히 1+({ $displaystyle$ 1 $+\epsilon$ 입니다.근로자 1은 자신이 거짓말을 하고 모든 직업에 대한 타이밍이 1이라고 말하면 (결정론적) 메커니즘에 의해 $J_{1}$ ({ $displaystyle$ J_ ${1$ })의 $J_{1}$ 일자리가 할당되어 비용이 거의 0에 가깝다는 것을 알고 있습니다.진실성을 유지하기 위해서는 여기서도 같은 메커니즘이 필요합니다.그러면 워커 1은 거짓말로부터 이익을 얻지 않게 됩니다.그러나 에이전트 $J_{2}$ 에 J2 $(\$ 의 $J_{2}$ $J_{2}$ 을 균등하게 나누면 제작 시간을 절반으로 늘릴 수 있습니다.

따라서 메커니즘의 근사 계수는 2 이상이어야 한다.

단조로움과 진실성

단일 파라미터로 작업하는 Uniform Machines Scheduling의 특별한 경우를 생각해 봅시다.작업자마다 속도가 있으며 작업자가 작업을 수행하는 데 걸리는 시간은 작업 길이를 속도로 나눈 것입니다.속도는 노동자의 개인 정보입니다.우리는 기계가 진짜 속도를 드러내도록 장려하고 싶습니다.Archer 및^[2] Tardos는 스케줄링 알고리즘이 단조인 경우에만 진실함을 증명합니다.즉, 기계가 더 빠른 속도를 보고하고 다른 모든 입력이 그대로 유지되면 기계에 할당된 총 처리 시간이 약하게 증가합니다.이 문제의 경우:

Auletta, De Prisco, Penna 및 Persiano는^[3] 기계 수가 고정되면 폴리타임으로 실행되는 4 근사 모노톤 알고리즘을 제시했습니다.
Ambrosio와 Auletta는^[4] 기계 속도가 c 2 2의 거듭제곱일 때 최장 처리 시간 알고리즘이 단조롭다는 것을 증명했지만 c 78 1.78일 때는 그렇지 않았다.반대로 리스트 스케줄링은 c >2의 경우 모노톤이 아닙니다.
안델만, 아자르, 소라니^[5] 등은 기계 수가 변동하더라도 폴리타임으로 실행되는 5개 근사 모노톤 알고리즘을 제시했다.
Kovacz는^[6] 3 근사 모노톤 알고리즘을 제시했다.

레퍼런스

^ ^a ^b Nisan, Noam; Ronen, Amir (2001). "Algorithmic Mechanism Design". Games and Economic Behavior. 35 (1–2): 166–196. doi:10.1006/game.1999.0790.
^ Archer, A.; Tardos, E. (2001-10-01). "Truthful mechanisms for one-parameter agents". Proceedings 42nd IEEE Symposium on Foundations of Computer Science: 482–491. doi:10.1109/SFCS.2001.959924.
^ Auletta, Vincenzo; De Prisco, Roberto; Penna, Paolo; Persiano, Giuseppe (2004). Diekert, Volker; Habib, Michel (eds.). "Deterministic Truthful Approximation Mechanisms for Scheduling Related Machines". STACS 2004. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer: 608–619. doi:10.1007/978-3-540-24749-4_53. ISBN 978-3-540-24749-4.
^ Ambrosio, Pasquale; Auletta, Vincenzo (2005). Persiano, Giuseppe; Solis-Oba, Roberto (eds.). "Deterministic Monotone Algorithms for Scheduling on Related Machines". Approximation and Online Algorithms. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer: 267–280. doi:10.1007/978-3-540-31833-0_22. ISBN 978-3-540-31833-0.
^ Andelman, Nir; Azar, Yossi; Sorani, Motti (2005). Diekert, Volker; Durand, Bruno (eds.). "Truthful Approximation Mechanisms for Scheduling Selfish Related Machines". STACS 2005. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer: 69–82. doi:10.1007/978-3-540-31856-9_6. ISBN 978-3-540-31856-9.
^ Kovács, Annamária (2005). Brodal, Gerth Stølting; Leonardi, Stefano (eds.). "Fast Monotone 3-Approximation Algorithm for Scheduling Related Machines". Algorithms – ESA 2005. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer: 616–627. doi:10.1007/11561071_55. ISBN 978-3-540-31951-1.

[NisanRonen01-1] Nisan, Noam; Ronen, Amir (2001). "Algorithmic Mechanism Design". Games and Economic Behavior. 35 (1–2): 166–196. doi:10.1006/game.1999.0790.

[2] Archer, A.; Tardos, E. (2001-10-01). "Truthful mechanisms for one-parameter agents". Proceedings 42nd IEEE Symposium on Foundations of Computer Science: 482–491. doi:10.1109/SFCS.2001.959924.

[3] Auletta, Vincenzo; De Prisco, Roberto; Penna, Paolo; Persiano, Giuseppe (2004). Diekert, Volker; Habib, Michel (eds.). "Deterministic Truthful Approximation Mechanisms for Scheduling Related Machines". STACS 2004. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer: 608–619. doi:10.1007/978-3-540-24749-4_53. ISBN 978-3-540-24749-4.

[4] Ambrosio, Pasquale; Auletta, Vincenzo (2005). Persiano, Giuseppe; Solis-Oba, Roberto (eds.). "Deterministic Monotone Algorithms for Scheduling on Related Machines". Approximation and Online Algorithms. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer: 267–280. doi:10.1007/978-3-540-31833-0_22. ISBN 978-3-540-31833-0.

[5] Andelman, Nir; Azar, Yossi; Sorani, Motti (2005). Diekert, Volker; Durand, Bruno (eds.). "Truthful Approximation Mechanisms for Scheduling Selfish Related Machines". STACS 2005. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer: 69–82. doi:10.1007/978-3-540-31856-9_6. ISBN 978-3-540-31856-9.

[6] Kovács, Annamária (2005). Brodal, Gerth Stølting; Leonardi, Stefano (eds.). "Fast Monotone 3-Approximation Algorithm for Scheduling Related Machines". Algorithms – ESA 2005. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer: 616–627. doi:10.1007/11561071_55. ISBN 978-3-540-31951-1.

[1]

[2]

[3]

[4]

[5]

[6]

Search

정확한 작업 스케줄링

네임스페이스

더

목차

정의들

플러스 바운드– m – VCG 메커니즘

음의 한계 – 2

단조로움과 진실성

레퍼런스