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

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

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

Решение

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

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

Допустим, срок ith работа Ji является di и прибыль, полученная от этой работы, составляет pi. Следовательно, оптимальное решение этого алгоритма - возможное решение с максимальной прибылью.

Таким образом, $ 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) $.

пример

Давайте рассмотрим набор заданий, как показано в следующей таблице. Нам нужно найти последовательность работ, которые будут выполнены в срок и принесут максимальную прибыль. Каждая работа связана с дедлайном и прибылью.

Работа J1 J2 J3 J4 J5
Крайний срок 2 1 3 2 1
Прибыль 60 100 20 40 20

Решение

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

Работа J2 J1 J4 J3 J5
Крайний срок 1 2 2 3 1
Прибыль 100 60 40 20 20

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

  • Следующий, J1 выбран, так как он дает больше прибыли по сравнению с J4.

  • В следующие часы, J4 не может быть выбран, поскольку его крайний срок истек, поэтому J3 выбирается по мере выполнения в установленный срок.

  • Работа J5 отбрасывается, так как не может быть выполнен в срок.

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

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