탐욕스러운 순차적 / 병렬 작업 스케줄링

Question

프로세스를 위해 예약 해야하는 N 작업이 있습니다. 각 작업은 순서대로 실행 해야하는 두 부분으로 구성됩니다. 첫 번째 것은 뮤텍스에 의해 지켜 지므로 한 번에 하나의 작업만이 파트를 실행할 수 있습니다. 두 번째 부분은 그러한 제약이 없으며 모든 작업이 동시에이 작업을 실행할 수 있습니다. Task i의 경우 우리는 각 부분에서 지출 해야하는 시간, 즉 Guarded 파트의 M _{i (즉, 병렬로 실행될 수있는 부분에 대해 i )을 알고 있습니다. .}

문제는 모든 것을 실행하는 데 필요한 시간이 최소화되도록 작업의 순열을 찾는 것입니다.

내 직감은 _{i 주문을 내림차순으로 작업을 스케줄링하여 탐욕스러운 알고리즘으로 해결할 수 있다고 말합니다.}

예를 들어 다음과 같은 작업이 주어집니다. m _{1 = 3, 1 = 9 m 2 = 2, a 2 = 7 m 3 = 6, a 3 = 10}

최적의 해결책은 순열 3, 1, 2입니다.

그러나 나는 탐욕스러운 솔루션이 최적 인 것을 증명하는 데 어려움이 있습니다. 그것을하는 방법에 대한 아이디어는 무엇입니까?

Answer 1

나는 꽤 지저분한 증거를 가지고 있습니다. 이게 조금 일하는 것으로 정리 될 수 있다고 확신합니다. 그 증거를 단순화 할 필요가 있는지 알려주세요.

증명을 위해서는 모든 용어를 재배치 할 수 있습니다. $ A_1 \ GEQ A_2 \ GEQ A_3 \ LDOTS $ . $ f (1), f (2), \ ldots, f (n) $ 몇 가지 일정이되도록하십시오. 모든 일정 $ f $ 에 대해 소요되는 총 시간은 다음에 의해 제공됩니다. $$ T (F)=MAX \ {M_ {F (1)} + A_ {f (1)}, m_ {f (1)} + m_ {f (2 )} + A_ {f (2)}, \ ldots, \ sum_ {i= 1} ^ n m_ {f (i)} + a_ {f (n)} \} $$ 모순을 위해서는 탐욕스러운 방법이 최적의 솔루션이 아니라고 가정 해보십시오. $ t (id)> t (\ phi) $ 과 같은 일정 $ \ phi $ 이 존재합니다. (여기서 $ ID $ 은 IS입니다). $ \ sum_ {i= 1} ^ K m_ {i} + a_k= t (id) $ k $ 을 선택하십시오. ) $ . $ h $ $ \ {1, \ ldots, k \} \ subset \ \ \ \ phi (1), \ ldots, \ phi (h) \} $ . $ \ phi (h) \ leq k $ 을 주목하십시오. $ \ {1, \ ldots, k \} \ subset \ {\ phi (1), \ ldots, \ phi (h) \} $ , $ \ sum_ {i= 1} ^ h m _ {\ phi (i)} \ geq \ sum_ {i= 1} ^ k m_i $ . $ A_1 \ GEQ A_2 \ GEQ \ LDOTS $ 이기 때문에 $ A _ {\ PHI (H) \ GEQ)를 알고 있기 때문입니다. A_K $ . 이것은 그것을 의미합니다 $$ \ SUM_ {i= 1} ^ K M_I + A_K \ LEQ \ SUM_ {i= 1} ^ h m _ _ \ phi (i)} + a _ {\ phi (h )} $$ 그러나 $ T (id)= sum_ {i= 1} ^ K m_i + a_k \ leq \ sum_ {i= 1} ^ h m _ _ \ phi (i) + a_ {\ phi (h)} \ leq t (\ phi) $ . 이것은 모순입니다.