작업 스케줄링 게임

이 기사는 고아입니다. 다른 기사는 연결되어 있지 않습니다.관련 기사에서 이 페이지에 대한 링크를 소개하십시오. 제안을 보려면 링크 찾기 도구를 사용하십시오. (2016년 10월)

게임 이론에서, 작업 스케줄링 게임(job scheduling game)은 다수의 이기적인 사용자가 다수의 프로세싱 머신을 활용하고자 하는 시나리오를 모델링하는 게임입니다.각 사용자는 단일 작업을 가지고 있으며 이 작업을 처리할 단일 시스템을 선택해야 합니다.각 사용자의 동기는 가능한 한 빨리 작업을 실행하는 것입니다.

정의.

작업 스케줄링 게임은$$M({$displaystyle$ M$}$개의$$ $시스템$과$$N({$displaystyle$N}개의$$ 작업)이 $지정$된 문제 집합입니다.각 작업 i{displaystyle i}는 각 기계의 크기에 해당하는 벡터 파이 = (pi 1 , . . , pim ) {\displaystyle p_{i}=(p_{i}^{m}}})와 연관되어 있습니다(즉, pij {displaystyle p_{i}^{j}).플레이어는 직업에 해당합니다.각 플레이어의 전략 세트는 기계 세트입니다.각 플레이어에 대한 전략이 주어지면 각 시스템의 총 부하는 해당 시스템을 선택한 작업의 처리 시간 합계입니다.일반적으로 각 플레이어는 선택한 기계의 총 부하를 최소화하려고 합니다.표준 목표 기능은 가장 많이 로드된 기계의 총 부하를 최소화하는 것입니다(이 목표를 makespan minimization이라고 함)

예를 들어, 2대의 기계 M1과 M2, 2개의 작업 J1과 J2가 있는 게임이 주어집니다.행은 J1 작업이 선택할 수 있는 전략을 나타내고 열은 J2 작업이 선택할 수 있는 전략을 나타냅니다.

J1/J2	M1	M2
M1	(1,10)	(10,10)
M2	(1,1)	(10,1)

동기

일부 글로벌 목표 기능을 최적화하는 방식으로 여러 기계 간에 여러 작업을 나누는 문제는 잘 알려져 있으며 컴퓨터 과학에서 널리 연구되어 왔습니다.이러한 유형의 문제에는 컴퓨터에 작업을 할당하는 중앙 설계자가 있으며 모든 참여 엔티티는 프로토콜을 준수하는 것으로 가정됩니다.하지만, 인터넷의 등장 이후, 분산된 환경의 문제들도 연구되어 왔습니다.이러한 유형의 문제에서는 다른 전략적 주체가 다른 기계와 작업을 소유할 수 있으며, 일반적으로 글로벌 목표가 아닌 자체 목표를 최적화하려고 시도합니다.

기본 속성

안정성의 대가는 비효율성을 측정하는 데 사용됩니다.그것은 모든 평형이 비효율적인 게임과 비효율적인 평형이 존재하는 게임을 구별합니다.

모든 작업 일정에 대해 안정성의 게임 가격은 1과 같습니다.

입증: 안정성의 가격은 최상의 내쉬 평형을 OPTimum으로 나눈 값과 같습니다.따라서 안정성 가격 = 1을 증명하기 위해서는 최적이 최상의 내쉬 균형과 같다는 것을 증명하기에 충분합니다.이를 증명하기 위해, 내시 평형에 있는 OPTimum 솔루션이 있다는 것을 증명하는 것으로 충분합니다. OPTimum도 내시 평형이라면 특히 최고의 내시 평형이기 때문입니다.

최적 상태는 가장 로드가 많은 기계일수록 로드가 적을 때입니다.가장 많이 로드된 시스템으로 예약된 각 작업이 다른 시스템으로 이동하지 않는다고 가정합니다.또한 가장 많이 로드된 작업이 아닌 시스템으로 예약된 각 작업은 가장 많이 로드된 시스템으로 이동하지 않습니다.M$($ $스타일$ M$)$ 기계로$$ 최적 상태의 게임이 주어집니다.가장$로드$가 많은 시스템 - $Md${displaystyle M_${d$ $대신$ $({$ $시스템$에서 예약하려는 $작업{\displaystyle }$x({$d})$가 있다고$$ 가정합니다. 이 경우 $작업{\displaystyle }$x({$d})$가 전송된 후,작업$x{\displaystyle }$ {\$displaystyle$ x$$$}$이(가) 변경되기 전 $시스템{\displaystyle {}_{}}$ $({d})$의 로드보다 로드가 작습니다.이는 게임이 OPTimum 상태라는 가정과 모순됩니다.따라서 작업은 가장 로드가 많은 시스템에서 또는 가장 로드가 많은 시스템으로 재할당되지 않습니다.M${\displaystyle }$-$$({$displaystyle$ $M-1})$ $시스템$의 남은 일정과 남은 작업 수($({$ 시스템에 예약된 작업 제외)는 다음과 같습니다.앞서 언급한 것과 동일한 이유로 (새로운) 가장 부하가 높은 기계 또는 (새로운) 가장 부하가 높은 기계로 이동하려는 작업이 없습니다.$유도{\displaystyle }$단계에서 $모든$ M{$displaystyle$ M} 시스템을 통과하면 M${displaystyle$ M$\}$으로 예약된 작업이 있습니다. 이러한 작업은 자신의 시스템에서 이동하려는 것이 아닙니다.즉, 각 직무에 대한 전략은 프로파일에 대한 최선의 대응입니다.즉, 내시 평형 상태에 있는 OPTimum 상태가 있습니다.따라서 안정성의 가격 = 1.

---

무정부 상태의 가격은 최대 사회적 효용과 게임의 균형점의 효용의 차이를 설명하는 게임 이론의 개념입니다.

무정부 상태의 가격이 제한되지 않는 작업 스케줄링 게임이 있습니다.

클레임: 무정부 상태의 가격 =${\displaystyle \mathrm{}}$∞ ${{displaystyle \infty$

증명: 이 게임에서 2개의 기계 M1({1})과 M2({{2}})와 2개의 작업 J1 = 1, K({1}=1, K)와 J2 = K(1), 1({2}=K, 1)이 자연스러운 K>1({displaystyle K>1})인 경우,작업 J 1({displaystyle J_{1}})은 기계 M 1({displaystyle M_{1}})에서 비용은 1이고 기계 K({displaystyle K})입니다$({$ 및 $({$}})는 기계 $({$과 $기계{\displaystyle {}_{}}$ $({$에서 K$({displaystyle$ K$})$의 비용이 $듭니다{\displaystyle }$.OPTimum 상태는 목표 함수가 1이므로 $({$$displaystyle$ $J_$${$$1$})이 $({$로 예약되고 $({$가 $({$로 예약된 $경우$입니다.또한, 가장 나쁜 내쉬 균형은 J1({displaystyle J_{1})이 M2({displaystyle M_{2})로 예약되고 J2({displaystyle J_{2})가 M1({displaystyle M_{1})로 예약되는 경우입니다. 목표 함수가 K({displaystyle K})이기 때문에 J1(J1)이 M2(머신 M2)로 예약되기 때문입니다$eM_{2$$}}:$ 이 기계의 총 $부하는$에서${\displaystyle }$K$$+ ${\displaystyle 1}$({$displaystyle$ K$+1$})로 증가하며 $작업{\displaystyle {}_{}}$ ${\displaystyle {J\mathrm{}}_{}}$2({$displaystyle J_{2$도 마찬가지입니다. 무정부 상태의 가격은 내시 평형을 최적으로 나눈 값과 같으므로 무정부 상태의 가격 =$K{\displaystyle }$({$displaystyle$ K$\})$입니다.이는 모든 $자연{\displaystyle }$ K${displaystyle$ K$}$에 해당하므로 무정부 상태의 가격은 주장된 것처럼 제한되지 않습니다.

외부 링크

• http://www.faculty.idc.ac.il/tami/Papers/approxSE.pdf
• https://www.computer.org/csdl/proceedings/wetice/2007/2879/00/28790251-abs.html
• http://www.computer.org/csdl/proceedings/compeng/2010/3974/00/3974a124-abs.html
• http://rd.springer.com/chapter/10.1007/978-3-642-31724-8_65
• https://patents.google.com/patent/US8671409B2/en