Scheduling and Packing Under Uncertainty

Abstract

Incomplete information is a major challenge when translating combinatorial optimization results to recommendations for real-world applications since problem relevant parameters change frequently or are not known in advance. A particular solution may perform well on some specific input data or estimation thereof, but once the data is slightly perturbed or new tasks need to be performed, the solution may become arbitrarily bad or even infeasible. Thus, either solving the problem under uncertainty or efficiently updating the solution becomes a necessity. This thesis explores several models for uncertainty in various problems from two fundamental fields of combinatorial optimization: scheduling and packing. Scheduling arise whenever scarce resources have to complete a set of tasks while optimizing some objective such as minimizing the duration of the system or maximizing the throughput in a given time interval. Packing problems appear whenever items have to be assigned to resources with capacities. Typically, they require compliance with certain capacity constraints while maximizing the overall value of successfully packed items. Incomplete information may be caused by various reasons, such as the unpredictable arrival of new tasks or items or having only estimates of input parameters at hand. In any of these cases, we are interested in finding provably good solutions in reasonable time. In other words, we would like to design algorithms that deal with incomplete information while performing sufficiently well. This thesis focuses on three models of uncertainty in the input: stochastic, online, and dynamic.