Lot Sizing in Serial Assembly Systems with Multiple Constrained Resources

We present a heuristic for lot sizing in serial assembly systems with multiple contrained resources. This procedure, the Coefficient Modification Heuristic (CMH), exploits a special problem structure by solving repetitively a small linear programming restriction of the original problem. The key idea is to modify the constraint coefficients of certain variables in the LP restriction to implicitly account for the capacity consumed in setups. We compare the performance of the CMH with the commercial code, Optimization System Library (OSL), on three families of test problems. The first set is a collation of small-scale random problems that are solved to optimality to provide known benchmarks. The second is a set of problems based on a real printed circuit board manufacturing situation. The third group is a set of medium-scale randomly generated problems based on the underlying structure of the printed circuit board set. Overall, the CMH found solutions that averaged 18% better than time constrained OSL runs in a small fraction of the corresponding CPU times.