DAA-마감일이있는 작업 순서 지정

문제 설명

작업 순서 문제에서 목표는 마감일 내에 완료되고 최대 이익을 제공하는 일련의 작업을 찾는 것입니다.

해결책

고려해 보겠습니다. n마감일까지 작업이 완료되면 마감일 및 수익과 관련된 일자리가 주어집니다. 이러한 작업은 최대 이익이있는 방식으로 주문해야합니다.

주어진 모든 작업이 기한 내에 완료되지 않을 수 있습니다.

가정, 기한 ithJi 이다 di 이 직업에서 얻은 이익은 pi. 따라서이 알고리즘의 최적 솔루션은 최대 수익으로 실현 가능한 솔루션입니다.

따라서 $ D (i)> 0 $ for $ 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 2 1
이익 60 100 20 40 20

해결책

이 문제를 해결하기 위해 주어진 일자리는 수익에 따라 내림차순으로 정렬됩니다. 따라서 정렬 후 작업은 다음 표와 같이 정렬됩니다.

J2 J1 J4 J3 J5
마감 시간 1 2 2 1
이익 100 60 40 20 20

이 작업 세트에서 먼저 J2, 마감일 내에 완료 할 수 있으며 최대 수익에 기여합니다.

  • 다음, J1 더 많은 이익을 제공하기 때문에 선택됩니다 J4.

  • 다음 시계에 J4 마감일이 지났기 때문에 선택할 수 없습니다. J3 기한 내에 실행되므로 선택됩니다.

  • 작업 J5 기한 내에 실행할 수 없으므로 폐기됩니다.

따라서 솔루션은 일련의 작업 (J2, J1, J3), 기한 내에 실행되고 최대 이익을 제공합니다.

이 시퀀스의 총 이익은 100 + 60 + 20 = 180.