Repair scheduling for glass furnaces using branch and bound techniques

The Problem: Given a set of glass furnaces, producing 3 colours of glass and grouped together in factories, to find a method of calculating a stable pattern of timing of normal rebuilds over a seven year period. Objective: To minimize the total cost of production and repairs Constraints (1) No two furnaces in the same factory can be rebuilt in the same quarter* (2) No two amber or green furnaces to be rebuilt in the same quarter; no more than two white furnaces to be rebuilt in the same quarter. (5) Given sales demands for each colour glass in each quarter. The sum of the production over 3 consecutive quarters must be greater than or equal to the sum of the demand over these 3 consecutive quarters. Initially an analytic approach of monitoring the variables that effect cost and production was tried. It became apparent that some essential data on furnace behaviour was either not in existence or at a very experimental stage - in particular data on furnace life expectancy and ageing effects on costs and production. In its place the following method evolved. I would be given a number of optional schedules for each furnace along with data on production and costs. Out of these one has to choose one schedule for each furnace in such a way that we have a minimum cost combination that satisfies all the constraints. We now have a different problem to solve. The simplified problem: Given a set of glass furnaces, producing 3 colours of glass and grouped together in factories, and given one set of possible repair schedules for each furnace. To find a method of choosing one repair schedule for each furnace to give a stable pattern of timing of normal rebuilds over a seven year period. Objective and Constraints are the same as before