Author name cluster

Laurence A. Kramer

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers

2 author rows

EAAI Journal 2008 Journal Article

Airlift mission monitoring and dynamic rescheduling

David E. Wilkins
Stephen F. Smith
Laurence A. Kramer
Thomas J. Lee
Timothy W. Rauenbusch

We describe the Flight Manager Assistant (FMA), a prototype system, designed to support real-time management of airlift operations at the USAF Air Mobility Command (AMC). In current practice, AMC flight managers are assigned to manage individual air missions. They tend to be overburdened with associated data monitoring and constraint checking, and generally react to detected problems in a local, myopic fashion. Consequently, decisions taken for one mission can often have deleterious effects on others. FMA combines two key capabilities for overcoming these problems: (1) intelligent monitoring of incoming information (for example, weather, airport operations, aircraft status) and recognition of those situations that require corrective action and (2) dynamic rescheduling of missions in response to detected problems, both to understand the global implications of changed circumstances and to determine appropriate rescheduling actions. FMA builds on two existing technologies: an execution-monitoring framework previously applied to small-unit operations and control of robots, and a dynamic scheduling tool that is transitioning into operational use in AMC's Tanker/Airlift Control Center. FMA's dynamic-mediation module provides for collaborative mission management by different planning and execution offices by structuring communication for decision making.

Details DOI

AAAI Conference 2007 Conference Paper

Understanding Performance Tradeoffs in Algorithms for Solving Oversubscribed Scheduling

Laurence A. Kramer

In recent years, planning and scheduling research has paid increasing attention to problems that involve resource oversubscription, where cumulative demand for resources outstrips their availability and some subset of goals or tasks must be excluded. Two basic classes of techniques to solve oversubscribed scheduling problems have emerged: searching directly in the space of possible schedules and searching in an alternative space of task permutations (by relying on a schedule builder to provide a mapping to schedule space). In some problem contexts, permutation-based search methods have been shown to outperform schedule-space search methods, while in others the opposite has been shown to be the case. We consider two techniques for which this behavior has been observed: TaskSwap (TS), a schedule-space repair search procedure, and Squeaky Wheel Optimization (SWO), a permutation-space scheduling procedure. We analyze the circumstances under which one can be expected to dominate the other. Starting from a real-world scheduling problem where SWO has been shown to outperform TS, we construct a series of problem instances that increasingly incorporate characteristics of a second real-world scheduling problem, where TS has been found to outperform SWO. Experimental results provide insights into when schedule-space methods and permutation-based methods may be most appropriate.

PDF Details

ICAPS Conference 2006 Conference Paper

Resource Contention Metrics for Oversubscribed Scheduling Problems

Laurence A. Kramer
Stephen F. Smith

We investigate a task insertion heuristic for oversubscribed scheduling problems, max-availability, that uses a simple estimate of resource contention to assign tasks to intervals expected to have the best worst case resource availability. Prior research in value and variable ordering heuristics for scheduling problems indicated that sophisticated, but more costly measures of resource contention can outperform simpler ones by more reliably pruning the search space. We demonstrate that for oversubscribed, priority-based problems where a feasible, optimal solution may not even exist, max-availability generates schedules of similar quality to other contention based heuristics with much less computational overhead.

Details

ICAPS Conference 2005 Conference Paper

Maximizing Availability: A Commitment Heuristic for Oversubscribed Scheduling Problems

Laurence A. Kramer
Stephen F. Smith

In this paper we reconsider a "task-swapping" procedure for improving schedules in the face of resource oversubscription. Prior work has demonstrated that use of a retraction heuristic to determine which tasks to rearrange in an existing schedule allows for addition of new tasks which would otherwise fail to be scheduled. The existing task swap procedure employs a variable ordering heuristic for task insertion that is the same as the retraction heuristic, but scored in the reverse. That is, the least constrained tasks are retracted, and of these the most constrained are committed first. Value selection for commitment is defaulted to a task’s earliest feasible start time. We have found that by applying a value selection heuristic, max-availability, to the choice of where to assignthe retracted tasks, both solution quality and runtime performance of task swap can be improved greatly. Max-availability considers resource contention for an unassigned task and places it where availability is predicted to be maximal over the range of that task. This heuristic is applicable not only in a repair context, but can also promote resource levelling in the context of constructive task allocation. Finally, we show that use of max-availability in task swapping promotes schedule stability when compared to the prior greedy task insertion policy.

Details

ICAPS Conference 2004 Conference Paper

Task Swapping for Schedule Improvement: A Broader Analysis

Laurence A. Kramer
Stephen F. Smith

In this paper we analyze and extend a recently developed "task-swapping procedure" for improving schedules in oversubscribed situations. In such situations, there are tasks which cannot be directly added to the current schedule without introducing capacity conflicts. A schedule is improved if one or more of these tasks can be feasibly included, and the goal of task swapping is to rearrange some portion of the current schedule to make this possible. Key to effective task swapping is an ability to exploit the scheduling flexibility inherent in the constraints associated with various scheduled tasks, and previous work has shown that the use of retraction heuristics that favor tasks with greater rescheduling flexibility can give rise to strong schedule improvement capabilities. We extend this work by developing and evaluating several improvements to the core task swapping procedure. We introduce three pruning techniques and show that each significantly improves computational efficiency while maintaining solution quality. We then investigate the possibility of improving the "end" solutions by stochastically exploring the "neighborhood" around them, and demonstrate that improved solutions are possible given the ability to spend additional time.

Details

IJCAI Conference 2003 Conference Paper

Maximizing Flexibility: A Retraction Heuristic for Oversubscribed Scheduling Problems

Laurence A. Kramer
Stephen E Smith

In this paper we consider the solution of scheduling problems that are inherently over-subscribed. In such problems, there are always more tasks to execute within a given time frame than available resource capacity will allow, and hence decisions must be made about which tasks should be included in the schedule and which should be excluded. We adopt a controlled, iterative repair search approach, and focus on improving the results of an initial priority-driven solution generation procedure. Central to our approach is a new retraction heuristic, termed max-flexibility, which is responsible for identifying which tasks to (temporarily) retract from the schedule for reassignment in an effort to incorporate additional tasks into the schedule. The max-flexibility heuristic chooses those tasks that have maximum flexibility for assignment within their feasible windows. We empirically evaluate the performance of max-flexibility using problem data and the basic scheduling procedure from a fielded airlift mission scheduling application. We show that it produces better improvement results than two contention-based retraction heuristics, including a variant of min-conflictsLMinton et al. , 1992], with significantly less search and computational cost.

PDF