<휴리스틱 flow shop 스케줄링 사례로 이해해보기>
Pw를 내림차순으로 배열하여 작업(J) 우선순위 정하기
이것을 하는 이유는 처리 시간이 긴 작업을 우선적으로 처리하고, 더 높은 우선순위를 부여하여 전체 작업의 소요 시간을 최소화하기 위한 전략입니다.
<Makespan : 모든 작업의 최소 완료시간의 합 구하기>
<유휴 시간 이해해 보기>
Ex) J3의 M2를 구할 때, J3행의 9(왼쪽 값)과, M2열의 8(위쪽 값) 중 더 큰 값을 선택.
왼쪽 값을 쓰게 될 때에 기계가 놀고 있는 시간, 즉 유휴시간이 발생한다.
J3라는 작업을 기계1이 아직 하고 있는데… 기계2가 J4라는 앞 일을 먼저 끝낸 경우
기계2는 전기는 먹고 있는데 놀고 있는 현상이 발생함.
Makespan이란?
Makespan은 모든 작업이 완료되기까지 걸리는 시간 또는 작업이 모두 완료되는 시점까지의 시간을 나타냅니다. 즉, 작업의 시작부터 마지막 작업이 끝날 때까지 걸리는 총 시간을 말합니다.
스케줄링 문제에서 목표는 작업들을 어떤 순서로 배치하여 최소의 makespan을 달성하는 것입니다. Makespan이 최소화되면 작업들이 가장 효율적으로 처리되는 것을 의미합니다.
<각 기계들의 최저 시간 구하기 : Makespan의 달성도를 평가하기 위한 기준을 구하는 과정 >
위의 표와같이 M1, M2, M3의 합을 구한뒤,
구하고자 하는 줄의 합계 + 나머지줄의 합 중 가장 작은 합
단, 작업이 이어지지 않는 경우, LB1처럼 같은 행에서 두 합을 더한 값을 찾을 필요없다.
LB2처럼 다른 행에서 각각 제일 작은 값들을 취할 수 있다.
밑에 식들을 참고하면 이해가 바로 될 것이다.
< Makesapn(H), LB(O) H – O / O * 100 식으로 평가하는 이유. >
상대적 비교: makespan과 LB 사이의 차이를 백분율로 표현하여 상대적인 비교를 할 수 있습니다. makespan이 LB에 비해 얼마나 큰지를 상대적으로 파악할 수 있습니다.
최적해 대비 품질 평가: 실제 makespan을 최적해에 비교하는 것은 어렵거나 불가능할 수 있습니다. 따라서, 하한 값인 LB를 사용하여 makespan의 품질을 상대적으로 평가할 수 있습니다. 식을 통해 얻은 백분율 값은 makespan이 LB에 비해 얼마나 우수한지를 보여줍니다.
알고리즘 성능 평가: 휴리스틱 알고리즘 등을 사용하여 makespan을 계산하는 경우, 이 식을 통해 알고리즘의 성능을 평가할 수 있습니다. 식을 계산하여 얻은 값이 낮을수록 알고리즘이 LB에 더 가까운 해를 도출하는 것으로 평가할 수 있습니다.
'📈알고리즘 > 알고리즘' 카테고리의 다른 글
| NP-완전 문제 (0) | 2023.05.24 |
|---|---|
| 근사 알고리즘(1)[여행자 문제, 정점 커버 문제, 통 채우기 문제] (0) | 2023.05.22 |
| 유전자 알고리즘 이해해보기 (0) | 2023.05.17 |
| 쉘 정렬 , 힙 정렬, 정렬 문제의 하한 (0) | 2023.05.08 |
| 버블정렬, 선택정렬, 삽입정렬 (0) | 2023.05.04 |