양방향 컨테이너 흐름을 고려한 선점형 트윈 크레인 스케줄링 = Preemptive Twin-Crane Scheduling Considering Bidirectional Container Flows

국문 초록 (Abstract)

자동화 컨테이너 터미널(ACT)에서 컨테이너 처리량과 운영 복잡도가 지속적으로 증가함에 따라, 야드 블록 병목을 완화하기 위한 자동화 야드 크레인 스케줄링의 중요성이 커지고있다. 본 연구는 양쪽 끝에 입·출고 지점이 설치된 야드 블록에서 트윈 크레인을 대상으로,수입·수출 컨테이너가 동일 블록 내에서 공존하는 양방향 컨테이너 흐름을 고려한 선점 기반스케줄링 문제를 다룬다. 선점은 한 크레인이 컨테이너를 중간 위치에 임시로 내려놓고 다른크레인이 해당 작업을 이어받도록 함으로써 크레인 간 간섭을 줄이고 작업량을 보다 균형있게 분배하는 기법이다. 그러나 선점이 과도하게 발생하면 불필요한 추가 이동과 상·하차작업이 증가하여 오히려 비효율을 초래할 수 있다. 이에 본 연구는 단일 크레인 스케줄링분석에서 도출한 근사치를 활용해, 선점 여부와 인계 지점을 함께 결정하는 정수 선형 계획모형을 제안한다. 제안한 모형은 불필요한 선점 발생을 억제하고, 주어진 요청 집합의 특성을반영한 효율적인 중간 인계 지점을 식별함으로써 총 작업 완료 시간(makespan)을 최소화하는것을 목표로 한다. 실험 결과, 제안한 선점 전략은 기존 방법 대비 makespan과 차단 시간을유의미하게 감소시키며 다양한 상황에서도 강건한 성능을 보였다. 또한 통계적 분석을 통해제안 방법이 크레인의 이동 시간 및 상·하차 시간을 줄여 기준 방법보다 평균 makespan을단축함을 확인하였다. 이러한 결과는 선점이 ACT의 트윈 크레인 운영에서 유망하고 실질적인개선 효과를 제공하는 스케줄링 전략임을 보여준다.

다국어 초록 (Multilingual Abstract)

As container throughput and operational complexity continue to increase in automated containerterminals (ACTs), the scheduling of automated stacking cranes (ASCs) has become increasinglyimportant for mitigating yard block bottlenecks. This study addresses a flexible preemption basedscheduling problem for twin ASCs operating in a yard block equipped with input/output points atboth ends. The problem considers bidirectional container flows, where import and export containers coexist within the same block. Preemption allows one crane to temporarily place a container at an intermediate position so that the other crane can complete its delivery, thereby reducing craneinterference and balancing workloads. However, excessive preemption may result in unnecessaryadditional operations that offset these benefits. To address this trade-off, we develop an Integer Linear Programming-based preemption decision model that incorporates approximations derived from single-crane scheduling analysis. This model aims to minimize makespan, limit redundant preemptions, and identify efficient transfer points that reflect the characteristics of the given request set. Extensive computational experiments demonstrate that the proposed preemption strategy outperforms existing methods in terms of makespan and blocking time, showing robust and superior performance.
Statistical analysis further confirms that the proposed approach reduces empty travel time and loading/unloading time, resulting in a shorter average makespan than the baseline method. These findings indicate that flexible preemption is a promising and effective scheduling strategy for ACT operations,providing practical insights for efficient twin-ASC coordination.

목차 (Table of Contents)

• 제 1 장 서론 1
• 1.1 연구 배경 . 1
• 1.2 연구 목적 . 1
• 1.3 연구 구성 . 8
• 제 2 장 선행 연구. 9
• 제 3 장 문제 설명. 14
• 제 4 장 방법론. 18
• 4.1 선점 결정 . 18
• 4.2 작업 순서 및 우선순위 최적화 26
• 제 5 장 실험 결과. 30
• 5.1 실험 계획 . 30
• 5.1.1 인스턴스 생성. 31
• 5.2 결과 및 논의 . 32
• 5.2.1 Makespan 비교 32
• 5.2.2 선점 전략에 따른 위치-시간 그래프. 35
• 5.2.3 차단 시간 분석 39
• 5.2.4 유연한 선점의 효과 . 41
• 제 6 장 결론 43
• 참고문헌 . 45
• 부록 50
• 1 Mixed Integer Programming for BPCSP 50
• 2 평가 함수 53
• 3 BH 성능 비교 54
• 4 대규모 인스턴스에서 비교 55
• Abstract 57