TY - GEN
A1 - Sagnol, Guillaume
A1 - Balzer, Felix
A1 - BorndÃ¶rfer, Ralf
A1 - Spies, Claudia
A1 - von Dincklage, Falk
T1 - Makespan and Tardiness in Activity Networks with Lognormal Activity Durations
N2 - We propose an algorithm to approximate the distribution of the completion time (makespan)
and the tardiness costs of a project, when durations are lognormally distributed. This problem arises naturally for the optimization of surgery scheduling,
where it is very common to assume lognormal procedure times. We present an analogous of Clark's formulas to compute the moments of the maximum of a set of
lognormal variables. Then, we use moment matching formulas to approximate the earliest starting time of each activity of the project by a shifted lognormal variable.
This approach can be seen as a lognormal variant of a state-of-the-art method used for the statistical static timing analysis (SSTA) of digital circuits.
We carried out numerical experiments with instances based on real data from the application to surgery scheduling. We obtained very
promising results, especially for the approximation of the mean overtime in operating rooms,
for which our algorithm yields results of a similar quality to Monte-Carlo simulations
requiring an amount of computing time several orders of magnitude larger.
T3 - ZIB-Report - 16-23
KW - scheduling
KW - activity network
KW - lognormal distribution
Y1 - 2016
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-59290
SN - 1438-0064
ER -
TY - GEN
A1 - Sagnol, Guillaume
A1 - Schmidt genannt Waldschmidt, Daniel
A1 - Tesch, Alexander
T1 - The Price of Fixed Assignments in Stochastic Extensible Bin Packing
N2 - We consider the stochastic extensible bin packing problem (SEBP) in which $n$ items of stochastic size are packed into $m$ bins of unit capacity. In contrast to the classical bin packing problem, bins can be extended at extra cost. This problem plays an important role in stochastic environments such as in surgery scheduling: Patients must be assigned to operating rooms beforehand, such that the regular capacity is fully utilized while the amount of overtime is as small as possible.
This paper focuses on essential ratios between different classes of policies: First, we consider the price of non-splittability, in which we compare the optimal non-anticipatory policy against the optimal fractional assignment policy. We show that this ratio has a tight upper bound of $2$. Moreover, we develop an analysis of a fixed assignment variant of the LEPT rule yielding a tight approximation ratio of $1+1/e \approx 1.368$ under a reasonable assumption on the distributions of job durations.
Furthermore, we prove that the price of fixed assignments, which describes the loss when restricting to fixed assignment policies, is within the same factor. This shows that in some sense, LEPT is the best fixed assignment policy we can hope for.
T3 - ZIB-Report - 18-19
KW - Approximation Algorithms
KW - Stochastic Scheduling
KW - Extensible Bin Packing
Y1 - 2018
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-68415
SN - 1438-0064
ER -