A polyhedral approach to a production planning problem

Production planning in manufacturing industries is concerned with the deter mination of the production quantities (lot sizes) of some items over a time horizon, in order to satisfy the demand with minimum cost, subject to some production constraints. In general, production planning problems become harder when different types of constraints are present, such as capacity constraints,minimum lot sizes , changeover times, among others. Models incorporating some of these constr aints yield, in general, NP-hard problems. We consider a single-machine, multi-item lot-sizing problem, with those dif ficult characteristics. There is a natural mixed integer programming formul ation for this problem. However, the bounds given by linear relaxation are in general weak, so solving this problem by LP based branch and bound is in efficient. In order to improve the LP bounds, we strengthen the formulation by adding cutting planes. Several families of valid inequalities for the s et of feasible solutions are derived, and the corresponding separation prob lems are addressed. The result is a branch and cut algorithm, which is able to solve some real life instances with 5 items and up to 36 periods.