Y. Pochet et La. Wolsey, LOT-SIZING WITH CONSTANT BATCHES - FORMULATION AND VALID INEQUALITIES, Mathematics of operations research, 18(4), 1993, pp. 767-785
Citations number
12
Categorie Soggetti
Operatione Research & Management Science",Mathematics,"Operatione Research & Management Science",Mathematics
We consider the classical lot-sizing problem with constant production
capacities (LCC) and a variant in which the capacity in each period is
an integer multiple of some basic batch size (LCB). We first show tha
t the classical dynamic program for LCC simplifies for LCB leading to
an O(n2 min{n, C}) algorithm (where n is the number of periods and C t
he batch size). Using this new algorithm, we show how to formulate bot
h problems as linear programs with O(n3) variables and constraints. A
class of so-called (k, l, S, I) inequalities are described for LCB whi
ch capture both the dynamic nature of the problem as well as the capac
ity aspects. For LCB, we prove that these inequalities are the only fa
cet-defining inequalities of a certain form. For LCC, we show that the
se inequalities include all the known classes of valid inequalities. F
inally, we discuss several open questions and possible extensions.