DAA - последовательность работ с указанием крайнего срока

Постановка задачи

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

Решение

Рассмотрим набор nзаданные задания, которые связаны со сроками, и прибыль получается, если работа завершена к установленному сроку. Эти работы нужно заказывать таким образом, чтобы получить максимальную прибыль.

Может случиться так, что все поставленные работы не будут выполнены в установленные сроки.

Допустим, срок i^th работа 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₁	J₂	J₃	J₄	J₅
Крайний срок	2	1	3	2	1
Прибыль	60	100	20	40	20

Решение

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

Работа	J₂	J₁	J₄	J₃	J₅
Крайний срок	1	2	2	3	1
Прибыль	100	60	40	20	20

Из этого набора заданий сначала выбираем J₂, так как он может быть завершен в срок и приносит максимальную прибыль.

Следующий, J₁ выбран, так как он дает больше прибыли по сравнению с J₄.
В следующие часы, J₄ не может быть выбран, поскольку его крайний срок истек, поэтому J₃ выбирается по мере выполнения в установленный срок.
Работа J₅ отбрасывается, так как не может быть выполнен в срок.

Таким образом, решение представляет собой последовательность работ (J₂, J₁, J₃), которые выполняются в срок и приносят максимальную прибыль.

Общая прибыль этой последовательности составляет 100 + 60 + 20 = 180.