Optimizing the allocation of components to kits in small-lot, multiechelon assembly systems

The kitting problem is multiechelon assembly system is to allocate on-hand stock and anticipated future deliveries to kits so that cost is minimized. This article structures the kitting problem and describes several preprocessing methods that are effective in refining the formulation. The model is resolved using an optimizing approach based on Lagrangean relaxation, which yields a separable problem that decomposes into a subproblem for each job. The resulting subproblems are resolved using a specialized dynamic programming algorithm, and computational efficiency is enhanced by dominance properties devised for that purpose. The Lagrangean problem is resolved effectively using subgradient optimization and a specialized branching method incorporated in the branch-and-bound procedure. Computational experience demonstrates that the specialized approach out-performs the general-purpose optimizer OSL. The new solution approach facilitates time-managed flow control, prescribing kitting decisions that promote cost-effective performance to schedule.