데드라인 스케줄링(Deadline Scheduling) - Job Sequencing Problem

 마감일 전에 작업이 끝나면 모든 작업의 ​​마감 시간과 관련 이익이있는 일련의 작업이 제공됩니다. 또한 모든 작업에 단일 단위 시간이 걸리므로 모든 작업의 ​​최소 마감 시간은 1입니다. 한 번에 하나의 작업 만 예약 할 수있는 경우 총 이익을 최대화하는 방법.

작업순서문제 (Job Sequencing Problem)는 마감(deadline) 전에 작업을 완료하면 해당 작업에 연관된 이익(profit)이 제공된다. 
데드라인이 있는 여러 작업들이 있을때 한번에 하나의 작업만 할 수 있는 경우 총 이익을 최대화 하는 방법을 푸는 것이다. 
조건은 모든 작업에 단일 단위 시간(single unit of time)이 걸린다는 것이다. 즉 마감이 2시간 이면 최소 모든 작업에 걸리는 시간은 1시간이므로 최소 1시부터 시작해야 작업이 완되고 이익을 얻게되는 구조이다.

단일 단위 시간은 1일이 될수도 있고 시간이 될수도 있고 해석하기 나름인데 어쨌든 주어진 데드라인보다 최소 -1 앞에서부터 시작해야한다는것이 포인트이다.

예를들어보자.

JobID	Deadline	Profit
a	4	20
b	1	0
c	1	40
d	1	30

위 예에서 최대 이익을 얻으려면  c, a 를 선택해야 한다. 왜냐면 ,b,c,d 는 데드라인이 1이니 동시에   수행할수 없다 

이 중 이익을 가장 크게 낼수 있는 것(그리디 알고리즘) 을 선택해야하니 당연히 c 를 선택하고 데드라인 일정과 겹치치 않은 나머지 a 를 선택하면 총 이익 60을 가져갈수 있는것이다.

두번재 예도 위와 같은 방법으로 풀면 되는데 

JobID	Deadline	Profit
a	2	100
b	1	19
c	2	27
d	1	25
e	3	15

 데드라인이 1인 것중(b,d) 중 이익이 높은 d를 선택, 2인것중(a,c) 이익이 높은 a를 선택, 그리고 나머지 e를 선택하면 작업시간이 겹치치 않으면서 최대의 이익을 가져갈수 있다.
 

Job Sequencing Problem를 풀기위한 알고리즘 순서이다.

알고리즘

1. 주어진 작업들에 N개를 이익이 큰 순서부터 데드라인이 겹치지 않도록 검사해야 하니 이익(profit)을 키로하여 내림차순 정렬을 한다.
2. 정렬된 작업 목록들중 첫번째 것을 선택한다.
3. 남은 N-1 작업들에 대해서 데드라인이 겹치면 다음 작업으로 넘어가고 겹치지 않으면 선택한다.

데드라인이 겹치는지 확인하기위해 몇 가지 방법이 있는데 여기서는 스케줄링을 할수 있는 배열 s를 잡고 데드라인이 1이면 싱글단위시간이 1이라 -1을 0번인덱스에 이미 작업을 했다고 마크하는 방식으로 할 것이다.
첫번째 예로 설명하면 처음 c 를 선택하면 s는 그림1과 같다.

그림1. c를 선택했을때 deadline s[c`s deadline - single uinittime = 0] = c 

그리고 데드라인이 겹치지 않은것중 이익이 가장큰 a 를 선택하면 s 는 그림2와 같다.

그림2. a를 선택했을때 deadline s[a`s deadline - single uinittime = c] = a

 

4. 최종적으로 선택된 job id들을 출력한다.

 
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
 
public class JobSequencingMain {
 
 
    public static class Job {
        char jobId ;
        int deadline ;
        int profit;
 
        public Job(char jobId, int deadline, int profit) {
            this.jobId = jobId;
            this.deadline = deadline;
            this.profit = profit;
        }
 
        @Override
        public String toString() {
            return "Job{" +
                    "jobId=" + jobId +
                    ", deadline=" + deadline +
                    ", profit=" + profit +
                    '}';
        }
    }
    public static void main(String[] args)  {
 
        List<Job> jobs = Arrays.asList(
                new Job('a', 2, 100),
                new Job('b', 1, 19),
                new Job('c', 2, 27),
                new Job('d', 1, 25),
                new Job('e', 3, 15)
 
        );
 
        List<Job> resultJobs = jobSequencing(jobs);
        for(Job job : resultJobs) {
            System.out.println(job);
        }
 
 
    }
 
 
    public static List<Job> jobSequencing(List<Job> jobs) {
 
 
        // 1.  주어진 작업들에 N개를 이익이 큰 순서부터 데드라인이 겹치지 않도록 검사해야 하니 이익(profit)을 키로하여 내림차순 정렬을 한다.
        jobs = jobs.stream()
                .sorted((a, b) -> b.profit - a.profit)
                .collect(Collectors.toList());
 
        // 2. 정렬된 작업 목록들중 첫번째 것을 선택한다.
        // 3. 남은 N-1 작업들에 대해서 데드라인이 겹치면 다음 작업으로 넘어가고 겹치지 않으면 선택한다.
 
        List<Job> result = new ArrayList<>();
        int []s = new int[4];
        
        for(Job job : jobs) {
            if(s[job.deadline-1] == 0) {
                // 이미 작업을 한 것으로 체크.
                s[job.deadline-1] = 1;
                result.add(job);
            }
        }
        return result;
    }
    
}