Задача определения последовательности заданий состоит в том, чтобы найти последовательность заданий, которая выполняется в установленные сроки и дает максимальную прибыль.
Решение
Давайте рассмотрим, набор из n заданных заданий, которые связаны со сроками и прибыль получается, если задание завершено к его крайнему сроку. Эти рабочие места должны быть заказаны таким образом, чтобы была максимальная прибыль.
Может случиться так, что все данные задания не будут выполнены в установленные сроки.
Предположим, срок выполнения i- го задания J i — d i, а прибыль, полученная от этого задания, — p i . Следовательно, оптимальное решение этого алгоритма является возможным решением с максимальной прибылью.
Таким образом, $ D (i)> 0 $ для $ 1 \ leqslant i \ leqslant n $.
Первоначально эти задания упорядочены в соответствии с прибылью, т.е. $ p_ {1} \ geqslant p_ {2} \ geqslant p_ {3} \ geqslant \: … \: \ geqslant p_ {n} $.
Algorithm: Job-Sequencing-With-Deadline (D, J, n, k)
D(0) := J(0) := 0
k := 1
J(1) := 1 // means first job is selected
for i = 2 … n do
r := k
while D(J(r)) > D(i) and D(J(r)) ≠ r do
r := r – 1
if D(J(r)) ≤ D(i) and D(i) > r then
for l = k … r + 1 by -1 do
J(l + 1) := J(l)
J(r + 1) := i
k := k + 1
Анализ
В этом алгоритме мы используем два цикла, один внутри другого. Следовательно, сложность этого алгоритма составляет $ O (n ^ 2) $.
пример
Давайте рассмотрим набор заданий, как показано в следующей таблице. Мы должны найти последовательность заданий, которые будут выполнены в установленные сроки и принесут максимальную прибыль. Каждая работа связана со сроками и прибылью.
| работа | J 1 | J 2 | J 3 | J 4 | J 5 |
|---|---|---|---|---|---|
| Крайний срок | 2 | 1 | 3 | 2 | 1 |
| прибыль | 60 | 100 | 20 | 40 | 20 |
Решение
Чтобы решить эту проблему, данные работы сортируются в соответствии с их прибылью в порядке убывания. Следовательно, после сортировки задания упорядочиваются, как показано в следующей таблице.
| работа | J 2 | J 1 | J 4 | J 3 | J 5 |
|---|---|---|---|---|---|
| Крайний срок | 1 | 2 | 2 | 3 | 1 |
| прибыль | 100 | 60 | 40 | 20 | 20 |
Из этого набора заданий сначала выбираем J 2 , так как он может быть выполнен в установленные сроки и приносит максимальную прибыль.
-
Затем выбирается J 1, поскольку он дает больше прибыли по сравнению с J 4 .
-
На следующих часах J 4 не может быть выбран, поскольку его крайний срок истек, поэтому J 3 выбирается, поскольку он выполняется в пределах своего крайнего срока.
-
Задание J 5 отбрасывается, поскольку оно не может быть выполнено в срок.
Затем выбирается J 1, поскольку он дает больше прибыли по сравнению с J 4 .
На следующих часах J 4 не может быть выбран, поскольку его крайний срок истек, поэтому J 3 выбирается, поскольку он выполняется в пределах своего крайнего срока.
Задание J 5 отбрасывается, поскольку оно не может быть выполнено в срок.
Таким образом, решение — это последовательность заданий ( J 2 , J 1 , J 3 ), которые выполняются в установленные сроки и дают максимальную прибыль.
Общая прибыль этой последовательности составляет 100 + 60 + 20 = 180 .