188宝金博页面版

Schedule robustness through Solve-and-Robustify:generating flexible schedules from different fixed-time solutionsNicola Policella, Amedeo Cesta and Angelo OddiPlanning & Scheduling TeamInstitutefor CognitiveScience and Technology - CNRRome, Italyname.surname@istc.cnr.itStephen F. SmithThe Robotics InstituteCarnegie Mellon UniversityPittsburgh,USAsfs@cs.cmu.eduAbstractIn previous works the authors have defined Solve-and-Robustify an original two-step procedure to generate flexiblesolutions,orpartial orderschedules,for schedulingproblems.The partition in two steps — first find a solution then makeitrobust — not only represents a way to generate flexible, ro-bust schedulesbut is also an alternative to achievegoodqual-ity solutions. Thispaperextendstheanalysisof thisparadigminvestigating the effects of using different start solutions as abaseline to generate partial order schedules. Two approachesare compared: the first based on the construction of flexibleschedules after performing an iterative improvement phasefocused on makespan optimization, the second that selectsthe best partial order schedule considering different fixed-time schedules as starting points. The paper experimentallyshowshow the characteristicsof the fixed-time solutionsmaylower the robustness of the final partial order schedules anddiscussesmotivations for such behavior.IntroductionIn previous works (Policella et al. 2004b; 2004a) these au-thors show how a two step procedure — find a solutionthenmake it robust — represents a way to generate flexible, ro-bustschedules and, toimprove thesolutionqualityinseveraldirections. Under this scheme, a feasible fixed-time sched-uleisgenerated instageone(inparticularanearlystarttimessolution is identifies), and then, in the second stage, a pro-cedure referred to as chaining is applied to transform thisfixed-time schedule into a Partial Order Schedule, orThe same works explain why alution.The common thread underlyingthe “chained” representa-tionof the schedule is the characteristic that activitieswhichrequire the same resource units are linked via precedenceconstraints into precedence chains.each constraintbecomes morethanjusta simpleprecedence.It also represents a producer-consumer relation, allowingeach activity to know the precise set of predecessors whichwill supply the units of resource it requires for execution. Inthis way, the resulting network of chains can be interpretedas a flow of resource units through the schedule; each timean activity terminates its execution, it passes its resource???.??? represents a robust so-Given this structure,Copyright cgence(www.aaai.org). All rights reserved.? 2005, American Association for Artificial Intelli-unit(s) on to its successors. It is clear that this representa-tion is robust if and only if there is temporal slack that al-lows chained activities to move “back and forth”. Conceptssimilartochaininghave alsobeen usedelsewhere: forexam-ple, the Transportation Network introduced in (Artigues &Roubellat 2000), and the Resource Flow Network describedin (Leus & Herroelen 2004) are based on equivalent struc-tural assumptions.This paper addresses an aspect not explored in previousworks: how different start schedules influence the wholeprocess of identifying partial order schedules. This analy-sis is presented here describing two different combinationsof a constraint-based solver with our best chaining algo-rithm from previous works: the first combination schemaconstructs flexible schedules after an iterative sampling op-timization procedure, while the second iterates both solveand robustify considering different fixed-time schedules asstarting points and selecting the best partial order schedulefound.The paper introduces first the basic concepts of schedulerobustness and Partial Order Schedules, then describes thetwo step approach tothen introduced by describing the broadened search proce-dures, an experimental evaluation and a detailed discussion.Some conclusions end the paper.??? synthesis. The new analysis isScheduling with Uncertainty and PartialOrder SchedulesThe usefulness ofschedules inmost practicalschedulingdo-mains is limited by their brittleness. Though a schedule of-fers thepotentialfora more optimizedexecution than wouldotherwise be obtained,it mustin factbe executed as plannedto achieve this potential. In practice this is generally madedifficultbyadynamic executionenvironment,where unfore-seen events quickly invalidate the schedule’s predictive as-sumptions and bring into question the continuingvalidityofthe schedules’s prescribed actions. The lifetime of a sched-ule tends to be very short, and hence its optimizing advan-tages are generallynotrealized. For instance, letus considerthe example in Fig. 1 that shows the allocation of three dif-ferent activities on a binary resource. According to quitecommon practice in scheduling, a solutionassociates an ex-act start and end time to each activity.