단일 머신 스케줄링

단일 머신 스케줄링 또는 단일 자원 스케줄링은 컴퓨터 과학과 운영 연구의 최적화 문제다.처리량 등 특정 목표를 최적화하는 방식으로 단일 기계에서 스케줄링해야 하는 다양한 처리 시간의 작업₁ J, J, J가₂_n 부여된다.

단일 기계 스케줄링은 동일한 기계 스케줄링의 특별한 경우로서, 그 자체가 최적의 작업 스케줄링의 특별한 경우다.일반적으로 NP-hard인 많은 문제들이 단일 머신 사례에서 다항식 시간에 해결될 수 있다.^[1]^{: 10–20}

최적의 작업 스케줄링 문제를 위한 표준 3필드 표기법에서 단일 기계 변형은 첫 번째 분야에서 1로 표시된다.예를 들어 " 1 ∑ $\sum C_{j}$ $\sum C_{j}$ $\sum C_{j}$ ${\$ 는 제약조건이 없는 동일한 기계 스케줄링 문제로서, 여기서 목적은 완료 시간의 합을 최소화하는 것이다.

변형

makepan-minimization 문제 1 ∑ $\sum C_{\max }$ $\sum C_{\max }$ $\sum C_{\max }$ ${\$ $\sum C_{\max }$ 는 makepan이 항상 동일하기 때문에 하나의 기계에서는 사소한 것이다.따라서 다른 목적을 연구하였다.^[2]

문제 1 ∑ $\sum C_{j}$ $\sum C_{j}$ $\sum C_{j}$ ${\$ 는 완료 시간의 합을 최소화하는 것을 목표로 $\sum C_{j}$ 한다.최단 처리 시간 첫 번째 규칙(SPT)에 의해 최적으로 해결될 수 있다: 작업은 $p_{j}$ 시간 p ${\$ 의 오름차순으로 스케줄링된다 $p_{j}$
- 문제 1 ∑ $\sum w_{j}C_{j}$ $\sum w_{j}C_{j}$ $\sum w_{j}C_{j}$ $\sum w_{j}C_{j}$ ${\$ }}}{j $}}}$ 은 완료 시간의 가중 합계를 최소화하는 것을 목표로 $\sum w_{j}C_{j}$ 한다.가중 최단 처리 시간 첫 번째 규칙(WSPT): p $p_{j}/w_{j}$ / $p_{j}/w_{j}$ $p_{j}/w_{j}$ ${\$ 비율의 오름차순으로 작업이 예약됨 $p_{j}/w_{j}$ ^[2]^{: lecture 1, part 2}
- 문제 1 체인 $\sum w_{j}C_{j}$ w $\sum w_{j}C_{j}$ $\sum w_{j}C_{j}$ ${\$ 은(는) 체인 형태의 종속성을 가진 직업에 대해 위의 문제를 일반화한 것이다 $\sum w_{j}C_{j}$ .또한 WSPT의 적절한 일반화를 통해 최적으로 해결할 수 있다.^[2]^{: lecture 1, part 3}
문제 1 L $L_{\max }$ $L_{\max }$ ${\$ 은(는) 최대 지각을 최소화하는 것을 목표로 $L_{\max }$ 한다.각 job j에 대해 $d_{j}$ $d_{j}$ j {\ $displaystyle d_{$ j}}이 있다 $d_{j}$ 만기일 이후 완료되면 $L_{j}:=C_{j}-d_{j}$ $L_{j}:=C_{j}-d_{j}$ $L_{j}:=C_{j}-d_{j}$ - $L_{j}:=C_{j}-d_{j}$ j ${\$ 로 정의되는 지연이 발생한다. $=C_{j}-d_{j$ 1 L $L_{\max }$ $L_{\max }$ ${\$ 은(는) EDD(최초 마감일 L_ ${\$ max) 규칙으로 최적으로 해결할 수 있음 $L_{\max }$ : 작업은 $d_{j}$ d j {\ $displaystyd$ d_{ $j}$ 의 오름차순으로 예약됨 $d_{j}$ ^[2]^{: lecture 2, part 2}
- 문제는 1prec h({\displaystyle h_{\max}}}두가지 방법 첫째, 그것은, 두번째, 각각의 일은 완료 시점의 기능 자의적인 비용 함수 hj야 할 수 있는 일자리에 임의의 선행 제약 조건을 가능하게 하는 비용의 'caput'(지각은 특별한 사건은 1L최대{\displaystyle L_{\max}generalizesunction.최대 비용은 롤러의 알고리즘으로 알려진 탐욕스러운 알고리즘에 의해 최소화될 수 있다.^[2]^{: lecture 2, part 1}
- 문제 1 $r_{j}$ $r_{j}$ ${\$ $r_{j}$ $L_{\max }$ $L_{\max }$ ${\$ 은(는) 작업별로 처리 가능이 되는 릴리스 시간이 달라지도록 하여 $L_{\max }$ 1 $L_{\max }$ ${\$ 을 $L_{\max }$ (를) 일반화한다.해제 시간이 존재한다는 것은 경우에 따라서는 아직 해제되지 않은 중요한 일을 기다리기 위해 기계를 공회전시키는 것이 최선이 될 수도 있다는 것을 의미한다.이 설정에서 최대 지각을 최소화하는 것은 NP-hard이다.그러나 실제로는 분기 및 바인딩 알고리즘을 사용하여 해결할 수 있다.^[2]^{: lecture 2, part 3}
문제 1 ∑ $\sum U_{j}$ $\sum U_{j}$ $\sum U_{j}$ ${\$ 는 지각을 불문하고 늦은 일자리의 수를 최소화하는 것을 목표로 $\sum U_{j}$ 하고 있다.Hodgson-Moore 알고리즘으로 최적으로 해결할 수 있다.^[3]^[2]^{: lecture 3, part 1}
- $\sum w_{j}U_{j}$ 1 ∑ $\sum w_{j}U_{j}$ $\sum w_{j}U_{j}$ $\sum w_{j}U_{j}$ j ${\$ $U_{j}}$ 는 늦은 일자리의 비중을 최소화하는 것을 목표로 $\sum w_{j}U_{j}$ 한다.모든 작업의 마감일이 동일한 특수 사례( $d_{j}=d$ $d_{j}=d$ = $d_{j}=d$ = d {\ $displaystyle d_{j$ }=d $}$ $\sum w_{j}U_{j}$ ww ${\$ 로 표시됨)이므로 NP-hard이다. $U_{j}})$ 는 배낭 문제와 맞먹는다.^[2]^{: lecture 3, part 2}

마감일이 있는 설정에서는 작업이 마감일까지 완료되면 이익 p가_j 있을 수 있다.그렇지 않으면 이익이 없다.이윤을 극대화하는 것이 목표다.마감일이 있는 단일 머신 스케줄링은 NP-hard이며, Sanni는^[4] 정확한 지수 시간 알고리즘과 다항 시간 근사 알고리즘을 모두 제시한다.
작업에는 실행 간격이 있을 수 있다.각 job에 대해 처리시간 t와_j 시작시간 s가_j 있으므로 [s_j, s_j+t_j] 간격으로 실행해야 한다.일부 구간이 겹치기 때문에 모든 작업을 완료할 수 있는 것은 아니다.완성된 일자리의 수, 즉 처리량을 최대화하는 것이 목표다.더 일반적으로, 각 직업에는 가능한 여러 가지 간격이 있을 수 있으며, 각 간격이 다른 이익과 연관될 수 있다.총이익이 극대화되도록 각 직무별로 최대 1개 구간을 선택하는 것이 목표다.자세한 내용은 간격 예약 페이지를 참조하십시오.
더 일반적으로, 일자리는 시작 시간과 마감 시간을 모두 갖는 시간 창을 가질 수 있으며, 이는 일자리의 길이보다 더 클 수 있다.각 작업은 시간대 내 어디에서나 스케줄링할 수 있다.바-노이, 바-예후다, 프룬드, 나오르, 쉬버가^[5] (1-53)/2 근사치를 제시한다.

참고 항목

단일 머신 스케줄링 문제 해결에 많은 솔루션 기법이 적용되어 왔다.그 중 일부는 아래에 열거되어 있다.

참조

^ Eugene L. Lawler, Jan Karel Lenstra, Alexander H. G. Rinnooy Kan, David B. Shmoys (1993-01-01). "Chapter 9 Sequencing and scheduling: Algorithms and complexity". Handbooks in Operations Research and Management Science. 4: 445–522. doi:10.1016/S0927-0507(05)80189-6. ISSN 0927-0507.{{cite journal}}: CS1 maint : 복수이름 : 작성자 목록(링크)
^ ^a ^b ^c ^d ^e ^f ^g ^h Grinshpoun, Tal (2020). "Subjects in Scheduling". www.youtube.com. Retrieved 2021-09-12.{{cite web}}: CS1 maint : url-status (링크)
^ "Knapsack-like scheduling problems, the Moore-Hodgson algorithm and the 'tower of sets' property". Mathematical and Computer Modelling. 20 (2): 91–106. 1994-07-01. doi:10.1016/0895-7177(94)90209-7. ISSN 0895-7177.
^ 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.
^ Bar-Noy, Amotz; Bar-Yehuda, Reuven; Freund, Ari; (Seffi) Naor, Joseph; Schieber, Baruch (2001-09-01). "A unified approach to approximating resource allocation and scheduling". Journal of the ACM. 48 (5): 1069–1090. doi:10.1145/502102.502107. ISSN 0004-5411.

[:0-1] Eugene L. Lawler, Jan Karel Lenstra, Alexander H. G. Rinnooy Kan, David B. Shmoys (1993-01-01). "Chapter 9 Sequencing and scheduling: Algorithms and complexity". Handbooks in Operations Research and Management Science. 4: 445–522. doi:10.1016/S0927-0507(05)80189-6. ISSN 0927-0507.{{cite journal}}: CS1 maint : 복수이름 : 작성자 목록(링크)

[:1-2] ^ ^a ^b ^c ^d ^e ^f ^g ^h Grinshpoun, Tal (2020). "Subjects in Scheduling". www.youtube.com. Retrieved 2021-09-12.{{cite web}}: CS1 maint : url-status (링크)

[3] "Knapsack-like scheduling problems, the Moore-Hodgson algorithm and the 'tower of sets' property". Mathematical and Computer Modelling. 20 (2): 91–106. 1994-07-01. doi:10.1016/0895-7177(94)90209-7. ISSN 0895-7177.

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

[5] Bar-Noy, Amotz; Bar-Yehuda, Reuven; Freund, Ari; (Seffi) Naor, Joseph; Schieber, Baruch (2001-09-01). "A unified approach to approximating resource allocation and scheduling". Journal of the ACM. 48 (5): 1069–1090. doi:10.1145/502102.502107. ISSN 0004-5411.

[1]

[2]

[3]

[4]

[5]

v t 최적의 작업 스케줄링 문제
1단계 직업	단일 기계 동일 기계 균일 기계 관련 없는 컴퓨터
다단계 작업	병렬 태스크 오픈 숍 플로우 숍 잡샵
최적화 목표	메이즈팬 귀리 지각 지각 처리량
기타요구사항	인터벌 스케줄링 진실된 작업 스케줄링

Search

단일 머신 스케줄링

네임스페이스

더

변형

참고 항목

참조