EURO 2025 Leeds
Abstract Submission

1754. The single machine adversarial bilevel total tardiness problem with job selection

Invited abstract in session MB-12: Scheduling models and algorithms, stream Scheduling and Project Management.

Monday, 10:30-12:00
Room: Clarendon SR 1.02

Authors (first author is the speaker)

1. Elena Rener
University of Bern
2. Federico Della Croce
DIGEP, Politecnico di Torino
3. Andrea Grosso
Università di Torino
4. Vincent T'KINDT
University of Tours

Abstract

Bilevel scheduling problems emerge in a variety of domains, including manufacturing and information systems. In these contexts, local schedulers interact with global decision centers in a system characterized by asymmetric information and self-interested behavior. Our study focuses on a particular case where a local scheduler aims to minimize total tardiness by assigning jobs to a single machine. The scheduler first submits the jobs to a dispatching center, which selects only a subset of them. Assuming that the selection criteria are unknown and do not take into account the scheduler's objective, we consider the adversarial analysis, which evaluates the worst-case situation for the local scheduler, i.e., the case where the minimum total tardiness is the maximum among all possible job selections.
From a computational perspective, this setting poses significant challenges in developing tight bounds and identifying partial job selections that yield suboptimal solutions. This is because the final schedule heavily depends on the full job selection. Nonetheless, in instances where the partial job selection exhibits specific characteristics, it is possible to derive an upper bound. Moreover, powerful job dominance conditions can be applied during the search process, and properties of optimal solutions can be used to rapidly identify good solutions. We propose an exact algorithm, derived from these results, that efficiently solves instances with more than a hundred jobs.

Keywords

Status: accepted

Back to the list of papers