짧은 일부터 처리하면, 끝날 때까지의 비용도 최소일까요?

처리자가 세 일을 한 번에 하나씩 끝내요. 모두 시각0부터 시작할 수 있고, 시작한 일은 중단하지 않으며 빈 시간을 넣지 않아요. 각 일은 시작 전과 처리 중 모두 완료될 때까지 시간당 비용 w를 내요. 처리시간 p와 비용률은 자체 수치예요.

완료시각을 Cᵢ라 할 때 총비용 ΣwᵢCᵢ를 최소로 하는 순서를 구해 볼까요? 짧은 일부터 또는 비용률이 큰 일부터 하면 되나요? 임의의 서로 다른 n개 일에서 pᵢ,wᵢ>0일 때 모든 최적 순서의 조건도 증명해 볼까요?

이웃한 i,j 전에 이미 T시간 지났다고 해 볼까요? i→j와 j→i의 비용 차는

뒤의 일은 두 순서 모두 T+pᵢ+pⱼ 후에 시작해 변하지 않아요. 따라서 pᵢ/wᵢ≤pⱼ/wⱼ일 때 i를 먼저 하는 편이 비용을 늘리지 않아요. 이 예의 비는 B가1/2,A가6/7,C가1이므로 B→A→C입니다. 완료시각은2,8,9라 최소비용은4×2+7×8+1×9=73입니다. 짧은 순 C→B→A는76, 비용률 순 A→B→C는83입니다.

두 일의 비교만으로 전체 최적성이 되는 이유도 적어 볼게요. 비용은 각 일 자체의 wᵢpᵢ와, i가 j보다 앞이면 생기는 pᵢwⱼ를 모든 두 일에 걸쳐 더한 값이에요. 각 쌍의 추가 비용은 min(pᵢwⱼ,pⱼwᵢ)보다 작을 수 없어요. p/w가 작아지는 일이 없도록 정렬하면 모든 쌍에서 이 하한을 동시에 얻으므로 전체 비용도 최소예요.

반대로 그 비율 순서가 깨진 배열에는 이웃한 엄격한 역전이 있어요. 두 일을 바꾸면 위 차가 양수여서 비용이 줄므로 그 배열은 최적일 수 없어요. 따라서 최적 순서일 필요충분조건은 p/w의 비감소 순서예요. 비가 모두 다르면 순서는 유일하고, 같은 비끼리는 어느 순서로 바꿔도 비용이 같아요. 서로 다른 비의 동률 묶음 크기가 m₁,…,mₖ이면 최적 순서는 m₁!⋯mₖ!개예요.

여기서 비용은 끝날 때까지의 시간에 붙어요. 시작 전 대기만 합산하는 다른 기준과 섞지 않아요. 원문이 설명한 이웃 교환을 자체 세 일에 적용하고, 모든 쌍의 하한과 동률 경우까지 직접 증명했어요. 무엇을 먼저 하겠다는 직관을 적은 뒤, 그 규칙이 최소로 하려는 양을 식으로 확인해 봐요.

출처·착안: Stanford CS161, Lecture14 — Greedy Algorithms의 Scheduling. 자체 조건·수치·문항·최적 순서 전체의 증명을 새로 작성했다.