We develop methodological, mathematical, statistical, and computational approaches to constructing schedules of cancer screening that maximize the probability that by the time of primary tumor detection it has not yet metastasized. Solving this problem is based on a comprehensive mechanistic model of cancer progression. We apply the model with realistic parameters and the screening optimization methodology to mammographic screening for breast cancer within the American female population. We uncover some general patterns of optimal screening schedules. We show that optimization of screening regimens leads to a significant reduction in the probability of detecting breast cancer that has already disseminated. Copyright © 2012 John Wiley & Sons, Ltd.