[메타 휴리스틱] 보수 전략(repairing strategy)

 

이번 글의 내용은 전남대학교 산업공학과 김여근 교수님의 메타휴리스틱 교재 정리 및 참조하였음을 먼저 밝힙니다.

(다른 참조한 논문과 자료들은 아래에 기재되어 있습니다.) 

 

 

이 포스트는 "메타 휴리스틱" 책의 내용을 참조 및 공부한 것을 바탕으로 제가 이해한 정보를 추가하여 쓰여졌습니다.  

 

 

혹시 제가 잘못 알고 있는 점이나 보완할 점 있다면 댓글로 알려주시면 감사하겠습니다. 

 

---

 

작업 선행공정도

 

 

※ 보수전략은 메타휴리스틱의 탐색 연산에서 비가능해가 생산되면, 이 비가능해를 보수하는 전략입니다. 

 

 

 

비가능해를 보수할 때 이 비가능해가 가지고 있는 특성을 반영하는 전략이 탐색에 효율적일 수도 있습니다. 위의 그림과 같은 작업 선행공정도를 갖는 작업들의 할당순서를 구하는 문제를 살펴 보겠습니다. 이 그림에서 마디는 작업을 , 마디 위의 값은 작업소요시간을, 화살표는 작업선행관계를 나타냅니다. 컨베이어가 흐르는 작업을 할당할 때 제약으로 할당하는 작업 순서가 아래 선행공정도에 나타난 선행 관계가 만족되어야 합니다. 작업 할당은 작업 3과 4는 작업 1이 완료된 후, 작업 5는 작업 2가 완료된 후, 작업 6은 작업 3이 끝난 후에 가능합니다. 예를 들어서 할당순서가 (1,2,3,4,5,6,7,8,9) 이면 가능 할당입니다.

 

 

어떤 탐색연산에서 (2,1,5,4,7,6,9,3,8)가 유도 되었다고 가정합니다. 이는 비가능 할당이 됩니다. 이를 가능 할당으로 변환하는 다음 절차를 사용할 수 있습니다. 선행관계를 어기는 할당 이후의 모든 작업을 재할당합니다. 이때 재할당 순서는 할당 가능 작업 (직선행 작업이 모두 할당된 작업) 中에서 작업 시간이 가장 큰 작업을 할당합니다. 그러면 비가능해 (2,1,5,4,7,6,9,3,8)는 보수 작업을 통해 (2,1,5,4,7,3,6,8,9)의 가능 할당으로 변환됩니다.

 

 

---

 

가능해로 변환시키는 또 다른 절차로 선행관계를 어기는 부분의 할당 순서는 현재 할당 가능 작업 집합에서 표현된 해에서 먼저 나타난 작업을 할당합니다. 이 과정을 가능해가 만들어 질 때까지 반복합니다. 이 예제에서 작업 2,1,5,4,7의 할당 순서는 가능 할당이고, 이후 할당 가능작업집합은 작업 {3,8}이고, 비가능해에서 작업 3이 작업 8보다 앞에 있으므로 작업 3을 할당합니다. 다음 할당가능작업집합은 작업 {6,8}이고 비가능해 표현에서 작업 6이 8보다 앞에 나타나 작업 6을 할당하고 다음은 작업 8이, 그리고 작업 9가 할당되어 가능해 (2,1,5,4,7,3,6,8,9)로 변환됩니다.

 

 

 

 

 

긴글 읽어주셔서 감사합니다.

 

---

 

 

[References]

 

 

[1] Y. Kim. (2017). 메타휴리스틱스, Metaheuristics

 

[2] Nanda, S. J., & Panda, G. (2014). A survey on nature inspired metaheuristic algorithms for partitional clustering. Swarm and Evolutionary Computation, 16, 1–18.