(301w) A Hybrid Tabu-Branch&Bound Approach for the Solution of Large-Scale Supply Chain Management Models

The globalization of markets brings new opportunities for existing businesses, as well as raises the complexity of their supply chains. As a result, with the fragmentation of market and reduction in product life span, companies need to introduce flexibility capabilities and diversify types of products in their existing production lines, to survive and remain competitive. This escalating complexity results in large scale Supply Chain Management (SCM) problems that can be formulated as multi-period Mixed Integer Programming (MIP) models (Neiro and Pinto, 2004). These models are often unsolvable to optimality ? or even to feasibility ? due to excessive computational time requirements and technological limitations. To solve such complex problems, many strategies have been proposed and implemented in the literature, among which are decomposition techniques and metaheuristic approaches.

Decomposition-based strategies tackle these large-scale problems by breaking them down into solvable sizes and computing the original solution by using the information contained in the solution of these smaller problems (Jackson and Grossmann, 2003). While these approaches have shown very promising results, the advantage of these techniques rely on specific structures of the original problem and, therefore, such techniques cannot be successfully applied to the SCM problems in general.

Metaheuristic approaches, in turn, attempt to obtain a good solution to a problem by systematically guiding the search for solutions within different areas of the feasibility region. These approaches are not able to guarantee finding of the optimal solution to the problem, once no optimality criteria can be identified, but they employ more flexible memory strategies that make them useful for treating large scale problems.

Our approach is based on the premise that a hybrid approach within a tree enumeration framework could make use of the inherent advantages of each technique and would ultimately improve the tractability of many SCM problems that arise in industry. We propose, therefore, an algorithm based on a hybrid implementation of Branch & Bound approaches and Tabu Search guidance proposed by Glover (2006) to solve models in which a subset of the discrete variables are responsible for a large portion of the computational complexity of the problem. This approach takes simultaneous advantage of the highly structured tree search from B&B and the memory flexibility from tabu strategies to reduce computational requirements without significantly compromising the quality of the solutions. The results are finally compared and contrasted to full-scale solutions previously obtained with the use of Lagrangean decomposition-based methods.

_______________________

Glover, F.; Parametric tabu-search for mixed integer programs. Comp. & Op. Res., vol. 33, pp. 2449-2494, 2006.

Jackson, J.R. and Grossmann, I.E.; Temporal decomposition scheme for nonlinear multisite production planning and distribution models. Ind. Eng. Chem. Res., vol. 42, pp. 3045-3055, 2003.

Neiro, S.M.S. and Pinto, J.M.; A general modeling framework for the operational planning of petroleum supply chains. Comp. & Chem. Eng., vol. 28, pp. 871-896, 2004.