Cyclic Scheduling with Spacing Constraints
Abstract
We have studied a vehicle routing and scheduling problem in which a cyclic schedule of airlift missions is required to provide evenly spaced customer service. This thesis presents results in two areas relating to our solution of this problem. First, we developed and tested a route-first/schedule-second heuristic. This approach is suitable for applications in which routing costs are the primary concern and the spacing requirement is not a hard constraint. The crucial element of this approach is the ability to schedule airlift missions so that the spacing requirement is satisfied. To accomplish this, we allow missions to be disrupted, either expediting or delaying mission stops compared to the standard time allowed for travel between consecutive mission stops. This scheduling problem is solved through a heuristic that requires the solution of a large number of assignment problems, which led to the second major area of our research. We then developed efficient algorithms for special cases of the assignment problem related to our scheduling problem. We determined that cost matrices defined by a convex function of linear displacement between sorted locations on a line have the Strong Monge Property. Based on this finding, we developed assignment algorithms with worst case time complexities comparable to sorting a list.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 28, 1994
- Accession Number
- ADA281990
Entities
People
- John J. Borsi
Organizations
- Air Force Institute of Technology