Sponzors
DIMATIA
Program committee Organizing committee
Nikhil Bansal, IBM Watson Research Center Anna Koteˇsovcov´a Sanjoy Baruah, University of North Carolina Jana Kratochv´ılov´a Christoph D¨urr, Ecole Polytechnique Duˇsan Knop Leah Epstein, University of Haifa Marek Krˇc´al
Monaldo Mastrolilli, IDSIA Ondˇrej Pangr´ac
Rolf M¨ohring, Technische Universit¨at Berlin (chair) Tom´aˇs Ebenlendr Chris Potts, University of Southampton Ondˇrej Zaj´ıˇcek Andreas Schulz, Massachusetts Institute of Technology Tom´aˇs Dzetkuliˇc Jiˇr´ı Sgall, Charles University (cochair) Jiˇr´ı Sgall (chair) Frits Spieksma, K. U. Leuven
Maxim Sviridenko, IBM Watson Research Center Steef van de Velde, Erasmus University Rotterdam Gerhard Woeginger, Technische Universiteit Eindhoven Guochuan Zhang, Zhejiang University
Preface
This volume contains abstracts of talks presented at the 10th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2011), held from June 19 to June 24, 2011, in Nymburk, Czech Republic.
MAPSP is a biennial workshop dedicated to all theoretical and practical aspects of scheduling, planning, and timetabling. Previous MAPSP meetings have been held in Menaggio, Italy (1993), Wernigerode, Germany (1995), Cambridge, UK (1997), Renesse, Netherlands (1999), Aussois, France (2001), Aussois, France (2003), Siena, Italy (2005), Istanbul, Turkey (2007), and Kerkrade, Netherlands (2009).
The abstracts in this volume are: 5 invited talks by Yossi Azar, Bert Zwart, Roman Bart´ak, David Shmoys, and Ralf Bornd¨orfer plus 81 contributed talks chosen out of 88 submissions. Of these 81 contributed talks, 10 were chosen as plenary talks and the remaining 71 were split into three parallel tracks. Each submission was reviewed by at least three program committee members.
We thank to all sponsors of MAPSP 2011. Sponsors include the company Gurobi Optimization (http://www.gurobi.com), the research center DIMATIA Charles University (http://dimatia.mff.cuni.cz), and Czech research grants MSM0021620838, IAA100190902 and ITI-1M0545 (http://iti.mff.cuni.cz).
We are very grateful to the members of the program committee, external referees, and the members of the organizing committee. Special thanks go to Ondˇrej Pangr´ac for de- signing and maintaining the website, to Marek Krˇc´al and Duˇsan Knop for preparing this booklet, to Jan Kratochv´ıl Jr. for designing the poster, and to Sebastian Stiller for de- signing the MAPSP logo. Most of all, we thank Conforg, s.r.o. (http://www.conforg.cz) – Anna Kotˇeˇsovcov´a and Jana Kratochv´ılov´a – for running all the local arrangements and registration.
June 2011
Rolf M¨ohring Jiˇr´ı Sgall
Mo nda y Mo rni ng
9:10 – 10:10Invitedspeaker: YossiAzar Fastapproximationalgorithmsforsubmodularoptimizationproblems[p.1] TrackATrackBTrackC 10:50 – 11:10
FabianKuhnandMonaldoMastrolilliShengYu,PrudenceW.H.Wongand YinfengXuStefanHeinzandJensSchulz VertexCoverinGraphswithLocallyFew ColorsandPrecedenceConstrainedSchedul- ingwithFewPredecessors[p.49]
OnlineSchedulingofLinearDeteriorating JobsonParallelMachines[p.58]ExplanationAlgorithmsforCumulative Scheduling[p.67] 11:15 – 11:35
AndreasSchranzhofer,Jian-JiaChenand LotharThieleJasonA.D.Atkin,EdmundK.Burkeand StefanRavizzaZdenˇekBaumelt,Pˇremysl
ˇ S˚uchaand ZdenˇekHanz´alek TimingPredictabilityforResourceSharing MulticoreSystems-ChallengesandOpen Problems[p.52]
AStatisticalApproachforTaxiTimeEsti- mationatLondonHeathrowAirport[p.61]AGeneticAlgorithmforANurseReroster- ingProblem[p.70] 11:40 – 12:00
RuslanSadykovandFran¸coisVanderbeckCsan´adImrehandTam´asN´emethMarjanvandenAkker,RolandGeraerts, HanHoogeveenandCorienPrins Machineschedulingbycolumn-and-rowgen- erationonthetime-indexedformulation [p.55]
Parameterlearninginonlineschedulingal- gorithms[p.64]Pathplanningingames[p.73]
Mo nda y A fter no o n
15:30 – 16:00Plenarytalk: VincenzoBonifaciandAlbertoMarchetti-Spaccamela FeasibilityAnalysisofSporadicReal-TimeMultiprocessorTaskSystems[p.20] 16:00 – 16:30
Plenarytalk: ElisabethG¨unther,MarcoL¨ubbeckeandRolfM¨ohring ChallengesinSchedulingwhenPlanningtheShipTrafficontheKielCanal[p.23] TrackATrackBTrackC 16:45 – 17:05
ChristopheLent´e,MathieuLiedloff,Ameur SoukhalandVincentT’KindtFlorianDahms,KatharinaBeygangand SvenO.KrumkeMohamedMarouf,LaurentGeorgeand YvesSorel Exponential-timealgorithmsforscheduling problems[p.76]OnlinealgorithmsandboundsfortheTrain MarshallingProblem[p.88]Schedulabilityanalysisforacombinationof preemptivestrictperiodictasksandsporadic tasks[p.100] 17:10 – 17:30 VitalyStrusevichandKabirRustogiSofieCoeneandFritsSpieksmaEnricoBini Enchancedmodelsofsinglemachine schedulingwithadeteriorationeffectand maintenanceactivities[p.79]
Thelockmaster’sproblem[p.91]Mappingreal-timeapplicationsovermulti- processors[p.103] 17:35 – 17:55
Tom´aˇsEbenlendrandJiˇr´ıSgallWeiYuandGuochuanZhangPhilippeThierry,LaurentGeorgeand Jean-Fran¸coisHermant Alowerboundondeterministiconlineal- gorithmsforschedulingonrelatedmachines withoutpreemption[p.82]
Improvedapproximationalgorithmsfor routingshopscheduling[p.94]Real-timeschedulinganalysisforARINC- basedvirtualizedsystems[p.106] 18:00 – 18:20
LukaszJe˙zGrzegorzPawlak,MateuszCichenski, MateuszJarusandSlawomirWalkowskiLilianaCucu-Grosjean OnetoRuleThemAll:aGeneralRandom- izedAlgorithmforBufferManagementwith BoundedDelay[p.85]
Theroadtrafficmodelforthecarfactory logistics[p.97]Probabilisticanalysisofperiodicreal-time taskswithrandomexecutiontimesoniden- ticalprocessors[p.110]
T ue sda y Mo rni ng
9:00 – 10:00Invitedspeaker: BertZwart Schedulingandqueueuing:Optimalityunderrareeventsandheavyloads[p.4] TrackATrackBTrackC 10:40 – 11:00
Sebasti´anMarb´an,CyrielRuttenand TjarkVredeveldMarinBougeret,Pierre-FrancoisDutot andDenisTrystramSt´ephaneDauz`ere-P´er`es,SadiaAzem andRiadAggoune Learninginstochasticmachinescheduling [p.113]Usingoraclesforthedesignofefficientap- proximationalgorithms[p.125]AColumnGenerationApproachfortheJob- ShopSchedulingProblemwithAvailability Constraints[p.137] 11:05 – 11:25 RodrigoCarrasco,GarudIyengarand CliffordSteinJos´eVerschaeandAndreasWieseBastianBludauandKarl-HeinzK¨ufer Energyawarescheduling:minimizingtotal energycostandcompletiontimebyα-points andα-speeds[p.116]
OntheConfiguration-LPforSchedulingon UnrelatedMachines[p.128]Atwo-machineflowshopproblemconsisting ofadiscreteprocessorandabatchprocessor underuncertainty[p.140] 11:30 – 11:50
S.Anand,NaveenGargandNicole MegowJessicaChang,HalGabowandSamir KhullerTom´aˇsZaj´ıˇcekandPˇremysl
ˇ S˚ucha Meetingdeadlines:Howmuchspeedsuf-SchedulingJobsinParallelforEnergySav-AcceleratingaFlowShopSchedulingAlgo- fices?[p.119]ings[p.131]rithmontheGPU[p.143] 11:55 – 12:15
S.Baruah,V.Bonifaci,G.D’Angelo,H.Li, A.Marchetti-Spaccamela,N.MegowandL. Stougie MuratFırat,CorHurkensandGerhard WoegingerM.S.Barketau,M.Y.Kovalyov,Maciej MachowiakandJ.W¸eglarz Mixed-criticalityscheduling[p.122]Vehiclerefuelingwithlimitedresources [p.134]Schedulingmalleabletaskswitharbitrary processingspeedfunctions[p.145]
T ue sda y A ft er no o n
15:30 – 16:00Plenarytalk: KirkPruhsandCliffordStein HowToScheduleWhenYouHaveToBuyYourEnergy[p.26] 16:00 – 16:30
Plenarytalk: RichardCole,Jos´eCorrea,VasilisGkatzelis,VahabMirrokniandNeilOlver InnerProductSpacesforMinSumCoordinationMechanisms[p.29] TrackATrackBTrackC 16:45 – 17:05
LeahEpsteinandElenaKleimanTaoLiandJoelWeinKarinTh¨ornblad,MichaelPatriksson, Ann-BrithStr¨om
bergandTorgnyAlmgren OnthequalityandcomplexityofPareto equilibriaintheJobSchedulingGame [p.148]
AllocatingResourcesinCloudsofGame Servers[p.159]Mathematicalmodellingofarealflexiblejob shopinaeroenginecomponentmanufactur- ing[p.171] 17:10 – 17:30
RubenHoeksmaandMarcUetzJoannaBerli´nskaandMaciejDrozdowskiAldarDugarzhapovandAlexander Kononov ThePriceofAnarchyforRelatedMachine Scheduling[p.151]Schedulingandperformanceofdivisible MapReduceapplications[p.162]Anexactpolynomialtimealgorithmforthe preemptivemixedshopproblemwithtwo unitoperationsperjob[p.174] 17:35 – 17:55
Eyj´olfurIngi
´ As geirssonandPradipta MitraZdenˇekHanz´alek,ClaireHanenandPˇre- mysl
SergeySevastyanovandBertrandM.T. ˇ S˚uchaLin PerformanceofDistributedGameTheoretic AlgorithmsforSingleSlotSchedulingin WirelessNetworks[p.153]
CyclicScheduling-NewApplicationand ConceptofCorePrecedences[p.165]Efficientenumerationofoptimalandap- proximatesolutionsofthetwo-machine flow-shopproblem[p.177] 18:00 – 18:20
ThierryGaraix,ChristianArtiguesand CyrilBriandKanFang,NelsonUhan,FuZhaoand JohnSutherlandRoman ˇ Capek,Pˇremysl
ˇ S˚uchaand ZdenˇekHanz´alek FastminimumfloatcomputationinactivityFlowShopSchedulingforSustainableMan-SchedulingwithAlternativeProcessPlans networksunderintervaluncertainty[p.156]ufacturing[p.168]andtheTotalWeightedTardinessCriterion [p.180]
W edne sda y
9:00 – 10:00Invitedspeaker: RomanBart´ak ModellingandSolvingSchedulingProblemsusingConstraintProgramming[p.8] 10:40 – 11:10
Plenarytalk: AlexanderSouza,AntoniosAntoniadis,FalkH¨uffner,PascalLenznerandCarstenMoldenhauer BalancedIntervalColoring[p.32] 11:10 – 11:40 Plenarytalk: TimNonner CliqueClusteringyieldsaPTASformax-ColoringIntervalGraphs[p.35]
Th ur sda y M or ning
9:00 – 10:00Invitedspeaker: DavidShmoys StrongLPFormulationsandPrimal-DualApproximationAlgorithms[p.15] TrackATrackBTrackC 10:40 – 11:00
LeahEpsteinandAsafLevinRobertDavisAmmarOulamaraandAmeurSoukhal AnAFPTASforduedateschedulingwith relatedmachinesofgeneralcosts[p.183]QuantifyingtheSub-optimalityofUnipro- cessorFixedPriorityScheduling[p.195]Schedulingserialbatchingmachinewithtwo competitiveagents[p.207] 11:05 – 11:25
KlausJansen,LarsP
r¨ad el,UlrichM. SchwarzandOlaSvenssonGurulingeshRaravi,B j¨or
nAndersson andKonstantinosBletsasFr´ed´ericGuinand,AmineMahjouband EricSanlaville Fasterapproximationalgorithmsfor schedulingwithfixedjobs[p.186]Intra-TypeMigrativeSchedulingofImplicit- DeadlineSporadicTasksonTwo-TypeHet- erogeneousMultiprocessor[p.198]
Mmachineschedulingunderuncertainties onmachineavailabilities[p.210] 11:30 – 11:50
AlexanderGrigoriev,Alexander KononovandMaximSviridenkoSlemanSaliba,IiroHarjunkoskiandMat- teoBiondiHanaRudov´aandPavelTroubil Logarithmic-approximationsforthereloca- tionproblem[p.189]ProductionOptimizationandSchedulingin aSteelPlant:HotRollingMill[p.201]MediaStreamsPlanning[p.213] 11:55 – 12:15 NeilDobbs,TomaszNowicki,Maxim SviridenkoandGrzegorzSwirszczVincenzoBonifaci,Gianlorenzo D’Angelo,AlbertoMarchetti-Spaccamela, SuzannevanderSterandLeenStougie TrivikramDokka,IoannisMourtosand FritsSpieksma ApproximatingtheJointReplenishment Problem[p.192]Mixed-criticalityschedulingofsporadictask systems[p.204]Fastseparationalgorithmsforthree-index assignmentproblems[p.216]
Th ur sda y A fter no o n
15:30 – 16:00Plenarytalk: TobiasBrunsch,HeikoRoeglin,CyrielRuttenandTjarkVredeveld Smoothedperformanceguaranteesoflocaloptimaformultiprocessorscheduling[p.38] 16:00 – 16:30
Plenarytalk: NataliaShakhlevich DivisibleLoadSchedulingtoMinimizetheComputationTimeandCost[p.41] TrackATrackBTrackC 16:45 – 17:05
RalfBornd¨orfer,GuillaumeSagnolandEl- marSwaratDirkBriskornandMalteFliednerTanujitDey,DavidPhillipsandPatrick Steele AnIntegratedVehicleRoutingandDuty RosterPlanningofTollControlInspectors [p.219]
Thetrainpositioningproblem[p.231]Minimizingpredictedairtraveldelay [p.242] 17:10 – 17:30
CorHurkens,MuratFıratandAlexandre LaugierStanleyP.Y.Fung,ChungKeungPoon andDuncanK.W.YungYasminaSeddik,ChristopheGonzales andSafiaKedad-Sidhoum Stabilityinmulti-skillworkforceassign- ments:complexityanalysisandstableas- signmentspolytope[p.222]
OnlineSchedulingofUnit-LengthIntervals onParallelMachines[p.233]Solvingtheone-machineschedulingproblem withcumulativepayoffs[p.245] 17:35 – 17:55
MarcoSchulzeandJ¨urgenZimmermannClemensThielen,SvenKrumkeand StephanWestphalAlexanderKozlov Schedulingofundergroundminingprocesses [p.225]IntervalSchedulingonRelatedMachines: ComplexityandOnlineAlgorithms[p.236]Totheconjectureontheminimumnumber ofmigrationsintheoptimalschedulefor thePm|pmtn(delay=d)|Cmaxproblem [p.248] 18:00 – 18:20 DriesGoossensandFritsSpieksmaDenisTrystram,Fr´ed´ericWagner, HaifengXuandGuochuanZhangHeshamAlfaresandAhmadZaid Breaks,cuts,andpatterns[p.228]NewLowerBoundsforOnlineMulti- threadedPagingProblem[p.239]Particleswarmoptimizationalgorithmfor workforcejobrotationscheduling[p.250]
F r ida y
9:00 – 10:00Invitedspeaker: RalfBornd¨orfer Schedulingproblemsandalgorithmsintrafficandtransport[p.17] TrackATrackBTrackC 10:40 – 11:00
LeahEpsteinandAsafLevin Optimalrobustalgorithmsforpreemptive scheduling[p.253] 11:05 – 11:25
AttilaBenk˝o,Gy¨orgyD´osaandXinHan Reassignmentmodelsinonlinescheduling ontworelatedmachines[p.256] 11:30 – 12:00
Plenarytalk: ReneSitters Efficientalgorithmsforaveragecompletiontimescheduling[p.44] 12:00 – 12:30 Plenarytalk: NikhilBansalandKirkPruhs TheGeometryofScheduling[p.46]
Table of contents
Invited Talks
Yossi Azar. . . 1 Fast approximation algorithms for submodular optimization problems
Bert Zwart . . . 4 Scheduling and queueuing: Optimality under rare events and heavy loads
Roman Bart´ak . . . 8 Modelling and Solving Scheduling Problems using Constraint Programming
David B. Shmoys . . . 15 Strong LP Formulations and Primal-Dual Approximation Algorithms
Ralf Bornd¨orfer . . . 17 Scheduling problems and algorithms in traffic and transport
Plenary Talks
Vincenzo Bonifaci, Alberto Marchetti-Spaccamela . . . 20 Feasibility Analysis of Sporadic Real-Time Multiprocessor Task Systems
Elisabeth G¨unther, Marco E. L¨ubbecke, Rolf H. M¨ohring . . . 23 Challenges in Scheduling when Planning the Ship Traffic on the Kiel Canal
Kirk Pruhs, Cliff Stein . . . 26 How To Schedule When You Have To Buy Your Energy
Richard Cole, Jos´e R. Correa, Vasilis Gkatzelis, Vahab Mirrokni, Neil Olver . . 29 Inner Product Spaces for MinSum Coordination Mechanisms
Antonios Antoniadis, Falk H¨uffner, Pascal Lenzner, Carsten Moldenhauer,
Alexander Souza . . . 32 Balanced Interval Coloring
Tim Nonner. . . 35 Clique Clustering yields a PTAS for max-Coloring Interval Graphs
Tobias Brunsch, Heiko R¨oglin,Cyriel Rutten, Tjark Vredeveld . . . 38 Smoothed performance guarantees of local optima for multiprocessor scheduling
Natalia V. Shakhlevich. . . 41 Divisible Load Scheduling to Minimize the Computation Time and Cost
Ren´e Sitters . . . 44 Efficient algorithms for average completion time scheduling
Nikhil Bansal,Kirk Pruhs . . . 46 The Geometry of Scheduling
Regular Talks
Fabian Kuhn,Monaldo Mastrolilli. . . 49 Vertex Cover in Graphs with Locally Few Colors and Precedence Constrained Scheduling with Few Predecessors
Andreas Schranzhofer,Jian-Jia Chen, Lothar Thiele . . . 52 Timing Predictability for Resource Sharing Multicore Systems - Challenges and Open Problems
Ruslan Sadykov, Fran¸cois Vanderbeck . . . 55 Machine scheduling by column-and-row generation on the time-indexed formulation Sheng Yu,Prudence W. H. Wong, Yinfeng Xu . . . 58 Online Scheduling of Linear Deteriorating Jobs on Parallel Machines
Jason A. D. Atkin, Edmund K. Burke,Stefan Ravizza . . . 61 A Statistical Approach for Taxi Time Estimation at London Heathrow Airport
Csan´ad Imreh, Tam´as N´emeth . . . 64 Parameter learning in online scheduling algorithms
Stefan Heinz,Jens Schulz . . . 67 Explanation Algorithms for Cumulative Scheduling
Zdenˇek B¨aumelt, Pˇremysl ˇS˚ucha, Zdenˇek Hanz´alek . . . 70 A Genetic Algorithm for A Nurse Rerostering Problem
Marjan van den Akker, Roland Geraerts,Han Hoogeveen, Corien Prins . . . 73 Path planning in games
Christophe Lent´e, Mathieu Liedloff, Ameur Soukhal,Vincent T’kindt . . . 76 Exponential-time algorithms for scheduling problems
Vitaly A. Strusevich, Kabir Rustogi . . . 79 Enchanced models of single machine scheduling with a deterioration effect and mainte- nance activities
Tom´aˇs Ebenlendr, Jiˇr´ı Sgall . . . 82 A lower bound on deterministic online algorithms for scheduling on related machines without preemption.
Lukasz Je ˙z. . . 85 One to Rule Them All: a General Randomized Algorithm for Buffer Management with Bounded Delay
