A tire production scheduling system for Bridgestone/Firestone off-the-road

We describe a scheduling system for the curing operation at Bridgestone/Firestone Off-The-Road (BFOR), a manufacturer of large tires for heavy off-the-road machines such as trucks, tractors, and earthmoving equipment used in the construction, lumber, and mining industries. The huge tires, having different priorities, are built in molds and put into heaters for the curing process. The problem is to find a feasible assignment of tires to molds and molds to heaters to achieve a maximum total priority. Our system produces about 7% more tires per shift compared to the previous manual way of developing schedules and moves the company toward its goal of quick response manufacturing with low inventories. The core algorithm is a column generation procedure to produce a production schedule for one work shift. This approach is then used in a ‘rolling horizon’ fashion. The size of the problem posed several computational challenges. Computational efficiencies come from (1) a dramatic effort to eliminate alternative solutions up front in an aggregation preprocessor, (2) considering the most ‘interesting’ tires to be scheduled subsequently at each point of the algorithm, and (3) using cutting planes to provide for tight LP formulations for the subproblems.