중기계획 부하를 고려한 제약 프로그래밍 기반 장기 계획 최적화

Abstract

The berth scheduling process pertains to the long-term scheduling within the shipyard's production plans and directly influences the annual operations of the shipyard. Due to its nature as a shipbuilding schedule spanning 3 to 6 years or even longer, the berth scheduling involves a large number of target ships, and it often requires a significant amount of time for planning, mainly relying on heuristic judgment by planners in most shipyards. Moreover, to consider the load of preceding processes, the method of planning multiple berths scheduling cases and subsequently calculating the berth case-specific loads is employed. However, this approach becomes a factor that increases the planning time. As a result, the berth scheduling is currently being done based on trial and error without a specific algorithm, and this limitation arises due to the constraints of the search space, which prevents the guarantee of the optimality of the resulting schedules. In this paper, we have developed a constraint programming-based model for optimizing berth scheduling by defining the constraints and objective functions. The model aims to derive the optimal berth schedules that satisfy these defined constraints and objective functions. Constraint programming is based on logical operations, enabling the straightforward modeling of complex constraints, and it leverages graph theory, making it a suitable method for solving scheduling problems effectively. The berth scheduling optimization problem is highly complex, consisting of numerous intricate constraints and covering an extensive time frame, making it a large-scale problem. Due to these challenges, we employed the constraint programming methodology to address this optimization problem effectively. The proposed model in this paper includes five key constraints, including daily launching frequency, possible launching dates for each ship type, shipyard space, daily workload of assembly processes, and key event constraint. By adding the daily workload constraint of the processes, the berth scheduling and the workload analysis of preceding processes have been integrated into a single model, avoiding them being treated as separate tasks. Utilizing constraint programming, the model efficiently searches for the optimal solutions, enabling fast berth scheduling. The model considers two main objective functions: maximizing workstage efficiency and ensuring contract deadline compliance for berth scheduling. To validate the model's effectiveness, we compared the model's results with actual performance data and verified the constraints using the same dataset. Additionally, we conducted a weighted analysis of multiple objective functions to derive Pareto optimal solutions, demonstrating the versatility of the model for berth scheduling. After ensuring the validity of the constraints and objective functions, we conducted a case study on various ship configurations and target ship quantities. During the case study, we conducted an exploration of solutions, analyzing the objective function values of the obtained results. Additionally, we performed an analysis of metrics such as ship leadtime increasing rate and consecutive assignment ratio by berth to gain a comprehensive understanding of the berth scheduling solutions generated by the model. In this paper, we propose a constraint programming-based model for optimizing berth scheduling. The developed model overcomes the limitations of planner-based berth scheduling, which heavily relies on implicit knowledge and experience and is constrained by planning time, to guarantee optimal solutions. Moreover, the model integrates dynamic optimization for the target period, which was not addressed in previous studies, along with load analysis, offering a comprehensive approach to berth scheduling optimization. Through this research, we have established a theoretical foundation for berth scheduling optimization and achieved practical implementation in optimizing berth scheduling.

선표 계획 과정은 조선소의 생산 계획 중 장기계획에 해당하며 조선소의 연간 운영에 직접적으로 영향을 미친다. 선표 계획은 3년에서 6년 또는 그 이상의 기간에 대한 건조 계획이기 때문에 계획 대상 호선이 많고, 대부분의 조선소에서 계획자의 휴리스틱한 판단에 의해 이루어지기 때문에 하나의 선표를 계획하는데 적지 않은 기간이 소요된다. 또한 선행공정의 부하를 고려하기 위해 다수의 선표를 계획한 뒤 선표 케이스별 부하를 계산하는 방법을 사용하는데, 이 방법은 계획 시간을 증가시키는 요인이 된다. 결과적으로, 특정한 알고리즘 없이 시행착오를 바탕으로 선표를 계획하고 있으며 이는 해 탐색 범위의 한계로 인해 도출된 계획의 최적 여부를 보장할 수 없다는 한계가 존재한다. 본 논문에서는 선표 계획 최적화를 위한 제약조건 및 목적함수를 정의하고 이를 만족하는 최적의 선표를 도출하는 제약 프로그래밍 기반의 모델을 개발하였다. 제약 프로그래밍은 논리 연산을 기반으로 하므로 복잡한 제약조건을 간단히 모델링 할 수 있고 그래프 이론을 기반으로 하여 스케줄링 문제를 풀기에 적합한 방법이다. 선표 계획 최적화 문제는 매우 복잡한 제약조건으로 구성되어 있고 대상 기간이 매우 길어 규모가 큰 문제이기 때문에 제약 프로그래밍 방법론을 사용하였다. 본 논문에서 제안하는 모델에는 일 별 진수 횟수, 선대 별 진수 가능 요일, 선대 공간, 조립 공정의 일 별 부하, 그리고 key event 시점 관련 항목까지 5개의 주요 제약조건이 포함된다. 공정의 일 별 부하 제약조건을 추가함으로써 선표 계획과 선행공정의 부하분석을 별개의 작업이 아닌 단일 모델로 통합하였으며, 제약 프로그래밍을 통해 최적의 해를 탐색하여 신속한 선표 계획을 가능하게 하였다. 목적함수로는 선표 계획에 가장 중요한 선대-선종 효율 최대화와 계약 납기 준수, 총 2가지를 모델에 반영하였다. 모델의 타당성 검토를 위해 동일한 데이터에 대하여 실적 결과와의 비교 및 제약조건 검증을 진행하였고, 다중 목적함수에 대한 가중치 분석을 통해 pareto optimal을 도출하여 선표 계획에 대한 모델의 범용성을 제시하였다. 제약조건 및 목적함수에 대한 타당성을 확보한 뒤, 다양한 선종의 구성 및 배치 대상 호선 수에 대한 사례 연구를 진행하였다. 사례 연구에서는 탐색이 진행되며 출력되는 해들에 대한 목적함수 값 분석과 호선 공기 증가율 및 선대 연속 배치 비율과 같은 지표에 대한 분석을 수행하였다. 본 논문에서는, 제약 프로그래밍 기반 선표 계획 최적화 모델을 제시하였다. 계획자의 암묵지 및 경험 기반의 선표 계획의 최적해 보장 및 계획 시간에 대한 한계를 극복하는 모델이며, 선행 연구에서 반영되지 못했던 배치 대상 기간에 대한 동적 최적화와 부하 분석을 통합한 모델을 개발하였다. 이를 통해, 선표 계획 최적화 문제에 대한 이론적 기반을 재정립하고, 선표 계획 최적화의 실용화를 달성하였다.