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

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

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

Решение

Давайте рассмотрим, набор из 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 2 , J 1 , J 3 ), которые выполняются в установленные сроки и дают максимальную прибыль.

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