6841
eng
reportzib
0
--
2018-04-23
--
The Price of Fixed Assignments in Stochastic Extensible Bin Packing
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.
1438-0064
urn:nbn:de:0297-zib-68415
Guillaume Sagnol
Guillaume Sagnol
Daniel Schmidt genannt Waldschmidt
Alexander Tesch
ZIB-Report
18-19
eng
uncontrolled
Approximation Algorithms
eng
uncontrolled
Stochastic Scheduling
eng
uncontrolled
Extensible Bin Packing
Scheduling theory, stochastic [See also 68M20]
Mathematical Optimization
Sagnol, Guillaume
Tesch, Alexander
BMBF-IBOSS
Mathematics of Health Care
https://opus4.kobv.de/opus4-zib/files/6841/stoch_EBP_zib.pdf
8418
2021
eng
79:1
79:14
204
article
0
--
--
--
Restricted Adaptivity in Stochastic Scheduling
We consider the stochastic scheduling problem of minimizing the expected makespan on m parallel identical machines. While the (adaptive) list scheduling policy achieves an approximation ratio of 2, any (non-adaptive) fixed assignment policy has performance guarantee Ω(logm/loglogm). Although the performance of the latter class of policies are worse, there are applications in which non-adaptive policies are desired. In this work, we introduce the two classes of δ-delay and τ-shift policies whose degree of adaptivity can be controlled by a parameter. We present a policy - belonging to both classes - which is an O(loglogm)-approximation for reasonably bounded parameters. In other words, an exponential improvement on the performance of any fixed assignment policy can be achieved when allowing a small degree of adaptivity. Moreover, we provide a matching lower bound for any δ-delay and τ-shift policy when both parameters, respectively, are in the order of the expected makespan of an optimal non-anticipatory policy.
29th Annual European Symposium on Algorithms (ESA 2021)
10.4230/LIPIcs.ESA.2021.79
Leibniz International Proceedings in Informatics (LIPIcs)
yes
publish
arXiv:2106.15393
Guillaume Sagnol
Guillaume Sagnol
Daniel Schmidt genannt Waldschmidt
Mathematical Optimization
Sagnol, Guillaume
BMBF-IBOSS
Mathematics of Health Care
Network Optimization
7122
2018
eng
327
347
11312
conferenceobject
0
--
--
--
The Price of Fixed Assignments in Stochastic Extensible Bin Packing
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, the number of bins is fixed and they 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+e−1)≈1.368 under a reasonable assumption on the distributions of job durations.
Furthermore, we prove that the price of fixed assignments, related to the benefit of adaptivity, 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.
WAOA 2018: Approximation and Online Algorithms
10.1007/978-3-030-04693-4_20
Lecture Notes in Computer Science
yes
urn:nbn:de:0297-zib-68415
accepted for publication
2018-07-23
Guillaume Sagnol
Guillaume Sagnol
Daniel Schmidt genannt Waldschmidt
Alexander Tesch
Mathematical Optimization
Sagnol, Guillaume
Tesch, Alexander
BMBF-IBOSS
Mathematics of Health Care