2차원 적재 및 가용 제약을 고려한 병렬 배치 기계 스케줄링 기반 조선소 항차 계획 최적화 연구 = Optimization of Shipyard Voyage Planning using Parallel Batch Machine Scheduling with 2D Packing and Availability Constraints

국문 초록 (Abstract)

조선소의 항차 계획은 제작처에서 완성된 블록들을 한정된 바지선 자원을 활용하여 후행 공정지로 이송하는 바지선의 계획을 것을 의미한다. 이는 적재 효율을 높이기 위한 2차원 패킹 문제와 적기 생산을 위한 스케줄링 문제가 결합된 복합적인 의사결정 과정으로, 매우 높은 연산 복잡도를 가진다. 그러나 실제 현업에서는 숙련된 작업자의 수기 계획 방식을 택하고 있으며, 이러한 방식은 계획에 수정 사항이 발생하는 경우나 장기 계획 같은 문제 크기가 커질 경우 유연하게 반영하는 데 한계가 존재한다.
본 연구에서는 이러한 실제 조선소의 운영 환경을 반영하기 위해 2차원 적재 제약과 작업별 가용 시작일 및 납기일, 그리고 자원 제약을 통합한 2D-PBMSP-TW-RC(2D Bin Packing Parallel Batch Machine Scheduling Problem with Time Windows and Resource Constraints) 수리 모델을 정의하였다. 이 모델은 학술적으로 정의된 병렬 배치 기계 스케줄링 모델을 확장하여 실제 항차 계획에서 발생하는 자원 가용성과 시간 창 제약을 엄밀하게 정식화한 결과이다.
제안하는 최적화 프레임워크는 전역 탐색을 담당하는 직교 편향 랜덤 키 유전 알고리즘 (Orthogonal Biased Random Key Genetic Algorithm, OBRKGA)과 지역 최적화 및 제약 준수를 담당하는 제약 프로그래밍이 결합된 계층적 구조를 가진다. 전역 탐색 모델인 OBRKGA는 직교 실험 설계 기법 과 편향 교차를 도입하여 초기 해의 탐색 공간 분포를 균일화하고 수렴 속도를 최적화함으로써 탐색의 안정성을 확보하였다. 배치 그룹화 단계에서는 납기 근접도와 적재 효율을 동시에 고려하는 Hierarchical Best Fit First 알고리즘을 제안하며, 그룹화 된 배치들을 바탕으로 스케줄링의 실행 가능성을 판별하는 Extended Backward Scheduling 알고리즘을 제안해 스케줄링 목적함수의 간접 평가 메커니즘으로 활용하였다. 이러한 계층적 구조는 탐색 지능과 제약 준수 로직을 분리함으로써 복잡한 물리적 제약 하에서도 탐색 효율을 극대화하며, 실무적인 제약 조건 변화에 유연하게 대응할 수 있는 구조적 확장성을 제공한다.
제안 방법론의 성능과 실효성을 검증하기 위해 단계적인 실험을 수행하였다. 먼저 다양한 규모의 학술적 실험 인스턴스를 활용하여 기존의 메타 휴리스틱 알고리즘들과 성능을 비교하였으며, 이를 통해 제안 알고리즘이 대규모 문제에서도 우수한 수렴 성능과 해의 품질을 유지함을 확인하였다. 이어 삼성중공업의 실제 항차 계획 데이터를 기반으로 수행한 사례 연구에서는 소형부터 대규모 인스턴스에 이르기까지 모든 경우에서 약 300초 내외의 실무적으로 허용 가능한 시간 내에 현업의 실적 대비 항차 횟수 절감과 납기 준수율의 향상을 동시에 달성하였다. 이는 본 연구에서 제안한 모델과 알고리즘이 실제 조선소 현장의 복합적인 제약 환경을 준수하면서도 물류 운영의 효율성을 개선할 수 있는 실질적인 대안임을 입증한다.

다국어 초록 (Multilingual Abstract)

The voyage planning in a shipyard involves scheduling barges to transport completed blocks from production sites to downstream process areas. This process is a complex decision-making task that combines a 2D packing problem to maximize loading efficiency with a scheduling problem for Just-In-Time production, resulting in extremely high computational complexity. Currently, most shipyards rely on the manual planning of experienced workers, which lacks flexibility when facing schedule revisions or large-scale long-term planning.
To address these practical operational environments, this study defines a mathematical model for the 2D-PBMSP-TW-RC (2D Bin Packing Parallel Batch Machine Scheduling Problem with Time Windows and Resource Constraints). This model extends the academically defined parallel batch machine scheduling problem by rigorously formulating the resource availability and time window constraints encountered in real-world voyage planning.
The proposed optimization framework features a hierarchical structure that combines the Orthogonal Biased Random Key Genetic Algorithm (OBRKGA) for global search with Constraint Programming (CP) for local optimization and constraint satisfaction. OBRKGA, the global search model, ensures search stability by incorporating orthogonal experimental design and biased crossover to optimize both the initial distribution of the search space and the convergence speed. In the batch grouping stage, a Hierarchical Best Fit First algorithm is proposed to simultaneously consider due-date proximity and loading efficiency. Furthermore, an Extended Backward Scheduling algorithm is developed to determine the feasibility of the schedule and is utilized as an indirect evaluation mechanism. This hierarchical structure maximizes search efficiency under complex physical constraints by decoupling search intelligence from constraint satisfaction logic and provides structural scalability to flexibly respond to changes in practical constraints.
The performance and effectiveness of the proposed methodology were verified through a series of staged experiments. First, the performance was compared with existing meta-heuristic algorithms using academic instances of various scales, confirming that the proposed algorithm maintains superior convergence and solution quality even in large-scale problems. Subsequently, a case study based on actual voyage planning data from Samsung Heavy Industries demonstrated that for all instances, ranging from small to large scales, the proposed approach achieved a reduction in the number of voyages and an improvement in due-date satisfaction compared to actual results—all within a practically acceptable computation time of approximately 300 seconds. These results prove that the model and algorithm proposed in this study serve as a practical alternative for improving logistics efficiency while complying with the complex constraint environments of real-world shipyards.

목차 (Table of Contents)

• 초록 i
• 목차 iii
• 표 목차 iv
• 그림 목차 vi
• Abbreviation 1
• Nomenclature 3
• 제 1 장 서론 5
• 제 2 장 선행 연구 8
• 제 3 장 배경 이론 11
• 제 3.1 절 문제 분해 방법론 11
• 제 3.2 절 유전 알고리즘 14
• 제 3.3 절 제약 프로그래밍 17
• 제 4 장 수학적 모델링 19
• 제 4.1 절 문제 개요 및 가정 사항 19
• 제 4.2 절 지표 및 파라미터 21
• 제 4.3 절 수리적 정식화 25
• 제 5 장 방법론 29
• 제 5.1 절 계층적 방법론 29
• 제 5.2 절 OBRKGA 기반 작업 그룹화 33
• 제 5.3 절 제약 프로그래밍 기반 배치 스케줄링 50
• 제 6 장 실험 및 결과 54
• 제 6.1 절 데이터 생성 및 평가 지표 54
• 제 6.2 절 실험 설계 58
• 제 6.3 절 실험 및 결과 61
• 제 7 장 사례 연구: 항차 계획 76
• 제 7.1 절 문제 정의 76
• 제 7.2 절 실험 설계 및 결과 81
• 제 8 장 결론 85
• 참고 문헌 87