💻 computer science

Solving the flexible job-shop scheduling problem based on the hierarchical collaborative evolution multi-objective artificial raindrop algorithm

본 논문은 유연한 작업 숍 스케줄링 문제에서 총 소요 시간, 에너지 소비 및 비용을 효과적으로 최적화하기 위해 라틴 하이퍼큐브 샘플링, 특화된 탐색 전략을 갖춘 분할된 하위 집단, 그리고 적응형 유량 계수 업데이트 메커니즘을 통합한 계층적 공진화 다목적 인공 빗방울 알고리즘(HCMOARA)을 제안한다.

원저자: Zhibo Zhai, Shaoxuan Wang, Boyang Shi, Liang Ma, Haolong Wang, Jiangchao Zhou

게시일 2026-08-27

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Zhibo Zhai, Shaoxuan Wang, Boyang Shi, Liang Ma, Haolong Wang, Jiangchao Zhou

원본 논문은 CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

현대 제조업의 중심부에서는 속도, 비용, 그리고 환경 사이에서 조용한 긴장감이 흐르고 있습니다. 공장들은 경쟁력을 유지하기 위해 제품을 빠르게 생산해야 하지만, 동시에 제품 하나를 만들 때마다 더 적은 에너지를 사용하고 비용을 줄여야 한다는 점점 높아지는 압박에 직면해 있습니다. 이러한 균형 잡기 작업을 스케줄링(scheduling)이라고 합니다. 수십 가지의 서로 다른 제품을 만들어야 하고, 각 제품이 특정 기계에서 수행되어야 하는 일련의 단계들을 거쳐야 하는 작업장을 상상해 보십시오. 단순한 공장에서는 한 단계를 수행할 수 있는 기계가 단 하나뿐일 수 있습니다. 하지만 유연한 작업장에서는 단일 단계가 서로 다른 속도, 에너지 사용량, 비용을 가진 여러 대의 기계 중 어느 하나에 의해 수행될 수 있습니다. 과제는 어떤 기계가 어떤 단계를 수행할지, 그리고 어떤 순서로 할지를 결정하는 것입니다. 계획이 부실하면 공장은 가동이 중단되고, 에너지는 낭비되며, 비용은 치솟습니다. 계획이 훌륭하다면 공장은 잘 기름칠 된 기계처럼 매끄럽게 돌아가며, 더 적은 비용을 쓰면서도 작업을 더 빠르게 마칠 수 있습니다.

수십 년 동안 연구자들은 새 떼의 움직임이나 개미가 먹이를 찾는 방식과 같이 자연을 모방한 컴퓨터 알고리즘을 사용하여 이 퍼즐을 풀기 위해 노력해 왔습니다. 이러한 방법들은 괜찮은 해결책을 찾는 데는 능숙하지만, 문제가 너무 복잡해지거나 목표들이 서로 충돌할 때는 종종 어려움을 겪습니다. 시간을 최소화하는 계획은 전기를 너무 많이 소비할 수 있고, 에너지를 절약하는 계획은 시간이 너무 오래 걸릴 수 있습니다. 목표는 하나의 목표를 개선하면 다른 목표가 악화되는, 즉 '최선의 가능한' 타협점들의 집합을 찾는 것입니다. 이것이 허베이 공업대학교의 연구팀이 이 어려운 지형을 헤쳐 나가기 위해 개발한 새로운 방법을 통해 다루고 있는 핵심 과제입니다.

연구진은 공장이 세 가지 경쟁적인 목표, 즉 모든 작업을 최대한 빨리 끝내는 것, 총 에너지 사용량을 최소로 하는 것, 그리고 총 생산 비용을 최대한 낮게 유지하는 것을 동시에 조절해야 하는 특정 유형의 스케줄링 문제에 집중했습니다. 이를 해결하기 위해 그들은 '계층적 공동 진화 다목적 인공 빗방울 알고리즘(hierarchical co-evolutionary multi-objective artificial raindrop algorithm)'이라는 새로운 컴퓨터 알고리즘을 만들었습니다. 그 이름은 빗방울이 지형을 따라 떨어지고 흘러가는 방식을 모방한 데서 유래되었습니다. 자연에서 빗방울은 모여서 시내로 흐르고 결국 강으로 합쳐집니다. 연구진은 이 아이디어를 사용하여 스케줄링 문제에 대한 잠재적인 해결책들이 시간이 지남에 따라 어떻게 이동하고 개선되는지를 시뮬레이션합니다. 그러나 기존의 이 '빗방울' 방식은 한계가 있었습니다. 때때로 좋지 않은 아이디어 세트로 시작하거나, 새롭고 폭넓은 해결책을 찾는 탐색과 좋은 것을 정교하게 다듬는 과정 사이의 균형을 잡는 데 어려움을 겪었습니다.

이러한 문제를 해결하기 위해 연구진은 '계층적 공동 진화' 시스템을 도입했습니다. 모든 잠재적 해결책을 동일하게 취급하는 대신, 그들은 해결책의 질과 다른 것들과의 독특함(유사성)을 기준으로 세 가지 별도의 그룹으로 분류했습니다. 첫 번째 그룹인 '탐험가(explorers)'는 가장 독특하고 다양한 해결책들로 구성되었습니다. 이들에게는 탐색이 한 작은 영역에 갇히지 않도록 멀리 넓게 내다보는 전략이 부여되었습니다. 두 번째 그룹인 '착취자(exploiters)'는 서로 매우 유사한 가장 강력한 해결책들을 포함했습니다. 이들에게는 가장 유망한 영역을 깊게 파고들어 미세한 개선을 끌어내는 데 집중하는 정교화 및 다듬기 전략이 부여되었습니다. 세 번째 그룹인 '기본 업데이트 팀'은 아이디어의 안정적인 흐름을 유지하기 위해 기존의 꾸준한 빗방울 알고리즘 방식을 유지했습니다. 이 세 그룹이 함께 진화하도록 함으로써, 알고리즘은 새로운 영역을 탐색하는 동시에 발견한 최선의 아이디어들을 완벽하게 다듬을 수 있었습니다.

연구진은 소규모 작업장에서 대규모의 복잡한 공장에 이르기까지 규모가 다양한, 브랜드마르테(Brandimarte) 벤치마크라고 알려진 표준적인 10가지 어려운 스케줄링 문제를 사용하여 이 새로운 방법을 테스트했습니다. 그들은 이 새로운 빗방울 방식이 입자 군집(particle swarms)이나 쇠똥구리(dung beetles)에 기반한 몇몇 인기 있는 자연 모방 방식들을 지속적으로 능가했음을 비교를 통해 보여주었습니다. 결과에 따르면, 새로운 빗방울 방식은 모든 작업을 마치는 데 걸리는 시간 측면에서 10가지 테스트 케이스 중 7가지에서 가장 빠른 스케줄을 찾아냈으며, 나머지 3가지에서도 최고 수준과 동률을 기록했습니다. 또한 대부분의 시나리오에서 에너지 소비와 비용을 다른 방법들보다 낮게 유지했습니다.

새로운 방식은 단순히 더 빠른 스케줄을 찾는 것을 넘어, 훨씬 더 나은 트레이드오프(trade-off) 옵션의 집합을 만들어냈습니다. 다목적 문제에서는 단 하나의 '완벽한' 답이 존재하는 경우가 드뭅니다. 대신, 좋은 옵션들의 범위가 존재합니다. 연구진은 자신들의 알고리즘이 다른 방법들보다 더 고르게 퍼져 있고 더 넓은 가능성의 영역을 포괄하는 해결책 집합을 생성한다는 것을 발견했습니다. 이는 공장 관리자가 속도, 에너지 절약, 또는 비용 중 무엇을 우선시하든 간에 선택할 수 있는 더 풍부한 메뉴를 갖게 된다는 것을 의미합니다. 연구 또한 새로운 방식의 어떤 부분이 가장 중요한지를 확인하기 위한 테스트를 포함했습니다. 연구진이 알고리즘의 초기 탐색 방식을 제거하거나, '빗방울'의 흐름을 조절하는 능력을 없앴을 때 성능이 하락하는 것을 확인했습니다. 이는 그들의 새로운 설계의 모든 부분이 최종적인 성공에 필수적인 역할을 한다는 것을 입증했습니다.

이 연구는 계층적 접근 방식이 녹색 제조를 위한 강력한 새로운 도구를 제공한다고 결론짓습니다. 새로운 아이디어를 탐색하는 것과 최선의 것을 정교하게 다듬는 것 사이의 균형을 맞춤으로써, 이 알고리즘은 현대 생산의 복잡하고 상충하는 요구사항들을 처리할 수 있습니다. 현재의 테스트는 기계가 고장 나거나 작업이 늦게 도착하지 않는 시뮬레이션 환경에서 수행되었지만, 결과는 강력한 전망을 제시합니다. 이 방법은 효율적일 뿐만 아니라 경제적이고 환경적으로도 건전한 스케줄을 생성하는 방법을 제공하며, 공장이 속도나 이익을 희생하지 않으면서도 더 지속 가능한 미래를 향해 나아갈 수 있도록 돕습니다.

기술 요약: 계층적 협력 진화 다목적 인공 빗방울 알고리즘을 이용한 유연 작업 숍 스케줄링 문제 해결

1. 문제 정의

본 논문은 고전적인 작업 숍 스케줄링 문제(JSP)의 복잡한 확장형인 **다목적 유연 작업 숍 스케줄링 문제(MOFJSP)**를 다룬다. FJSP에서는 특정 공정에 기계가 고정되어 있는 JSP와 달리, 각 공정이 적격한 기계 집합 중 어떤 기계에서도 처리될 수 있다. 이러한 유연성은 적응성을 높이지만, 솔루션 공간과 계산 복잡성을 크게 확장시킨다.

본 연구는 다음 세 가지를 동시에 최소화하는 것을 목표로 하는 삼목적 최적화 모델을 수립한다:

메이크스팬 ( $f_1$ ): 모든 작업의 최대 완료 시간.
총 에너지 소비량 ( $f_2$ ): 모든 기계의 가공 에너지와 대기 에너지의 합.
총 비용 ( $f_3$ ): 기계 사용 시간에 기반한 누적 가공 비용.

이 목적 함수들은 서로 상충하므로 동시에 최적화하기 어렵다. 문제는 기술적 선행 관계, 기계 독점성(한 번에 한 기계당 하나의 공정), 비선점형 가공을 포함한 표준 제약 조건을 따른다.

2. 방법론: 계층적 협력 진화 다목적 인공 빗방울 알고리즘 (HCMOARA)

불균등한 초기 모집단 분포, 고정된 탐색 파라미터, 전역 탐색(global exploration)과 지역 탐색(local exploitation) 사이의 균형 부족과 같은 기존 군집 지능 알고리즘의 한계를 극복하기 위해, 저자들은 HCMOARA를 제안한다. 이 알고리즘은 다음과 같은 핵심 구성 요소를 통합한다:

인코딩 및 디코딩: 두 개의 세그먼트로 구성된 연속 인코딩 방식이 사용된다. 첫 번째 세그먼트는 공정 순서 우선순위를 인코딩하며(정렬을 통해 순서 결정), 두 번째 세그먼트는 기계 선택을 인코딩한다(적격 기계 인덱스로 매핑). 이는 연속 최적화 알고리즘과 FJSP의 이산적 특성 사이를 연결한다.
라틴 하이퍼큐브 샘플링(LHS)을 통한 초기화: 무작위 초기화 대신 LHS를 채택하여, 의사 결정 공간 전체에 초기 모집단을 더 균일하게 분포시킴으로써 클러스터링을 줄이고 커버리지를 개선한다.
계층적 모집단 층화: 모집단은 **비지배 순위(nondominated rank)**와 **혼잡 거리(crowding distance)**에 따라 세 개의 하위 모집단으로 동적으로 분할된다:
1. 탐색 하위 모집단 ( $Pop_1$ ): 혼잡 거리가 큰 순위 1의 개체들로 구성된다. 이들은 전역 탐색과 다양성을 높이기 위해 외부 파레토 아카이브의 리더(최대 혼잡 거리를 기준으로 선택됨)와 차분 변이(differential mutation)를 사용하는 DE-best-2 전략에 의해 유도된다.
2. 착취 하위 모집단 ( $Pop_2$ ): 혼잡 거리가 낮은 순위 1의 개체들과 모든 순위 2의 개체들로 구성된다. 이 그룹은 정교한 지역 탐색을 수행하고 유망한 영역 근처에서의 수렴을 개선하기 위해 하이브리드 SBX–RHC(시뮬레이티드 바이너리 교차 및 랜덤 힐 클라이밍) 전략을 활용한다.
3. 기본 업데이트 하위 모집단 ( $Pop_3$ ): 순위가 2보다 큰 개체들을 포함한다. 이들은 원래의 인공 빗방울 알고리즘(ARA) 업데이트 메커니즘을 유지하되, 개인적 경험과 사회적 경험의 균형을 동적으로 조절하기 위해 반복(iteration)에 따라 선형적으로 변화하는 적응형 흐름 계수( $c_1, c_2$ )를 활용한다.
외부 파레토 아카이브: 전용 아카이브가 고품질의 비지배 솔루션을 유지하여, 최적화 과정 전반에 걸쳐 파레토 프런트(Pareto front)를 보존한다.

3. 주요 기여

본 논문은 다목적 최적화 및 스케줄링 분야에 대해 다음과 같은 기여를 주장한다:

알고리즘 혁신: MOFJSP에 특화된 계층적 협력 진화 프레임워크를 인공 빗방울 알고리즘에 도입한 HCMOARA를 제안하였다.
전략적 차별화: 특정 모집단 하위 그룹에 할당된 차별화된 진화 전략(탐색을 위한 DE-best-2, 착취를 위한 SBX-RHC, 기본 업데이트를 위한 적응형 흐름)을 설계하였다.
초기화 개선: 초기 솔루션 분포의 균일성을 향상시키기 위해 ARA 프레임워크에 라틴 하이퍼큐브 샘플링을 적용하였다.
적응형 메커니즘: 고정된 파라미터를 대체하여 최적화 과정 중 탐색 동작을 동적으로 조정할 수 있는 적응형 흐로 계수를 도입하였다.

4. 실험 결과

알고리즘은 **Brandimarte 벤치마크 인스턴스(MK01–MK10)**에서 평가되었으며, 다섯 가지 다른 알고리즘(원래의 MOARA, NSPSO, NSOOA, NSDBO, NSCOA)과 비교되었다.

최적화 성능: HCMOARA는 10개 인스턴스 중 7개(MK02, MK03, MK05, MK06, MK07, MK09, MK10)에서 최상의 메이크스팬 결과를 달성했으며, 나머지 2개에서는 공동 최고치를 기록했다. 또한 대부분의 인스턴스에서 총 에너지 소비량과 총 비용을 최소화하는 데 있어 우수한 성능을 입증했다.
파레토 프런트 품질:
- 역 생성 거리 (IGD): HCMOARA는 7개 인스턴스에서 가장 낮은 IGD 값을 달лось 하며, 특히 MK02, MK03, MK06, MK09에서는 0의 값을 기록하여 솔루션 집합이 참조 파레토 프런트를 밀접하게 커버하고 있음을 보여주었다.
- 하이퍼볼륨 (HV): HCMOARA는 10개 인스턴스 중 9개에서 가장 높은 HV를 얻었으며, 이는 목적 공간에 대한 우수한 커버리지와 분포를 입증한다.
수렴성: 수렴 곡선은 HCMOARA가 비교 알고리즘들보다 더 빠르게 수렴하고, 특히 대규모 인스턴스에서 정체 현상을 더 잘 피한다는 것을 보여주었다.
절제 연구 (Ablation Study): 특정 구성 요소(LHS, 적응형 흐로, DE-best-2, SBX-RHC)를 제거한 실험을 통해 각 전략이 전체 성능에 긍정적으로 기여함을 확인하였다. 전체 알고리즘은 IGD, HV 및 목적 함수 값 측면에서 절제된 변형 모델들보다 일관되게 우수한 성능을 보였다.

5. 의의 및 범위

저자들은 HCMOARA가 다목적 유연 작업 숍 스케줄링 문제를 해결하는 효과적인 접근 방식이며, 특히 에너지와 비용이 효율성과 함께 중요한 그린 제조(green manufacturing) 맥의에서 유용하다고 주장한다. 본 연구는 계층적 협력 진화 전략이 전역 탐색과 지역 착취 사이의 균형을 효과적으로 맞추어, 조기 수렴 및 불균등한 솔루션 분포와 같은 일반적인 문제점을 해결한다는 점을 강조한다.

본 논문은 현재 모델이 정적 스케줄링 환경에서 작동하며, 기계 고장, 새로운 작업 도착 또는 확률적 가공 시간 변동과 같은 동적 요인을 제외하고 있다는 한계점을 명시하고 있다. 저자들은 향ay 실제 생산 환경에서의 적용성을 높이기 위해 향후 연구에서 이러한 동적 요소들을 포함해야 한다고 제안한다.