Blockbuster Inc., a chain of VHS, DVD, Blu-ray, and video game rental stores, has developed a highly specialized distribution network. The company maintains a single distribution center in which it receives products from suppliers, and processes and packs them for shipping to stores across the United States. The volumes of particular products and the number of different products shipped in a week have significant week-to-week volatility. Short lead times are typical because of supplier manufacturing delays and strict in-store due-date requirements. At the distribution center, processing and packing are scheduled through multiple processing departments that compete for use of shared merge conveyors and shared sortation systems. Blockbuster's general processing and packing goal is on-time delivery of products to stores while controlling costs.
In this paper, we describe the development and implementation of a mixed-integer programming model to schedule Blockbuster's short-range order-processing operations. Implemented beginning in January 2007, the model has helped Blockbuster to maintain timely shipping, reduce related labor and transportation costs, improve capacity utilization, and attain a better understanding of how to achieve further improvements. Blockbuster's structure, in which multiple processing departments compete for subsequent shared resources, such as merge conveyors and sortation systems, is common in other industries; therefore, we also discuss the relevance of this model to other organizations.