Accession Number : ADA281990

Title :   Cyclic Scheduling with Spacing Constraints.

Descriptive Note : Doctoral thesis,

Corporate Author : AIR FORCE INST OF TECH WRIGHT-PATTERSON AFB OH

Personal Author(s) : Borsi, John J.

Report Date : 1994

Pagination or Media Count : 166

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.

Descriptors :   *AIRLIFT OPERATIONS, *SCHEDULING, ROUTING, MISSIONS, CYCLES, TRAVEL, DELAY.

Subject Categories : Logistics, Military Facilities and Supplies
      Military Operations, Strategy and Tactics

Distribution Statement : APPROVED FOR PUBLIC RELEASE