MAPSP 2011, June 19 - 24, Nymburk, Czech Republic
10th Workshop on Models and Algorithms for Planning and Scheduling Problems
Invited speakers
Important dates
Registration
Program
Local info
Committees
Submissions
Documents
Previous MAPSPs
Final schedule
A printable schedule and more compact list of accepted talks are available as well.Sunday, June 19
16:00 A conference bus from Prague18:30 Welcome party
(no talks on Sunday)
Monday, June 20
9:10 - 10:10 Invited talkYossi Azar. Fast approximation algorithms for submodular optimization problems
10:50 - 12:00 Parallel presentations
A
Fabian Kuhn and Monaldo Mastrolilli. Vertex Cover in Graphs with Locally Few Colors and Precedence Constrained Scheduling with Few Predecessors
Andreas Schranzhofer, Jian-Jia Chen and Lothar Thiele. Timing Predictability for Resource Sharing Multicore Systems - Challenges and Open Problems
Ruslan Sadykov and Francois Vanderbeck. Machine scheduling by column-and-row generation on the time-indexed formulation
B
Sheng Yu, Prudence W.H. Wong and Yinfeng Xu. Online Scheduling of Linear Deteriorating Jobs on Parallel Machines
Jason A. D. Atkin, Edmund K. Burke and Stefan Ravizza. A Statistical Approach for Taxi Time Estimation at London Heathrow Airport
Csanad Imreh and Tamas Nemeth. Parameter learning in online scheduling algorithms
C
Stefan Heinz and Jens Schulz. Explanation Algorithms for Cumulative Scheduling
Zdenek Baumelt, Premysl Sucha and Zdenek Hanzalek. A Genetic Algorithm for A Nurse Rerostering Problem
Marjan Van Den Akker, Roland Geraerts, Han Hoogeveen and Corien Prins. Path planning in games
15:30 - 16:30 Plenary presentations
Vincenzo Bonifaci and Alberto Marchetti-Spaccamela. Feasibility Analysis of Sporadic Real-Time Multiprocessor Task Systems
Elisabeth Günther, Marco Lübbecke and Rolf Möhring. Challenges in Scheduling when Planning the Ship Traffic on the Kiel Canal
16:45 - 18:20 Parallel presentations
A
Christophe Lenté, Mathieu Liedloff, Ameur Soukhal and T'Kindt Vincent. Exponential-time algorithms for scheduling problems
Vitaly Strusevich and Kabir Rustigi. Enchanced models of single machine scheduling with a deterioration effect and maintenance activities
Tomá Ebenlendr and Jiří Sgall. A lower bound on deterministic online algorithms for scheduling on related machines without preemption
Łukasz Jeż. One to Rule Them All: a General Randomized Algorithm for Buffer Management with Bounded Delay
B
Florian Dahms, Katharina Beygang and Sven O. Krumke. Online algorithms and bounds for the Train Marshalling Problem
Sofie Coene and Frits Spieksma. The lockmaster's problem
Wei Yu and Guochuan Zhang. Improved approximation algorithms for routing shop scheduling
Grzegorz Pawlak, Mateusz Cichenski, Mateusz Jarus and Slawomir Walkowski. The road traffic model for the car factory logistics
C
Mohamed Marouf, Laurent George and Yves Sorel. Schedulability analysis for a combination of preemptive strict periodic and sporadic tasks
Enrico Bini. The problem of mapping real-time applications over multiple machines
Philippe Thierry, Laurent George and Jean-François Hermant. Real-time scheduling analysis for ARINC-based virtualized systems
Liliana Cucu-Grosjean. Probabilistic analysis of periodic real-time tasks with random execution times on identical processors
Tuesday, June 21
9:00 - 10:00 Invited talkBert Zwart. Scheduling and queueuing - optimality under rare events and heavy loads
10:40 - 12:15 Parallel presentations
A
Sebastián Marbán, Cyriel Rutten and Tjark Vredeveld. Learning in stochastic machine scheduling
Rodrigo Carrasco, Garud Iyengar and Clifford Stein. Energy aware scheduling: minimizing total energy cost and completion time by α-points and α-speeds
Anand S, Naveen Garg and Nicole Megow. Meeting deadlines: How much speed suffices?
Sanjoy Baruah, Vincenzo Bonifaci, Gianlorenzo D'Angelo, Haohan Li, Alberto Marchetti-Spaccamela, Nicole Megow and Leen Stougie. Mixed-criticality scheduling
B
Marin Bougeret, Pierre-Francois Dutot and Denis Trystram. Using oracles for the design of efficient approximation algorithms
José Verschae and Andreas Wiese. On the Configuration-LP for Scheduling on Unrelated Machines
Jessica Chang, Hal Gabow and Samir Khuller. Scheduling Jobs in Parallel for Energy Savings
Murat Firat, Cor Hurkens and Gerhard Woeginger. Optimal planning in vehicle refueling problem with limited resources
C
Stéphane Dauzère-Pérès, Sadia Azem and Riad Aggoune. A Column Generation Approach for the Job-Shop Scheduling Problem with Availability Constraints
Bastian Bludau. A two-machine flow shop problem consisting of a discrete processor and a batch processor under uncertainty
Tomá Zajíček and Premysl Sucha. Accelerating a Flow Shop Scheduling Algorithm on the GPU
Maciej Machowiak, Jan Węglarz, Mikhail Y. Kovalyov and M.S. Barketau. Scheduling malleable tasks with arbitrary processing speed functions
15:30 - 16:30 Plenary presentations
Kirk Pruhs and Clifford Stein. How To Schedule When You Have To Buy Your Energy
Richard Cole, Jose Correa, Vasilis Gkatzelis, Vahab Mirrokni and Neil Olver. Inner Product Spaces for MinSum Coordination Mechanisms
16:45 - 18:20 Parallel presentations
A
Leah Epstein and Elena Kleiman. On the quality and complexity of Pareto equilibria in the Job Scheduling Game
Ruben Hoeksma and Marc Uetz. The Price of Anarchy for Related Machine Scheduling
Eyjólfur Ingi Ásgeirsson and Pradipta Mitra. Performance of Distributed Game Theoretic Algorithms for Single Slot Scheduling in Wireless Networks
Thierry Garaix, Christian Artigues and Cyril Briand. Fast minimum float computation in activity networks under interval uncertainty
B
Tao Li and Joel Wein. Allocating Resources in Clouds of Game Servers
Joanna Berlinska and Maciej Drozdowski. Scheduling and performance of divisible MapReduce applications
Zdenek Hanzalek, Claire Hanen and Premysl Sucha. Cyclic Scheduling - New Application and Concept of Core Precedences
Kan Fang, Nelson Uhan, Fu Zhao and John Sutherland. Flow Shop Scheduling for Sustainable Manufacturing
C
Karin Thörnblad, Michael Patriksson, Ann-Brith Strömberg and Torgny Almgren. Mathematical modelling of a real flexible job shop in aero engine component manufacturing
Aldar Dugarzhapov and Alexander Kononov. An exact polynomial time algorithm for the preemptive mixed shop problem with two unit operations per job
Sergey Sevastyanov and Bertrand M.T. Lin. Efficient enumeration of optimal and approximate solutions of the two-machine flow-shop problem
Roman Čapek, Přemysl ůcha and Zdeněk Hanzálek. Scheduling with Alternative Process Plans and the Total Weighted Tardiness Criterion
Wednesday, June 22
9:00 - 10:00 Invited talkRoman Barták. Modelling and Solving Scheduling Problems using Constraint Programming
10:40 - 11:40 Plenary presentations
Alexander Souza, Antonios Antoniadis, Falk Hüffner, Pascal Lenzner and Carsten Moldenhauer. Balanced Interval Coloring
Tim Nonner. Clique Clustering yields a PTAS for max-Coloring Interval Graphs
13:00 - ??? Excursion and conference dinner
Thursday, June 23
9:00 - 10:00 Invited talkDavid Shmoys. Strong LP Formulations and Primal-Dual Approximation Algorithms
10:40 - 12:15 Parallel presentations
A
Leah Epstein and Asaf Levin. An AFPTAS for due date scheduling with related machines of general costs
Klaus Jansen, Lars Prädel, Ulrich M. Schwarz and Ola Svensson. Faster approximation algorithms for scheduling with fixed jobs
Alexander Grigoriev, Alexander Kononov and Maxim Sviridenko. Logarithmic-approximations for the relocation problem
Neil Dobbs, Tomasz Nowicki, Maxim Sviridenko and Grzegorz Swirszcz. Approximating the Joint Replenishment Problem
B
Robert Davis. Quantifying the Sub-optimality of Uniprocessor Fixed Priority Scheduling
Gurulingesh Raravi, Björn Andersson and Konstantinos Bletsas. Intra-Type Migrative Scheduling of Implicit-Deadline Sporadic Tasks on Two-Type Heterogeneous Multiprocessor
Sleman Saliba, Iiro Harjunkoski and Matteo Biondi. Production Optimization and Scheduling in a Steel Plant: Hot Rolling Mill
Vincenzo Bonifaci, Gianlorenzo D'Angelo, Alberto Marchetti-Spaccamela, Suzanne Van Der Ster and Leen Stougie. Mixed-criticality scheduling of sporadic task systems
C
Ammar Oulamara and Ameur Soukhal. Scheduling serial batching machine with two competitive agents
Frederic Guinand, Amine Mahjoub and Eric Sanlaville. M machine scheduling under uncertainties on machine availabilities
Hana Rudová and Pavel Troubil. Media Streams Planning
Trivikram Dokka, Ioannis Mourtos and Frits Spieksma. Fast separation algorithms for three-index assignment problems
15:30 - 16:30 Plenary presentations
Tobias Brunsch, Heiko Roeglin, Cyriel Rutten and Tjark Vredeveld. Smoothed performance guarantees of local optima for multiprocessor scheduling
Natalia Shakhlevich. Divisible Load Scheduling to Minimize the Computation Time and Cost
16:45 - 18:20 Parallel presentations
A
Ralf Borndörfer, Guillaume Sagnol and Elmar Swarat. An Integrated Vehicle Routing and Duty Roster Planning of Toll Control Inspectors
Cor Hurkens, Murat Firat and Alexandre Laugier. Stability in multi-skill workforce assignments: complexity analysis and stable assignments polytope
Marco Schulze and Jürgen Zimmermann. Scheduling of underground mining processes
Dries Goossens and Frits Spieksma. Breaks, cuts, and patterns
B
Dirk Briskorn and Malte Fliedner. The train positioning problem
Stanley P.Y. Fung, Chung Keung Poon and Duncan K.W. Yung. Online Scheduling of Unit-Length Intervals on Parallel Machines
Clemens Thielen, Sven Krumke and Stephan Westphal. Interval Scheduling on Related Machines: Complexity and Online Algorithms
Denis Trystram, Frederic Wagner, Haifeng Xu and Guochuan Zhang. New Lower Bounds for Online Multi-threaded Paging Problem
C
Tanujit Dey, David Phillips and Patrick Steele. Minimizing predicted air travel delay
Yasmina Seddik, Christophe Gonzales and Safia Kedad-Sidhoum. Solving the one-machine scheduling problem with cumulative payoffs
Alexander Kozlov. To the conjecture on the minimum number of migrations in the optimal schedule for the Pm | pmtn(delay=d) | Cmax problem
Hesham Alfares and Ahmad Zaid. Particle swarm optimization algorithm for workforce job rotation scheduling
Friday, June 24
9:00 - 10:00 Invited talkRalf Borndörfer. Scheduling problems and algorithms in traffic and transport
10:40 - 11:25 Parallel presentations
A
Leah Epstein and Asaf Levin. Optimal robust algorithms for preemptive scheduling
Attila Benkő, Gyorgy Dósa and Xin Han. Reassignment models in online scheduling on two related machines
11:30 - 12:30 Plenary presentations
Rene Sitters. Efficient algorithms for average completion time scheduling
Nikhil Bansal and Kirk Pruhs. The Geometry of Scheduling
14:00 A bus to Prague