Conference Agenda

Overview and details of the sessions of this conference. Please select a date or location to show only sessions at that day or location. Please select a single session for detailed view (with abstracts and downloads if available).

Session Overview
D1S3T2: Optimization under Uncertainty
Wednesday, 23/Feb/2022:
2:45pm - 3:45pm

Session Chair: Daniel Schmand

External Resource:
Show help for 'Increase or decrease the abstract text size'

Exploiting Untrusted Predictions in the Design of Scheduling Algorithms

Lindermayr, Alexander; Megow, Nicole

University of Bremen, Germany

Scheduling decisions are at the core of many logistics decision processes. The quality of a schedule often directly affects total cost, customer satisfaction and profit. Clearly, this quality crucially depends on the given accuracy of the model and the input data. However, in typical realistic scheduling scenarios, the precise processing times of individual tasks might be unknown. While classical online optimization methods design non-clairvoyant algorithms with bounded worst-cases guarantees for such settings, it might be overly pessimistic to make no assumptions on a task's length. Today, in the advent of data-driven applications we may expect to have an estimate for these sizes, e.g., based on simple statistics or complex machine-learning models. Such predictions are often good, but there is no guarantee on their quality and they might be arbitrarily wrong.

In this presentation, we show how to implement such error-prone predictions in scheduling algorithms and still prove performance guarantees for the quality of the resulting schedule. We design algorithms that perform well when given sufficiently good predictions, while being robust against arbitrarily bad predictions. Our performance bounds depend on the quality of a prediction, giving a smooth transition of guarantees from good to bad predictions. We focus on scheduling on a single as well as multiple (heterogeneous) machines with the objective to minimize the total (weighted) completion time.

Explorable Uncertainty meets Decision-Making in Logistics

Megow, Nicole; Schlöter, Jens

University of Bremen, Germany

Decision-making under uncertainty is a major challenge in logistics. Mathematical optimization has a long tradition in providing powerful methods for solving logistics problems. While classical optimization models for uncertainty in the input data do not consider the option to actively query the precise value of uncertain input elements, this option is in practice often available at a certain cost. For instance, an intelligent container might be equipped with sensors to enable active queries for more precise information on the state of transported goods, and tests in a laboratory might reveal more precise information on the shelf life of perishable goods. Queries come at a cost (battery usage, cost of laboratory usage), but the revealed information can be used to optimize an adaptive logistics planning framework. The recent line of research on optimization under explorable uncertainty develops methods with provable performance guarantees for such scenarios.

In this talk, we consider fundamental problems under explorable uncertainty, such as minimum spanning tree computation, selection problems and graph orientation, that are important (sub)problems when optimizing logistics processes. We highlight recent results from the mathematical optimization perspective and outline the potential power of such models and techniques for solving logistics problems. Since more complex logistics problems admit strong lower bounds with respect to worst-case analysis, we focus on exploiting additional information to break those lower bounds. To this end, we present algorithms for the stochastic problem variant (average-case analysis) and show how machine-learned predictions can be exploited to obtain improved results.

The Assignment Problem with Uncertainty

Hommelsheim, Felix1; Mühlenthaler, Moritz2; Schaudt, Oliver3

1University of Bremen, Germany; 2Université Grenoble-Alpes; 3RWTH Aachen University

A typical task in production planning is to assign tasks to machines or employees, while minizing the cost for the assignment. Such a cost-minimizing assignment can be computed efficiently by so-called matching algorithms. However, these algorithms do not take into account that we might encounter uncertainty: for example, an employee can get sick or a machine might fail. In this paper we develope robust algorithms that can deal with uncertainty. To be more precise, we show that computing such a robust assignment is NP-hard in general and thus we cannot expect to compute an optimal solution in reasonable time. However, we design approximation algorithms for this task, i.e. algorithms that efficiently compute near-optimal solutions.

Contact and Legal Notice · Contact Address:
Privacy Statement · Conference: LDIC 2022
Conference Software - ConfTool Pro 2.6.144
© 2001–2022 by Dr. H. Weinreich, Hamburg, Germany