MAPSP 2013, 23rd - 28th June 2013, Pont à Mousson

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

Invited speakers
Important dates
Travel information
Alternative accommodation
Previous MAPSPs

This program is currently subject to modifications, please visit regularly this page before preparing your trip. An (optional) program will be proposed for the accompanying persons. Please contact us if you travel with children.

PDF version of the program

  • Sunday
    • Registration open
    • 20:00 Welcome buffet
  • Monday
    • 8:00 Registration open
    • 9:00-9:05 Opening remarks
    • 9:05-10:05 Invited Talk: Ola Svensson, Strong Convex Relaxations for Allocation Problems
    • 10:05-10:30 Break
    • 10:30-11:30 Tutorial 1: Thomas Rothvoss An introduction to the Lasserre Hierarchy in Approximation algorithms
    • 11:30-2:30 Lunch
    • 2:30-3:30 Plenary Talks:
      Elisabeth Gunther, Olaf Maurer, Nicole Megow and Andreas Wiese. Title: A New Approach to Online Scheduling: Approximating the Optimal Competitive Ratio
      Sungjin Im, Benjamin Moseley and Kirk Pruhs The Secret of Potential Functions: Breaking the Magician's Oath?
    • 3:30-3:45 Break
    • 3:45-4:55 Session 1:
      • Track A
        Vincenzo Bonifaci, Alberto Marchetti-Spaccamela, Sebastian Stiller and Andreas Wiese Deadline Scheduling of Jobs and Tasks in the Sporadic DAG Model
        Leah Epstein, Asaf Levin and Gerhard J. Woeginger Vertex cover meets multiprocessor scheduling
        Rodrigo Carrasco, Garud Iyengar and Clifford Stein Single Machine Scheduling with Job-Dependent Convex Cost and Arbitrary Precedence Constraints
      • Track B
        Alberto Marchetti-Spaccamela, Cyriel Rutten, Suzanne van der Ster and Andreas Wiese Assigning Sporadic Tasks to Unrelated Machines
        Ruben van der Zwaan, Nikhil Bansal, Suzanne van der Ster, Cyriel Rutten and Tjark Vredeveld Approximating real-time scheduling on identical machines
        Alexandra French, Zhishan Guo and Sanjoy Baruah Scheduling mixed-criticality workloads upon unreliable processors
      • Track C
        József Békési, Gábor Galambos, Michael Jung, Marcus Oswald and Gerhard Reinelt Exact Algorithms for the General Coupled Task Scheduling Problem Roman Capek, Lucie Buzková and Zdenek Hanzálek Constraint Programming and Evaluation Methods for Scheduling with Alternative Process Plans Stefan Kreter and Jurgen Zimmermann Mixed-integer linear programming formulations for the RCPSP/max with calendars
    • 4:55 -5:10 Break
    • 5:10 -6:20 Session 2
      • Track A
        Fidaa Abed and Chien-Chung Huang Preemptive coordination mechanisms for unrelated machines
        Jasper de Jong, Marc Uetz and Andreas Wombacher The (Sequential) Price of Anarchy for Throughput Scheduling
        Janardhan Kulkarni, Kamesh Munagala, Sungjin Im and Sayan Bhattacharya Coordination Mechanisms from (almost) all Scheduling Policies
      • Track B
        Mihai Burcea, Prudence W.H. Wong and Fencol C.C. Yung Improved Results on Online Dynamic Bin Packing
        Hongyang Sun and Rui Fan Improved Semi-Online Makespan Scheduling with a Reordering Buffer
        Jiri Sgall and Gerhard J. Woeginger Multiprocessor jobs, preemptive schedules, and one-competitive online algorithms
      • Track C
        Liliana Grigoriu Multiprocessor scheduling with fixed jobs or downtimes
        Anis Kooli and Mehdi Serairi An assignment based lower bound for the single machine with unequal release dates
        Safia Kedad-Sidhoum, Florence Monna, Gregory Mounie and Denis Trystram Approximation Algorithms for a Scheduling Problem on Multi-Cores with GPUs
    • Dinner
  • Tuesday
    • 9:00-10:00 Plenary Talks:
      Gyorgy Dosa and Jiri Sgall First Fit bin packing: A tight analysis
      Leah Epstein, Asaf Levin and Rob van Stee Unified approach to truthful scheduling on related machines
    • 10:00 -10:30 Break
    • 10:30 - 11:30 Tutorial 2 Viswanath Nagarajan Approximation algorithms for robust optimization
    • 11:30 - 2:30 Lunch
    • Social Event: guided tour of the historical center of Nancy, banquet at the City Hall of Nancy, the sound and lights show on Stanislas place
  • Wednesday
    • 9:00 -10:00 Invited Talk: Anupam Gupta Approximation Algorithms for Stochastic Packing Problems
    • 10:00- 10:30 Break
    • 10:30- 11:30 Tutorial 3 Klaus Jansen Efficient polynomial time approximation schemes
    • 11:30- 2:30 Lunch
    • 2:30- 3:30 Plenary Talks
      Marek Cygan, Fabrizio Grandoni and Monaldo Mastrolilli How to Sell Hyperedges: The Hypermatching Assignment Problem
      Ruben Hoeksma and Marc Uetz Two-Dimensional Optimal Mechanism Design for a Single Machine Scheduling Problem
    • 3:30-3:45 Break
    • 3:45- 4:55 Session 3
      • Track A
        Evripidis Bampis, Alexander Kononov, Dimitrios Letsios, Giorgio Lucarelli and Maxim Sviridenko Energy Efficient Multiprocessor Scheduling via Configuration LP
        Minming Li DVS scheduling algorithms for various models of processors: progress and open problems
        Peter Kling and Peter Pietrzyk Scheduling Profitably on Multiple Processors
      • Track B
        Martijn van Brink, Alexander Grigoriev and Tjark Vredeveld Express Delivery Problem
        Frans Schalekamp, Rene Sitters, Suzanne van der Ster, Leen Stougie, Victor Verdugo and Anke van Zuylen Split scheduling with uniform setup times
        Peter Brucker and Natalia Shakhlevich On General Methodology for Solving Inverse Scheduling Problems
      • Track C
        Bala Kalyanasundaram and Mahe Velauthapillai Establishing A Periodic Transmission Schedule in Wireless Sensor Network for Non-Uniform Transmission Case
        Aysegul Altindag and Ceyda Oguz Variable Neighborhood Search for Order Acceptance Scheduling Problem
        Eyjólfur Ingi Asgeirsson, Magnus M. Halldorsson, Pradipta Mitra, Joseph Foley, Helga Gudmundsdottir, Sveinn Fannar Kristjansson, Sindri Magnusson, Henning Ulfarsson and Ymir Vigfusson Distributed Scheduling for Data Aggregation in Wireless Networks
    • 4:55- 5:10 Break
    • 5:10- 6:20 Session 4
      • Track A
        Benjamin Moseley, Kirk Pruhs and Clifford Stein The Complexity of Scheduling for p-norms of Flow and Stretch
        Mordechai Shalom, Prudence W.H. Wong and Shmuel Zaks Interval Scheduling to Maximize Bandwidth Provision
        Nicole Megow and José Verschae Dual techniques for scheduling on a machine with varying speed
      • Track B
        Dorin Maxim, Liliana Cucu-Grosjean, Olivier Buffet, Luca Santinelli and Robert Davis Optimal Priority Assignment Algorithms for Probabilistic Real-Time Systems
        Robert Davis and Marko Bertogna Optimal FP Scheduling with Deferred Pre-emption
        Zdenek Hanzalek and Tomas Tunys On Non-Preemptive Mixed-Criticality Scheduling
      • Track C
        Eric Angel, Evripidis Bampis, Vincent Chau and Dimitrios Letsios Throughput Maximization for Speed-Scaling with Agreeable Deadlines
        Jude-Thaddeus Ojiaku, Daniel Thomas and Prudence W.H. Wong Energy-Efficient Flow Time Scheduling: An Experimental Study
        Antonios Antoniadis, Chien-Chung Huang, Sebastian Ott and Jose Verschae Profitable Scheduling with Energy Costs
    • Dinner
  • Thursday
    • 9:00- 10:00 Invited Talk: Magnus Halldorsson , Wireless scheduling
    • 10:00 - 10:30 Break
    • 10:30-11:30 Tutorial 4: Seffi Naor Submodular maximization: recent progress
    • 11:30-2:30 Lunch
    • 2:30- 3:30 Plenary Talks:
      Stefano Leonardi, Nicole Megow, Roman Rischke, Leen Stougie, Chaitanya Swamy and Jose Verschae Scheduling with time-varying cost: deterministic and stochastic models
      Deeparnab Chakrabarty and Sanjeev Khanna A Special Case of Restricted Assignment Makespan Minimization
    • 3:30 -3:45 Break
    • 3:45- 5:20 Session 5
      • Track A
        Leah Epstein, Lukasz Jez, Jiri Sgall and Rob van Stee Online interval scheduling on uniformly related machines
        Tulia Herrera and Cliff Stein Online scheduling for energy minimization with a constrained adversary
        Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Lukasz Jez, Jiri Sgall and Grzegorz Stachowiak Online Control Message Aggregation in Chain Networks
        Giampaolo Ferraro and Julian Mestre A Tight Analysis of the Longest Wait First Heuristic for Online Broadcast Scheduling
      • Track B
        Ilya Chernykh and Sergey Sevastyanov On the power of preemption in open shops
        Trivikram Dokka, Yves Crama and Frits Spieksma Approximation Algorithms for Multi-Dimensional Vector Assignment Problems
        Ehab Morsy Approximating the k-Splittable Capacitated Network Design Problem
        Marton Drotos, Peter Gyorgyi and Tamas Kis Approximation algorithms for machine scheduling with non-renewable resources
      • Track C
        Yakov Zinder, Samuel Walker and Claire Hanen The Worst-Case Performance of One Class of Scheduling Algorithms for Flexible Multiprocessor Tasks
        Morten Tiedemann and Stephan Westphal An LP-Based Heuristic for the Flexible Job Shop Scheduling Problem
        Agnès Le Roux, Odile Bellenguez-Morineau and Christelle Guéret Valid inequalities and dominance rules for speed-dating scheduling linear models
        Ammar Oulamara, Djamal Rebaine and Mehdi Serairi Open shop scheduling problem with time-dependent resource consumption
    • 5:30 Sport: soccer matches, tennis and hiking
    • Dinner
  • Friday
    • 9:00- 10:00 Plenary Talks
      Antonios Antoniadis and Chien-Chung Huang Non-Preemptive Speed Scaling
      José R. Correa, Victor Verdugo and José Verschae Approximation algorithms for scheduling split jobs with setup times
    • 10:00- 10:30 Break
    • 10:30-12:05 Session 6
      • Track A
        Ruben van der Zwaan, Sungjin Im and Viswanath Nagarajan Minimum Latency Submodular Cover
        Vitaly Strusevich and Hans Kellerer Approximation Schemes for Convex Positive Half-Product and Its Scheduling Applications
        Alexander Kononov Improved approximation algorithms for two routing open shop problems
        Tim Nonner and Maxim Sviridenko An Efficient Polynomial-Time Approximation Scheme for the Joint Replenishment Problem
      • Track B
        Alexander Souza and Matthias Hellwig Approximation Algorithms for Generalized and Variable-Sized Bin Covering
        Wim Vancroonenburg, Federico Della Croce, Dries Goossens and Frits Spieksma The Red-Blue Transportation Problem
        Philippe Baptiste and Nicolas Bonifas Generating redundant cumulative constraints to compute preemptive bounds
        David Bunde, Michael Bender, Cynthia Phillips, Vitus Leung and Samuel Mccauley Efficient Scheduling to Minimize Calibrations
      • Track C
        Abdoul Bitar, Stéphane Dauzère-Pérès and Claude Yugma A genetic algorithm for a parallel machine scheduling problem with auxiliary resources and sequence dependent setup times T'Kindt Vincent, Christophe Lenté and Mathieu Liedloff A Study of worst-case complexity for parallel machine scheduling problems based on an extension of the Sort & Search method Murat Firat, Dirk Briskorn, Stanislas Francfort and Alexandre Laugier A two-level optical FTTH network design problem Quang-Chieu Ta, Jean-Charles Billaut and Jean-Louis Bouquard Recovering beam search and Matheuristic algorithms for the F2||sum T_j scheduling problem
    • 12:05-2:00 Lunch
    • Conference Adjourns