Capacitated lot-sizing with sequence dependent setup costs

This paper considers single-stage system where a number of different items have to be manufactured on one machine. Expenditures for the setups depend on the sequence in which items are scheduled on the machine. Holding costs are incurred for holding items in inventory. The demand of the items has to be satisfied without delay, i.e. shortages are not allowed. The objective is to compute a schedule such that the sum of holding and setup costs is minimized with respect to capacity constraints. For this problem which the paper calls capacitated lot-sizing problem with sequence dependent setup costs (CLSD) it formulates a new model. The main differences between the new model and the discrete lot-sizing problem with sequence dependent setup costs (DLSDSD), introduced by Fleischmann, is that continuous lot-sizes are allowed and the setup state can be preserved over idle time. For the solution of the new model the paper presents a heuristic which applies a priority rule. Since the priority values are affected by two significant parameters, it perfroms a local search in the parameter space to obtain low cost solutions. The solution quality is analyzed by a computational study. The comparison with optimal solutions of small instances shows that the solution quality of heuristic is the present acceptable. The Fleischmann approach for the DLSPSD computes upper bounds for new problem. On the basis of large instances the paper shows that our heuristic is more efficient to solve the CLSD.