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

Question

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

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

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

Например, учитывая задачи с: м ₁ = 3, а ₁ = 9 м ₂ = 2, а ₂ = 7 m ₃ = 6, a ₃ = 10

Оптимальным решением является перестановка 3, 1, 2, где задачи перекрываются следующим образом (плюсы - затраченное время в части 1, а минус - время, потраченное на часть 2):

3 ++++++---------- (6, 10)
1       +++--------- (3,9)
2          ++------- (2,7)
Total time needed: 6+3+2+7: 18

Любая другая перестановка дает более высокое общее необходимое время, например:

1 +++--------- (3,9)
2    ++------- (2,7)
3      ++++++---------- (6, 10)
Total time needed: 3+2+6+10: 21

Однако у меня возникают проблемы с доказательством что жадное решение оптимально. Есть идеи, как это сделать?

Answer 1

Я получил довольно умный ответ на этот вопрос с доказательством от противоречия в виде cs.stackexchange .

Answer 2

Чтобы решить этот вопрос, давайте сначала напишем уравнение для расчета общего времени, необходимого для выполнения N задач.

Это уравнение: t = m ₁ + a ₁ + макс ((a ₂ + m ₂ - a ₁ ), (a ₃ + m ₃ - a ₂ ), ...).

Первая часть этого уравнения (m ₁ + m ₂ + ...) - время, необходимое для выполнения первой задачи

Вторая часть уравнения более сложная. Просто max () вычисляет максимальное количество времени задачи, которое не перекрывается с первой задачей (в вашем примере это максимальное время равно 9).

Давайте теперь докажем оптимальное решение с помощью индукции. Предположим, что оптимальный ответ для n задач - это упорядочение в порядке убывания _i . Затем, если мы введем еще a _{n + 1} и m _{n + 1} и a _{n + 1} будет наименьшим значением a _i (мы можем предположить это с помощью индуктивной гипотезы), a _{n + 1} должно go оказаться в конце списка.

Чтобы доказать это, предположим, что a _{n + 1} перешел на любую другую позицию, скажем i. Тогда значения a _{i + 1} + m _{i + 1} - a _n , очевидно, будут больше, чем были раньше (и даже больше, чем _п + м _п - а _и-1 ). Следовательно, функция max () вернет значение, большее или равное ее предыдущему значению.

Теперь нам нужно доказать индуктивную гипотезу для n = 2. Предположим, что у нас есть ₁ и a ₂ .

Значение уравнения t = m ₁ + a ₁ + a ₂ + m ₂ - a ₁ , что упрощается до t = m ₁ + a ₂ + m ₂ теперь представляет интерес.

Тривиально увидеть, что ₂ должно быть меньшим значением, чтобы это уравнение было минимизировано. Таким образом, индуктивная гипотеза была доказана.