The increasing market demand for product variety forces manufacturers to design mixed-model assembly lines on which different product models can be switched back and forth and mixed together with little changeover costs. This paper describes the design and implementationofan optimization-based scheduling algorithmformixed-model compressor assembly lines at Toshiba with complicated component supply requirements.Aseparable integer optimization formulation is obtained by treating compressor lots going through a properly balanced line as undergoing a single operation, and the scheduling goal is to delivery products just in time while avoiding possible component shortage. The problem is solved b y using Lagrangian Relaxation (LR). Several generic defects of LR leading toslowalgorithm convergence are identified based on geometrical insights, and are overcome by perturbing/ changing problem parameters. Numerical testing shows that near-optimal schedules are efficiently obtained, convergence is significantly improved, and the method is effectiveforpractical problems. The system is currently under deployment at Toshiba