|
8:50 |
Welcome: Marc Uetz, Tjark Vredeveld, Cliff Stein |
|
9:00 |
Invited
Speaker: Chandra Chekuri.
Online Broadcast Scheduling: New
Perspectives and Results |
|
9:50 |
Plenary:
Nikhil Bansal, Ho-Leung Chan and Kirk Pruhs.
Speed Scaling with an Arbitrary Power Function
|
|
10:20 |
Coffee
Break |
|
11:00 |
Parallel
Sessions |
| |
Session A |
Session B |
| |
Andreas S. Schulz and
Nelson A. Uhan.
Near-Optimal Solutions and Large Integrality Gaps for
Almost All Instances of Single-Machine
Precedence-Constrained Scheduling |
Donatas Elvikis,
Horst W. Hamacher and Vincent T'Kindt.
Scheduling two interfering job sets on uniform parallel
machines with sum and makespan criteria |
| |
Alix Munier Kordon, Fadi
Kacem, Benoit Dupont de Dinechin and Lucian Finta.
Minimizing the makespan for an interval ordered
precedence graph on m processors with communication
delays and unit execution time tasks |
Thijs Urlings and Rubén
Ruiz.
A new algorithm for multidimensional scheduling problems
|
| |
Ronald Koch, Britta Peis,
Martin Skutella and Andreas Wiese.
Routing and Scheduling Messages through Communication
Networks:Approximation Algorithms and Complexity |
Yakov Zinder and Samuel
Walker.
Scheduling flexible multiprocessor tasks on parallel
machines |
| |
Christoph Ambühl, Monaldo
Mastrolilli, Nikolaus Mutsanas and Ola Svensson.
Precedence Constraint Scheduling: Connections to
Dimension Theory of Partial Orders and Inapproximability
Results |
Claire Hanen, Philippe
Lacomme, Emmanuel Medernach and Eric Sanlaville.
Two formulations for a grid cyclic scheduling problem |
|
12:30 |
Lunch |
|
14:30 |
Parallel
Sessions |
| |
Session A |
Session B |
| |
Dries Goossens, Sergey
Polyakovskiy, Frits C.R. Spieksma and Gerhard J. Woeginger.
The focus of attention problem
|
Liliana
Cucu-Grosjean and Yves Sorel.
A schedulability test for real-time dependant periodic
task systems with latency constraints |
| |
Rolf Harren and Rob van
Stee.
An Absolute 2-Approximation for Rectangle Packing |
Valery S. Gordon and Vitaly
A.
Strusevich.
Single machine due date assignment and scheduling with
positionally dependent processing times |
| |
Benjamin Hiller and Tjark
Vredeveld.
Stochastic dominance analysis of online bin coloring
algorithms |
Paul C. Bell and Prudence
W. H. Wong.
Multiprocessor Speed Scaling for Jobs with Arbitrary
Sizes and Deadlines |
| |
Elisabeth Günther, Felix
G. König and Nicole Megow.
The Bin Scheduling Problem |
Stanley P.Y. Fung.
Online Algorithms for Maximizing Weighted Throughput of
Unit Jobs with Temperature Constraints |
|
15:50 |
Coffee Break |
|
16:20 |
Plenary:
Matthias Englert, Deniz Özmen and Matthias Westermann.
The Power of Reordering for Online Minimum Makespan
Scheduling |
|
16:50 |
Short Break & Room
Change |
|
17:00 |
Parallel
Sessions |
| |
Session A |
Session B |
| |
José R. Correa, Martin Skutella
and José Verschae.
The power of preemption on unrelated machines and
applications to scheduling orders |
Joseph Chan, Francis Y.L.
Chin, Hing-Fung Ting and Yong Zhang.
Online Tree Node Assignment with Resource Augmentation
|
| |
René Sitters.
Minimizing average flow time on unrelated machines |
Walter Kern and Jacob Jan
Paulus.
On the lower bound for online strip packing
|
| |
Wiebke Höhn, Tobias
Jacobs and Nicole Megow.
On Eulerian Extension Problems and their Application to
Sequencing Problems |
Sleman Saliba, Sven
O. Krumke, Benjamin Hiller and Andreas Tuchscherer.
Randomized online algorithms for the dynamic
multi-period routing problem |
| |
Tomáš Ebenlendr and Jiří
Sgall.
Semi-Online Preemptive Scheduling: One Algorithm for All
Variants |
|
|
19:00 |
Welcome Reception &
Dinner |
