Advances in multi-crane scheduling: Extended non-interference modeling and temporal-constraint-based valid inequalities

This study investigates the multi-crane scheduling problem (MCSP), motivated by operational challenges at a steelmaking plant in South Korea. In this problem, multiple cranes operate on tracks and perform tasks involving the transportation of materials between production machines. A key challenge in the MCSP is avoiding interference between cranes that share tracks. While an existing closed-form non-interference model is available, it applies only to scenarios where cranes remain stationary while executing tasks-such as quay cranes in container terminals. This research significantly extends that model to accommodate tasks in which cranes transport materials across multiple locations on tracks, enabling more efficient modeling and analysis for broader variants of the MCSP. In addition, we address temporal constraints (TCs), including both time windows for task start times and generalized precedence relations among tasks, which arise from pre-scheduled production plans. To solve the MCSP with TCs, we propose a novel mixed-integer linear programming (MILP) formulation that minimizes the total flow time of tasks, based on the extended non-interference model. We further enhance the MILP by incorporating valid inequalities derived from network analysis on TCs. The effectiveness of our methods is validated through comparisons with existing MILPs using real-world data from the investigated plant.