MAPSP 2011, June 19 - 24, Nymburk, Czech Republic

10th Workshop on Models and Algorithms for Planning and Scheduling Problems

Invited speakers
Important dates
Local info
Previous MAPSPs

Accepted submissions

Plenary presentations (30 minutes, no parallel talks)

Vincenzo Bonifaci and Alberto Marchetti-Spaccamela. Feasibility Analysis of Sporadic Real-Time Multiprocessor Task Systems
Richard Cole, Jose Correa, Vasilis Gkatzelis, Vahab Mirrokni and Neil Olver. Inner Product Spaces for MinSum Coordination  Mechanisms
Rene Sitters. Efficient algorithms for average completion time scheduling
Elisabeth Günther, Marco Lübbecke and Rolf Möhring. Challenges in Scheduling when Planning the Ship Traffic on the Kiel Canal
Nikhil Bansal and Kirk Pruhs. The Geometry of Scheduling
Heiko Roeglin, Cyriel Rutten and Tjark Vredeveld. Smoothed performance guarantees of local optima for multiprocessor scheduling
Kirk Pruhs and Clifford Stein. How To Schedule When You Have To Buy Your Energy
Tim Nonner. Clique Clustering yields a PTAS for max-Coloring Interval Graphs
Natalia Shakhlevich. Divisible Load Scheduling to Minimize the Computation Time and Cost
Alexander Souza, Antonios Antoniadis, Falk Hüffner, Pascal Lenzner and Carsten Moldenhauer. Balanced Interval Coloring

Regular contributions (20 minutes, in 3 parallel tracks)

Robert Davis. Quantifying the Sub-optimality of Uniprocessor Fixed Priority Scheduling
Joanna Berlinska and Maciej Drozdowski. Scheduling and performance of divisible MapReduce applications
Fabian Kuhn and Monaldo Mastrolilli. Vertex Cover in Graphs with  Locally Few Colors and Precedence Constrained Scheduling with Few Predecessors
Dries Goossens and Frits Spieksma. Breaks, cuts, and patterns
Aldar Dugarzhapov and Alexander Kononov. An exact polynomial time algorithm for the preemptive mixed shop problem with two unit operations per job
Sleman Saliba, Iiro Harjunkoski and Matteo Biondi. Production Optimization and Scheduling in a Steel Plant: Hot Rolling Mill
José Verschae and Andreas Wiese. On the Configuration-LP for Scheduling on Unrelated Machines
Clemens Thielen, Sven Krumke and Stephan Westphal. Interval Scheduling on Related Machines: Complexity and Online Algorithms
Ruben Hoeksma and Marc Uetz. The Price of Anarchy for Related Machine Scheduling
Marco Schulze and Jürgen Zimmermann. Scheduling of underground mining processes
Eyjólfur Ingi Ásgeirsson and Pradipta Mitra. Performance of Distributed Game Theoretic Algorithms for Single Slot Scheduling in Wireless Networks
Klaus Jansen, Lars Prädel, Ulrich M. Schwarz and Ola Svensson. Faster approximation algorithms for scheduling with fixed jobs
Christophe Lenté, Mathieu Liedloff, Ameur Soukhal and T'Kindt Vincent. Exponential-time algorithms for scheduling problems
Sofie Coene and Frits Spieksma. The lockmaster's problem
Marjan Van Den Akker, Roland Geraerts, Han Hoogeveen and Corien Prins. Path planning in games
TomᚠEbenlendr and Jiøí Sgall. A lower bound on deterministic online algorithms for scheduling on related machines without preemption
Andrei M. Bandalouski, Mikhail Y. Kovalyov and Uladzimir A. Pashkevich. Model and algorithms for a problem of scheduling touristic services
Vitaly Strusevich and Kabir Rustigi. Enchanced models of single machine scheduling with a deterioration effect and maintenance activities
Marin Bougeret, Pierre-Francois Dutot and Denis Trystram. Using oracles for the design of efficient approximation algorithms
Ralf Borndörfer, Guillaume Sagnol and Elmar Swarat. An Integrated Vehicle Routing and Duty Roster Planning of Toll Control Inspectors
Sebastián Marbán, Cyriel Rutten and Tjark Vredeveld. Learning in stochastic machine scheduling
Sheng Yu, Prudence W.H. Wong and Yinfeng Xu. Online Scheduling of Linear Deteriorating Jobs on Parallel Machines
Vincenzo Bonifaci, Gianlorenzo D'Angelo, Alberto Marchetti-Spaccamela, Suzanne Van Der Ster and Leen Stougie. Mixed-criticality scheduling of sporadic task systems
Dirk Briskorn and Malte Fliedner. The train positioning problem
Trivikram Dokka, Ioannis Mourtos and Frits Spieksma. Fast separation algorithms for three-index assignment problems
Sergey Sevastyanov and Bertrand M.T. Lin. Efficient enumeration of optimal and approximate solutions of the two-machine flow-shop problem
Jessica Chang, Hal Gabow and Samir Khuller. Scheduling Jobs in Parallel for Energy Savings
Kan Fang, Nelson Uhan, Fu Zhao and John Sutherland. Flow Shop Scheduling for Sustainable Manufacturing
Denis Trystram, Frederic Wagner, Haifeng Xu and Guochuan Zhang. New Lower Bounds for Online Multi-threaded Paging Problem
Ammar Oulamara and Ameur Soukhal. Scheduling serial batching machine with two competitive agents
Leah Epstein and Asaf Levin. An AFPTAS for due date scheduling with related machines of general costs
Anand S, Naveen Garg and Nicole Megow. Meeting deadlines: How much speed suffices?
Csanad Imreh and Tamas Nemeth. Parameter learning in online scheduling algorithms
Wei Yu and Guochuan Zhang. Improved approximation algorithms for routing shop scheduling
Bastian Bludau. A two-machine flow shop problem consisting of a discrete processor and a batch processor under uncertainty
Gurulingesh Raravi, Björn Andersson and Konstantinos Bletsas. Intra-Type Migrative Scheduling of Implicit-Deadline Sporadic Tasks on Two-Type Heterogeneous Multiprocessor
Jason A. D. Atkin, Edmund K. Burke and Stefan Ravizza. A Statistical Approach for Taxi Time Estimation at London Heathrow Airport
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
Mohamed Marouf, Laurent George and Yves Sorel. Schedulability analysis for a combination of preemptive strict periodic and sporadic tasks
Neil Dobbs, Tomasz Nowicki, Maxim Sviridenko and Grzegorz Swirszcz. Approximating the Joint Replenishment Problem
Philippe Thierry, Laurent George and Jean-François Hermant. Real-time scheduling analysis for ARINC-based virtualized systems
Ruslan Sadykov and Francois Vanderbeck. Machine scheduling by column-and-row generation on the time-indexed formulation
Attila Benkõ, Gyorgy Dósa and Xin Han. Reassignment models in online scheduling on two related machines
Leah Epstein and Asaf Levin. Optimal robust algorithms for preemptive scheduling
Grzegorz Pawlak, Mateusz Cichenski, Mateusz Jarus and Slawomir Walkowski. The road traffic model for the car factory logistics
Rodrigo Carrasco, Garud Iyengar and Clifford Stein. Energy aware scheduling: minimizing total energy cost and completion time by α-points and α-speeds
Maciej Machowiak, Jan Wêglarz, Mikhail Y. Kovalyov and M.S. Barketau. Scheduling malleable tasks with arbitrary processing speed functions
£ukasz Je¿. One to Rule Them All: a General Randomized Algorithm for Buffer Management with Bounded Delay
Thierry Garaix, Christian Artigues and Cyril Briand. Fast minimum float computation in activity networks under interval uncertainty
Liliana Cucu-Grosjean. Probabilistic analysis of periodic real-time tasks with random execution times on identical processors
Michael Wagner. Online Lot-Sizing Problems with Ordering, Holding and Shortage Costs
Tao Li and Joel Wein. Allocating Resources in Clouds of Game Servers
Fei Li. A Better Memoryless Online Algorithm for FIFO Buffering Packets with Two Values
Andreas Schranzhofer, Jian-Jia Chen and Lothar Thiele. Timing Predictability for Resource Sharing Multicore Systems - Challenges and Open Problems
Yasmina Seddik, Christophe Gonzales and Safia Kedad-Sidhoum. Solving the one-machine scheduling problem with cumulative payoffs
Roman Èapek, Pøemysl Šùcha and Zdenìk Hanzálek. Scheduling with Alternative Process Plans and the Total Weighted Tardiness Criterion
TomᚠZajíèek and Premysl Sucha. Accelerating a Flow Shop Scheduling Algorithm on the GPU
Zdenek Baumelt, Premysl Sucha and Zdenek Hanzalek. A Genetic Algorithm for A Nurse Rerostering Problem
Stefan Heinz and Jens Schulz. Explanation Algorithms for Cumulative Scheduling
Hesham Alfares and Ahmad Zaid. Particle swarm optimization algorithm for workforce job rotation scheduling
Zdenek Hanzalek, Claire Hanen and Premysl Sucha. Cyclic Scheduling - New Application and Concept of Core Precedences
Alexander Grigoriev, Alexander Kononov and Maxim Sviridenko. Logarithmic-approximations for the relocation problem
Murat Firat, Cor Hurkens and Gerhard Woeginger. Optimal planning in vehicle refueling problem with limited resources
Cor Hurkens, Murat Firat and Alexandre Laugier. Stability in multi-skill workforce assignments: complexity analysis and stable assignments polytope
Stanley P.Y. Fung, Chung Keung Poon and Duncan K.W. Yung. Online Scheduling of Unit-Length Intervals on Parallel Machines
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
Leah Epstein and Elena Kleiman. On the quality and complexity of Pareto equilibria in the Job Scheduling Game
Enrico Bini. The problem of mapping real-time applications over multiple machines
Dvir Shabtay, Moshe Kaspi and Liron Yedidsion. Complexity analysis of an assignment problem with controllable assignment costs
Hana Rudová and Pavel Troubil. Media Streams Planning
Frederic Guinand, Amine Mahjoub and Eric Sanlaville. M machine scheduling under uncertainties on machine availabilities
Tanujit Dey, David Phillips and Patrick Steele. Minimizing predicted air travel delay
Florian Dahms, Katharina Beygang and Sven O. Krumke. Online algorithms and bounds for the Train Marshalling Problem
Alexander Kozlov. To the conjecture on the minimum number of migrations in the optimal schedule for the Pm | pmtn(delay=d) | Cmax problem