A Framework for Multi-Plate Nesting Optimization with Dynamic Allocation and Placement Strategies = 동적 할당 및 배치 전략을 고려한 다중강판 네스팅 최적화 프레임워크에 관한 연구

국문 초록 (Abstract)

조선소 네스팅 작업은 수천 개의 비정형 강재 부재를 절단 전에 강판에 어떻게 배치하고 할당할지를 결정하는 과정으로, 선체 생산에서 소재 사용량, 조달 비용, 일정 리스크에 직접적인 영향을 미친다. 대형 조선소에서는 이러한 의사결정이 여러 두께·강종·LOT에 걸쳐 이루어지며, 강판 크기 및 발주를 담당하는 조달 단계의 목표와 수율·공정 안정성을 중시하는 생산 단계의 목표를 동시에 만족시켜야 한다. 이때 두께·강종·LOT 호환성, 가공 설비 한계 등 다양한 산업 제약을 함께 고려해야 하므로, 단일 강판 배치 문제를 넘어 블록 단위의 다중 강판 문제로 확장되는 것이 실무적 특징이다.
본 학위논문에서는 조선소 환경에 특화된 다중 강판 네스팅 최적화를 위해, 동적 할당·배치 전략을 통합한 Aggregate Nesting (AN) 프레임워크를 제안한다. 제안 프레임워크는 조선소 네스팅을 Aggregate Nesting 문제로 재해석하여, 강판 사이즈 및 할당(Q2P)과 강판 내 배치 및 재배치(P2Q, P2QR)를 블록 단위의 단일 목적하에 결합한다. 이때 블록 단위 목적함수는 강재 총중량 최소화를 기본으로 하고, 강판 수, 플레이트 수율, 잔재율, 공급사 가격 구간 등을 재료비의 대리(proxy) 지표로 활용한다. 강판들 사이의 두께·강종·LOT 호환성과 선후 관계는 유향 비순환 그래프(DAG)로 표현하여, 이러한 제약을 만족하는 범위 내에서 강판 간 부재 재배치를 체계적으로 수행할 수 있도록 하였다. 강판 내 배치는 하이브리드 Raster–Vector 기하 모델과 다층 목적함수를 갖는 Random Greedy Sequential Algorithm (RGSA) 휴리스틱을 사용하여, 위치·각도 탐색에서 기하학적 정밀도와 계산 효율 사이의 균형을 맞추도록 설계하였다.
제안 프레임워크는 세 단계의 실험을 통해 검증하였다. 첫째, 샘플 예제 데이터를 대상으로 P2Q 및 Q2P 모듈을 GA 기반 baseline과 비교하였다. 그 결과, Raster + Vector + RGSA 조합은 Raster + GA + BL baseline과 유사한 수율을 유지하면서도 계산 시간은 1–2자릿수 이상 단축되었으며, Q2P 모듈은 Decoupled FFD과 BL로 구성된 베이스라인 대비 거의 동일한 강재 사용량을 달성하면서 탐색 시간이 짧고, 소규모이지만 추가적인 재료비 절감 효과를 보였다. 둘째, CNTR 컨테이너선의 서로 다른 구역에서 선정한 5개 블록에 대해 실제 조선소 데이터를 활용한 사례 연구를 수행하였다.
전문 설계자의 수기 네스팅 결과와 비교한 결과, 제안 AN 프레임워크는 대부분의 블록에서 강재 총중량과 강판 수를 감소시키거나 최소한 비열화시키지 않으면서, 실제 블록 단위 재네스팅에 적용 가능한 수준의 계산 시간 내에서 동작함을 확인하였다.
추가 연구로, 생산 네스팅 문제를 마르코프 의사결정 과정으로 정식화하고, LPG 운반선 및 암모니아 운반선 블록에서 유도한 단순화 환경을 대상으로 계층형 PPO 기반 강화학습(RL) 에이전트를 적용하였다. 실험 결과, 일부 블록에서는 RL 에이전트가 초기 휴리스틱 정책에 비해 평균 수율을 향상시키고 사용 강판 수를 줄이는 경향을 보였으나, 동시에 학습 비용,데이터 요구량, 일반화 안정성 등 실무 적용을 위한 과제도 함께 드러났다. 전체적으로 볼 때, 본 논문이 제안하는 Aggregate Nesting 프레임워크는 조선 선체 생산에서 강판 사이즈 결정과네스팅을 통합적으로 다루는 실용적인 엔지니어링 해법을 제시하며, 향후 고급 최적화 기법과 학습 기반 정책을 결합하는 연구를 위한 기반을 제공한다.

다국어 초록 (Multilingual Abstract)

Shipyard nesting determines how thousands of irregular steel parts are assigned and placed on plates before cutting, directly affecting material usage, procurement cost, and schedule risk in hull production. In large shipyards, these decisions span multiple thicknesses, grades, and production LOTs, and they must reconcile procurement objectives related to plate sizing and ordering with production objectives such as yield and process stability, under industrial constraints including attribute compatibility and
machine envelopes.
This dissertation proposes a heuristic framework for multi-plate nesting optimization with dynamic allocation and placement strategies, tailored to shipyard environments. The framework views shipyard nesting as an Aggregate Nesting (AN) problem in which plate sizing and allocation (Q2P) are explicitly coupled with placement and re-allocation (P2Q and P2QR) under a block-level objective that minimizes total steel weight while using plate-level yield, trim ratio, and supplier price buckets as proxy indicators for material cost. A directed acyclic graph (DAG) encodes compatibility and precedence relations between plates, enabling systematic reallocation of parts across plates while respecting thickness, grade, and LOT constraints. Within each plate, a hybrid raster–vector geometric model and a Random Greedy Sequential Algorithm (RGSA)
heuristic with a multi-layer objective function balance geometric fidelity and computational efficiency when searching position–orientation configurations.
The proposed modules are validated in three stages. First, module-level experiments on a simplified dataset compare P2Q and Q2P against GA-based baselines. The hybrid Raster + Vector + RGSA combination achieves nesting yields comparable to a Raster + GA + BL baseline while reducing computation time by one to two orders of magnitude, and the Q2P module attains almost identical steel usage to a Decoupled FFD and BL baseline with shorter runtimes and a small additional reduction in material cost. Second, industrial case studies on five blocks from different regions of a container carrier show that the AN framework reduces or at least does not degrade total steel weight and plate count compared with expert manual nesting, with runtimes that are compatible with block-level re-nesting workflows in production.
As an auxiliary study, the dissertation further formulates production nesting as a Markov decision process and investigates a hierarchical PPO-based reinforcement learning (RL) agent for plate sizing and allocation in simplified environments derived from LPG and ammonia carrier blocks. The RL agent can improve average yield and reduce the number of plates relative to its initial heuristic behavior for some blocks, while also revealing practical challenges such as training cost, data requirements, and generalization. Overall, the results indicate that Aggregate Nesting provides a practical engineering framework for integrated plate sizing and nesting in hull production and a basis for future extensions using more advanced optimization models and learning-based policies.

목차 (Table of Contents)

• 1. Introduction 2
• 1.1 Background and Motivation 2
• 1.2 Problem Context: Shipyard-Wide Nesting and Aggregate Nesting 3
• 1.3 Problem Definition: Aggregate Nesting as an Optimization Problem 5
• 1.4 Optimization Objective and Cost Modeling 6
• 1.5 Research Questions and Contributions 8
• 1.6 Structure of the Dissertation 9
• 2. Theoretical Background 11
• 2.1 Cutting-and-Packing Problems and Nesting: Problem Taxonomy 11
• 2.1.1 From single-container placement to multi-container allocation 12
• 2.1.2 Shipbuilding context 12
• 2.2. Single-Plate Nesting: Geometry Handling and Placement Optimization 13
• 2.2.1 Geometric representations for overlap detection 13
• 2.2.2 Search strategies: constructive heuristics and metaheuristics 16
• 2.2.3 Implications to this study 18
• 2.3 Multi-Plate (Multi-Bin) Nesting and Shipbuilding-Orented Studies 19
• 2.3.1 Variable-sized bin packing and integrated decisions 20
• 2.3.2 Irregular multi-bin packing and limited shipbuilding-sacle evidence 20
• 2.3.3 Implications to this study: research gap for shipbuilding multi-plate nesting 21
• 2.4 Graph-Based Modeling Perspectives for Packing and Nesting 22
• 2.4..1 Network(arc-flow) formulations as compact pattern graphs 22
• 2.4.2 Conflic and compatibility graphs for allocation planning 23
• 2.4.3 Graph representations in learning-based packing 23
• 2.5 Reinforcement Learning Backgorund 27
• 2.5.1 Markov Decision Process (MDP) formulation 27
• 2.5.2 Algorithm families and positioning of PPO 32
• 2.5.3 Proximal Policy Optimization (PPO) 33
• 2.6 Positioning and Research Gaps Aligned with Our-Framework 38
• 3. Methodology 42
• 3.1 Problem Definition and Assumptions 42
• 3.1.1 Input Data and Notation 42
• 3.1.2 Block-Level Objective: Minimization of Steel Weight 43
• 3.1.3 Industrial Constraints and Assumptions 45
• 3.2 Aggregate Nesting Framework 45
• 3.3. Directed Acyclic Graph (DAG) Construction 46
• 3.3.1 Nodes and Atrribtues
• 3.3.2 Attribute-Wise Predicates and Policy Family 48
• 3.3.3 Role of the DAG in Aggregate Nesting 51
• 3.4 Q2P 51
• 3.4.1 Initial Plate Sizing for Original Items 52
• 3.4.2 Sink-First Aggregate Nesting Schedule 54
• 3.5 P2Q and P2QR: Hybrid Geomery and Placement 58
• 3.5.1 Hybrid Raster-Vector Geometric Model 58
• 3.5.2 Random Greedy Sequential Algorithm (RGSA) Heuristic 60
• 3.5.3 Multi-Layer Objective Function 62
• 3.5.4 P2QR: Reallocation and Weight-Aware Resizing 64
• 4. Experiemtns 68
• 4.1 Experimental Design and Evaluation Metrics 68
• 4.2 Modul-Level Validation on Simplified Examples 75
• 4.2.1 P2Q vs. GA-Based Baseline 77
• 4.2.2 Q2P vs. Decoupled FFD+BLF Baseline 78
• 4.3 Shipyard Case Studies: Expert Manual Nesting vs. Aggregate Nesting 79
• 4.3.1 Data and Experimental Procedure 80
• 4.3.2 Results and Discussion 82
• 4.4 Exploratory Reinforcement Learing Extension 88
• 4.4.1 Motivation: Heuristic vs. Reinforcement Learning 88
• 4.4.2 RL Environment and Experimental Deesign 90
• 4.4.3 Experiment 1: Learning Behavior on LPG and VLAC Carriers 92
• 4.4.4 Experiment 2: Comparision with Heuristic Aggregate Nesting 95
• 5. Conclusion and Future Work 99
• 5.1 Conclusion and Future Work 99
• 5.1.1 Answers to Research Questions 102
• 5.2 Discussion and Limitation 104
• 5.2.1 Problem Formulation and Cost Modeling 104
• 5.2.2 Experimental Scope and Baselines 105
• 5.2.3 Reinforcement Learning Study 106
• 5.2.4 Algorithmic Properties and Sensitivity 107
• 5.2.5 Threats to Validity 109
• 5.2.6 Depolyment and Governance Considerations 109
• 5.3 Future Work 111
• 5.3.1 Toward a More Explicit Optimziation Formulation 111
• 5.3.2 Richer and More Industry-Complete Cost Objectives 112
• 5.3.3 Broader Industrial Validation and Bechmarking 113
• 5.3.4 Learning-Enhanced Components Under Practical Constraints 113
• 5.3.5 A Straged Roadmap for High-Leverage Extensions 114
• 5.3.6 Benchmark and Evaluation Protocol for Future Studies 115
• Biblography 117
• 한국어 초록 124
• Acknowledgements 126