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.

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.