Production Planning Problems: Models and Software

Laurence Wolsey, University of Utrecht, on leave from CORE, Universite Catholique de Louvain, Belgium

Download slides here (gzipped PostScript file).

This talk is on modeling and solving the capacitated economic lot-sizing problem that arises in production planning.

The problem is to find a production plan that will meet the demand dt > 0 of a product over NT time periods. There exists a capacity limit ct on the amount of production in period t. If we produce xt units in period t, a fixed set-up cost ft and a variable production cost pt xt is charged. In addition, if st units are kept in stock from period t to t+1, an inventory holding cost of ht st is incurred. We would like find a production plan that minimizes the total production and inventory costs.

A fixed charge network flow formulation of the problem is given in Slide 4. The network has a source node for total production and a sink node for each demand period.

Different versions of the problem are classified and a generic formulation is given in Slides 6 and 7. The generic model handles multiple products and backlogging of a product (negative inventory).

The motivation for developing a modeling and branch-cut system specifically for the lot-sizing problem is to make use of the knowledge created by research over the last 15 years. EMOSL (Extended Modelling and Subroutine Library) of XPRESS enables the user to create a model in mps format by using a language based on lot-sizing terminology. Routines to generate valid inequalities, seperation routines and specialized heuristics are included in the optimizer module.

The system has been tested on a testbed of various types of lot-sizing problems. An order of 10 speedup in run time is achieved in some of the test problems.