A multistage benders decomposition method for production planning problems with approved vendor matrices

A production planning problem is studied based on an actual manufacturer of hard-disk drives that offers the approved vendor matrix as a competitive advantage. An approved vendor matrix allows customers to pick and choose the component suppliers for individual components or pairs of components constituting their product. The problem is to develop production plans that minimize the total tardiness in fulfilling customer orders while observing the matrix restrictions and limited component supplies. It is first shown that this problem has an equivalent multicommodity network flow representation. A solution procedure using multistage Benders decomposition is then developed. The computational efficiency of the approach is compared with the column-generation method and the CPLEX general-purpose LP solver under different scenarios of matrix restrictions.