초록

용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

다중 프로세서 시스템이 개발됨에 따라, 새로운 일정계획문제, 하나의 작업이 하나이상의 기계에 의해 동시에 처리되어야 하는 문제가 대두되었다. 이 연구에서는 선행관계를 가진 이러한 다중 프로세서 일정계획문제에 대해 다루어 보았다. 이 연구의 목적은 makespan을 최소화하는 일정계획을 찾는 것이다. 일반적으로 Branch and Bound 기법을 이용하여 선행관계를 가진 다중 프로세서 일정계획문제의 최적해를 찾았는데, 해의 탐색시간이 너무 오래 걸린다는 단점이 있었다. 본 연구에서는 짧은 시간 내에 최적해와 가까운 근사해를 simulated annealing(SA)방법을 이용하여 구해보았다. SA의 성능을 측정하기 위하여, SA의 CPU 처리시간과 구한 근사해를 40개의 예제문제를 통하여 Kramer의 방법의 CPU 처리시간과 최적해와 비교해 보았다.

다중 프로세서 시스템이 개발됨에 따라, 새로운 일정계획문제, 하나의 작업이 하나이상의 기계에 의해 동시에 처리되어야 하는 문제가 대두되었다. 이 연구에서는 선행관계를 가진 이러한 다중 프로세서 일정계획문제에 대해 다루어 보았다. 이 연구의 목적은 makespan을 최소화하는 일정계획을 찾는 것이다. 일반적으로 Branch and Bound 기법을 이용하여 선행관계를 가진 다중 프로세서 일정계획문제의 최적해를 찾았는데, 해의 탐색시간이 너무 오래 걸린다는 단점이 있었다. 본 연구에서는 짧은 시간 내에 최적해와 가까운 근사해를 simulated annealing(SA)방법을 이용하여 구해보았다. SA의 성능을 측정하기 위하여, SA의 CPU 처리시간과 구한 근사해를 40개의 예제문제를 통하여 Kramer의 방법의 CPU 처리시간과 최적해와 비교해 보았다.

주제어

#Scheduling   #Multiprocessor tasks   #Simulated Annealing  

AI 본문요약

엑셀 다운로드 AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

• 연구 주제
• 연구 방법
• 연구 결과

문제 정의

• 단점이 있다. 그러므로, 본 연구에서는 Simulated Annealing(SA» 이용하여 빠른 시간 내에 최적해와 별로 차이가 없는 근사해를 찾아 보았다. 결과에서 보는 대로 SA에 의해 구한 해는 많은 경우에 최적해를 찾을 수 있었고, 모든 경우에 있어 좋은 해를 짧은 컴퓨터 CPU시간에 제공해 주었다.
• 만약 작업들 ■/와 4 동시에 처리될 수 있다면 이러한 관계는 평행관계(parallel relationship)로 정의하고 ■시I /로 표시하기로 한다. 본연구에서는 평행관계를 가진 작업들만 고려하여 인접해들을 탐색하도록 한다.

제안 방법

• 수락되도록 충분히 높게 설정되어야 한다. 또한, 온도제어 패러미터를 탐색과정에 따라 감소시키는 방법을 쿨링스케쥴이라고 하는데 본 연구에서는 일반적으로 자주 쓰이는 다음 방법을 쓰기로 한다: Tk+l=aTk, 여기서 k는 현재의 반복횟수이고 其는 쿨링스케쥴에서의 현재 온도이다. 패러미터 a는 일반적으로 0.
• 우⑵는 순열 flowshop에서 makespan을 최소화하는 문제를 SA를 이용해 풀어보았다. 또한, 김 [1]은 TSP(Traveling salesman problem)를 엔트로피 개념을 이용해 개선한 SA를 적용하여 좋은 해를 구했다.
• Chen 과 Lee [6]는 작업의 기계에 대한 할당과 일정계획을 모두 고려한 일반적인 다중 프로세서문제를 연구했다. 특히, 기계가 두 대일 때와 세 대일 때의 특수한 경우에는 최적해를 찾는 방법을 동적계획법을 이용해 개발했다. Blazewicz et al.

대상 데이터

• 불리는 두 가지의 데이터 종류가 사용 되었는더】, 각 종류의 데이터는 10개의 예제들이 포함되어 있다. 각 예제들은 5개의 기계로 구성되어 있고, r data에 대해서는 20개 혹은 30개의 작업들이, vdata에 대해서는 20개 혹은 40개의 작업들로 구성되어 있다.

데이터처리

• SA 기법의 결과는 Kramer의 branch and bound 기법의 결과와 비교되었다. SA는 'C 언어, 로 구현되어 800MHz p/c로 실행되었고, Kramer의 방법은 역시 C 언어, 로 구현되어 Sun 4/20 Workstation0]]의해 실행되었다.

성능/효과

• 20개의 작업들이 있는 예제들[Table 2]와 [Table 4]인 경우에는 거의 대부분 SA에 의해 최적해를 찾을 수 있었고, 작업수가 30개 혹은 40개인 경우에는 SA에 의한 해는 대부분의 경우 최적해와 차이가 있었다. 그렇지만, 이러한 차이, 즉, error율은 크지 않아서 최악인 경우 7.
• 그러므로, 본 연구에서는 Simulated Annealing(SA» 이용하여 빠른 시간 내에 최적해와 별로 차이가 없는 근사해를 찾아 보았다. 결과에서 보는 대로 SA에 의해 구한 해는 많은 경우에 최적해를 찾을 수 있었고, 모든 경우에 있어 좋은 해를 짧은 컴퓨터 CPU시간에 제공해 주었다. 특히, 작업들의 수가 20 개인 경우에는 대부분 최적해를 찾은 반면, 작업의 수가 증가할수록(30개 혹은 40개) 최적해와의 차이가 발생하게 되었다.
• 모든 경우에 있어 SA는 1, 2초내에 근사해를 제공한 반면, Kramei의 기법은 최소 13.9초, 최대 5시간에 최적해를 제공했다. 그러므로, SA는 좋은 해를 짧은 시간 내에 제공한다고 할 수가 있겠다.
• 05%에 지나지 않았다. 특히, 40개의 예제들 중 세 가지 예제들에서는 Kramer의 알고리듬이 5시간동안 최적해를 찾지 못하고 그 시간동안의 최선해가 괄호안에 기록되었는데, SA에 의해 제공된 해가 최선해보다 나았다.

후속연구

• 특히, 작업들의 수가 20 개인 경우에는 대부분 최적해를 찾은 반면, 작업의 수가 증가할수록(30개 혹은 40개) 최적해와의 차이가 발생하게 되었다. 그러므로, 작업의 수가 많은 경우에는 좀 더 나은 해를 제공할 수 있는 새로운 기법의 연구가 필요하다.

본문요약 정보가 도움이 되었나요? 예 아니오 제출

이 논문을 인용한 문헌

더보기

저자의 다른 논문 :

이동주 (30) 황인극 (21) 김진호 (28)