MAPSP 2022

Invited Speakers

Alessandro Agnetis

Università di Siena, Dipartimento di Ingegneria dell'Informazione e Scienze Matematiche

Scheduling machines subject to unrecoverable failures and other related stochastic sequencing problems

Consider the following basic setting. A set of n jobs has to be performed on a set of parallel, identical machines. Unlike most scheduling situations, machines may actually fail, i.e., while performing a job i, they can become unavailable (e.g. break down) with probability \pi_i. Such failures are unrecoverable, in the sense that from then onwards the machine is lost and so are the jobs not yet processed on that machine. If a job i is successfully completed, a reward r_i is attained. The problem is how to assign the jobs to the machines and sequence them so that the expected reward is maximized. In this talk we review the main results, discuss relationships with other sequencing problems and point out some open problems. While the single-machine case is easy, for two or more machines the problem is hard and various approaches have been proposed to address it. For general m, list scheduling yields a 0.8531-approximate solution. The argument is similar to the one used by Schwiegelshohn to prove Kawaguchi and Kyan's bound for the minimization of total weighted completion time. A variant of this problem is attained if, in order to hedge against failures, we can use job replication. In this case, copies of the same job can be scheduled on different machines, and the reward r_i is attained if at least one copy is successfully completed. In this case, the sequence of the n copies of the jobs on each machine has to be decided. Although also this problem is hard for m>=2, relatively simple algorithms provide solutions which are provably close to optimality. A related sequencing problem is the following. A system consists of n components, each of which can be either functioning or not. Only if all components are functioning, the system is "up". Component i is functioning with probability \pi_i, and testing it costs c_i. As soon as a component that is not functioning is detected, the testing stops (concluding that the system is "down"). The problem is to decide in which order should the components be tested, in order to minimize the expected costs. While the single-tester problem is solved by a simple priority rule, various problem variants can be considered. In particular, if several testers operate in parallel, under time constraints, the problem gets more complicated. While it is NP-hard for three or more testers, its complexity with two testers is still open.

Thomas Erlebach

University of Durham, United Kingdom

Explorable Uncertainty and Untrusted Predictions

The research area of explorable uncertainty is concerned with problems where some of the input data is uncertain, but queries can be executed to reveal the true values of uncertain input elements. Uncertain values are typically given in the form of intervals. The goal is to minmise the number of queries that are needed until a provably correct solution can be output. In addition to the intervals, we may have access to predictions of the true values, possibly obtained via machine learning. Our aim is then to devise query strategies that benefit from accurate predictions but do not get misled too much by incorrect predictions. In this talk, we will discuss some recent progress in this combined setting, including query strategies for minimum spanning trees with edge uncertainty that benefit from good predictions while maintaining the best possible worst-case competitive ratio even if the predictions are arbitrarily wrong. (The talk is mainly based on joint work with Murilo Santos de Lima, Nicole Megow and Jens Schlöter.)

Lene Monrad Favrholdt

University of Southern Denmark, Odense, Denmark

Paging and Packing with Possibly Precise Predictions

The talk will survey techniques for designing and analyzing online algorithms with predictions, advice as well as possibly imprecise predictions. Online problems with predictions relate to semi-online problems in that some information is available which would not be available to a purely online algorithm. In the advice as well as the semi-online setting, this additional information is usually exact. In the semi-online setting, some emphasis is put on the information being realistically obtainable, whereas in the advice setting, the focus is on minimizing the amount of information communicated to the algorithm. In online problems with predictions, the concern is how well the algorithm adapts to errors in the information and the information should preferably be learnable. The running example will be the paging problem, but we will also consider packing problems such as knapsack and bin packing.

Alberto Marchetti Spaccamela

Università di Roma La Sapienza, Dipartimento di Ingegneria informatica automatica e gestionale

Scheduling DAGs: recent results and challenges

Multi-core architectures are nowadays widely used for their increased performance over single-core processors. To take full advantage of these architectures we must exploit intra-task parallelism. The Directed Acyclic Graph (DAGs) is a popular representation to describe the structure of parallel applications and to model the execution of multi-threaded programs that is widely used in cloud computing and in real-time systems. In this talk I will present recent results on DAG scheduling considering different models and focusing on complexity, approximation and integer linear program representations.