Жадное последовательное/параллельное планирование задач

Question

У нас есть N задачи, которые необходимо запланировать для обработки.Каждое задание состоит из двух частей, которые необходимо выполнять по порядку.Первый защищен мьютексом, поэтому одновременно эту часть может выполнять только одна задача.Во второй части такого ограничения нет, и любое количество задач может выполняться одновременно.Для задачи i мы знаем, сколько времени ему необходимо потратить на каждую часть, а именно м_я для охраняемой части и_я для той части, которая может выполняться параллельно.

Проблема состоит в том, чтобы найти такую ​​перестановку задач, чтобы время, необходимое для их выполнения, было минимальным.

Моя интуиция подсказывает, что это можно решить жадным алгоритмом, планируя задачи по спуску_я заказ.

Например, учитывая задачи с:
м₁ = 3, а₁ = 9
м₂ = 2, а₂ = 7
м₃ = 6, а₃ = 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)$ (здесь $Идентификатор$ это личность).Выбирать $к$ такой, что $\sum_{i = 1}^k m_{i} + a_k = T(Id)$.Позволять $ч$ быть наименьшим числом таким, что $\{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( \фи)$.Это противоречие.