Scheduling, Greedy algorithm

Question

Это вариация популярной проблемы El Goog.

---

Рассмотрите следующую проблему с планированием: есть n заданий, i = 1..n. Существует 1 суперкомпьютер и неограниченные ПК. Каждое задание необходимо предварительно обработать суперкомпьютером сначала, а затем обработать на ПК. Время, требуемое для работы i на суперкомпьютере, равно si, i = 1..n. Для ПК это pi, i = 1..n. ПК могут работать параллельно, но суперкомпьютер может работать только по одной задаче за раз. Создается расписание S, согласно которому суперкомпьютер будет обрабатывать задания. Время завершения Ti (S) в расписании S задается часовым временем, на котором задание заканчивается на ПК. Мы хотим найти график, который минимизирует Maxi [Ti (s)] (для чтения: нам нужно найти расписание, которое минимизирует наивысшее время окончания). Предлагается следующий жадный алгоритм: упорядочить задания в порядке убывания времени обработки на ПК. Сложность этого алгоритма O (nlogn). Либо докажите, что этот алгоритм создает оптимальное решение, либо обеспечивает встречный пример, чтобы показать, что он этого не делает.

---

Мое решение (не уверен, что это правильно): Я не думаю, что важно, как мы заказываем работу. Самое высокое время окончания будет по-прежнему одинаковым. Рассмотрим этот пример времени обработки на ПК для списка заданий: < 5, 7, 17, 8, 10>. Это даст время окончания, как < 5, 12, 29, 37, 47>. В соответствии с алгоритмом мы отсортируем список как < 17, 10, 8, 7, 5> и дадим время окончания < 17, 27, 35, 42, 47>. Поэтому, в то время как технически, жадный алгоритм дает оптимальный порядок, для этого требуется nlogn time, а просто повторение списка заданий дает нам тот же результат.

Если кто-то думает, что жадный алгоритм будет работать лучше или что мой подход испорчен, я буду благодарен за ваши мысли. Спасибо!

---

Update: Я думаю, что, возможно, есть ответ. Время, затраченное суперкомпьютером, не имеет значения. Ключом здесь является то, что ПК работают в параллельно. Из исходного примера pi = < 5, 7, 17, 8, 10>, добавим si = < 8, 5, 1, 12, 9>. Теперь в неустановленном порядке по умолчанию у нас будет время обработки < 13, 20, (8 + 5 + 1 + 17 =) 31, 34, 45>. Так что 45 - это время завершения. Предположим, что отсортированный порядок, в котором pi уменьшаются. Выход: < 18, 20, 30, 34, 40>. [Отсортированный вход: pi = < 17, 10, 8, 7, 5>, si = < 1, 9, 12, 5, 8>].

Вот пример, который, вероятно, очищает все это: si = < 17, 10>, pi = < 10, 17>. Вывод в несортированном случае (который также сортируется в порядке убывания si) будет < 27, 44>. Сортировка на основе pi, входной сигнал: si = < 10, 17>, pi = < 17, 10>. Выход: < 27, 37>. Поскольку ПК работают параллельно, вы хотите отправить самое короткое задание последним.

Answer 1

Для Ограниченное число ПК:

w.l.o.g Предположим, что нет суперкомпьютер, ваша проблема будет конвертирован в Minmum Makespan Scheduling задачи (или ppt), которая является NP-трудной. Таким образом, ваш текущий алгоритм не работает или P = NP.

Но жадные алгоритмы полезны для приближений. Также вы можете преобразовать Bin Packing в эту проблему, и по фиксированному количеству ошибок для приближения найти хорошие результаты, но время выполнения не будет хорошим полиномом (например, n^10).

P.S: Вы можете просто предположить, что нет супер компьютер, для этого считать экземпляр таким образом, что Max (s _я) < Min (P _я).

P.S2: Сначала я не видел неограниченное количество компьютеров, поэтому я написал это, я буду думать о неограниченном количестве ПК.

UnLimited случай:

Ваш текущий алгоритм не так, пусть это условия:

For PCs: <5, 7, 17, 8, 10> 
For super computer: <1000,800,500,600,700). 

Ваше текущее решение будет терпит неудачу.

Answer 2

S={a1,a2,...,an} of n unit-time task. Задача единичного времени требует ровно 1 единицу времени для завершения крайних сроков d1,d2,...,dn, 1<=di<=n штрафы w1,w2,...,wn. Штраф wi понесен, если задание ai не завершено к моменту времени di, и штраф в случае завершения задания в крайний срок.

Проблема заключается в том, чтобы найти график S, который минимизирует общую неустойку понесены за пропущенные сроки

У меня проблема относительно этого. Это выглядит следующим образом

ai 1 2 3 4 5 6 7 
di 4 2 4 3 1 4 6 
wi 70 60 50 40 30 20 10 

Решение этой проблемы заключается в

{a2,a4,a1,a3,a7,a5,a6} 
penalty, w5+w6=50 

Answer 3

Рабочие места должны быть заказаны в порядке убывания времени ПК.
Источник - http://mypathtothe4.blogspot.in/2013/03/greedy-algorithm-example.html