Scheduling Coast Guard district cutters

Abstract

Pacific areas, which are further subdivided into districts. Each district assigns cutters (ships) of length 180 feet or less into weekly statuses. The resulting cutter schedules reflect the district's level of readiness to respond to such emergencies as search and rescue, law enforcement, and pollution response. The First Coast Guard District has one of the largest scheduling problems, assigning each of 16 cutters to one of six weekly statuses. The First District's quarterly schedules must adhere to a number of guidelines which ensure patrol coverage, enforce equitable distribution of patrols, and restrict consecutive cutter statuses. This thesis formulates and solves the quarterly scheduling problem as an elastic mixed integer linear program. Face valid schedules, which are superior to actual schedules for all measures of effectiveness considered, are obtained within 15 minutes on a 486/33 Mhz personal computer using a commercially available integer programming solver.