Two-phase algorithm for lot size scheduling in single-stage production systems with parallel facilities (Q1087133)

Consider a single stage production system where the items may be manufactured on a set of parallel non-uniform facilities. There are sequence independent setup charges and setup times incurred when a facility is changed over between different items. The scheduling concerns the task of selecting lot sizes which are assigned to production facilities in subsequent T time stages so that the combined production and inventory holding costs are minimized. We present an approximate, two-phase algorithm for the corresponding mixed-integer optimization problem. In the first phase of the algorithm the various Lagrangean relaxations are applied. In the second phase, the algorithm based on perturbations of the parameters of the optimization problem is used to find a feasible, near-optimal solution. The presented perturbation algorithm provides a general scheme for the Lagrangean heuristics which may be also used to obtain approximate feasible solutions for other optimization problems.