貪欲な順次/並列タスクスケジューリング

Question

処理のためにスケジュールする必要があるNタスクを持っています。各タスクは、順番に実行する必要がある2つの部分で構成されています。最初のものはミューテックスによって保護され、したがってこの部分を一度に実行することができるタスクは1つだけです。 2番目の部分にはそのような制約はありません。また、任意の数のタスクが同時に実行される可能性があります。タスクiの場合、各部分に費やす必要がある時間、すなわちガード部分のM _{i 、並列に実行できる部分の i を知っています。 。}

問題は、それらのすべての実行に必要な時間が最小化されるようなタスクの置換を見つけることです。

私の直感は、このタスクを降りて降順にスケジュールすることによって、これが貪欲なアルゴリズムで解決されることができます。

たとえば、タスクを指定した場合：
m _{1 = 3、a 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）} \} $$ 。

矛盾のために、あなたの欲張り方法が最適な解決策ではないとしましょう。 $ \ phi $ が存在するスケジュールがあります。 $ t（id）> t（\ phi）$ （ここで $ id $ はIDです）です。 $ k $ を選択して、 $ \ sum_ {i= 1} ^ k m_ {i} + a_k= t（ID ）$ 。 $ 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 _ {\ fi（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）$ 。これは矛盾です。