Scheduling patrols using a hybrid integer programming/rule-based system approach

Summary form only given, as follows. Formal mathematical programming algorithms have been developed for many scheduling problems of interest to the maritime community, but computational complexity often restricts their use to disappointingly small problems. An interactive system which uses a rule base and advice from the scheduler to formulate constraints for an integer program is discussed. The interaction results in fixing the values of many decision variables, thus considerably reducing the size of the decision space, and consequently the computational burden. As a sample problem, the task of scheduling US Coast Guard Atlantic Area cutters is addressed. Some 30 ships are involved, with varying patrol lengths, maintenance and training requirements, and capabilities. The system illustrates the coupling of symbolic computing techniques with a high-level math programming language GAMS