Joint Planning of Assembly Sequence Planning and Assembly Line Balancing Based on Improved Artificial Fish Swarm Algorithm

기술 요약: 개선된 인공 어류 군집 알고리즘을 기반으로 한 조립 순서 계획 및 조립 라인 밸런싱의 통합 계획

문제 정의
본 논문은 조립 순서 계획(ASP)과 조립 라인 밸런싱(ALB)을 동시에 최적화하는 복잡한 과제를 다룹다. 이 두 문제는 본질적으로 결합되어 있다. ASP는 비용을 최소화하기 위해 부품을 조립하는 최적의 순서를 결정하며, ALB는 유휴 시간을 최소 단축하고 라인을 균형 있게 만들기 위해 이러한 작업들을 워크스테이션에 할당한다. 두 문제 모두 다항 시간 복잡도를 가진 비결정론적 다항 시간(NP-hard) 문제로 분류된다. 저자들은 이 문제들을 개별적으로 최적화하는 것이 종종 전체 시스템의 성능을 저하시킨다는 점을 지적한다. 또한, 기존의 ASP 방식은 그래프 탐색을 사용할 때 "조합 폭발" 문제를 겪는 경우가 많으며, 전통적인 행렬 생성 방식은 복잡한 제품에 대해 시간이 많이 소요되고 비효율적일 수 있다. 아울러, 많은 ALB 연구들이 ASP에 내재된 조립 도구 및 방향의 동적인 변화를 고려하지 못하여, 실제 조립 공정에서 실행 불가능한 밸런싱 결과를 초래하기도 한다.

방법론
제안된 접근 방식은 개선된 인공 어류 군집 알고리즘(HAFSA)을 사용하여 ASP와 ALB를 하나의 통합된 다목적 최적화 프레임워크로 통합한다. 방법론은 크게 세 가지 단계로 구성된다:

1. BOM 및 제약 행렬을 통한 ASP 모델링:

   • 조합 폭발을 일으키는 AND/OR 그래프에만 의존하는 대신, 저자들은 자재명세서(BOM) 계층 구조도에 기반한 모듈형 조립 제약 행렬을 구축한다.
   • 조립 제약 행렬($E(G)$)은 부품을 나타내는 요소와 우선순위 및 연결 관계(예: 직접 연결 전은 $1$, 후는$-1$, 비직접 연결 전은$9$ 등)를 나타내는 값을 가진 유향 그래프를 사용하여 정의된다.
   • 하위 조립품 분할: 알고리즘은 BOM 계층 구조를 분석하여 하위 조립품의 독립성을 결정한다. 이는 제약 행렬의 열 값을 반복적으로 확인한다. 만약 특정 부품 그룹이 외부 부품과 일관된 비양수 또는 비음수 관계를 보이면 이를 독립적인 하위 조립품으로 식별한다. 그렇지 않을 경우, 알고리즘은 특정 행을 제거하여 실행 가능한 독립 모듈을 생성한다.
   • 내부 계획: 식별된 각 하위 조립품 내에서는 제약 행렬 값을 기반으로 실행 가능한 내부 조립 순서를 생성하기 위해 특정 스와핑(swapping) 및 고형화(solidifying) 알고리즘이 사용된다.

2. 다목적 최적화 모델:
   통합 모델은 다음 세 가지 목적 함수를 동시에 최소화하는 것을 목표로 한다:

   • 워크스테이션 시간 균형: 생산 리듬($T_c$)과 개별 워크스테이션 시간($T_m$) 사이의 분산을 최소화한다.
   • 전환 비용: 연속된 작업 간의 조립 도구 변경 횟수와 조립 방향 변경 횟수의 총합을 최소화한다.
   • 최대 워크스테이션 시간: 사이클 타임(모든 워크스테이션 중 최대 시간)을 최소화한다.

3. 하이브리드 인공 어류 군집 알고리즘 (HAFSA):
   이 다목적 문제를 해결하기 위해 저자들은 인공 어류 군집 알고리즘(AFSA)에 입자 군집 최적화(PSO)와 파레토 최적성 개념을 결합한 HAFSA를 제안한다.

   • 인코딩/디코딩: 조립 작업은 하위 조립품 내의 우선순위 가중치에 따라 인코딩된다. 디코딩은 작업을 순차적으로 워크스테이션에 할당하며, 사이클 타임 제약을 초과할 때만 새로운 워크스테이션을 개설한다.
   • 파레토 해 집합: 외부 저장소는 비지배 해(non-dominated solutions)를 저장한다. 다양성을 유지하고 저장소 크기를 관리하기 위해 혼잡도 거리(crowding distance) 메커니즘이 사용된다.
   • 알고리즘 개선 사항:
     • 행동 로직: 알고리즘은 꼬리 쫓기(tail-chasing), 먹이 찾기(foraging), 군집 형성(clustering), 무작위 행동(random behavior)의 순차적 탐색 순서를 따른다.
     • PSO 통합: 표준 AFSA의 약점인 지역 최적점(local optima) 함몰을 방나하기 위해 PSO 연산이 도입된다. 여기에는 특정 확률로 악화된 해를 수용하여 지역적 함정에서 벗어날 수 있게 하는 메트로폴리스 기준(시뮬레이티드 어닐링 개념)이 포함된다.
     • 동적 관성: 인공 어류의 "시야(visual field, 탐색 범위)"는 PSO에서 영감을 얻은 관성 가중치($\omega$)를 사용하여 동적으로 조정된다. 이는 전역 탐색을 위해 넓은 시야로 시작하여 국부 수렴을 위해 좁혀지는 방식을 취한다.

주요 기여

• 통합 프레임워크: 본 논문은 ASP와 ALB를 순차적으로 처리하는 대신, 이들의 상호 의존성을 인정하고 공동으로 계획하는 방법을 제안한다.
• 행렬 기반 하위 조립품 식별: BOM 계층 구조와 조립 제약 행렬을 사용하여 독립적인 하위 조립품을 자동으로 식별하는 새로운 접근 방식을 통해 탐색 공간을 줄이고 조합 폭발을 방지한다.
• HAFSA 알고리즘: 전역 탐색 능력을 향상시키고 지역 최적점을 피하기 위해 PSO 연산과 시뮬레이티드 어닐링 원리를 결합하여 표준 AFSA를 개선한 파레토 기반 하이브리드 인공 어류 군집 알고리즘을 개발하였다.
• 다목적 처리: 전통적인 시간 균형 외에도 도구 변경 및 방향 변경을 최적화 목적 함수로 명시적으로 포함하였다.

결과
제안된 방법은 21개의 조립 작업이 있는 특정 제품의 사례 연구를 통해 검증되었다. HAFSA(AFSA&PSO로 표기)는 표준 입자 군집 최적화(PSO) 알고리즘 및 표준 인공 어류 군집 알고리즘(AFSA)과 비교되었다.

• 워크스테이션 밸런스: 세 알고리즘 모두 31분의 동일한 최대 워크스테이션 작업 시간을 달로 달성했다. 그러나 스테이션 간 밸런스 값은 HAFSA가 0.69로, PSO 결과(0.75)보다 우수했으며 표준 AFSA(0.69)와 동일했다.
• 전환 효율성: HAFSA는 총 22회의 변경(도구 + 방향)을 달성했다. 이는 PSO 결과(22회)와 동일하지만, 24회의 변경을 초래한 표준 AFFA보다는 현저히 우수했다.
• 데이터 결론: HAFSA는 스테이션 시간을 효과적으로 균형 있게 맞추면서도 운영 전환 횟수를 최소화하는 파레토 최적 해를 찾는 능력을 입증하였으며, 전환 감소 측면에서 표준 AFSA보다 뛰어난 성능을 보였고 밸런스 지표에서는 PSO와 대등하거나 그 이상의 성능을 보였다.

의의 및 주장
본 논문은 주요 의의가 ASP와 ALB의 공동 계획의 효율성과 실행 가능성을 개선하는 데 있다고 주장한다. BOM 계층 구조를 활용하여 하위 조립품을 사전 처리함으로써, 탐색 공간을 보다 목표 지향적으로 만들어 솔루션 효율성을 높이고 다수의 실행 불가능한 해가 생성되는 것을 방지한다.

저자들은 제안된 HAFSA가 이 특정 다목적 문제에 대해 전통적인 AFSA 및 PSO 알고리즘보다 더 효과적이라고 단언한다. 어류 군집 행동에 PSO 연산을 통합함으로써 알고리즘이 지역 최적점에서 더 잘 벗어날 수 있게 하며, 결과적으로 더 높은 품질의 파레토 해를 도출한다. 본 연구는 이러한 통합적 접근 방식이 특히 도구 및 방향 변경이 중요한 비용 요인인 복잡한 제품 조립 라인에 대해 더욱 합리적이고 효율적인 계획 방법을 제공한다고 결론짓는다.