균일한 기계 스케줄링

균일한 기계 스케줄링(균등하게 관련된 기계 스케줄링 또는 관련 기계 스케줄링이라고도 함)은 컴퓨터 과학 및 운영 연구의 최적화 문제입니다.이것은 최적의 작업 스케줄링의 변형입니다.처리시간이 다른 작업 J, J₂, ..., J가_n n개 부여되어 있으며, 이 작업들은₁ m개의 다른 기계로 스케줄이 필요합니다.목표는 일정을 실행하는 데 필요한 총 시간인 제작 시간을 최소화하는 것입니다.작업 j를 처리하기 위해 필요한 머신의 시간은 p로 표시됩니다_i,j.일반적인 경우, 시간_i,j p는 관계가 없으며 양의 처리 시간의 행렬이 모두 가능하다.균일한 머신 스케줄링이라고 하는 특정의 변형에서는, 일부의 머신이 다른 머신보다 균일하게 고속입니다.즉, 각 기계 i에 대해 속도 계수_i s가 존재하며 기계 i에서의 작업 j의 실행 시간은 p = p_j/s입니다_i,j_i.

최적의 작업 스케줄링 문제를 위한 표준 3필드 표기법에서는 균일한 기계 변형이 첫 번째 필드에서 Q로 표시됩니다.예를 들어 "Q $C_{\max }$ C $C_{\max }$ $\$ $displaystyle C_{\max$ 로 나타나는 문제는 제약이 없는 균일한 머신 스케줄링 문제이며, 최대 완료 시간을 최소화하는 것이 목표입니다.균일한 머신 스케줄링의 특별한 경우는 모든 머신의 속도가 동일한 머신 스케줄링입니다.이 변형은 첫 번째 필드에 P로 표시됩니다.

문제의 일부 변형에서는 최대 완료 시간을 최소화하는 대신 평균 완료 시간을 최소화하는 것이 바람직합니다(모든 n개 작업에 대해 평균). Q $\sum C_{i}$ $\sum C_{i}$ i \ $style \sum$ C_ ${i$ 로 표시됩니다.일반적으로 일부 작업이 다른 작업보다 중요한 경우 가중 평균의 최소화를 권장합니다.각 작업의 가중치가 다른 완료 시간.이것은 Q $\sum w_{i}C_{i}$ $\sum w_{i}C_{i}$ $(\$ w_ ${i}C_{i$ 로 나타납니다.

알고리즘

평균 완료 시간 최소화

평균 완료 시간은 다항식 시간으로 최소화할 수 있습니다.

SPT 알고리즘(최단 처리 시간 우선)은 작업을 길이, 최단 처리 시간 순으로 정렬한 후 지금까지의 종료 시간이 가장 빠른 프로세서에 할당합니다.이는 시간 O(n log n)로 실행되며 동일한 ^[1]머신 $($ P $\sum C_{i}$ C $\sum C_{i}$ i \ $displaystyle$ \ $sum C_{$ i $\sum C_{i}$ 의 평균 완료 시간을 최소화합니다.
Horowitz와 Sahni는^[2] 균일한 머신의 평균 완료 시간을 최소화하기 위해 실행 시간 O(n log m n)를 가진 정확한 알고리즘을 제시합니다.Q $\sum C_{i}$ $\sum C_{i}$ i \ $display$ style $\sum$ C _ { $i$ } 。
Bruno, Coffman 및^[3] Sethi는 시간 $O(\max(mn^{2},n^{3}))$ ( $O(\max(mn^{2},n^{3}))$ ( $O(\max(mn^{2},n^{3}))$ $O(\max(mn^{2},n^{3}))$ , $O(\max(mn^{2},n^{3}))$ 3 $O(\max(mn^{2},n^{3}))$ ) $O(\max(mn^{2},n^{3}))$ \ $displaystyle$ O ( \ $max$ ( $mn$ ^ { $2$ , $n$ ^ { $3$ } ) $O(\max(mn^{2},n^{3}))$ ）。관련되지 않은 머신의 평균 완료 시간을 최소화하기 위한 알고리즘을 제공합니다.R $\sum C_{i}$ $\sum C_{i}$ i $\sum C_{i}$ \ $displaystyle$ \ $sum$ C _ { $i$ } $\sum C_{i}$ } 。

가중평균완료시간최소화

같은 머신에서도, 배낭의 ^[2]문제를 경감하는 것으로, 가중 평균의 완료 시간을 최소한으로 억제하는 것은 NP-hard입니다.파티션 문제를 ^[4]줄여 기계 수가 고정되고 최소 2개라도 NP-hard입니다.

Sahni는^[4] 동일한 기계에 대한 지수 시간 알고리즘과 다항 시간 근사 알고리즘을 제공합니다.

Horowitz와 Sahni는^[2] 다음과 같이 발표했습니다.

균일한 기계에서 가중 평균 완료 시간을 최소화하기 위한 정확한 동적 프로그래밍 알고리즘.이 알고리즘들은 지수적인 시간에 실행됩니다.
다항식 시간 근사 스킴은 임의의 >0에 대해 최대 (1+)OPT에 도달한다.균일한 2대의 기계에서 가중 평균 완료 시간을 최소화하기 위해 실행 시간은 $O(10^{l}n^{2})$ O( $O(10^{l}n^{2})$ $O(10^{l}n^{2})$ $O(10^{l}n^{2})$ 2 $)({display style O$ (10 $^{l}n^{$ 2}) $O(n^{2}/\epsilon )$ = $O(10^{l}n^{2})$ $O(n^{2}/\epsilon )$ ( $O(n^{2}/\epsilon )$ 2 / $))$ { $display style$ O $(n^{2}/\epsilon$ 이므로 FPTAS가 됩니다.이들은 알고리즘이 임의의 수의 균일한 머신에 대해 쉽게 확장될 수 있다고 주장하지만 이 경우 런타임은 분석하지 않습니다.관련되지 않은 시스템의 가중 평균 완료 시간에 대한 알고리즘은 제시하지 않습니다.

최대 완료 시간(메이크 스팬) 최소화

파티션 문제를 줄여 같은 머신이라도 최대 완료 시간을 최소화하는 것은 NP-hard입니다.

Longest-Processing-Time-First Algorithm(LPT; 최장 처리 시간 우선 알고리즘)에 의해 상수 계수 근사치를 얻을 수 있다.

Horowitz와 Sahni는^[2] 다음과 같이 발표했습니다.

정확한 동적 프로그래밍 알고리즘으로 균일 및 관련 없는 기계 모두에서 최대 완료 시간을 최소화합니다.이러한 알고리즘은 지수 시간 내에 실행됩니다(이러한 문제는 모두 NP-하드임을 호출합니다).
다항식 시간 근사 스킴은 임의의 >0에 대해 최대 (1+)OPT에 도달한다.2개의 균일한 머신에서 최대 완료 시간을 최소화하기 위해 알고리즘은 $O(10^{2l}n)$ O( $O(10^{2l}n)$ $O(10^{2l}n)$ n $)$ {\ $displaystyle$ O( $10^{2l}n$ $여기서$ l { $displaystyle$ l $}$ 은 $l$ $\epsilon \geq 2\cdot 10^{-l}$ 2 $\epsilon \geq 2\cdot 10^{-l}$ $\epsilon \geq 2\cdot 10^{-l}$ - $\epsilon \geq 2\cdot 10^{-l}$ l { $displaystyle \epsilon 2\cdot$ 10 $\epsilon \geq 2\cdot 10^{-l}$ 로 실행됩니다.따라서 실행시간은 O $O(n/\epsilon ^{2})$ $O(n/\epsilon ^{2})$ $O(n/\epsilon ^{2})$ 2 $)({displaystyle O(n$ /\ $epsilon$ ^{ $2$ 이므로 FPTAS가 됩니다.관련 없는 2대의 머신에서 최대 완료 시간을 최소화하기 위해 실행 시간은 $O(10^{l}n^{2})$ O( $O(10^{l}n^{2})$ $O(10^{l}n^{2})$ n $O(10^{l}n^{2})$ ) $O(10^{l}n^{2})$ { $display$ O $(10^{l}n^{2}}$ = $O(10^{l}n^{2})$ $O(n^{2}/\epsilon )$ 2 / $))$ { $display style$ O $(n^{2}/\epsilon})$ 입니다 $O(n^{2}/\epsilon )$ 이들은 알고리즘이 임의의 수의 균일한 머신에 대해 쉽게 확장될 수 있다고 주장하지만 이 경우 런타임은 분석하지 않습니다.

Hochbaum과 Shmoys는^[5] 동일한 기계 수에 대한 몇 가지 근사 알고리즘을 제시했다.나중에 ^[6]그들은 균일한 기계를 위한 PTAS를 개발했다.

Epstein과 Sgall은^[7] 보다 일반적인 목적 함수를 처리하기 위해 균일한 기계를 위해 PTAS를 일반화했다.C_i(1과 m 사이의 i에 대하여)를 주어진 스케줄에서 기계 i의 메이크스팬으로 합니다.목적함수 max(C_i)를 최소화하는 대신 목적함수 max(f(C_i))를 최소화할 수 있습니다. 여기서 f는 고정함수입니다.마찬가지로 목적함수합(f(C_i))을 최소화할 수 있다.

단조로움과 진실성

어떤 설정에서는 기계속도는 기계의 사적인 정보이며, 우리는 기계가 진짜 속도를 드러내도록 장려하고 싶습니다. 즉, 우리는 진실된 메커니즘을 원합니다.진실을 얻기 위한 중요한 고려사항은 ^[8]단조로움이다.즉, 기계가 더 빠른 속도를 보고하고 다른 모든 입력이 그대로 유지되면 기계에 할당된 총 처리 시간이 약하게 증가합니다.이 문제의 경우:

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

내선번호

종속 작업:경우에 따라 작업이 종속될 수 있습니다.예를 들어 콘솔에서 사용자 credential을 읽은 후 이를 사용하여 인증을 수행하고 인증에 성공하면 콘솔에 일부 데이터가 표시됩니다.분명히 한 작업은 다른 작업에 의존합니다.이는 작업 간에 어떤 순서가 존재하는지를 보여주는 명백한 사례입니다.사실 부분적인 순서로 모델링할 수 있는 것은 확실합니다.그러면 정의상 태스크 세트가 격자 구조를 구성한다.이로 인해 멀티프로세서 스케줄링 문제가 더욱 복잡해집니다.

정적과 동적:머신 스케줄링 알고리즘은 정적 또는 동적입니다.스케줄링 알고리즘은 프로그램을 실행하기 전에 어떤 연산 태스크를 어떤 프로세서에 할당할지 스케줄링에 의해 결정되는 경우 정적입니다.알고리즘은 런타임에 실행되는 경우 역동적입니다.정적 스케줄링 알고리즘의 경우 일반적인 접근법은 우선순위 관계에 따라 작업을 순위를 매기고 목록 스케줄링 기술을 사용하여 프로세서에 ^[13]작업을 스케줄링하는 것입니다.

다단계 작업:다양한 설정에서 각 작업에는 병렬로 실행해야 하는 여러 작업이 있을 수 있습니다.이러한 설정 중 일부는 오픈샵 스케줄링, 플로우숍 스케줄링 및 잡숍 스케줄링을 통해 처리됩니다.

외부 링크

프리엠션 없는 병렬 시스템 문제 요약

레퍼런스

^ Horowitz, Ellis; Sahni, Sartaj (1976-04-01). "Exact and Approximate Algorithms for Scheduling Nonidentical Processors". Journal of the ACM. 23 (2): 317–327. doi:10.1145/321941.321951. ISSN 0004-5411.
^ ^a ^b ^c ^d Horowitz, Ellis; Sahni, Sartaj (1976-04-01). "Exact and Approximate Algorithms for Scheduling Nonidentical Processors". Journal of the ACM. 23 (2): 317–327. doi:10.1145/321941.321951. ISSN 0004-5411.
^ Bruno, J.; Coffman, E. G.; Sethi, R. (1974-07-01). "Scheduling independent tasks to reduce mean finishing time". Communications of the ACM. 17 (7): 382–387. doi:10.1145/361011.361064. ISSN 0001-0782.
^ ^a ^b Sahni, Sartaj K. (1976-01-01). "Algorithms for Scheduling Independent Tasks". Journal of the ACM. 23 (1): 116–127. doi:10.1145/321921.321934. ISSN 0004-5411.
^ Hochbaum, Dorit S.; Shmoys, David B. (1987-01-01). "Using dual approximation algorithms for scheduling problems theoretical and practical results". Journal of the ACM. 34 (1): 144–162. doi:10.1145/7531.7535. ISSN 0004-5411. S2CID 9739129.
^ Hochbaum, Dorit S.; Shmoys, David B. (1988-06-01). "A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach". SIAM Journal on Computing. 17 (3): 539–551. doi:10.1137/0217033. ISSN 0097-5397.
^ Epstein, Leah; Sgall, Jiri (2004-05-01). "Approximation Schemes for Schedulingon Uniformly Related and Identical Parallel Machines". Algorithmica. 39 (1): 43–57. doi:10.1007/s00453-003-1077-7. ISSN 1432-0541.
^ 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.
^ Kwok, Yu-Kwong; Ahmad, Ishfaq (1999-12-01). "Static scheduling algorithms for allocating directed task graphs to multiprocessors". ACM Computing Surveys. 31 (4): 406–471. CiteSeerX 10.1.1.322.2295. doi:10.1145/344588.344618. ISSN 0360-0300.

[1] Horowitz, Ellis; Sahni, Sartaj (1976-04-01). "Exact and Approximate Algorithms for Scheduling Nonidentical Processors". Journal of the ACM. 23 (2): 317–327. doi:10.1145/321941.321951. ISSN 0004-5411.

[:0-2] Horowitz, Ellis; Sahni, Sartaj (1976-04-01). "Exact and Approximate Algorithms for Scheduling Nonidentical Processors". Journal of the ACM. 23 (2): 317–327. doi:10.1145/321941.321951. ISSN 0004-5411.

[3] Bruno, J.; Coffman, E. G.; Sethi, R. (1974-07-01). "Scheduling independent tasks to reduce mean finishing time". Communications of the ACM. 17 (7): 382–387. doi:10.1145/361011.361064. ISSN 0001-0782.

[:3-4] Sahni, Sartaj K. (1976-01-01). "Algorithms for Scheduling Independent Tasks". Journal of the ACM. 23 (1): 116–127. doi:10.1145/321921.321934. ISSN 0004-5411.

[:02-5] Hochbaum, Dorit S.; Shmoys, David B. (1987-01-01). "Using dual approximation algorithms for scheduling problems theoretical and practical results". Journal of the ACM. 34 (1): 144–162. doi:10.1145/7531.7535. ISSN 0004-5411. S2CID 9739129.

[6] Hochbaum, Dorit S.; Shmoys, David B. (1988-06-01). "A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach". SIAM Journal on Computing. 17 (3): 539–551. doi:10.1137/0217033. ISSN 0097-5397.

[7] Epstein, Leah; Sgall, Jiri (2004-05-01). "Approximation Schemes for Schedulingon Uniformly Related and Identical Parallel Machines". Algorithmica. 39 (1): 43–57. doi:10.1007/s00453-003-1077-7. ISSN 1432-0541.

[8] 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.

[9] 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.

[10] 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.

[11] 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.

[12] 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.

[13] Kwok, Yu-Kwong; Ahmad, Ishfaq (1999-12-01). "Static scheduling algorithms for allocating directed task graphs to multiprocessors". ACM Computing Surveys. 31 (4): 406–471. CiteSeerX 10.1.1.322.2295. doi:10.1145/344588.344618. ISSN 0360-0300.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

v t 최적의 작업 스케줄링 문제
1단계 작업	싱글 머신 동일 기계 균일한 기계 관련 없는 기계
다단계 작업	병렬 태스크 오픈 숍 플로우 숍 잡샵
최적화 목표	메이크스판 귀기울림 지각 지각 스루풋
기타 요건	인터벌 스케줄링 정확한 작업 스케줄링

Search