The discrete lot-sizing and scheduling problem with sequence-dependent setup costs

We consider the problem of scheduling several products on a single machine so as to meet the known dynamic demand and to minimize the sum of inventory costs and sequence-dependent setup costs. The planning interval is subdivided into many short periods, e.g. shifts or days, and any lot must last one or several full periods. We formulate this problem as a travelling salesman problem with time windows and present a new procedure for determining lower bounds using Lagrangean relaxation as well as a heuristic. Computational results for problems with up to 10 products and 150 periods are reported.