Mixed-model assembly line scheduling using the Lagrangian relaxation technique

The increasing market demand for product variety forces the manufacturers to design a mixed-model assembly line on which different model products can be switched quickly to satisfy diversified demand. Scheduling is critical to generate a sequence of different products to meet due dates and to avoid possible component shortage or starvation. Because of the combinatorial nature of integer programming and large sizes of real problems, the scheduling for mixed-model assembly line has been recognized to be extremely difficult. In this paper, an optimization-base scheduling method for mixed-model assembly line is presented. The study is motivated by the design and implementation of a scheduling system for the compressor assembly lines of Toshiba. In the shop, an assembly line can be simplified as a single machine and the number of components can be supplied is limited within fixed length windows. A separable integer programming formulation is developed and a solution methodology based on a combined Lagrangian relaxation and heuristic can be applied to get near-optimal schedule. The method has been implemented using the object-oriented programming language C++, and numerical testing shows that the generated sequence will help on-time product delivery, low finished goods inventory and smooth usage of components.