상대적 긴급도 계산 기반 초기해 개선을 통한 제조 스케줄링 최적화 = RUBI: Relative-Urgency Based Initialization for Scheduling Optimization in Shipyard Manufacturing

국문 초록 (Abstract)

본 연구는 잡샵 스케줄링 문제(Job Shop Scheduling Problem, JSSP)의 최적해를 구하기 위한 탐색 기반 알고리즘의 초기해 생성 알고리즘으로써 RUBI(Relative Urgency Based Initialization)를 제안한다. JSSP는 여러 개의 작업이 복수의 공정을 거쳐 완료되는 제조 시스템을 모델링한 대표적인 조합 최적화 문제이며, 전체 작업의 완료 시간인 makespan을 최소화하는 것을 목적으로 한다. 조선소와 같은 대규모 생산 시스템의 경우 다수의 작업 대상이 존재하고 공정 간의 복잡한 선후행 제약 조건이 존재한다는 점에서 JSSP로 모델링할 수 있다. 본 논문에서 제안하는 RUBI는 메타휴리스틱을 비롯한 탐색 알고리즘에서 JSSP 문제의 최적해에 근접한 이웃해를 다수 생성하여 초기해로 활용하는 방법으로, 그래프 기반 해 표현의 위상적 구조를 활용하여 작업 시간 특성과 무관하게 해를 생성한다는 점에서 기존 방법론과 대비된다. 이때 작업 간의 상대적 긴급도(Relative Urgency)가 높은 순으로 먼저 처리할 작업을 선택함으로써 JSSP의 해를 생성하며, 본 논문에서는 이를 RU principle로 정식화하여 제안하였다.
본 연구에서는 제안 방법의 효과성을 증명하기 위해 다수의 JSSP 인스턴스에 대해 RUBI를 적용한 유전 알고리즘 기반의 최적화를 수행하였으며, 그 결과 RUBI가 전통적인 초기해 생성 기법인 Giffler and Thompson 알고리즘과 비교하여 비슷하거나 더 우수한 수준의 초기해를 더 빠른 시간 내에 생성한다는 것을 확인하였다.
본 연구에서는 또한 JSSP 문제의 특성에 따라 RUBI의 성능 편차가 발생하는지 검증하기 위한 실험을 진행하였다. JSSP 문제의 크기를 결정하는 작업 및 설비의 개수, 설비의 분포 특성에 해당하는 Bottleneck Index 및 Flowshop Index, 작업 시간의 표준편차 등 5개 요인을 선정하여 RUBI의 makespan 개선 비율인 PIR(Performance Improvement Ratio)에 대한 영향을 평가한 결과, 작업 및 설비의 개수가 PIR에 영향을 주지 않으며, 작업 시간의 표준편차와 RUBI의 PIR 간에 음의 상관관계가 존재한다는 것을 확인하였다. 또한 RUBI의 PIR과 Bottleneck Index 사이에 2차함수적 관계가 존재하며, Flowshop Index 와는 관계가 없다는 것을 확인하였다.
마지막으로, 실제 조선소 공정 데이터를 바탕으로 생성한 JSSP 인스턴스를 활용하여 RUBI의 대규모 제조 시스템에 대한 적용 가능성을 검증하였다. 형강 공정 및 안벽 의장 공정 데이터를 바탕으로 생성한 대규모 JSSP 인스턴스에 대해 RUBI를 적용한 결과, 비교 알고리즘에 비해 빠른 시간 내에 최적해에 근접한 이웃해를 생성할 수 있음을 확인하였다. 이를 통해 RUBI가 대규모 제조 시스템 최적화 문제에 대해 효과적인 초기화 알고리즘으로 작동할 수 있음을 확인하였다.

다국어 초록 (Multilingual Abstract)

This thesis proposes Relative Urgency-Based Initialization (RUBI) as an initialization framework for search-based algorithms solving the Job Shop Scheduling Problem (JSSP). The JSSP is a representative combinatorial optimization problem that models manufacturing systems in which multiple jobs are completed through multiple operations on shared machines, typically with the objective of minimizing the makespan. RUBI generates a set of initial solutions by constructing feasible schedules that follow the Relative Urgency (RU) principle, which prioritizes operations with higher relative urgency, defined by the number of remaining operations within a job. By exploiting the topological structure of a graph-based representation and encoding solutions in a repetitive permutation form, RUBI produces diverse neighborhood solutions that are close to high-quality regions of the search space and can be directly used as an initial population for subsequent enumerative search techniques.
To validate the RU principle, this study defines an RU score that quantifies the degree to which a solution satisfies RU-based ordering. Linear regression analysis reveals a strong relationship between RU score and makespan. The effectiveness of RUBI is further evaluated through genetic-algorithm-based optimization on a wide range of benchmark JSSP instances. The results show that RUBI produces initial solutions of comparable or superior quality to the classical Giffler and Thompson method while requiring less computational time. In addition, sensitivity analyses are conducted with respect to five instance characteristics: the number of jobs, the number of machines, Bottleneck Index, Flowshop Index, and processing-time variance. The results indicate that RUBI’s performance improvement ratio is independent of problem size, negatively correlated with processing-time variability, exhibits a quadratic relationship with the Bottleneck Index, and shows no significant relationship with the Flowshop Index.
Finally, the applicability of RUBI to industrial-scale scheduling is demonstrated using large JSSP instances generated from shipyard production data, including profile processing and quay wall outfitting scenarios. The results confirm that RUBI efficiently generates high-quality initial populations and can serve as an effective initialization framework for large-scale manufacturing scheduling problems.

목차 (Table of Contents)

• 초 록 1
• 목 차 3
• Abbreviation 6
• Nomenclature 7
• 제 1 장 서론 8
• 제 2 장 잡샵 스케줄링 문제 15
• 제 1 절 문제 정의 및 가정 15
• 제 2 절 반복 순열 기반 해 표현 18
• 제 3 절 해 집합의 초기화 기법 21
• 제 3 장 방법론 24
• 제 1 절 탐색 기반 방법론 24
• 제 2 절 연구가설 수립 27
• 제 3 절 수학적 정식화 29
• 제 4 절 연구가설 검증 32
• 제 5 절 RUBI 프레임워크 36
• 제 4 장 실험 39
• 제 1 절 벤치마크 테스트 39
• 제 2 절 JSSP 특성에 대한 영향 평가 45
• 제 5 장 적용 54
• 제 1 절 형강 공정 사례 연구 54
• 제 2 절 안벽 의장 공정 사례 연구 57
• 제 6 장 결론 61
• 참고 문헌 65
• Abstract 70