Optimizing Short-term Planning in Flat Block Assembly Line using Constraint Programming and Discrete-Event Simulation

Abstract

Scheduling flat block assembly line in a shipyard is crucial for overall shipbuilding performance in terms of its high volume of workload. This problem is commonly known as the Permutation Flow-shop Scheduling Problem (PFSP) in Operation Research (OR), which has been extensively studied in various papers since the 1950s. However, existing solutions often involve simplifying real-world problems with certain assumptions, limiting their practical applicability. In recent times, Constraint Programming (CP) has emerged as a strong alternative to exact algorithms and has been successfully applied to various PFSP problems, addressing the limitations of exact algorithms. In light of this, our study proposes a two-step optimization process to overcome these limitations. First, a novel CP algorithm is introduced to incorporate actual industrial constraints. The modelled PFSP can be categorized as a Multi-Objective PFSP with hard due date constraint (MOPFSP-hd). Next, the feasibility and objective value of the optimized solution is validated using Discrete-Event Simulation (DES). To evaluate the performance of our proposed framework, two industrial cases are conducted. The experimental results from both cases demonstrated an improvement in makespan compared to manually planned schedule. Additionally, the solutions derived from our proposed model are reported to be feasible, while the manually planned schedules are often infeasible either due to not satisfying industrial constraints or encountering delays. Finally, the difference between the objectives calculated from CP and DES model is analyzed quantitatively using Critical Path Method (CPM). The proposed solution in this paper presented a practical and effective approach to address PFSP with real-world constraints. By combining CP and DES techniques, the authors demonstrated improved makespan and feasible schedules compared to traditional methods using two industrial cases.

평면 블록 조립 라인의 스케줄링은 조선소의 전체 조선 건조 성능에 있어서 높은 작업량 때문에 매우 중요하다. 이 문제는 운영 연구에서 잘 알려진 Permutation Flow-shop Scheduling Problem(PFSP)으로서 1950년대부터 다양한 논문에서 광범위하게 연구되었다. 그러나, 기존의 해결책들은 실제 문제를 단순화하고 특정 가정들을 포함시키는 경우가 많아서 실제 문제들에 대한 적용이 제한되고 있다. 최근 제약 프로그래밍(CP)이 수리적 알고리즘들에 대한 강력한 대안으로 등장하며, 수리적 알고리즘의 한계를 성공적으로 극복하는 연구 사례들이 등장하고 있다. 이러한 배경에 따라, 본 연구는 기존 알고리즘들의 한계를 극복하기 위해 두 단계 계획 수립 최적화 프레임워크를 제안한다. 먼저, 실제 산업 제약 조건을 반영하는 새로운 CP 알고리즘을 소개한다. 이 PFSP는 Multi-Objective PFSP with hard due date constraint (MOPFSP-hd)으로서 분류될 수 있다. 다음으로, 도출된 최적화 해들의 타당성과 목적 함수 값은 이산 사건 시뮬레이션(DES)을 통해 검증한다. 제안한 스케줄링 프레임워크의 성능을 평가하기 위해 두 개의 산업 사례를 대상으로 계획이 수행되었다. 두 사례에 대한 실험 결과는 일관적으로 현재 실행 계획에 적용되는 휴리스틱 룰에 기반하여 작성된 계획에 비해 makespan이 개선되었음을 보여준다. 또한, 본 연구에서 제안한 프레임워크를 통해 도출된 해들은 산업 제약 조건을 모두 만족시키고 실현 가능한 반면에, 기존의 방법으로 수립된 해는 제약을 불만족시키거나 지연이 발생하여 실현 불가능한 해임을 DES를 통해 확인할 수 있었다. 마지막으로, CP와 DES 모델로부터 계산된 목적 함수 사이의 차이는 임계 경로 분석법 (CPM)을 사용하여 분석하였다. 본 연구에서 제시한 해결책은 현실적인 산업 환경에서의 PFSP를 다루기 위한 실질적이고 효과적인 방법을 소개했다. 기존의 한계를 극복하기 위해 CP와 DES 기법을 결합하여 기존의 방법들보다 개선된 makespan을 가지는 실현 가능한 계획을 도출 할 수 있음을 두 개의 산업 사례를 활용하여 보였다.