확률적 스케줄링

확률적 스케줄링은 랜덤 처리 시간, 랜덤 만기일, 랜덤 가중치 및 확률적 기계 고장과 같은 랜덤 속성을 포함하는 스케줄링 문제와 관련이 있습니다.주요 응용 분야는 제조 시스템, 컴퓨터 시스템, 통신 시스템, 물류 및 운송, 기계 학습 ^{[citation needed]}등입니다.

서론

확률적 스케줄링 문제의 목적은 총 흐름 시간, 제작 기간 또는 납기일을 놓치는 총 지각 비용을 최소화하는 것과 같은 규칙적인 목표일 수도 있고, 작업 완료에 따른 지연 비용과 지연 비용을 최소화하는 것과 같은 불규칙적인 목표일 수도 있다.혹독한 ^[1]태풍과 같은 참혹한 사건의 발생.

이러한 시스템의 퍼포먼스는 정기적인 퍼포먼스 측정 또는 불규칙한 퍼포먼스 측정으로 평가되며, 시간이 지남에 따라 자원에 대한 작업의 접근을 우선시하기 위해 채택된 스케줄링 정책에 의해 크게 영향을 받을 수 있다.확률적 스케줄링의 목표는 목표를 최적화할 수 있는 스케줄링 정책을 식별하는 것입니다.

확률적 스케줄링 문제는 확률적 작업의 배치 스케줄링에 관한 문제, 멀티 암 밴디트 문제, 큐잉 시스템의^[2] 스케줄링에 관한 문제 등 세 가지 유형으로 분류할 수 있습니다.이 세 가지 유형은 일반적으로 관련된 랜덤 변수의 확률 분포를 미리 알고 있다는 점에서 완전한 정보를 사용할 수 있다고 가정한다.이러한 분포가 완전히 지정되지 않고 관심 있는 랜덤 변수를 모형화하기 위해 경쟁하는 분포가 여러 개 있는 경우 이 문제를 불완전한 정보라고 합니다.베이지안 방법은 불완전한 정보로 확률적 스케줄링 문제를 처리하기 위해 적용되었다.

확률적 작업의 배치 스케줄링

이 클래스의 모델에서는 랜덤 프로세스 시간을 갖는 고정 배치 $n개$ 의 \ $displaystyle$ n개의 $n$ $n$ 이 특정 성능 목표를 최적화하기 위해m개의 $m$ $기계$ 세트에 의해 완료되어야 합니다.

이 클래스에서 가장 간단한 모델은 예상되는 가중치 흐름 시간을 최소화하기 위해 단일 머신에서 $n$ 의 $\displaystyle$ n개의 $n$ 작업 세트를 시퀀싱하는 문제입니다.Job processing times are independent random variables with a general distribution $G_{i}(\cdot )$ with mean $p_{i}$ for job $i$ . Admissible policies must be nonanticipative (scheduling decisions are based on the system's history up to and including the present t time) 및 non preference(작업 처리는 일단 시작되면 완료까지 중단 없이 진행되어야 합니다).

$w_{i}\geq 0$ $w_{i}\geq 0$ 0 { $displaystyle w$ _ { $i$ } \ $geq$ 0 $w_{i}\geq 0$ ≥ 、 q i i {\ {\ {\ idisplay i i {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ $i$ { $displaystyle$ i ${\tilde {C}}_{i}$ 의 단위시간당 발생하는 코스트 레이트를 나타내고 C ${\tilde {C}}_{i}$ ~ ${\tilde {C}}_{i}$ ~i(\ $displaystyle {C})$ 는 ${\tilde {C}}_{i}$ 임의의 완료시간을 나타냅니다.「「 $\Pi$ 「 $display$ style \ $Pi 」$ 는 $\Pi$ 허용되는 모든 정책의 클래스를 나타내고, E $E_{\pi }[\cdot ]$ 「 [ $]($ 「 $display style$ E _ { \ $pi }[$ \ $cdot$ ])는 $E_{\pi }[\cdot ]$ $\pi \in \Pi$ 「 $\pi \in \Pi$ 」( 「 \ $display style$ \ pi \ $in$ \ Pi $\pi \in \Pi$ 의 기대를 나타냅니다.문제는 다음과 같습니다.

\displaystyle \min \pi \in \Pi }w_{1}E_{\pi }[{\tilde {C}_{1}]+\cdots +w_{n}E_{\pi }[{\tilde {C}}_{n}}]}

특별한 결정론적 경우 최적의 솔루션은 ^[3]Smith의 Shortest Weighted Processing Time 규칙: pii $\$ }\display ${$ p_i} priority $w_{i}p_{i}$ 의 비증강 순서로 작업을 시퀀싱한다.스미스 법칙의 자연적 확장 또한 위의 확률적 ^[4]모델에 최적이다.

모든 직업은nondecreasing 위험률 함수와 공통 일반적인 처리 시간 분포되어 있다 일반적으로, 짧은 것으로 예상되어 처리 시간 일자리에 더 중점을 할당한 규칙을flowtime 객관적으로 다음과 같은 가정에 모든 그 일 처리 시간 분배 지수,[5];[6]a가 최적이다알몬드 when 작업 처리 시간 분포는 확률적으로 ^[7]정렬됩니다.

멀티 암 밴디트 문제

멀티 암 밴디트 모델은 최적의 자원 할당의 특정 유형(통상 시간 할당으로 작업)을 형성합니다.이 유형에서는 다수의 머신 또는 프로세서가 일련의 경쟁 프로젝트(암이라고 함)에 할당됩니다.전형적인 프레임워크에서 시스템은 단일 기계와 확률적으로 독립적인 프로젝트 세트로 구성되며, 랜덤 보상은 서비스될 때 연속적으로 또는 특정 이산 시점에 기여합니다.목표는 동적으로 재검증 가능한 모든 ^[1]정책에 대해 예상되는 할인된 총 보상을 최대화하는 것입니다.

다중 밴디트 문제의 첫 번째 버전은 로빈스(1952)^[8]에 의해 순차 설계 영역에서 공식화되었다.그 이후로, 기틴스와 그의 협력자들이 마르코프 및 반마르코프 환경에서 ^[9]기틴스와 존스, ^[10]기틴스와 글래즈브룩,^[11] ^[12]휘틀에서 유명한 연구 성과를 올리기 전까지는 20년 동안 어떠한 본질적인 진보도 없었다.이 초기 모델에서 각 암은 상태 천이를 하는 시점이 결정 에폭인 마르코프 또는 반마르코프 프로세스에 의해 모델링된다.기계는 각 에폭에서 처리 중인 암의 현재 상태에 대한 함수로 표현되는 보상과 함께 사용할 암을 선택할 수 있으며, 솔루션은 암의 상태에만 의존하는 각 상태에 할당된 할당 지수로 특징지어집니다.따라서 이러한 지수는 Gittins 지수라고 하며, 그의 평판이 좋은 기여로 인해 최적의 정책은 Gittins 지수 정책이라고 한다.

기틴스의 주요 논문 직후, 확률적 도착 모델로의 분기 도적 문제 확장(오픈 도적 또는 팔 획득 도적 문제로도 알려져 있음)은 Whittle(1981)^[13]에 의해 조사되었다.다른 확장해 강도의 모델에서 각각의 팔이 초조하게 두가지 다른 메커니즘에 따라(아이들 패션과 바쁜 패션)진화함에 따라 위 틀은(1988년)[14], 그리고 반 Oyen 때 무기 incurs 간을 전환이 지수 정책 최적이라고 보여 주고(알.(1992년)[15]에 의해 교환 costs/delays을 모델에 의해 공식화된 포함한다. costs/d점등하다

큐잉 시스템 스케줄링

이 클래스의 모델은 큐잉 시스템에서 최적의 서비스 규율을 설계하는 문제와 관련되어 있습니다.큐잉 시스템에서는 완료해야 할 작업이 처음부터 사용할 수 있는 것이 아니라 시간이 지남에 따라 랜덤 에폭에 도달합니다.이 설정의 주요 모델은 MQN(멀티 클래스 큐잉 네트워크)으로 컴퓨터 통신 및 제조 시스템의 범용 모델로 널리 사용됩니다.

가장 단순한 유형의 MQN은 단일 서버에서 여러 작업 클래스를 스케줄링하는 것입니다.앞서 논의한 두 가지 모델 범주에서와 유사하게, 단순한 우선순위 지수 규칙은 다양한 그러한 모델에 최적인 것으로 나타났다.

보다 일반적인 MQN 모델에는 하나의 작업 클래스에서 다른 작업 클래스로 서비스를 변경하기 위한 전환 시간(Levy 및 Sidi, 1990)^[16] 또는 여러 처리 스테이션 등의 기능이 포함되어 있으며, 이러한 기능은 겹치지 않는 작업 클래스의 서브셋에 서비스를 제공합니다.그러한 모델의 난해성으로 인해, 연구자들은 최적에 가까운 성능을 달성하는 비교적 단순한 휴리스틱 정책을 설계하는 것을 목표로 해 왔다.

불완전한 정보를 가진 확률적 스케줄링

확률적 스케줄링 모델에 대한 대부분의 연구는 처리 시간과 기계 업/다운타임과 같은 관련 랜덤 변수의 확률 분포가 선험적으로 완전히 지정된다는 점에서 완전한 정보의 가정에 기초하여 대부분 확립되었다.

그러나 일부 정보만 사용할 수 있는 상황이 있습니다.불완전한 정보에 의한 스케줄링의 예는 환경 정화,^[17] 프로젝트 관리,^[18] 석유 탐사,^[19] 모바일 ^[20]로봇의 센서 스케줄링, 사이클 타임 모델링 등에서 ^[21]찾을 수 있습니다.

불완전한 정보의 결과로 관심 있는 랜덤 변수를 모형화하기 위해 여러 개의 경쟁 분포가 있을 수 있습니다.효과적인 접근방식은 Cai 등에 의해 개발된다.(2009년)^[22] 베이지안 정보 업데이트를 바탕으로 이 문제를 해결한다. $\Theta$ \ $displaystyle$ \ $Theta$ $\Theta$ θ $\Theta$ , , , , , 、 display \ $displaystyle$ \ $Theta ）$ a $\Theta$ a $\Theta$ a ical ical ical ical ical assum assum assum assum assum assum assum assum assum assum assum assum assum assum assum assum assum assum assum assum assum assum ation ation ation assum assum assum ation ation ation assum assum assum assum assum assum assum assum assum assum assumical ical $\Theta$ $\$ $displaystyle$ \ $Theta }$ 에 $\Theta$ 대한 정보는 랜덤 변수의 실현이 관찰된 후 갱신될 수 있습니다.의사결정의 주요 관심사는 어떻게 최신 정보를 활용하여 의사결정을 구체화하고 강화할 것인가 하는 것입니다.스케줄링 정책이 시간에 따라 변경되지 않는다는 의미에서 정적인 경우, 최적의 시퀀스를 식별하여 할인된 예상 보상을 최소화하고 공통 지수적 만기일 ^[22]하의 지각 작업 수를 확률적으로 최소화한다.스케줄링 정책이 최신 정보를 기반으로 프로세스 중에 조정을 할 수 있다는 점에서 동적인 경우, 사후 기틴 지수는 동적 ^[22]정책 클래스에서 예상되는 할인 보상을 최소화하는 최적의 정책을 찾기 위해 개발된다.

레퍼런스

^ ^a ^b Cai, X.Q.; Wu, X.Y.; Zhou, X. (2014). Optimal Stochastic Scheduling. Springer US. pp. 49, p.95. ISBN 978-1-4899-7405-1.
^ Nino-Mora, J. (2009). "Stochastic Scheduling". In Floudas, C.; Pardalos, P. (eds.). Encyclopedia of Optimization. US: Springer. pp. 3818–3824. ISBN 978-0-387-74758-3.
^ Smith, Wayne E. (1956). "Various optimizers for single-stage production". Naval Research Logistics Quarterly. 3 (1–2): 59–66. doi:10.1002/nav.3800030106.
^ Rothkopf, Michael (1966). "Scheduling with random service times". Management Science. 12 (9): 707–713. doi:10.1287/mnsc.12.9.707.
^ Weiss, Gideon; Pinedo, Michael (1980). "Scheduling tasks with exponential service times on non-identical processors to minimize various cost functions". Journal of Applied Probability. 17 (1): 187–202. doi:10.2307/3212936. JSTOR 3212936.
^ Weber, Richard R. (1982). "Scheduling jobs with stochastic processing requirements on parallel machines to minimize makespan or flowtime". Journal of Applied Probability. 19 (1): 167–182. doi:10.2307/3213926. JSTOR 3213926.
^ Weber, Richard; Varaiya, P.; Walrand, J. (1986). "Scheduling jobs with stochastically ordered processing times on parallel machines to minimize expected flowtime". Journal of Applied Probability. 23 (3): 841–847. doi:10.2307/3214023. JSTOR 3214023.
^ Robbins, H. (1952). "Some aspects of the sequential design of experiments". Bulletin of the American Mathematical Society. 58 (5): 527–535. doi:10.1090/s0002-9904-1952-09620-8.
^ Gittins, J.C. (1979). "Bandit processes and dynamic allocation indices (with discussion)". Journal of the Royal Statistical Society, Series B. 41: 148–164. doi:10.1111/j.2517-6161.1979.tb01068.x.
^ Gittins, J.C.; Jones, D. "A Dynamic allocation index for the sequential allocation of experiments". In Gani, J.; et al. (eds.). Progress in statistics. Amsterdam: North Holland.
^ Gittins, J.C.; Glazebrook, K.D. (1977). "On Bayesian models in stochastic scheduling". Journal of Applied Probability. 14 (3): 556–565. doi:10.2307/3213458. JSTOR 3213458.
^ Whittle, P. (1980). "Multi-armed bandits and the Gittins index". Journal of the Royal Statistical Society, Series B. 42 (2): 143–149. doi:10.1111/j.2517-6161.1980.tb01111.x.
^ Whittle, P. (1981). "Arm-acquiring bandits". The Annals of Probability. 9 (2): 284–292. doi:10.1214/aop/1176994469.
^ Whittle, P. (1988). "Restless bandits: Activity allocation in a changing world". Journal of Applied Probability. 25: 287–298. doi:10.2307/3214163. JSTOR 3214163.
^ van Oyen, M.P.; Pandelis, D.G.; Teneketzis, D. (1992). "Optimality of index policies for stochastic scheduling with switching penaltie". Journal of Applied Probability. 29 (4): 957–966. doi:10.2307/3214727. JSTOR 3214727.
^ Levy, H.; Sidi, M. (1990). "Polling systems: applications, modeling, and optimization". IEEE Transactions on Communications. 38 (10): 1750–1760. doi:10.1109/26.61446.
^ Lee, S.I.; Kitanidis, P.K. (1991). "Optimal estimation and scheduling in aquifer remediation with incomplete information". Water Resources Research. 27 (9): 2203–2217. doi:10.1029/91wr01307.
^ Gardoni, P.; Reinschmidt, K. F.; Kumar, R. (2007). "A probabilistic framework for Bayesian adaptive forecasting of project progress". Computer-Aided Civil and Infrastructure Engineering. 22 (3): 182–196. doi:10.1111/j.1467-8667.2007.00478.x.
^ Glazebrook, K.D.; Boys, R.J. (1995). "A class of Bayesian models for optimal exploration". Journal of the Royal Statistical Society, Series B. 57 (4): 705–720. doi:10.1111/j.2517-6161.1995.tb02057.x.
^ Gage, A.; Murphy, R.R. (2004). "Sensor scheduling in mobile robots using incomplete information via Min-Conflict with Happiness". IEEE Transactions on Systems, Man, and Cybernetics - Part B: Cybernetics. 34 (1): 454–467. doi:10.1109/tsmcb.2003.817048. PMID 15369086.
^ Chen, C.Y.I.; Ding, Q.; Lin, B.M.T. (2004). "A concise survey of scheduling with time dependent processing times". European Journal of Operational Research. 152: 1–13. doi:10.1016/s0377-2217(02)00909-8.
^ ^a ^b ^c Cai, X.Q.; Wu, X.Y.; Zhou, X. (2009). "Stochastic scheduling subject to breakdown-repeat breakdowns with incomplete information". Operations Research. 57 (5): 1236–1249. doi:10.1287/opre.1080.0660.

[Cai_et_al._2014-1] Cai, X.Q.; Wu, X.Y.; Zhou, X. (2014). Optimal Stochastic Scheduling. Springer US. pp. 49, p.95. ISBN 978-1-4899-7405-1.

[2] Nino-Mora, J. (2009). "Stochastic Scheduling". In Floudas, C.; Pardalos, P. (eds.). Encyclopedia of Optimization. US: Springer. pp. 3818–3824. ISBN 978-0-387-74758-3.

[3] Smith, Wayne E. (1956). "Various optimizers for single-stage production". Naval Research Logistics Quarterly. 3 (1–2): 59–66. doi:10.1002/nav.3800030106.

[Rothkopf1966-4] Rothkopf, Michael (1966). "Scheduling with random service times". Management Science. 12 (9): 707–713. doi:10.1287/mnsc.12.9.707.

[5] Weiss, Gideon; Pinedo, Michael (1980). "Scheduling tasks with exponential service times on non-identical processors to minimize various cost functions". Journal of Applied Probability. 17 (1): 187–202. doi:10.2307/3212936. JSTOR 3212936.

[6] Weber, Richard R. (1982). "Scheduling jobs with stochastic processing requirements on parallel machines to minimize makespan or flowtime". Journal of Applied Probability. 19 (1): 167–182. doi:10.2307/3213926. JSTOR 3213926.

[7] Weber, Richard; Varaiya, P.; Walrand, J. (1986). "Scheduling jobs with stochastically ordered processing times on parallel machines to minimize expected flowtime". Journal of Applied Probability. 23 (3): 841–847. doi:10.2307/3214023. JSTOR 3214023.

[8] Robbins, H. (1952). "Some aspects of the sequential design of experiments". Bulletin of the American Mathematical Society. 58 (5): 527–535. doi:10.1090/s0002-9904-1952-09620-8.

[9] Gittins, J.C. (1979). "Bandit processes and dynamic allocation indices (with discussion)". Journal of the Royal Statistical Society, Series B. 41: 148–164. doi:10.1111/j.2517-6161.1979.tb01068.x.

[10] Gittins, J.C.; Jones, D. "A Dynamic allocation index for the sequential allocation of experiments". In Gani, J.; et al. (eds.). Progress in statistics. Amsterdam: North Holland.

[11] Gittins, J.C.; Glazebrook, K.D. (1977). "On Bayesian models in stochastic scheduling". Journal of Applied Probability. 14 (3): 556–565. doi:10.2307/3213458. JSTOR 3213458.

[12] Whittle, P. (1980). "Multi-armed bandits and the Gittins index". Journal of the Royal Statistical Society, Series B. 42 (2): 143–149. doi:10.1111/j.2517-6161.1980.tb01111.x.

[13] Whittle, P. (1981). "Arm-acquiring bandits". The Annals of Probability. 9 (2): 284–292. doi:10.1214/aop/1176994469.

[14] Whittle, P. (1988). "Restless bandits: Activity allocation in a changing world". Journal of Applied Probability. 25: 287–298. doi:10.2307/3214163. JSTOR 3214163.

[15] van Oyen, M.P.; Pandelis, D.G.; Teneketzis, D. (1992). "Optimality of index policies for stochastic scheduling with switching penaltie". Journal of Applied Probability. 29 (4): 957–966. doi:10.2307/3214727. JSTOR 3214727.

[16] Levy, H.; Sidi, M. (1990). "Polling systems: applications, modeling, and optimization". IEEE Transactions on Communications. 38 (10): 1750–1760. doi:10.1109/26.61446.

[17] Lee, S.I.; Kitanidis, P.K. (1991). "Optimal estimation and scheduling in aquifer remediation with incomplete information". Water Resources Research. 27 (9): 2203–2217. doi:10.1029/91wr01307.

[18] Gardoni, P.; Reinschmidt, K. F.; Kumar, R. (2007). "A probabilistic framework for Bayesian adaptive forecasting of project progress". Computer-Aided Civil and Infrastructure Engineering. 22 (3): 182–196. doi:10.1111/j.1467-8667.2007.00478.x.

[19] Glazebrook, K.D.; Boys, R.J. (1995). "A class of Bayesian models for optimal exploration". Journal of the Royal Statistical Society, Series B. 57 (4): 705–720. doi:10.1111/j.2517-6161.1995.tb02057.x.

[20] Gage, A.; Murphy, R.R. (2004). "Sensor scheduling in mobile robots using incomplete information via Min-Conflict with Happiness". IEEE Transactions on Systems, Man, and Cybernetics - Part B: Cybernetics. 34 (1): 454–467. doi:10.1109/tsmcb.2003.817048. PMID 15369086.

[21] Chen, C.Y.I.; Ding, Q.; Lin, B.M.T. (2004). "A concise survey of scheduling with time dependent processing times". European Journal of Operational Research. 152: 1–13. doi:10.1016/s0377-2217(02)00909-8.

[Cai_et_al._2009-22] Cai, X.Q.; Wu, X.Y.; Zhou, X. (2009). "Stochastic scheduling subject to breakdown-repeat breakdowns with incomplete information". Operations Research. 57 (5): 1236–1249. doi:10.1287/opre.1080.0660.

[1]

[2]

[3]

[4]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

Search