동일 머신의 스케줄링

동일한 기계 스케줄링은 컴퓨터 과학 및 운영 연구의 최적화 문제입니다.예를 들어 m개의 동일한 머신 상에서 스케줄 할 필요가 있는 다양한 처리 시간의 작업₁ J, J₂, ..., J가_n n개 주어지고, 예를 들어 특정 목적 함수의 최적화, makespan이 최소화됩니다.

동일한 머신 스케줄링은 균일한 머신스케줄링의 특수한 경우이며, 그 자체가 최적의 작업스케줄링의 특수한 경우입니다.일반적으로 각 작업의 처리시간은 기계마다 다를 수 있으며, 동일한 기계 스케줄링의 경우 각 작업의 처리시간은 기계마다 동일하다.따라서 동일한 기계 스케줄링은 멀티웨이 번호 분할과 동일합니다.동일한 머신 스케줄링의 특수한 경우는 단일 머신 스케줄링입니다.

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

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

알고리즘

평균 및 가중 평균 완료 시간 최소화

평균 완료 시간(P $\sum C_{i}$ C $\sum C_{i}$ i \ $displaystyle \sum$ C_ ${i$ 을 다항식 시간으로 최소화할 수 있습니다.SPT 알고리즘(최단 처리 시간 우선)은 작업을 길이, 최단 처리 시간 순으로 정렬한 후 지금까지의 종료 시간이 가장 빠른 프로세서에 할당합니다.이는 시간 O(n log n)로 실행되며 동일한 ^[1]머신 $($ P $\sum C_{i}$ C $\sum C_{i}$ i \ $displaystyle$ \ $sum C_{$ i $\sum C_{i}$ 의 평균 완료 시간을 최소화합니다.

SPT 공정표에는 여러 가지가 있을 수 있으며, 최소 종료 시간(OMFT - 최적 평균 종료 시간이라고도 함)을 갖는 SPT 공정표를 찾는 것은 NP-hard입니다.

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

Sahni는^[2] 동일한 기계에서 이러한 NP-하드 문제를 모두 해결하기 위한 지수 시간 알고리즘과 다항 시간 근사 체계를 제공합니다.

최적의 평균 완료 시간
가중평균완료시간

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

파티션 문제를 줄여 최대 완료 시간(P $C_{\max }$ $C_{\max }$ max {\ $displaystyle C_$ {\max $C_{\max }$ 을 최소화하는 것은 동일한 머신에서도 NP 하드입니다.많은 정확한 알고리즘과 근사 알고리즘이 알려져 있습니다.

Graham은 다음을 증명했다.

목록 스케줄링 알고리즘(임의의 고정된 순서로 작업을 처리하고 사용 가능한 첫 번째 머신으로 각 작업을 스케줄링하는 알고리즘)은 동일한 ^[3]머신에 대해 2 $2-1/m$ - $2-1/m$ / $2-1/m$ (\ $displaystyle 2-1/m)$ 의 $2-1/m$ 근사치입니다.어떤 m에도 바운드는 단단하다.이 알고리즘은 시간 O(n)에 실행됩니다.
Longest Processing Time First(LPT; 최장 처리 시간 우선)라고 불리는 특정 리스트 스케줄링 알고리즘은 동일한 머신에 ^[4]^{: sec.5}대해 4 $4/3-1/3m$ / $($ $스타일$ 4 $/3-1/3m)$ 의 $4/3-1/3m$ 근사치입니다.이것은 그리디 넘버 파티셔닝이라고도 합니다.

Coffman, Garey 및 Johnson은 13/11⁄1.182의 근사 계수를 갖는 빈 패킹 기술을 사용하여 멀티비트 알고리즘이라고 불리는 다른 알고리즘을 제시했습니다.

Huang과^[5] Lu는 잡일의 최대 공유 할당이라는 보다 일반적인 문제를 통해 시간 O(m log m + n)에서 11/9⁄1.222 근사치를 달성하는 단순한 다항식 시간 알고리즘을 제시했다.

Sahni는^[2] $O(n\cdot (n^{2}/\epsilon )^{m-1})$ O $O(n\cdot (n^{2}/\epsilon )^{m-1})$ $O(n\cdot (n^{2}/\epsilon )^{m-1})$ ( $O(n\cdot (n^{2}/\epsilon )^{m-1})$ $O(n\cdot (n^{2}/\epsilon )^{m-1})$ / $O(n\cdot (n^{2}/\epsilon )^{m-1})$ ) $O(n\cdot (n^{2}/\epsilon )^{m-1})$ - $O(n\cdot (n^{2}/\epsilon )^{m-1})$ ( $displaystyle$ O $(n\cdot (n^{2}/\epsilon)^{m-1$ 에 (1+)) OPT에 도달하는 PTAS를 제시했습니다.m이 고정일 경우 FPTAS입니다.m=2의 경우 실행 시간이 O $O(n^{2}/\epsilon )$ 2 $O(n^{2}/\epsilon )$ / $))$ { $displaystyle$ O $(n^{2}/\epsilon$ 로 향상됩니다.알고리즘은 인터벌 파티셔닝이라고 불리는 기술을 사용합니다.

Hochbaum과 Shmoys는^[6] (기계 수가 고정되지 않은 경우에도) 동일한 기계의 수에 대한 몇 가지 근사 알고리즘을 제시했다.

임의의 r >0에 대해 시간 $O(n(r+\log {n}))$ ( $O(n(r+\log {n}))$ ( $O(n(r+\log {n}))$ + $O(n(r+\log {n}))$ n ) $O(n(r+\log {n}))$ \ $displaystyle$ O ( n ( $r$ + $log {n$ ) )의 근사비율(6/5^−r+2)을 가지는 알고리즘.
임의의 r >0에 대해 시간 $O(n(rm^{4}+\log {n}))$ ( $O(n(rm^{4}+\log {n}))$ ( $O(n(rm^{4}+\log {n}))$ $O(n(rm^{4}+\log {n}))$ + $O(n(rm^{4}+\log {n}))$ n $O(n(rm^{4}+\log {n}))$ ) $O(n(rm^{4}+\log {n}))$ \ $displaystyle$ O ( $n$ ( n ( $rm$ ^ { $4$ ) + \ $log$ { $n$ } $O(n(rm^{4}+\log {n}))$ )의 근사비(7/6+2^−r)를 가지는 알고리즘.
임의의 >0 에 대해서, $O((n/\varepsilon )^{(1/\varepsilon ^{2})})$ O $O((n/\varepsilon )^{(1/\varepsilon ^{2})})$ ( ( $O((n/\varepsilon )^{(1/\varepsilon ^{2})})$ ( n / $O((n/\varepsilon )^{(1/\varepsilon ^{2})})$ ) $O((n/\varepsilon )^{(1/\varepsilon ^{2})})$ ( 1 / $O((n/\varepsilon )^{(1/\varepsilon ^{2})})$ 2 $O((n/\varepsilon )^{(1/\varepsilon ^{2})})$ ) $O((n/\varepsilon )^{(1/\varepsilon ^{2})})$ { $displaystyle$ O ( $n$ / \ $varepsilon )^{ 1$ / \ $varepsilon$ ^ { $O((n/\varepsilon )^{(1/\varepsilon ^{2})})$ 2} } $O((n/\varepsilon )^{(1/\varepsilon ^{2})})$ 에서의 근사비가 최대 ( $O((n/\varepsilon )^{(1/\varepsilon ^{2})})$ + )인 알고리즘입니다.이것은 PTAS 입니다.기계 수가 입력의 일부인 경우 문제는 NP-hard이므로 FPTAS는 불가능합니다.

Leung은^[7] 이 알고리즘의 실행시간을 $O\left((n/\varepsilon )^{(1/\varepsilon )\log {(1/\varepsilon )}}\right)$ O $O\left((n/\varepsilon )^{(1/\varepsilon )\log {(1/\varepsilon )}}\right)$ ( ( $O\left((n/\varepsilon )^{(1/\varepsilon )\log {(1/\varepsilon )}}\right)$ / $O\left((n/\varepsilon )^{(1/\varepsilon )\log {(1/\varepsilon )}}\right)$ ) ( $O\left((n/\varepsilon )^{(1/\varepsilon )\log {(1/\varepsilon )}}\right)$ / $O\left((n/\varepsilon )^{(1/\varepsilon )\log {(1/\varepsilon )}}\right)$ ) $O\left((n/\varepsilon )^{(1/\varepsilon )\log {(1/\varepsilon )}}\right)$ $O\left((n/\varepsilon )^{(1/\varepsilon )\log {(1/\varepsilon )}}\right)$ ( $O\left((n/\varepsilon )^{(1/\varepsilon )\log {(1/\varepsilon )}}\right)$ / $O\left((n/\varepsilon )^{(1/\varepsilon )\log {(1/\varepsilon )}}\right)$ ) \ $displaystyle$ O \ $left$ ( ( n / \ $varepsilon )^{$ ( $1$ / \ $varepsilon$ ) } \ $log$ { ( $1$ / \ $right )$ $O\left((n/\varepsilon )^{(1/\varepsilon )\log {(1/\varepsilon )}}\right)$ 로 $O\left((n/\varepsilon )^{(1/\varepsilon )\log {(1/\varepsilon )}}\right)$ 했습니다.

최소 완료 시간 극대화

최소 완료 시간 최대화( $C_{\min }$ min\ $displaystyle C_{\min$ 는 "작업"이 실제로 기계를 계속 작동시키는 데 필요한 예비 부품이고 수명이 서로 다른 경우에 적용할 수 있습니다.목표는 기계를 가능한 ^[8]한 오래 가동시키는 것입니다.LPT 알고리즘은 $({$ 에 ${\frac {3m-1}{4m-2}}$ 도달합니다.

Woeginger는^[9] $O(c_{\varepsilon }n\log {k})$ O ( c $O(c_{\varepsilon }n\log {k})$ n log $O(c_{\varepsilon }n\log {k})$ k $O(c_{\varepsilon }n\log {k})$ ) \ $displaystyle$ O ( c _ { \ $varepsilon$ $}$ n \ $log$ { $k$ )의 $1-{\varepsilon }$ $1-{\varepsilon }$ 계수를 $1-{\varepsilon }$ 구하는 PTAS를 제시하였다. $c_{\varepsilon }$ 서 c $c_{\varepsilon }$ \ $displaystyle c$ _ { \ $varepsilon }$ n } n \ log { k $c_{\varepsilon }$ } } } $1-{\varepsilon }$ ential $。$ 이 알고리즘은 정수 선형 프로그래밍에 Lenstra의 알고리즘을 사용합니다.

일반적인 목적 함수

Alon, Azar, Woeginger 및 Yadid는^[10] 보다 일반적인 목적 함수를 고려합니다.완료 시간_i C에만 의존하는 양의 실함수 f가 주어지면 $\sum _{i=1}^{m}f(C_{i})$ $그들$ 은 $\max _{i=1}^{m}f(C_{i})$ $\max _{i=1}^{m}f(C_{i})$ $\max _{i=1}^{m}f(C_{i})$ $\max _{i=1}^{m}f(C_{i})$ $\sum _{i=1}^{m}f(C_{i})$ $\max _{i=1}^{m}f(C_{i})$ f ( $\max _{i=1}^{m}f(C_{i})$ ${i})$ 를 최소화하고, $최대$ i $= 1$ $\max _{i=1}^{m}f(C_{i})$ f $\max _{i=1}^{m}f(C_{i})$ ( $C_$ ${$ 를 최소화하는 $\sum _{i=1}^{m}f(C_{i})$ $목표를 고려한다.$ $ystyle \sum$ _ ${i=1$ }^{ $m}f(C_{i})$ 및 $\min _{i=1}^{m}f(C_{i})$ $\min _{i=1}^{m}f(C_{i})$ $)$ $\min _{i=1}^{m}f(C_{i})$ (\ $displaystyle \min$ _ ${i=1}^{m}f(C_{i$ 만약 f가 음이 아니고 볼록하며 그들이 "F*"라고 부르는 강한 연속성 가정을 충족한다면, 두 최소화 문제 모두 PTAS를 갖는다는 것을 증명한다.마찬가지로 f가 음이 아니고 오목하며 F*를 만족하는 경우 두 최대화 문제 모두 PTAS가 있습니다.두 경우 모두 PTAS의 실행 시간은 O(n)이지만 1/µ 단위의 지수 상수입니다.

「」를 참조해 주세요.

페르난데스법

레퍼런스

^ ^a ^b 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. S2CID 18693114.
^ ^a ^b ^c 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. S2CID 10956951.
^ Graham, Ron L. (1966). "Bounds for Certain Multiprocessing Anomalies". Bell System Technical Journal. 45 (9): 1563–1581. doi:10.1002/j.1538-7305.1966.tb01709.x. ISSN 1538-7305.
^ Graham, Ron L. (1969-03-01). "Bounds on Multiprocessing Timing Anomalies". SIAM Journal on Applied Mathematics. 17 (2): 416–429. doi:10.1137/0117039. ISSN 0036-1399.
^ Huang, Xin; Lu, Pinyan (2021-07-18). "An Algorithmic Framework for Approximating Maximin Share Allocation of Chores". Proceedings of the 22nd ACM Conference on Economics and Computation. EC '21. Budapest, Hungary: Association for Computing Machinery: 630–631. arXiv:1907.04505. doi:10.1145/3465456.3467555. ISBN 978-1-4503-8554-1.
^ 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.
^ Leung, Joseph Y-T. (1989-05-08). "Bin packing with restricted piece sizes". Information Processing Letters. 31 (3): 145–149. doi:10.1016/0020-0190(89)90223-8. ISSN 0020-0190.
^ Friesen, D. K.; Deuermeyer, B. L. (1981-02-01). "Analysis of Greedy Solutions for a Replacement Part Sequencing Problem". Mathematics of Operations Research. 6 (1): 74–87. doi:10.1287/moor.6.1.74. ISSN 0364-765X.
^ Woeginger, Gerhard J. (1997-05-01). "A polynomial-time approximation scheme for maximizing the minimum machine completion time". Operations Research Letters. 20 (4): 149–154. doi:10.1016/S0167-6377(96)00055-7. ISSN 0167-6377.
^ Alon, Noga; Azar, Yossi; Woeginger, Gerhard J.; Yadid, Tal (1998). "Approximation schemes for scheduling on parallel machines". Journal of Scheduling. 1 (1): 55–66. doi:10.1002/(SICI)1099-1425(199806)1:1<55::AID-JOS2>3.0.CO;2-J. ISSN 1099-1425.

외부 링크

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

[:0-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. S2CID 18693114.

[:3-2] 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. S2CID 10956951.

[:2-3] Graham, Ron L. (1966). "Bounds for Certain Multiprocessing Anomalies". Bell System Technical Journal. 45 (9): 1563–1581. doi:10.1002/j.1538-7305.1966.tb01709.x. ISSN 1538-7305.

[:1-4] Graham, Ron L. (1969-03-01). "Bounds on Multiprocessing Timing Anomalies". SIAM Journal on Applied Mathematics. 17 (2): 416–429. doi:10.1137/0117039. ISSN 0036-1399.

[5] Huang, Xin; Lu, Pinyan (2021-07-18). "An Algorithmic Framework for Approximating Maximin Share Allocation of Chores". Proceedings of the 22nd ACM Conference on Economics and Computation. EC '21. Budapest, Hungary: Association for Computing Machinery: 630–631. arXiv:1907.04505. doi:10.1145/3465456.3467555. ISBN 978-1-4503-8554-1.

[:02-6] 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.

[7] Leung, Joseph Y-T. (1989-05-08). "Bin packing with restricted piece sizes". Information Processing Letters. 31 (3): 145–149. doi:10.1016/0020-0190(89)90223-8. ISSN 0020-0190.

[8] Friesen, D. K.; Deuermeyer, B. L. (1981-02-01). "Analysis of Greedy Solutions for a Replacement Part Sequencing Problem". Mathematics of Operations Research. 6 (1): 74–87. doi:10.1287/moor.6.1.74. ISSN 0364-765X.

[:22-9] Woeginger, Gerhard J. (1997-05-01). "A polynomial-time approximation scheme for maximizing the minimum machine completion time". Operations Research Letters. 20 (4): 149–154. doi:10.1016/S0167-6377(96)00055-7. ISSN 0167-6377.

[10] Alon, Noga; Azar, Yossi; Woeginger, Gerhard J.; Yadid, Tal (1998). "Approximation schemes for scheduling on parallel machines". Journal of Scheduling. 1 (1): 55–66. doi:10.1002/(SICI)1099-1425(199806)1:1<55::AID-JOS2>3.0.CO;2-J. ISSN 1099-1425.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

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

Search

동일 머신의 스케줄링

네임스페이스

더

목차

알고리즘

평균 및 가중 평균 완료 시간 최소화

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

최소 완료 시간 극대화

일반적인 목적 함수

「」를 참조해 주세요.

레퍼런스

외부 링크

Search

동일 머신의 스케줄링

알고리즘

평균 및 가중 평균 완료 시간 최소화

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

최소 완료 시간 극대화

일반적인 목적 함수

「 」를 참조해 주세요.

레퍼런스

외부 링크

「」를 참조해 주세요.