Many practical applications of lot-sizing and scheduling problems invo
lve start-up times. Operations research literature contains but few st
udies of lot-sizing models that take start-up times explicitly into ac
count. Here, we review some of these studies, discuss the models and t
heir complexity, and we propose further models. We consider in particu
lar a single-stage single-mode multi-item lot-sizing model with contin
uous set-ups and sequence independent start-up times, which we solve u
sing an integer programming column generation algorithm and we develop
a dynamic programming procedure for the single-item subproblem that t
reats the initial stock as a decision variable. We also use cutting pl
anes developed by Constantino for the multiitem polyhedra. By combinin
g column and cut generation, the lower bounds that we obtain before br
anching are on average less than 2% from an optimal solution. Our algo
rithm solves instances with 3 to 5 items and 24 periods in an average
of 50 seconds on a modern workstation, and problems with 36 periods in
an average of 750 seconds. Solutions guaranteed to be within 2% of op
timality are obtained in less than 75% of these times.