WA6 - Scheduling 4

This study addresses a large-scale Multiple-Depot Electric Bus Scheduling Problem with a homogeneous fleet. Given a fixed timetable, the goal is to construct feasible bus schedules that cover each trip exactly once while respecting battery constraints. The problem is formulated as a set partitioning model with additional side constraints, based on a connection-oriented network representation.
To solve this problem, we propose a hybrid approach that integrates Column Generation (CG) with Dynamic Discretization Discovery (DDD). The method starts with a relaxed model, dynamically checks the feasibility of bus schedules and refines the discretization of the state of charge when necessary. The CG framework relies on solving shortest path subproblems with resource constraints using a labeling algorithm. To obtain high-quality integer solutions, the CG-DDD procedure is embedded within a diving heuristic that incorporates schedule variable fixing and inter-task fixing strategies.

This paper designs bus bridging services under regional metro disruptions to replace the disrupted metro system and evacuate stranded passengers. In particular, to depart from the disrupted area in a timely manner, passengers may shift their destinations according to the available bus bridging services. Specifically, passengers may first take bus bridging services to nearby locations and then travel to their final destinations by other modes, such as walking or taxis. To model this problem, we design a bus bridging service with destination shifting that determines both bus routing and dispatching decisions and provides subsidies to passengers who are willing to shift their destinations. In disruption scenarios, passenger demands cannot be accurately observed in advance and may be affected by real-time disruption conditions. Therefore, this paper considers time-dependent demand uncertainty. To address this challenge, we propose a dynamic scenario-based predict-then-optimize approach based on a rolling horizon framework. For each horizon, we first develop a temporal fusion transformer method to predict demand quantiles rather than point forecasts, so as to model disruption-related demand uncertainty. Based on the predicted demand quantiles, demand scenarios are generated, and a scenario-based stochastic programming model is proposed to determine reliable bus dispatching decisions. Considering the computational time requirements of dynamic decision-making, we further develop a partial Benders decomposition method to solve the optimization part efficiently. Experimental results show that the proposed scenario predict-then-optimize approach can efficiently solve the dynamic problem and generate reliable dispatching decisions. In addition, the introduction of destination shifting can significantly improve passenger evacuation efficiency under disruption scenarios.

In this study, we solve the problem of scheduling jobs on identical machines. Jobs have different release dates, processing times and unit sizes. We propose a heuristic method based on a column generation algorithm.
Key words: job scheduling, column generation, branch and price

Smart manufacturing systems which rely solely on sensor-based fault classification may limit operational value due to classification uncertainty. The proposed model learns from historical data and determines the optimal time for system overhaul in real-time, accounting for misclassification, operational costs, and degradation trends, demonstrated through a grinding machine case study.