선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 다음 장에서는 실험을 통하여 제안하는 알고리듬과 기존의 Aggoune(2004)에서 제안한 알고리듬의 결과를 비교하여 제안하는 알고리듬이 얼마나 향상되었는지 알아보고자 한다.
- 실험결과두 알고리듬간의 성능에 대한 차이가 거의 없는 것으로 나타났다. 따라서 본 연구에서는 Aggoune(2004) 이 제안한 알고리듬보다 향상된 유전 알고리듬을 제안하고 이를 실험을 통해 보이고자 한다.
- 또한 긴 작업시간을 가지는 작업이 앞쪽에 배치되게 되면, 작업시간이 긴 작업이 먼저 할당될 확률이 높아지고 이것은 다음기계에서 해당 작업이 할당될 수 있는 범위를 좁혀 makespan을 증가시키는 요인이 된다. 따라서 이러한 문제를 개선하여 유휴시간의 발생을 최소화한 Schedule generator를 제안하고자 한다. 다음절에서 본 연구에서 제안하는 Schedule generator에 대해서 알아보고 그 절차를 설명하고자 한다.
- 본 연구는 NP-hard 문제인 기계가용성 제약을 고려한 흐름공정상황 하에서 makespan을 최소화하는 문제로 본연구에서 이 문제에 대해 알고리듬을 제안하였다.
- 문제를 해결하는 방법으로 타부서치와 유전 알고리듬 등이 소개되어 왔다. 본 연구에서는 m대의 기계에 각각 기계 비가용구간이 두 구간 존재하는 문제를 해결하는 향상된 알고리듬을 제안하였다. 그 결과 기존에 Aggoune(2004)이 제안하였던 알고리듬보다 거의 동일한 계산시간을 가지고 평균적으로 15%향상된 결과를 얻을 수 있었다.
- 예를들면, 기계가 오작동할 경우 기계를 멈추고 수리해야 할 때 기계가 가용하지 않게 되고, 기계를 정기적으로 점검해야 하는 상황에서도 기계의 비가용구간이 존재하게 된다. 본 연구에서는 이러한 기계가용성 제약을 고려한 흐름공정 문제에 대해 다루고자 한다.
- 따라서 본 연구에서도 비순열(non-permutation)스케줄을 허용하고 작업이 non-preemptive함을 가정한다. 이러한 문제 상황에서 makespan을 최소화하는 해를 구하는 것이 이 문제의 목적이다. Aggoune(2004)은 위의 문제에 대한 해법으로 유전 알고리듬과 타부서치를 제시하였는데 실험결과 두 알고리듬이 유사한 성능을 가진다고 보고하였다.
가설 설정
- 기존의 많은 흐름공정(flowshop)문제에서는 n개의 작업들이 m대의 기계를 모두 거칠 때 기계가 언제나 가용 가능하다는 가정을 한다. 하지만 이러한 가정은 실제 산업현장의 상황과 비추어 보았을 때, 현실적이지 못한 경우가 있다.
- 이러한 문제에 대해서 Aggoune(2004)의 연구에서 순열 스케줄이 꼭 좋은 해를 얻는 것은 아님을 증명을 하였다. 따라서 본 연구에서도 비순열(non-permutation)스케줄을 허용하고 작업이 non-preemptive함을 가정한다. 이러한 문제 상황에서 makespan을 최소화하는 해를 구하는 것이 이 문제의 목적이다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.