<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>7122</id>
    <completedYear/>
    <publishedYear>2018</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>327</pageFirst>
    <pageLast>347</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>11312</volume>
    <type>conferenceobject</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The Price of Fixed Assignments in Stochastic Extensible Bin Packing</title>
    <abstract language="eng">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.&#13;
&#13;
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.&#13;
&#13;
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.</abstract>
    <parentTitle language="eng">WAOA 2018: Approximation and Online Algorithms</parentTitle>
    <identifier type="doi">10.1007/978-3-030-04693-4_20</identifier>
    <enrichment key="Series">Lecture Notes in Computer Science</enrichment>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-68415</enrichment>
    <enrichment key="SubmissionStatus">accepted for publication</enrichment>
    <enrichment key="AcceptedDate">2018-07-23</enrichment>
    <author>Guillaume Sagnol</author>
    <submitter>Guillaume Sagnol</submitter>
    <author>Daniel Schmidt genannt Waldschmidt</author>
    <author>Alexander Tesch</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="sagnol">Sagnol, Guillaume</collection>
    <collection role="persons" number="tesch">Tesch, Alexander</collection>
    <collection role="projects" number="BMBF-IBOSS">BMBF-IBOSS</collection>
    <collection role="institutes" number="healthcare">Mathematics of Health Care</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>8126</id>
    <completedYear/>
    <publishedYear>2019</publishedYear>
    <thesisYearAccepted/>
    <language>deu</language>
    <pageFirst>20</pageFirst>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue>12</issue>
    <volume/>
    <type>other</type>
    <publisherName>Wiley</publisherName>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="deu">Algorithmen unterstützen OP-Planung</title>
    <abstract language="deu">Mathematische Algorithmen&#13;
können durch Vorhersage&#13;
von Unsicherheiten optimierte OP-Pläne berechnen,&#13;
sodass mehrere Zielkriterien&#13;
wie Überstunden, Wartezeit&#13;
und Ausfälle im OP minimiert werden.</abstract>
    <parentTitle language="deu">Management &amp; Krankenhaus</parentTitle>
    <enrichment key="PeerReviewed">no</enrichment>
    <enrichment key="SubmissionStatus">in press</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="FulltextUrl">https://www.management-krankenhaus.de/restricted-files/136444</enrichment>
    <enrichment key="opus.doi.autoCreate">false</enrichment>
    <enrichment key="opus.urn.autoCreate">true</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Guillaume Sagnol</submitter>
    <author>Alexander Tesch</author>
    <author>Guillaume Sagnol</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="sagnol">Sagnol, Guillaume</collection>
    <collection role="persons" number="tesch">Tesch, Alexander</collection>
    <collection role="projects" number="BMBF-IBOSS">BMBF-IBOSS</collection>
    <collection role="institutes" number="healthcare">Mathematics of Health Care</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>6841</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2018-04-23</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The Price of Fixed Assignments in Stochastic Extensible Bin Packing</title>
    <abstract language="eng">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.&#13;
 &#13;
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. &#13;
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.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-68415</identifier>
    <author>Guillaume Sagnol</author>
    <submitter>Guillaume Sagnol</submitter>
    <author>Daniel Schmidt genannt Waldschmidt</author>
    <author>Alexander Tesch</author>
    <series>
      <title>ZIB-Report</title>
      <number>18-19</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Approximation Algorithms</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Stochastic Scheduling</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Extensible Bin Packing</value>
    </subject>
    <collection role="msc" number="90B36">Scheduling theory, stochastic [See also 68M20]</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="sagnol">Sagnol, Guillaume</collection>
    <collection role="persons" number="tesch">Tesch, Alexander</collection>
    <collection role="projects" number="BMBF-IBOSS">BMBF-IBOSS</collection>
    <collection role="institutes" number="healthcare">Mathematics of Health Care</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/6841/stoch_EBP_zib.pdf</file>
  </doc>
</export-example>
