MA6 - Scheduling 1

Traditional robust optimization struggles to model sparse uncertainty, where only a small and unknown subset of parameters experiences significant deviations, leading to NP-hard combinatorial formulations that are intractable for standard convex methods. This work proposes a scalable framework for robust optimization under sparse uncertainty by intersecting sparsity sets with conventional convex uncertainty sets to reduce conservatism. Tractable approximations are obtained through problem lifting and projection-based relaxations, combined with a cutting-plane algorithm and efficient scenario reduction to identify near worst-case sparse perturbations. Theoretical guarantees and numerical experiments demonstrate strong scalability and effectiveness for large-scale robust decision-making problems.

We optimize home care routing and scheduling by incorporating learning effects, where a caregiver's familiarity with a client reduces service time. Our chance-constrained model treats uncertainty as endogenous based on prior assignments. This approach maximizes scheduled visits while meeting service levels, significantly reducing schedule variability compared to traditional exogenous models.

Winter berth planning at northern ports becomes much harder when ice and severe weather affect vessel handling times. We focus on a stochastic berth allocation problem and propose state-dependent cuts that use similarities across weather scenarios. In our experiments, this leads to faster convergence, fewer scenario evaluations, and more reliable berth allocation plans.

We introduce the Team Crew Pairing Problem (TCPP), a generalization of the Crew Pairing Problem that explicitly models cabin crew teams. In the TCPP, each pairing is associated with a set of crew slices, subsets of the crew requirements of a flight, forming teams. A flights can thus be covered by one main and possibly several complementary crew slices. Our model also handles several crew classes and downranking. We propose a scalable three-phase method: crew slice selection, pairing optimization, and reoptimization of downranking. It is tested on long-haul instances from a major Asian airline.