April-_1992 Rescheduling with Iterative Repair.pdf

= , NASA-TM-108119 z_ /A/ -_ 3- -7 z_7 /3d3_/ t /f Rescheduling with Iterative Repair MONTE ZWEBEN EUGENE DAVIS BRIAN DAUN MICHAEL DEALE AI RESEARCH BRANCrL MAIL STOP 269-2 NASA AMES RESEARCH CENTER MOFFETT FIELD, CA 94025, USA (NASA-TM-105119) ITERATIVE REPAIR ! I J J RESCHEOULING WITH N93-15288 (NASA) 17 p uncl .is G3/63 0135322 I__A Ames Research Cen_er T__ Artificial Intelligence Research Branch Technical Report FIA-D2-15 April-_1992 Rescheduling with Iterative Repair Monte Zweben Eugene Davis* Brian Daun t Michael Dealet NASA Ames Research Center M.S. 269-2 Moffett Field, California 94035 zweben@pIuto.arc.nasa.gov / i ff Abstract This paper presents a new approach to rescheduling called constraint- based iterative repair. This approach gives our system the ability to satisfy domain constraints, address optimization concerns, mini- mize perturbation to the original schedule, produce modified sched- ules quickly, and exhibits anytime behavior. The system begins with an initial, flawed schedule and then iteratively repairs constraint violations until a conflict-free schedule is produced. In an empirical demonstration, we vary the importance of minimizing perturbation and report how fast the system is able to resolve conflicts in a given time bound. We also show the anytime characteristics of the system. These experiments were performed within the domain of Space Shuttle ground processing. Function: Planning and Scheduling Domain: Space Shuttle Ground Processing Knowledge : Constraints *Recom Technologies ?Lockheed Artificial Intelligence Center t Lockheed Space Operations Company Introduction Space Shuttle ground processing encompasses the inspection, repair, and refurbishment of space shuttles in preparation for launch. During processing the Kennedy Space Center (KSC) flow management team frequently modifies the schedule in order to accommodate unanticipated events, such as lack of personnel availability, unexpected delays, and the need to repair newly discovered