The Navy's peacetime mission is "to conduct forward presence operations to help shape the strategic environment by deterring conflict, building interoperability, and by responding, as necessary, to fast breaking crises with the demonstration and application of credible combat power." (OPNAV INSTRUCTION 3501.316, February 1995) The ability to carry out this mission hinges on the Navy's ability to maintain ships and submarines forward deployed in regions where such crises may occur. The end of the Cold War and current budget constraints have caused a drawdown in the number of ships and submarines with which to provide forward presence. Coupled with the continued requirement to maintain a certain level of forward presence, this drawdown creates shortfalls when attempting to deploy ships or submarines to fill certain mission requirements. To minimize these shortfalls, this thesis formulates the problem of scheduling attack submarine deployments as an integer program. Due to its size and complexity, heuristic algorithms are developed to provide near-optimai solutions in a reasonable amount of time. In addition to providing near-optimal deployment schedules, results from the algorithms are also useful in evaluating changes in maintenance and operational policies.