1 |
1
담금질 기법(Simulated Annealing, SA) 기반의 이동 수단 재배치를 위한 스케줄링 방법에 있어서,이동 수단의 과잉 상태로 인해 이동 수단의 배출이 필요한 출발 위치들의 출발지 번호들과 이동 수단의 부족 상태로 인해 이동 수단의 공급이 필요한 목적 위치들의 목적지 번호들을 지정하는 단계;상기 출발지 번호들의 적어도 일부와 상기 목적지 번호들의 적어도 일부를 동일 비율 및 임의의 순서로 포함하되, 출발지 번호와 목적지 번호가 교번하도록 포함하는 정수 벡터에 해당하는 제1 후보 해를 결정하는 단계;상기 제1 후보 해에서 임의의 출발지 번호와 임의의 목적지 번호의 쌍으로 구성된 교환 쌍을 선택하는 단계;상기 제1 후보 해에서 상기 교환 쌍의 상기 출발지 번호와 상기 목적지 번호에 따른 원소 교환을 수행하여 제2 후보 해를 결정하는 단계;상기 제1 후보 해의 제1 적합도 및 상기 제2 후보 해의 제2 적합도를 평가하는 단계;상기 제1 적합도 및 상기 제2 적합도에 기초하여 상기 제1 후보 해 및 상기 제2 후보 해 중 어느 하나에 따른 SA를 수행하여 최종 해를 도출하는 단계; 및상기 최종 해에 대응하는 재배치 스케줄을 결정하는 단계를 포함하는 스케줄링 방법
|
2 |
2
제1항에 있어서,상기 교환 쌍을 선택하는 단계는0 내지 2*M-1 사이의 난수에 해당하는 R1, 및 0 내지 M-1 사이의 난수에 해당하는 R2를 결정하는 단계;(R1+2*R2)%(2*M)에 대응하는 P를 결정하는 단계; 및R1 번째 원소와 P 번째 원소를 상기 교환 쌍으로 선택하는 단계를 포함하는, 스케줄링 방법
|
3 |
3
제1항에 있어서,상기 제1 적합도는상기 제1 후보 해의 재배치 스케줄에 따른 총 이동 시간 및 총 이동 거리 중 적어도 일부에 기초하여 결정되는,스케줄링 방법
|
4 |
4
제3항에 있어서,상기 제1 적합도는상기 제1 후보 해의 상기 재배치 스케줄에 따른 재배치를 수행함에 있어서 한 번에 이동 가능한 이동 수단의 개수를 고려하여 결정되는,스케줄링 방법
|
5 |
5
제1항에 있어서,상기 최종 해를 도출하는 단계는상기 제1 후보 해와 상기 제2 후보 해 중 더 높은 적합도를 갖는 어느 하나를 선택하는 단계를 포함하는,스케줄링 방법
|
6 |
6
제1항에 있어서,상기 최종 해를 도출하는 단계는일정 주기 마다 냉각을 수행하는 단계를 포함하는,스케줄링 방법
|
7 |
7
제6항에 있어서,상기 최종 해를 도출하는 단계는상기 일정 주기에 따른 제K 후보 해의 제K 적합도가 제K-1 후보 해의 제K-1 적합도에 비해 낮더라도, 제K 적합도와 제K-1 적합도 간의 차이가 냉각 임계치보다 작다면, 상기 제K-1 후보 해와 상기 제K 후보 해 중 상기 제K 후보를 선택하는 단계를 포함하는,스케줄링 방법
|
8 |
8
하드웨어와 결합되어 제1항 내지 제7항 중 어느 하나의 항의 방법을 실행시키기 위하여 컴퓨터 판독 가능한 기록매체에 저장된 컴퓨터 프로그램
|
9 |
9
담금질 기법(Simulated Annealing, SA) 기반의 이동 수단 재배치를 위한 스케줄링 장치에 있어서,프로세서; 및상기 프로세서에서 실행가능한 명령어들을 포함하는 메모리를 포함하고,상기 명령어들이 상기 프로세서에서 실행되면, 상기 프로세서는이동 수단의 과잉 상태로 인해 이동 수단의 배출이 필요한 출발 위치들의 출발지 번호들과 이동 수단의 부족 상태로 인해 이동 수단의 공급이 필요한 목적 위치들의 목적지 번호들을 지정하고,상기 출발지 번호들의 적어도 일부와 상기 목적지 번호들의 적어도 일부를 동일 비율 및 임의의 순서로 포함하되, 출발지 번호와 목적지 번호가 교번하도록 포함하는 정수 벡터에 해당하는 제1 후보 해를 결정하고,상기 제1 후보 해에서 임의의 출발지 번호와 임의의 목적지 번호의 쌍으로 구성된 교환 쌍을 선택하고,상기 제1 후보 해에서 상기 교환 쌍의 상기 출발지 번호와 상기 목적지 번호에 따른 원소 교환을 수행하여 제2 후보 해를 결정하고,상기 제1 후보 해의 제1 적합도 및 상기 제2 후보 해의 제2 적합도를 평가하고,상기 제1 적합도 및 상기 제2 적합도에 기초하여 상기 제1 후보 해 및 상기 제2 후보 해 중 어느 하나에 따른 SA를 수행하여 최종 해를 도출하고,상기 최종 해에 대응하는 재배치 스케줄을 결정하는,스케줄링 장치
|
10 |
10
제9항에 있어서,상기 프로세서는0 내지 2*M-1 사이의 난수에 해당하는 R1, 및 0 내지 M-1 사이의 난수에 해당하는 R2를 결정하고,(R1+2*R2)%(2*M)에 대응하는 P를 결정하고,R1을 상기 출발지 번호로 갖고, P를 상기 목적지 번호로 갖는 상기 교환 쌍을 선택하는,스케줄링 장치
|
11 |
11
제9항에 있어서,상기 제1 적합도는상기 제1 후보 해의 재배치 스케줄에 따른 총 이동 시간 및 총 이동 거리 중 적어도 일부에 기초하여 결정되는,스케줄링 장치
|
12 |
12
제11항에 있어서,상기 제1 적합도는상기 제1 후보 해의 상기 재배치 스케줄에 따른 재배치를 수행함에 있어서 한 번에 이동 가능한 이동 수단의 개수를 고려하여 결정되는,스케줄링 장치
|
13 |
13
제9항에 있어서,상기 프로세서는일정 주기에 따른 제K 후보 해의 제K 적합도가 제K-1 후보 해의 제K-1 적합도에 비해 낮더라도, 제K 적합도와 제K-1 적합도 간의 차이가 냉각 임계치보다 작다면, 상기 제K-1 후보 해와 상기 제K 후보 해 중 상기 제K 후보를 선택하여, 상기 일정 주기 마다 냉각을 수행하는,스케줄링 장치
|