Capacitated lot-sizing and scheduling with parallel machines, back-orders and setup carry-over

Kurzfassung/Abstract

We address the capacitated lot-sizing and scheduling problem with setup times, setup carry-over, back-orders, and parallel machines as it appears in a semiconductor assembly facility. The problem can be formulated as an extension of the capacitated lot-sizing problem with linked lot-sizes (CLSPL).We present a mixed integer (MIP) formulation of the problem and a new solution procedure. The solution procedure is based on a novel “aggregate model”, which uses integer instead of binary variables. The model is embedded in a period-by-period heuristic and is solved to optimality or near-optimality in each iteration using standard procedures (CPLEX). A subsequent scheduling routine loads and sequences the products on the parallel machines. Six variants of the heuristic are presented and tested in an extensive computational study.