Hybrid heuristics for planning lot setups and sizes

The planning of a canning line at a drinks manufacturer is discussed and formulated as a mathematical programming model. Several alternative heuristic solution methods are developed, tested and compared on real data, illustrating the trade-offs between solution quality and computing time. The two most successful methods make hybrid use of local search and integer programming, but in rather different ways. The first method searches for the best proportion by which to factor setup times into unit production times. The second method carries out a local search on the first stage's binary setup variables. In both methods approximate mixed integer programming models are solved at each search iteration. In addition, a local search variant, called diminishing neighbourhood search, is used in order to avoid local optima in a variety of landscapes. Computational tests analyse the quality/time trade-offs between alternative heuristics, enabling an efficient frontier of non-dominated solutions to be identified. (C) 2003 Elsevier Ltd. All tights reserved.