Scheduling Coast Guard District Cutters

United States Coast Guard (USCG) districts schedule cutters 180 feet or less in length to weekly statuses (statuses is USCG jargon for assignments) from which they primarily respond to calls for search and rescue, law enforcement, and pollution control. The First Coast Guard District, based in Boston, has one of the largest scheduling problems: Each of 16 cutters is as-signed weekly to one of six statuses to ensure patrol coverage, enforce equitable distribution of patrols, and honor restrictions on consecutive cutter statuses. When we state this quarterly scheduling problem as an elastic mixed-integer linear program, we obtain face-valid schedules—superior to manually prepared schedules for all measures of effectiveness considered—within a few minutes on a personal computer. Initial acceptance of the model was hampered by disruptive schedule revisions that re-sulted from minor changes in input. Modifications to preserve run-to-run persistence of solutions have brought success. Semper Paratus —United States Coast less in length to weekly operational and Guard Motto.,., , ^^_ mamtenance statuses {statuses is USCG A ll 10 United States Coast Guard jargon for assignments) from which they (USCG) district commands face the primarily respond to calls for search and problem of scheduling cutters 180 feet or rescue, law enforcement, and pollution re