13일차 이후 ... - 그리디 배치(1차 MVP)

13일차까지 WebSocket, FullCalendar, 실시간 동기화까지 꾸준히 올렸는데

그 이후로 블로그에는 업데이트를 못 올리고 있었다.

그동안 개발은 계속 진행 됐고, 20일차 까지는 자동 스케줄링 엔진의 기본 구조, 그리디 배치, 점수 모델, 시간 슬롯 분할 / 연속 배치,  진행률 브로드캐스트까지는 전부 완성했다. ( + AWS EC2 배포까지 함 : http://54.206.65.33:8080 )

 

21일차 기준으로는 : 

 

• 캘린더 자동 업데이트 연동 완료
  • ScheduleGenerateResponse → FullCalendar 형식 반환
  • 프런트에서 생성된 스케줄이 바로 UI에 반영됨
• 점수 시각화는 일부만 완료
  • 백엔드: schedule.setScore() 까지 구현
  • 프런트: 점수 표시 UI 아직 없음

즉, 엔진 자체는 돌아가는 상태고, 이제 결과를 어떻게 보여줄지 남아 있는 상황.

프로젝트 전체 흐름에서 Week 3(자동 스케줄링 엔진 MVP)의 핵심 목표는 작업을 어떻게 자동으로 배치하고, 마감일과 우선순위를 고려해 가장 적절한 시간대에 넣을 것인가였다.
그 엔진의 중심이 되는 로직이 바로 그리디 기반 작업 최적화 알고리즘이다.

그래서 오늘은, 자동 스케줄링 기능이 어떤 기준으로 작업을 정렬하고, 어떻게 연속 슬롯을 찾고 배치하며, 점수를 계산해서 최적해에 가깝게 만드는지 구현했던 코드를 기반으로 전체 구조를 정리해보려고 한다.

---

작업 최적화 알고리즘 

아래는 전체 자동 스케줄링 로직을 “흐름 → 핵심 코드 → 설명” 형태로 정리한 내용이다

 

step 1. 작업 정렬 (마감일 → 우선순위 기준)

List<Task> sortedTasks = tasks.stream()
    .sorted(Comparator
        .comparing((Task t) -> {
            if (t.getDueAt() == null) return Long.MAX_VALUE;
            return Duration.between(OffsetDateTime.now(), t.getDueAt()).toMillis();
        })
        .thenComparing(Comparator.comparing(Task::getPriority).reversed()))
    .collect(Collectors.toList());

 

정렬 기준

• 마감일 임박 → 먼저 배치
• 마감일 없음 → 가장 뒤
• 같은 마감일이면 우선순위 높은 작업부터 처리

---

step 2. 그리디 방식으로 작업 순회 → 배치 시도 

Map<Long, List<TimeSlot>> usedSlots = new LinkedHashMap<>();
for (Task task : sortedTasks) {
    List<Assignment> taskAssignments = tryAssignTask(task, sortedSlots, usedSlots, schedule);
    if (taskAssignments != null) assignments.addAll(taskAssignments);
}

 

역할

• 정렬된 작업 순서대로 배치
• 사용된 슬롯은 usedSlots에 기록하여 중복 배치 방지
• 배치 실패한 작업은 넘어감

---

step 3. 각 작업에 대해 배치 가능한 연속 / 분할 슬롯 찾기 

int requiredSlots = (int) Math.ceil(task.getDurationMin() / 30.0);
List<Long> candidates = targetUserOnly ? List.of(targetUserId) : allUsers;

for (Long userId : candidates) {
    List<TimeSlot> slots = findConsecutiveSlots(...);
    if (slots != null) return createAssignments(...);
}

핵심 포인트

• 작업 시간(분) → ‘필요한 30분 슬롯 개수’로 변환
• 작업 배정자가 있으면 해당 사용자만 대상으로 배치
• 없으면 팀의 모든 사용자에게 배치 시도
• 연속 슬롯 우선, 없으면 분할 가능 시 split 슬롯 탐색

---

step 4. (분할 불가능한 작업) 연속 슬롯 탐색

// 마감일 여부에 따라 정렬 전략 변경
// 24시간 이상 여유 → 선호도 우선
// 임박 → 마감일 거리 우선
// 마감일 없음 → 선호도 단독 기준

 

연속성 판단

if (first.isConsecutive(next)) { ... }

연속된 슬롯이 requiredSlots 개수만큼 모이면 배치 성공 ! 

---

step 5. (분할 가능 작업) split 배치

연속 슬롯을 먼저 찾고, 불가능할 때만 분할 배치. 

List<TimeSlot> selectedSlots = freeSlots.stream()
    .limit(requiredSlots)
    .collect(Collectors.toList());

마감일 이전에 끝나는지 마지막 슬롯으로 검증

---

step 6. 점수 계산 (Hard / Soft 제약 기반)

• Hard 제약 (위반 시 0점)

Hard constraint는 절대 어기면 안되는 조건임 

// 마감일 준수 + 사용자 근무시간 내 배치
if (assignment.getEndsAt().isAfter(task.getDueAt())) return false;

 

• Soft 제약 점수 (가감점)

- 우선순위 점수

- 마감일 여유 점수

- 분할 페널티

- 선호도 페널티

- 연속성 보너스

- 기본 점수 1000점에서 +- 가감 

 

최종 점수는 : 

return Math.max(0, score);

---

전체 흐름 요약 

1. 작업을 먼저 정렬한다.
   - 마감일 임박 → 우선순위 높은 작업 순
   
   
2. 각 작업을 순서대로 배치 시도한다.
   - 연속 슬롯 가능하면 그쪽 우선
   - 불가능하면 분할(Split) 슬롯으로 배치
   
   
3. 사용자 근무 가능 시간 / 마감일 조건을 모두 만족하는지 확인
   
   
4. Assignment 리스트 생성
   
   
5. 전체 스케줄에 대해 점수를 계산해 최종 결과 반환